Lecture 5 | Machine Learning (Stanford)

TL;DR

Generative learning algorithms classify examples by modeling P(X given Y) and P(Y), then using Bayes rule to obtain P(Y given X). Gaussian discriminant analysis applies this approach to continuous features by fitting a multivariate Gaussian to each class. The comparison with logistic regression, cancer-classification example, and explanation of Gaussian covariance make it worth reading on.

Transcript

This presentation is delivered by the Stanford Center for Professional Development. So what I want to do today is talk about a different type of learning algorithm. Um and in particular start to talk about generative learning algorithms and a specific algorithm called Gaussian discriminant analysis. um take a slight digression talk about Gaussians ... Read More

Key Insights

• A discriminative learning algorithm is one that learns P(Y given X) directly, or learns a hypothesis that outputs values 0 or 1 directly. Logistic regression is an example of a discriminative learning algorithm because it searches for a line separating classes.
• A generative learning algorithm models P(X given Y), the probability of the features given the class label, and as a technical detail also models P(Y). It builds a probabilistic model for what the features look like conditioned on the class label.
• Generative learning works by building a separate model for each class. For cancer classification, you build one model for what malignant cancers look like and a separate model for what benign cancers look like, then match new examples to whichever model fits better.
• Bayes rule connects the two approaches: having modeled P(X given Y) and P(Y), you can compute P(Y given X) as P(X given Y=1) times P(Y) divided by P(X), where the denominator can be calculated from the modeled quantities.
• Gaussian discriminant analysis assumes input features X are in Rn and are continuous values. Its core assumption is that P(X given Y) is distributed as a multivariate Gaussian.
• A multivariate Gaussian is parameterized by a mean vector mu and a covariance matrix sigma. The covariance is defined as the expectation of (x minus mu)(x minus mu) transpose, generalizing the one-dimensional bell-shaped normal curve to high-dimensional vector-valued random variables.
• Shrinking the covariance matrix makes the Gaussian more peaked, while widening it spreads the density out. Increasing the off-diagonal entries makes the variables correlated, flattening the Gaussian along the x equals y direction and turning circular contours into ellipses.
• In GDA, P(Y) is modeled as a Bernoulli random variable parameterized by phi, and P(X given Y=0) and P(X given Y=1) are each modeled as Gaussians. Together the two fitted Gaussian densities define a separator that differs from the logistic regression decision boundary.

Questions & Answers

Q: What are generative learning algorithms and Gaussian discriminant analysis?

A generative learning algorithm models P(X given Y) and P(Y), then uses Bayes rule to compute P(Y given X) for prediction. Gaussian discriminant analysis is a generative algorithm for continuous features that assumes P(X given Y) follows a multivariate Gaussian distribution.

Q: What is the difference between generative and discriminative learning algorithms?

A discriminative algorithm learns P(Y given X) directly or learns a hypothesis that directly outputs class values such as 0 or 1. A generative algorithm instead models P(X given Y) and P(Y), building a probabilistic description of the features associated with each class.

Q: How does a generative learning algorithm classify a new example?

It builds a separate model for each class and determines which model better matches the new example. In the lecture’s cancer example, it models malignant and benign cancers separately, then classifies a new cancer according to the model it matches better.

Q: How does Bayes rule connect P(X given Y) to P(Y given X)?

After modeling P(X given Y) and P(Y), a generative algorithm applies Bayes rule to recover P(Y given X). This converts its class-conditioned feature models into the probability needed to predict a class from observed features.

Q: What assumptions does Gaussian discriminant analysis make?

Gaussian discriminant analysis assumes the input features X are continuous values in Rn. Its core modeling assumption is that P(X given Y) is distributed as a multivariate Gaussian.

Q: What parameters define a multivariate Gaussian distribution?

A multivariate Gaussian is parameterized by a mean vector mu and a covariance matrix sigma. The covariance is the expectation of (x minus mu)(x minus mu) transpose and describes how the vector-valued features vary together.

Q: How does the covariance matrix affect a multivariate Gaussian?

Shrinking the covariance matrix makes the Gaussian more peaked, while widening it spreads the density out. Increasing off-diagonal entries introduces correlation, changing circular contours into ellipses and flattening the Gaussian along the x equals y direction.

Q: How does Gaussian discriminant analysis model the classes and P(Y)?

GDA models P(Y) as a Bernoulli random variable parameterized by phi. It models P(X given Y=0) and P(X given Y=1) as Gaussians, fitting one density to the negative examples and another to the positive examples; together, those densities define the separator.

Summary

This video is about generative learning algorithms, specifically Gaussian discriminant analysis and naive Bayes. The speaker explains the difference between generative and discriminative learning algorithms and discusses the assumptions made in each algorithm. Gaussian discriminant analysis assumes that the features given the class label follow a Gaussian distribution, while naive Bayes assumes that the features are conditionally independent given the class label.

