Lecture 5 | Machine Learning (Stanford)

TL;DR

A generative learning algorithm builds a separate model for each class by modeling P(X given Y), the probability of the features given the class label, then uses Bayes rule to compute P(Y given X). Gaussian discriminant analysis assumes P(X given Y) is a multivariate Gaussian, fitting one Gaussian to positive examples and another to negative examples to form a decision boundary.

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 is the difference between generative and discriminative learning algorithms?

A discriminative learning algorithm learns P(Y given X) directly, or learns a hypothesis that outputs values 0 or 1 directly, such as logistic regression finding a line to separate classes. A generative learning algorithm instead models P(X given Y), the probability of the features given the class label, and also models P(Y). It builds a probabilistic model of what the features look like conditioned on each class label rather than searching for a separating boundary.

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

A generative algorithm builds a separate model for each class. Using the cancer example, you go through the training set and build a model for what malignant cancers look like, then build a separate model for what benign cancers look like. When a new patient arrives, you match the new cancer to your model of malignant cancers and to your model of benign cancers, see which model it matches better, and predict the class accordingly.

Q: What is Gaussian discriminant analysis?

Gaussian discriminant analysis is a specific generative learning algorithm that assumes the 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. The algorithm fits one Gaussian distribution to the positive examples and another Gaussian to the negative examples, and together these two densities define a separator between the two classes.

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

After a generative model has built a model for P(X given Y) and for P(Y), you can use Bayes rule to compute P(Y given X). Specifically P(Y=1 given X) equals P(X given Y=1) times P(Y) divided by P(X). If necessary, the denominator P(X) can be calculated from the modeled quantities. This lets a generative model, which starts by modeling P(X given Y), get back to the P(Y given X) needed for prediction.

Q: What parameters define a multivariate Gaussian distribution?

A multivariate Gaussian is parameterized by a mean vector mu and a covariance matrix sigma. The mean mu gives the location of the Gaussian, and the covariance sigma is defined as the expectation of (x minus mu)(x minus mu) transpose. It is a generalization of the one-dimensional normal bell-shaped curve to a high-dimensional vector-valued random variable Z, with a density formula that includes the determinant of sigma to the one-half in the denominator.

Q: How does changing the covariance matrix affect the shape of a Gaussian?

Shrinking the covariance matrix makes the Gaussian more peaked, while widening it spreads the density out. Increasing the diagonal entries and making the off-diagonals larger causes the variables to become correlated, flattening the Gaussian along the x equals y direction. In contour form, a standard normal has circular contours, but increasing the off-diagonal entries turns them into ellipses aligned along a 45 degree angle, and negative covariances tilt the correlation the other way.

Q: Why does Gaussian discriminant analysis produce a different decision boundary than logistic regression?

In the lecture demonstration, logistic regression finds a straight line that separates the positive and negative classes, shown as a green decision boundary. Gaussian discriminant analysis instead fits a Gaussian to the positive examples and a Gaussian to the negative examples, and together those two densities define a separator shown as a blue line. Because the two methods make different modeling assumptions, the GDA separator turns out to be a little bit different from the logistic regression boundary.

Q: How is P(Y) modeled in the Gaussian discriminant analysis model?

In the Gaussian discriminant analysis model, P(Y) is modeled as a Bernoulli random variable parameterized by a parameter phi, as is usual for a binary class label. Then P(X given Y=0) is modeled as a Gaussian and P(X given Y=1) is modeled as another Gaussian, each with its own mean. The density formula for these Gaussians includes the determinant of sigma to the one-half in the denominator, which the lecturer noted was initially missing on the board.

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.