Instructor (Andrew Ng):Okay, good morning. Just one quick announcement and reminder, the project guidelines handout was posted on the course website last week. So if you havenít yet downloaded it and looked at it, please do so. It just contains the guidelines for the project proposal and the project milestone, and the final project presentation.
So what I want to do today is talk about a different type of learning algorithm, and, in particular, start to talk about generative learning algorithms and the specific algorithm called Gaussian Discriminant Analysis. Take a slight digression, talk about Gaussians, and Iíll briefly discuss generative versus discriminative learning algorithms, and then hopefully wrap up todayís lecture with a discussion of Naive Bayes and the Laplace Smoothing.
So just to motivate our discussion on generative learning algorithms, right, so by way of contrast, the source of classification algorithms weíve been talking about I think of algorithms that do this. So youíre given a training set, and if you run an algorithm right, we just see progression on those training sets.
The way I think of logistic regression is that itís trying to find Ė look at the date and is trying to find a straight line to divide the crosses and Oís, right? So itís, sort of, trying to find a straight line. Let me Ė just make the days a bit noisier. Trying to find a straight line that separates out the positive and the negative classes as well as pass the law, right?
And, in fact, it shows it on the laptop. Maybe just use the screens or the small monitors for this. In fact, you can see thereís the data set with logistic regression, and so Iíve initialized the parameters randomly, and so logistic regression is, kind of, the outputting Ė itís the, kind of, hypothesis that iteration zero is that straight line shown in the bottom right.
And so after one iteration and creating descent, the straight line changes a bit. After two iterations, three, four, until logistic regression converges and has found the straight line that, more or less, separates the positive and negative class, okay? So you can think of this as logistic regression, sort of, searching for a line that separates the positive and the negative classes.
What I want to do today is talk about an algorithm that does something slightly different, and to motivate us, letís use our old example of trying to classify the team malignant cancer and benign cancer, right? So a patient comes in and they have a cancer, you want to know if itís a malignant or a harmful cancer, or if itís a benign, meaning a harmless cancer.
So rather than trying to find the straight line to separate the two classes, hereís something else we could do. We can go from our training set and look at all the cases of malignant cancers, go through, you know, look for our training set for all the positive examples of malignant cancers, and we can then build a model for what malignant cancer looks like. Then weíll go for our training set again and take out all of the examples of benign cancers, and then weíll build a model for what benign cancers look like, okay?
And then when you need to classify a new example, when you have a new patient, and you want to decide is this cancer malignant or benign, you then take your new cancer, and you match it to your model of malignant cancers, and you match it to your model of benign cancers, and you see which model it matches better, and depending on which model it matches better to, you then predict whether the new cancer is malignant or benign, okay?
So what I just described, just this cross of methods where you build a second model for malignant cancers and a separate model for benign cancers is called a generative learning algorithm, and let me just, kind of, formalize this. So in the models that weíve been talking about previously, those were actually all discriminative learning algorithms, and studied more formally, a discriminative learning algorithm is one that either learns PFY given X directly, or even learns a hypothesis that outputs value 0, 1 directly, okay? So logistic regression is an example of a discriminative learning algorithm.
In contrast, a generative learning algorithm of models PFX given Y. The probability of the features given the class label, and as a technical detail, it also models PFY, but thatís a less important thing, and the interpretation of this is that a generative model builds a probabilistic model for what the features looks like, conditioned on the class label, okay? In other words, conditioned on whether a cancer is malignant or benign, it models probability distribution over what the features of the cancer looks like.
Then having built this model Ė having built a model for PFX given Y and PFY, then by Bayes rule, obviously, you can compute PFY given 1, conditioned on X. This is just PFX given Y = 1 ◊ PFX ų PFX, and, if necessary, you can calculate the denominator using this, right? And so by modeling PFX given Y and modeling PFY, you can actually use Bayes rule to get back to PFY given X, but a generative model Ė generative learning algorithm starts in modeling PFX given Y, rather than PFY given X, okay?
Weíll talk about some of the tradeoffs, and why this may be a better or worse idea than a discriminative model a bit later. Letís go for a specific example of a generative learning algorithm, and for this specific motivating example, Iím going to assume that your input feature is X and RN and are continuous values, okay?
And under this assumption, let me describe to you a specific algorithm called Gaussian Discriminant Analysis, and the, I guess, core assumption is that weíre going to assume in the Gaussian discriminant analysis model of that PFX given Y is Gaussian, okay?
So actually just raise your hand, how many of you have seen a multivariate Gaussian before Ė not a 1D Gaussian, but the higher range though? Okay, cool, like maybe half of you, two-thirds of you. So let me just say a few words about Gaussians, and for those of you that have seen it before, itíll be a refresher.
So we say that a random variable Z is distributed Gaussian, multivariate Gaussian as Ė and the script N for normal with parameters mean U and covariance sigma squared. If Z has a density 1 over 2 Pi, sigma 2, okay? Thatís the formula for the density as a generalization of the one dimension of Gaussians and no more the familiar bell-shape curve. Itís a high dimension vector value random variable Z.
Donít worry too much about this formula for the density. You rarely end up needing to use it, but the two key quantities are this vector mew is the mean of the Gaussian and this matrix sigma is the covariance matrix Ė covariance, and so sigma will be equal to, right, the definition of covariance of a vector valued random variable is X - U, X - V conspose, okay?
And, actually, if this doesnít look familiar to you, you might re-watch the discussion section that the TAs held last Friday or the one that theyíll be holding later this week on, sort of, a recap of probability, okay?
So multi-grade Gaussians is parameterized by a mean and a covariance, and let me just Ė can I have the laptop displayed, please? Iíll just go ahead and actually show you, you know, graphically, the effects of varying a Gaussian Ė varying the parameters of a Gaussian. So what I have up here is the density of a zero mean Gaussian with covariance matrix equals the identity. The covariance matrix is shown in the upper right-hand corner of the slide, and thereís the familiar bell-shaped curve in two dimensions.
And so if I shrink the covariance matrix, instead of covariance your identity, if I shrink the covariance matrix, then the Gaussian becomes more peaked, and if I widen the covariance, so like same = 2, 2, then the distribution Ė well, the density becomes more spread out, okay?
Those vectors stand at normal, identity covariance one. If I increase the diagonals of a covariance matrix, right, if I make the variables correlated, and the Gaussian becomes flattened out in this X = Y direction, and increase it even further, then my variables, X and Y, right Ė excuse me, it goes Z1 and Z2 are my two variables on a horizontal axis become even more correlated.
Iíll just show the same thing in contours. The standard normal of distribution has contours that are Ė theyíre actually circles. Because of the aspect ratio, these look like ellipses. These should actually be circles, and if you increase the off diagonals of the Gaussian covariance matrix, then it becomes ellipses aligned along the, sort of, 45 degree angle in this example.
This is the same thing. Hereís an example of a Gaussian density with negative covariances. So now the correlation goes the other way, so that even strong [inaudible] of covariance and the same thing in contours. This is a Gaussian with negative entries on the diagonals and even larger entries on the diagonals, okay?
And other parameter for the Gaussian is the mean parameters, so if this is Ė with mew0, and as he changed the mean parameter, this is mew equals 0.15, the location of the Gaussian just moves around, okay?
All right. So that was a quick primer on what Gaussians look like, and hereís as a roadmap or as a picture to keep in mind, when we described the Gaussian discriminant analysis algorithm, this is what weíre going to do. Hereís the training set, and in the Gaussian discriminant analysis algorithm, what Iím going to do is Iím going to look at the positive examples, say the crosses, and just looking at only the positive examples, Iím gonna fit a Gaussian distribution to the positive examples, and so maybe I end up with a Gaussian distribution like that, okay? So thereís PFX given Y = 1.
And then Iíll look at the negative examples, the Oís in this figure, and Iíll fit a Gaussian to that, and maybe I get a Gaussian centered over there. This is the concept of my second Gaussian, and together Ė weíll say how later Ė together these two Gaussian densities will define a separator for these two classes, okay?
And itíll turn out that the separator will turn out to be a little bit different from what logistic regression gives you. If you run logistic regression, you actually get the division bound to be shown in the green line, whereas Gaussian discriminant analysis gives you the blue line, okay?
Switch back to chalkboard, please. All right. Hereís the Gaussian discriminant analysis model, put into model PFY as a Bernoulli random variable as usual, but as a Bernoulli random variable and parameterized by parameter phi; youíve seen this before. Model PFX given Y = 0 as a Gaussian Ė oh, you know what?
Yeah, yes, excuse me. I thought this looked strange. This should be a sigma, determined in a sigma to the one-half of the denominator there. Itís no big deal. It was Ė yeah, well, okay. Right. I was listing the sigma to the determining the sigma to the one-half on a previous board, excuse me.
Okay, and so I model PFX given Y = 0 as a Gaussian with mean mew0 and covariance sigma to the sigma to the minus one-half, and Ė okay? And so the parameters of this model are phi, mew0, mew1, and sigma, and so I can now write down the likelihood of the parameters as Ė oh, excuse me, actually, the log likelihood of the parameters as the log of that, right?
So, in other words, if Iím given the training set, then they can write down the log likelihood of the parameters as the log of, you know, the probative probabilities of PFXI, YI, right? And this is just equal to that where each of these terms, PFXI given YI, or PFYI is then given by one of these three equations on top, okay?
And I just want to contrast this again with discriminative learning algorithms, right? So to give this a name, I guess, this sometimes is actually called the Joint Data Likelihood Ė the Joint Likelihood, and let me just contrast this with what we had previously when weíre talking about logistic regression. Where I said with the log likelihood of the parameterís theater was log of a product I = 1 to M, PFYI given XI and parameterized by a theater, right?
So back where weíre fitting logistic regression models or generalized learning models, weíre always modeling PFYI given XI and parameterized by a theater, and that was the conditional likelihood, okay, in which weíre modeling PFYI given XI, whereas, now, regenerative learning algorithms, weíre going to look at the joint likelihood which is PFXI, YI, okay?
So letís see. So given the training sets and using the Gaussian discriminant analysis model to fit the parameters of the model, weíll do maximize likelihood estimation as usual, and so you maximize your L with respect to the parameters phi, mew0, mew1, sigma, and so if we find the maximum likelihood estimate of parameters, you find that phi is Ė the maximum likelihood estimate is actually no surprise, and Iím writing this down mainly as a practice for indicating notation, all right?
So the maximum likelihood estimate for phi would be Sum over I, YI ų M, or written alternatively as Sum over Ė all your training examples of indicator YI = 1 ų M, okay? In other words, maximum likelihood estimate for a newly parameter phi is just the faction of training examples with label one, with Y equals 1. Maximum likelihood estimate for mew0 is this, okay? You should stare at this for a second and see if it makes sense.
Actually, Iíll just write on the next one for mew1 while you do that. Okay? So what this is is what the denominator is sum of your training sets indicated YI = 0. So for every training example for which YI = 0, this will increment the count by one, all right?
So the denominator is just the number of examples with label zero, all right? And then the numerator will be, letís see, Sum from I = 1 for M, or every time YI is equal to 0, this will be a one, and otherwise, this thing will be zero, and so this indicator function means that youíre including only the times for which YI is equal to one Ė only the turns which Y is equal to zero because for all the times where YI is equal to one, this sum and will be equal to zero, and then you multiply that by XI, and so the numerator is really the sum of XIís corresponding to examples where the class labels were zero, okay? Raise your hand if this makes sense. Okay, cool.
So just to say this fancifully, this just means look for your training set, find all the examples for which Y = 0, and take the average of the value of X for all your examples which Y = 0. So take all your negative fitting examples and average the values for X and thatís mew0, okay?
If this notation is still a little bit cryptic Ė if youíre still not sure why this equation translates into what I just said, do go home and stare at it for a while until it just makes sense. This is, sort of, no surprise. It just says to estimate the mean for the negative examples, take all your negative examples, and average them. So no surprise, but this is a useful practice to indicate a notation.
[Inaudible] divide the maximum likelihood estimate for sigma. I wonít do that. You can read that in the notes yourself. And so having fit the parameters find mew0, mew1, and sigma to your data, well, you now need to make a prediction. You know, when youíre given a new value of X, when youíre given a new cancer, you need to predict whether itís malignant or benign.
Your prediction is then going to be, letís say, the most likely value of Y given X. I should write semicolon the parameters there. Iíll just give that Ė which is the [inaudible] of a Y by Bayes rule, all right? And that is, in turn, just that because the denominator PFX doesnít depend on Y, and if PFY is uniform.
In other words, if each of your constants is equally likely, so if PFY takes the same value for all values of Y, then this is just arc X over Y, PFX given Y, okay?
This happens sometimes, maybe not very often, so usually you end up using this formula where you compute PFX given Y and PFY using your model, okay?
Student:Can you give us arc x?
Instructor (Andrew Ng):Oh, letís see. So if you take Ė actually let me. So the min of Ė arcomatics means the value for Y that maximizes this.
Instructor (Andrew Ng):So just for an example, the min of X - 5 squared is 0 because by choosing X equals 5, you can get this to be zero, and the argument over X of X - 5 squared is equal to 5 because 5 is the value of X that makes this minimize, okay? Cool. Thanks for asking that.
Instructor (Andrew Ng):Okay. Actually any other questions about this? Yeah?
Student:Why is distributive removing? Why isnít [inaudible] Ė
Instructor (Andrew Ng):Oh, I see. By uniform I meant Ė I was being loose here. I meant if PFY = 0 is equal to PFY = 1, or if Y is the uniform distribution over the set 0 and 1.
Instructor (Andrew Ng):I just meant Ė yeah, if PFY = 0 zero = PFY given 1. Thatís all I mean, see? Anything else?
All right. Okay. So it turns out Gaussian discriminant analysis has an interesting relationship to logistic regression. Let me illustrate that. So letís say you have a training set Ė actually let me just go ahead and draw 1D training set, and that will kind of work, yes, okay.
So letís say we have a training set comprising a few negative and a few positive examples, and letís say I run Gaussian discriminate analysis. So Iíll fit Gaussians to each of these two densities Ė a Gaussian density to each of these two Ė to my positive and negative training examples, and so maybe my positive examples, the Xís, are fit with a Gaussian like this, and my negative examples I will fit, and you have a Gaussian that looks like that, okay?
Now, I hope this [inaudible]. Now, letís vary along the X axis, and what I want to do is Iíll overlay on top of this plot. Iím going to plot PFY = 1 Ė no, actually, given X for a variety of values X, okay? So I actually realize what I should have done. Iím gonna call the Xís the negative examples, and Iím gonna call the Oís the positive examples. It just makes this part come in better.
So letís take a value of X thatís fairly small. Letís say X is this value here on a horizontal axis. Then whatís the probability of Y being equal to one conditioned on X? Well, the way you calculate that is you write PFY = 1 given X, and then you plug in all these formulas as usual, right? Itís PFX given Y = 1, which is your Gaussian density, times PFY = 1, you know, which is essentially Ė this is just going to be equal to phi, and then divided by, right, PFX, and then this shows you how you can calculate this.
By using these two Gaussians and my phi on PFY, I actually compute what PFY = 1 given X is, and in this case, if X is this small, clearly it belongs to the left Gaussian. Itís very unlikely to belong to a positive class, and so itíll be very small; itíll be very close to zero say, okay? And then we can increment the value of X a bit, and study a different value of X, and plot what is the PFY given X Ė PFY = 1 given X, and, again, itíll be pretty small.
Letís use a point like that, right? At this point, the two Gaussian densities have equal value, and if I ask if X is this value, right, shown by the arrow, whatís the probably of Y being equal to one for that value of X? Well, you really canít tell, so maybe itís about 0.5, okay?
And if you fill in a bunch more points, you get a curve like that, and then you can keep going. Letís say for a point like that, you can ask whatís the probability of X being one? Well, if itís that far out, then clearly, it belongs to this rightmost Gaussian, and so the probability of Y being a one would be very high; it would be almost one, okay?
And so you can repeat this exercise for a bunch of points. All right, compute PFY equals one given X for a bunch of points, and if you connect up these points, you find that the curve you get [Pause] plotted takes a form of sigmoid function, okay?
So, in other words, when you make the assumptions under the Gaussian discriminant analysis model, that PFX given Y is Gaussian, when you go back and compute what PFY given X is, you actually get back exactly the same sigmoid function that weíre using which is the progression, okay?
But it turns out the key difference is that Gaussian discriminant analysis will end up choosing a different position and a steepness of the sigmoid than would logistic regression. Is there a question?
Student:Iím just wondering, the Gaussian of PFY [inaudible] you do?
Instructor (Andrew Ng):No, letís see. The Gaussian Ė so this Gaussian is PFX given Y = 1, and this Gaussian is PFX given Y = 0; does that make sense? Anything else?
Instructor (Andrew Ng):Yeah?
Student:When you drawing all the dots, how did you decide what Y given PFX was?
Instructor (Andrew Ng):What Ė say that again.
Student:Iím sorry. Could you go over how you figured out where to draw each dot?
Instructor (Andrew Ng):Letís see, okay. So the computation is as follows, right? The steps are I have the training sets, and so given my training set, Iím going to fit a Gaussian discriminant analysis model to it, and what that means is Iíll build a model for PFX given Y = 1. Iíll build a model for PFX given Y = 0, and Iíll also fit a Bernoulli distribution to PFY, okay?
So, in other words, given my training set, Iíll fit PFX given Y and PFY to my data, and now Iíve chosen my parameters of find mew0, mew1, and the sigma, okay? Then this is the process I went through to plot all these dots, right? Itís just I pick a point in the X axis, and then I compute PFY given X for that value of X, and PFY given 1 conditioned on X will be some value between zero and one. Itíll be some real number, and whatever that real number is, I then plot it on the vertical axis, okay?
And the way I compute PFY = 1 conditioned on X is I would use these quantities. I would use PFX given Y and PFY, and, sort of, plug them into Bayes rule, and that allows me to compute PFY given X from these three quantities; does that make sense?
Instructor (Andrew Ng):Was there something more that Ė
Student:And how did you model PFX; is that Ė
Instructor (Andrew Ng):Oh, okay. Yeah, so Ė well, got this right here. So PFX can be written as, right, so PFX given Y = 0 ◊ PFY = 0 + PFX given Y = 1, PFY = 1, right? And so each of these terms, PFX given Y and PFY, these are terms I can get out of, directly, from my Gaussian discriminant analysis model. Each of these terms is something that my model gives me directly, so plugged in as the denominator, and by doing that, thatís how I compute PFY = 1 given X, make sense?
Instructor (Andrew Ng):Okay. Cool. So letís talk a little bit about the advantages and disadvantages of using a generative learning algorithm, okay? So in the particular case of Gaussian discriminant analysis, we assume that X conditions on Y is Gaussian, and the argument I showed on the previous chalkboard, I didnít prove it formally, but you can actually go back and prove it yourself is that if you assume X given Y is Gaussian, then that implies that when you plot Y given X, you find that Ė well, let me just write logistic posterior, okay?
And the argument I showed just now, which I didnít prove; you can go home and prove it yourself, is that if you assume X given Y is Gaussian, then that implies that the posterior distribution or the form of PFY = 1 given X is going to be a logistic function, and it turns out this implication in the opposite direction does not hold true, okay?
In particular, it actually turns out Ė this is actually, kind of, cool. It turns out that if youíre seeing that X given Y = 1 is Hessian with parameter lambda 1, and X given Y = 0, is Hessian with parameter lambda 0. It turns out if you assumed this, then that also implies that PFY given X is logistic, okay?
So there are lots of assumptions on X given Y that will lead to PFY given X being logistic, and, therefore, this, the assumption that X given Y being Gaussian is the stronger assumption than the assumption that Y given X is logistic, okay? Because this implies this, right? That means that this is a stronger assumption than this because this, the logistic posterior holds whenever X given Y is Gaussian but not vice versa.
And so this leaves some of the tradeoffs between Gaussian discriminant analysis and logistic regression, right? Gaussian discriminant analysis makes a much stronger assumption that X given Y is Gaussian, and so when this assumption is true, when this assumption approximately holds, if you plot the data, and if X given Y is, indeed, approximately Gaussian, then if you make this assumption, explicit to the algorithm, then the algorithm will do better because itís as if the algorithm is making use of more information about the data. The algorithm knows that the data is Gaussian, right? And so if the Gaussian assumption, you know, holds or roughly holds, then Gaussian discriminant analysis may do better than logistic regression.
If, conversely, if youíre actually not sure what X given Y is, then logistic regression, the discriminant algorithm may do better, and, in particular, use logistic regression, and maybe you see [inaudible] before the data was Gaussian, but it turns out the data was actually Poisson, right? Then logistic regression will still do perfectly fine because if the data were actually Poisson, then PFY = 1 given X will be logistic, and itíll do perfectly fine, but if you assumed it was Gaussian, then the algorithm may go off and do something thatís not as good, okay?
So it turns out that Ė right. So itís slightly different. It turns out the real advantage of generative learning algorithms is often that it requires less data, and, in particular, data is never really exactly Gaussian, right? Because data is often approximately Gaussian; itís never exactly Gaussian.
And it turns out, generative learning algorithms often do surprisingly well even when these modeling assumptions are not met, but one other tradeoff is that by making stronger assumptions about the data, Gaussian discriminant analysis often needs less data in order to fit, like, an okay model, even if thereís less training data.
Whereas, in contrast, logistic regression by making less assumption is more robust to your modeling assumptions because youíre making a weaker assumption; youíre making less assumptions, but sometimes it takes a slightly larger training set to fit than Gaussian discriminant analysis. Question?
Student:In order to meet any assumption about the number [inaudible], plus here we assume that PFY = 1, equal two number of. [Inaudible]. Is true when the number of samples is marginal?
Instructor (Andrew Ng):Okay. So letís see. So thereís a question of is this true Ė what was that? Let me translate that differently. So the marving assumptions are made independently of the size of your training set, right? So, like, in least/great regression Ė well, in all of these models Iím assuming that these are random variables flowing from some distribution, and then, finally, Iím giving a single training set and that as for the parameters of the distribution, right?
Student:So whatís the probability of Y = 1?
Instructor (Andrew Ng):Probability of Y + 1?
Student:Yeah, you used the Ė
Instructor (Andrew Ng):Sort of, this like Ė back to the philosophy of mass molecular estimation, right? Iím assuming that theyíre PFY is equal to phi to the Y, Y - phi to the Y or Y - Y. So Iím assuming that thereís some true value of Y generating all my data, and then Ė well, when I write this, I guess, maybe what I should write isnít Ė so when I write this, I guess there are already two values of phi. One is thereís a true underlying value of phi that guards the use to generate the data, and then thereís the maximum likelihood estimate of the value of phi, and so when I was writing those formulas earlier, those formulas are writing for phi, and mew0, and mew1 were really the maximum likelihood estimates for phi, mew0, and mew1, and thatís different from the true underlying values of phi, mew0, and mew1, but Ė
Instructor (Andrew Ng):Yeah, right. So maximum likelihood estimate comes from the data, and thereís some, sort of, true underlying value of phi that Iím trying to estimate, and my maximum likelihood estimate is my attempt to estimate the true value, but, you know, by notational and convention often are just right as that as well without bothering to distinguish between the maximum likelihood value and the true underlying value that Iím assuming is out there, and that Iím only hoping to estimate.
Actually, yeah, so for the sample of questions like these about maximum likelihood and so on, I hope to tease to the Friday discussion section as a good time to ask questions about, sort of, probabilistic definitions like these as well. Are there any other questions? No, great. Okay.
So, great. Oh, it turns out, just to mention one more thing thatís, kind of, cool. I said that if X given Y is Poisson, and you also go logistic posterior, it actually turns out thereís a more general version of this. If you assume X given Y = 1 is exponential family with parameter A to 1, and then you assume X given Y = 0 is exponential family with parameter A to 0, then this implies that PFY = 1 given X is also logistic, okay? And thatís, kind of, cool. It means that Y given X could be Ė I donít know, some strange thing. It could be gamma because weíve seen Gaussian right next to the Ė I donít know, gamma exponential. Theyíre actually a beta.
Iím just rattling off my mental list of exponential family extrusions.
It could be any one of those things, so [inaudible] the same exponential family distribution for the two classes with different natural parameters than the posterior PFY given 1 given X Ė PFY = 1 given X would be logistic, and so this shows the robustness of logistic regression to the choice of modeling assumptions because it could be that the data was actually, you know, gamma distributed, and just still turns out to be logistic. So itís the robustness of logistic regression to modeling assumptions.
And this is the density. I think, early on I promised two justifications for where I pulled the logistic function out of the hat, right? So one was the exponential family derivation we went through last time, and this is, sort of, the second one. That all of these modeling assumptions also lead to the logistic function. Yeah?
Instructor (Andrew Ng):Oh, that Y = 1 given as the logistic then this implies that, no. This is also not true, right? Yeah, so this exponential family distribution implies Y = 1 is logistic, but the reverse assumption is also not true. There are actually all sorts of really bizarre distributions for X that would give rise to logistic function, okay?
Okay. So letís talk about Ė those are first generative learning algorithm. Maybe Iíll talk about the second generative learning algorithm, and the motivating example, actually this is called a Naive Bayes algorithm, and the motivating example that Iím gonna use will be spam classification.
All right. So letís say that you want to build a spam classifier to take your incoming stream of email and decide if itís spam or not. So letís see. Y will be 0 or 1, with 1 being spam email and 0 being non-spam, and the first decision we need to make is, given a piece of email, how do you represent a piece of email using a feature vector X, right? So email is just a piece of text, right? Email is like a list of words or a list of ASCII characters.
So I can represent email as a feature of vector X. So weíll use a couple of different representations, but the one Iíll use today is we will construct the vector X as follows. Iím gonna go through my dictionary, and, sort of, make a listing of all the words in my dictionary, okay?
So the first word is RA. The second word in my dictionary is Aardvark, ausworth, okay? You know, and somewhere along the way you see the word ďbuyĒ in the spam email telling you to buy stuff. Tell you how you collect your list of words, you know, you wonít find CS229, right, course number in a dictionary, but if you collect a list of words via other emails youíve gotten, you have this list somewhere as well, and then the last word in my dictionary was zicmergue, which pertains to the technological chemistry that deals with the fermentation process in brewing.
So say I get a piece of email, and what Iíll do is Iíll then scan through this list of words, and wherever a certain word appears in my email, Iíll put a 1 there. So if a particular email has the word ďaidĒ then thatís 1. You know, my email doesnít have the words ausworth or aardvark, so it gets zeros. And again, a piece of email, they want me to buy something, CS229 doesnít occur, and so on, okay? So this would be one way of creating a feature vector to represent a piece of email.
Now, letís throw the generative model out for this. Actually, letís use this. In other words, I want to model PFX given Y. The given Y = 0 or Y = 1, all right? And my feature vectors are going to be 0, 1 to the N. Itís going to be these split vectors, binary value vectors. Theyíre N dimensional. Where N may be on the order of, say, 50,000, if you have 50,000 words in your dictionary, which is not atypical. So values from Ė I donít know, mid-thousands to tens of thousands is very typical for problems like these.
And, therefore, there two to the 50,000 possible values for X, right? So two to 50,000 possible bit vectors of length 50,000, and so one way to model this is the multinomial distribution, but because there are two to the 50,000 possible values for X, I would need two to the 50,000, but maybe -1 parameters, right? Because you have this sum to 1, right? So -1. And this is clearly way too many parameters to model using the multinomial distribution over all two to 50,000 possibilities.
So in a Naive Bayes algorithm, weíre going to make a very strong assumption on PFX given Y, and, in particular, Iím going to assume Ė let me just say what itís called; then Iíll write out what it means. Iím going to assume that the XIís are conditionally independent given Y, okay?
Let me say what this means. So I have that PFX1, X2, up to X50,000, right, given the Y. By the key rule of probability, this is PFX1 given Y times PFX2 given Y, X1 times PF Ė Iíll just put dot, dot, dot. Iíll just write 1, 1 ◊ dot, dot, dot up to, you know, well Ė whatever. You get the idea, up to PFX50,000, okay?
So this is the chain were of probability. This always holds. Iíve not made any assumption yet, and now, weíre gonna meet whatís called the Naive Bayes assumption, or this assumption that X defies a conditionally independent given Y. Going to assume that Ė well, nothing changes for the first term, but Iím gonna assume that PFX3 given Y, X1 is equal to PFX2 given the Y. Iím gonna assume that that termís equal to PFX3 given the Y, and so on, up to PFX50,000 given Y, okay? Or just written more compactly, means assume that PFX1, PFX50,000 given Y is the product from I = 1 to 50,000 or PFXI given the Y, okay?
And stating informally what this means is that Iím, sort of, assuming that Ė so unless you know the cost label Y, so long as you know whether this is spam or not spam, then knowing whether the word ďAĒ appears in email does not affect the probability of whether the word ďAusworthĒ appears in the email, all right?
And, in other words, thereís assuming Ė once you know whether an email is spam or not spam, then knowing whether other words appear in the email wonít help you predict whether any other word appears in the email, okay? And, obviously, this assumption is false, right? This assumption canít possibly be true. I mean, if you see the word Ė I donít know, CS229 in an email, youíre much more likely to see my name in the email, or the TAís names, or whatever.
So this assumption is normally just false under English, right, for normal written English, but it turns out that despite this assumption being, sort of, false in the literal sense, the Naive Bayes algorithm is, sort of, an extremely effective algorithm for classifying text documents into spam or not spam, for classifying your emails into different emails for your automatic view, for looking at web pages and classifying whether this webpage is trying to sell something or whatever. It turns out, this assumption works very well for classifying text documents and for other applications too that Iíll talk a bit about later.
As a digression thatíll make sense only to some of you. Let me just say that if youíre familiar with Bayesian X world, say graphical models, the Bayesian network associated with this model looks like this, and youíre assuming that this is random variable Y that then generates X1, X2, through X50,000, okay? If youíve not seen the Bayes Net before, if you donít know your graphical model, just ignore this. Itís not important to our purposes, but if youíve seen it before, thatís what it will look like.
Okay. So the parameters of the model are as follows with phi FI given Y = 1, which is probably FX = 1 or XI = 1 given Y = 1, phi I given Y = 0, and phi Y, okay? So these are the parameters of the model, and, therefore, to fit the parameters of the model, you can write down the joint likelihood, right, is equal to, as usual, okay?
So given the training sets, you can write down the joint likelihood of the parameters, and then when you do maximum likelihood estimation, you find that the maximum likelihood estimate of the parameters are Ė theyíre really, pretty much, what youíd expect. Maximum likelihood estimate for phi J given Y = 1 is sum from I = 1 to M, indicator XIJ = 1, YI = 1, okay?
And this is just a, I guess, stated more simply, the numerator just says, ďRun for your entire training set, some [inaudible] examples, and count up the number of times you saw word ďJayĒ in a piece of email for which the label Y was equal to 1.Ē So, in other words, look through all your spam emails and count the number of emails in which the word ďJayĒ appeared out of all your spam emails, and the denominator is, you know, sum from I = 1 to M, the number of spam. The denominator is just the number of spam emails you got.
And so this ratio is in all your spam emails in your training set, what fraction of these emails did the word ďJayĒ appear in Ė did the, ďJayĒ you wrote in your dictionary appear in? And thatís the maximum likelihood estimate for the probability of seeing the word ďJayĒ conditions on the piece of email being spam, okay? And similar to your maximum likelihood estimate for phi Y is pretty much what youíd expect, right? Okay?
And so having estimated all these parameters, when youíre given a new piece of email that you want to classify, you can then compute PFY given X using Bayes rule, right? Same as before because together these parameters gives you a model for PFX given Y and for PFY, and by using Bayes rule, given these two terms, you can compute PFX given Y, and thereís your spam classifier, okay? Turns out we need one more elaboration to this idea, but let me check if there are questions about this so far.
Student:So does this model depend on the number of inputs?
Instructor (Andrew Ng):What do you mean, number of inputs, the number of features?
Student:No, number of samples.
Instructor (Andrew Ng):Well, N is the number of training examples, so this given M training examples, this is the formula for the maximum likelihood estimate of the parameters, right? So other questions, does it make sense? Or M is the number of training examples, so when you have M training examples, you plug them into this formula, and thatís how you compute the maximum likelihood estimates.
Student:Is training examples you mean M is the number of emails?
Instructor (Andrew Ng):Yeah, right. So, right. So itís, kind of, your training set. I would go through all the email Iíve gotten in the last two months and label them as spam or not spam, and so you have Ė I donít know, like, a few hundred emails labeled as spam or not spam, and that will comprise your training sets for X1 and Y1 through XM, YM, where X is one of those vectors representing which words appeared in the email and Y is 0, 1 depending on whether they equal spam or not spam, okay?
Student:So you are saying that this model depends on the number of examples, but the last model doesnít depend on the models, but your phi is the same for either one.
Instructor (Andrew Ng):Theyíre different things, right? Thereís the model which is Ė the modeling assumptions arenít made very well. Iím assuming that Ė Iím making the Naive Bayes assumption. So the probabilistic model is an assumption on the joint distribution of X and Y. Thatís what the model is, and then Iím given a fixed number of training examples. Iím given M training examples, and then itís, like, after Iím given the training sets, Iíll then go in to write the maximum likelihood estimate of the parameters, right? So thatís, sort of, maybe we should take that offline for Ė yeah, ask a question?
Student:Then how would you do this, like, if this [inaudible] didnít work?
Instructor (Andrew Ng):Say that again.
Student:How would you do it, say, like the 50,000 words Ė
Instructor (Andrew Ng):Oh, okay. How to do this with the 50,000 words, yeah. So it turns out this is, sort of, a very practical question, really. How do I count this list of words? One common way to do this is to actually find some way to count a list of words, like go through all your emails, go through all the Ė in practice, one common way to count a list of words is to just take all the words that appear in your training set.
Thatís one fairly common way to do it, or if that turns out to be too many words, you can take all words that appear at least three times in your training set. So words that you didnít even see three times in the emails you got in the last two months, you discard. So those are Ė I was talking about going through a dictionary, which is a nice way of thinking about it, but in practice, you might go through your training set and then just take the union of all the words that appear in it.
In some of the tests Iíve even, by the way, said select these features, but this is one way to think about creating your feature vector, right, as zero and one values, okay? Moving on, yeah. Okay. Ask a question?
Student:Iím getting, kind of, confused on how you compute all those parameters.
Instructor (Andrew Ng):On how I came up with the parameters?
Instructor (Andrew Ng):Letís see. So in Naive Bayes, what I need to do Ė the question was how did I come up with the parameters, right? In Naive Bayes, I need to build a model for PFX given Y and for PFY, right? So this is, I mean, in generous of learning algorithms, I need to come up with models for these. So howíd I model PFY? Well, I just those to model it using a Bernoulli distribution, and so PFY will be parameterized by that, all right?
Instructor (Andrew Ng):And then howíd I model PFX given Y? Well, letís keep changing bullets. My model for PFX given Y under the Naive Bayes assumption, I assume that PFX given Y is the product of these probabilities, and so Iím going to need parameters to tell me whatís the probability of each word occurring, you know, of each word occurring or not occurring, conditions on the email being spam or not spam email, okay?
Student:How is that Bernoulli?
Instructor (Andrew Ng):Oh, because X is either zero or one, right? By the way I defined the feature vectors, XI is either one or zero, depending on whether words I appear as in the email, right? So by the way I define the feature vectors, XI Ė the XI is always zero or one. So that by definition, if XI, you know, is either zero or one, then it has to be a Bernoulli distribution, right? If XI would continue as then you might model this as Gaussian and say you end up like we did in Gaussian discriminant analysis. Itís just that the way I constructed my features for email, XI is always binary value, and so you end up with a Bernoulli here, okay? All right. I should move on.
So it turns out that this idea almost works. Now, hereís the problem. So letís say you complete this class and you start to do, maybe do the class project, and you keep working on your class project for a bit, and it becomes really good, and you want to submit your class project to a conference, right? So, you know, around Ė I donít know, June every year is the conference deadline for the next conference. Itís just the name of the conference; itís an acronym.
And so maybe you send your project partners or senior friends even, and say, ďHey, letís work on a project and submit it to the NIPS conference.Ē And so youíre getting these emails with the word ďNIPSĒ in them, which youíve probably never seen before, and so a piece of email comes from your project partner, and so you go, ďLetís send a paper to the NIPS conference.Ē
And then your stamp classifier will say PFX Ė letís say NIPS is the 30,000th word in your dictionary, okay? So X30,000 given the 1, given Y = 1 will be equal to 0. Thatís the maximum likelihood of this, right? Because youíve never seen the word NIPS before in your training set, so maximum likelihood of the parameter is that probably have seen the word NIPS is zero, and, similarly, you know, in, I guess, non-spam mail, the chance of seeing the word NIPS is also estimated as zero.
So when your spam classifier goes to compute PFY = 1 given X, it will compute this right here ◊ PFY over Ė well, all right. And so you look at that terms, say, this will be product from I = 1 to 50,000, PFXI given Y, and one of those probabilities will be equal to zero because PFX30,000 = 1 given Y = 1 is equal to zero. So you have a zero in this product, and so the numerator is zero, and in the same way, it turns out the denominator will also be zero, and so you end up with Ė actually all of these terms end up being zero. So you end up with PFY = 1 given X is 0 over 0 + 0, okay, which is undefined.
And the problem with this is that itís just statistically a bad idea to say that PFX30,000 given Y is 0, right? Just because you havenít seen the word NIPS in your last two months worth of email, itís also statistically not sound to say that, therefore, the chance of ever seeing this word is zero, right?
And so is this idea that just because you havenít seen something before, that may mean that that event is unlikely, but it doesnít mean that itís impossible, and just saying that if youíve never seen the word NIPS before, then it is impossible to ever see the word NIPS in future emails; the chance of that is just zero.
So weíre gonna fix this, and to motivate the fix Iíll talk about Ė the example weíre gonna use is letís say that youíve been following the Stanford basketball team for all of their away games, and been, sort of, tracking their wins and losses to gather statistics, and, maybe Ė I donít know, form a betting pool about whether theyíre likely to win or lose the next game, okay?
So these are some of the statistics. So on, I guess, the 8th of February last season they played Washington State, and they did not win. On the 11th of February, they play Washington, 22nd they played USC, played UCLA, played USC again, and now you want to estimate whatís the chance that theyíll win or lose against Louisville, right?
So find the four guys last year or five times and they werenít good in their away games, but it seems awfully harsh to say that Ė so it seems awfully harsh to say thereís zero chance that theyíll win in the last Ė in the 5th game. So hereís the idea behind Laplace smoothing which is that weíre estimate the probably of Y being equal to one, right? Normally, the maximum likelihood [inaudible] is the number of ones divided by the number of zeros plus the number of ones, okay?
I hope this informal notation makes sense, right? Knowing the maximum likelihood estimate for, sort of, a win or loss for Bernoulli random variable is just the number of ones you saw divided by the total number of examples. So itís the number of zeros you saw plus the number of ones you saw.
So in the Laplace Smoothing weíre going to just take each of these terms, the number of ones and, sort of, add one to that, the number of zeros and add one to that, the number of ones and add one to that, and so in our example, instead of estimating the probability of winning the next game to be 0 ų 5 + 0, weíll add one to all of these counts, and so we say that the chance of their winning the next game is 1/7th, okay? Which is that having seen them lose, you know, five away games in a row, we arenít terribly Ė we donít think itís terribly likely theyíll win the next game, but at least weíre not saying itís impossible.
As a historical side note, the Laplace actually came up with the method. Itís called the Laplace smoothing after him. When he was trying to estimate the probability that the sun will rise tomorrow, and his rationale was in a lot of days now, weíve seen the sun rise, but that doesnít mean we can be absolutely certain the sun will rise tomorrow. He was using this to estimate the probability that the sun will rise tomorrow. This is, kind of, cool.
So, and more generally, if Y takes on K possible of values, if youíre trying to estimate the parameter of the multinomial, then you estimate PFY = 1. Letís see. So the maximum likelihood estimate will be Sum from J = 1 to M, indicator YI = J ų M, right? Thatís the maximum likelihood estimate of a multinomial probability of Y being equal to Ė oh, excuse me, Y = J. All right. Thatís the maximum likelihood estimate for the probability of Y = J, and so when you apply Laplace smoothing to that, you add one to the numerator, and add K to the denominator, if Y can take up K possible values, okay?
So for Naive Bayes, what that gives us is Ė shoot. Right? So that was the maximum likelihood estimate, and what you end up doing is adding one to the numerator and adding two to the denominator, and this solves the problem of the zero probabilities, and when your friend sends you email about the NIPS conference, your spam filter will still be able to make a meaningful prediction, all right? Okay. Shoot. Any questions about this? Yeah?
Student:So thatís what doesnít makes sense because, for instance, if you take the games on the right, itís liberal assumptions that the probability of winning is very close to zero, so, I mean, the prediction should be equal to PF, 0.
Instructor (Andrew Ng):Right. I would say that in this case the prediction is 1/7th, right? We donít have a lot of Ė if you see somebody lose five games in a row, you may not have a lot of faith in them, but as an extreme example, suppose you saw them lose one game, right? Itís just not reasonable to say that the chances of winning the next game is zero, but thatís what maximum likelihood estimate will say.
Instructor (Andrew Ng):And Ė
Student:In such a case anywhere the learning algorithm [inaudible] or Ė
Instructor (Andrew Ng):So some questions of, you know, given just five training examples, whatís a reasonable estimate for the chance of winning the next game, and 1/7th is, I think, is actually pretty reasonable. Itís less than 1/5th for instance. Weíre saying the chances of winning the next game is less than 1/5th.
It turns out, under a certain set of assumptions I wonít go into Ė under a certain set of Bayesian assumptions about the prior and posterior, this Laplace smoothing actually gives the optimal estimate, in a certain sense I wonít go into of whatís the chance of winning the next game, and so under a certain assumption about the Bayesian prior on the parameter. So I donít know. It actually seems like a pretty reasonable assumption to me. Although, I should say, it actually turned out Ė
No, Iím just being mean. We actually are a pretty good basketball team, but I chose a losing streak because itís funnier that way. Letís see. Shoot. Does someone want to Ė are there other questions about this? No, yeah. Okay. So thereís more that I want to say about Naive Bayes, but weíll do that in the next lecture. So letís wrap it for today.
[End of Audio]
Duration: 76 minutes