Questions & Answers

Q: What is the main difference between generative and discriminative learning algorithms?

Generative learning algorithms model the probability of features given the class label, while discriminative learning algorithms model the probability of the class label given the features. This means that generative algorithms try to model the underlying distribution of the data, while discriminative algorithms focus on finding the decision boundary that separates different classes.

Q: Can you explain Gaussian discriminant analysis?

Gaussian discriminant analysis is a generative learning algorithm that assumes the features given the class label follow a Gaussian distribution. It models the probability of the features given the class label, as well as the probability of the class label itself. By using Bayes' rule, it can then compute the probability of the class label given the features. This algorithm builds separate models for each class and uses them to classify new examples.

Q: How does naive Bayes differ from Gaussian discriminant analysis?

Naive Bayes is also a generative learning algorithm, but it makes a stronger assumption that the features are conditionally independent given the class label. This means that the occurrence of one feature does not affect the occurrence of other features, given the class label. This assumption allows naive Bayes to model the joint probability of the features as the product of their individual probabilities. This algorithm is commonly used for text classification, as it works well with bag-of-words representations.

Q: How does naive Bayes handle the large number of possible values for the features?

Naive Bayes uses a simplistic approach to reduce the number of parameters it needs to estimate. Instead of modeling the joint probability of all possible feature vectors, it assumes that the features are conditionally independent given the class label. This allows it to model the probability of each feature individually, resulting in a much smaller number of parameters to estimate.

Q: What are the advantages of using generative learning algorithms?

Generative learning algorithms, such as Gaussian discriminant analysis and naive Bayes, often require less training data compared to discriminative learning algorithms. This is because they make stronger assumptions about the underlying data distribution and can leverage more information. Additionally, these algorithms can handle missing data more effectively, as they can model the probability of the missing data.

Q: What are the disadvantages of using generative learning algorithms?

The main disadvantage of generative learning algorithms is that they make assumptions about the data distribution which may not always hold true. If the assumptions are violated, the performance of these algorithms may suffer. Additionally, because they model the joint probability of the features, they may require more computational resources compared to discriminative algorithms.

Q: How are the parameters estimated in Gaussian discriminant analysis?

The parameters in Gaussian discriminant analysis, including the class distributions and the Gaussian parameters, are estimated using maximum likelihood estimation. This involves finding the parameters that maximize the likelihood of the observed data given the model. In the case of Gaussian discriminant analysis, the parameters are estimated based on the frequency of feature occurrences in each class.

Q: How are the parameters estimated in naive Bayes?

The parameters in naive Bayes, such as the probabilities of each feature given the class label, are also estimated using maximum likelihood estimation. The maximum likelihood estimate of each parameter is simply the fraction of training examples where the corresponding feature occurs, conditioned on the class label. This estimate is then used to compute the probabilities required for classification.

Q: What is the impact of the naive Bayes assumption on the performance of the algorithm?

The naive Bayes assumption that the features are conditionally independent given the class label is a simplifying assumption that may not hold true in practice. However, despite this assumption being false, naive Bayes often performs very well in text classification tasks. This is because it effectively handles the high-dimensional feature space of text data and can generalize well even with limited training data.

Q: How does naive Bayes handle cases where a certain feature does depend on the occurrence of another feature?

While the naive Bayes assumption of feature independence may be violated in some cases, naive Bayes can still perform well. This is because it focuses on capturing the overall statistical trends of the data rather than the specific dependencies between features. Additionally, naive Bayes can still be effective when the dependencies between features are weak or when the occurrence of one feature does not significantly impact the occurrence of others.

Takeaways

Generative learning algorithms, such as Gaussian discriminant analysis and naive Bayes, model the underlying distribution of the data and make assumptions about the conditional dependencies between features and class labels. Although they require strong assumptions and might not always hold true, generative algorithms can perform well, especially with limited training data. Naive Bayes, in particular, is a powerful algorithm for text classification tasks, leveraging the assumption of feature independence to handle high-dimensional feature spaces effectively.

Summary & Key Takeaways

• The lecture introduces generative learning algorithms as a contrast to discriminative ones like logistic regression, which search for a straight line to separate positive and negative classes. Instead of finding a separating boundary directly, generative methods build a separate probabilistic model for each class and classify new examples by which model fits best.

• For a cancer example, a generative approach builds one model of what malignant cancers look like and another of what benign cancers look like. Formally, discriminative algorithms learn P(Y given X) directly, while generative algorithms model P(X given Y) and P(Y), then apply Bayes rule to recover P(Y given X) for prediction.

• Gaussian discriminant analysis assumes continuous features in Rn and that P(X given Y) is multivariate Gaussian. After reviewing how the mean and covariance parameters shape a Gaussian, the model fits one Gaussian to positive examples and one to negative examples, with P(Y) as a Bernoulli, producing a decision boundary distinct from logistic regression.