Skip to main content
Loading Explore guides…
Naive Bayes ML Lecture · Acedra
Home
Explore
Computer Science
Naive Bayes ML Lecture
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
153 segments
Copy
Hide video
0:05
good afternoon CSO at nine how are you guys doing today yeah it's the day before Thanksgiving how are you guys feeling okay it's got to be uh nice to have a little bit of a break coming up uh we have an exciting class today we're going to be talking about naive Bayes it is not only one of the things that you will be implementing on your final assignment in cs109 but it's going to be our first machine learning algorithm that we learn about in cs109 exciting day but it's a
0:32
Friday so because it's a Friday I was going to tell you guys a little bit story uh and I was going to tell you a little bit of story of my lovely daughter so this is my lovely daughter and I think you guys know I have a daughter at this point um but you know there's so much I can say about it like wow Parenthood what an adventure it's been I've learned so much more in these last year and a half uh then maybe I learned an entire PhD about life how people learn uh it's just been
1:00
such an exciting time you know how to teach people boundaries but there is you know there I I would love to share something interesting that we've also gone through uh as parents that not every parent goes to which is when very young so she was born as this crazy experience and then the next two weeks were like this sleep deprived Bliss of like this brand new soul in the world but then when she was two weeks old we got some interesting news we found out at that point that she was born not able
1:33
to hear at all which is surprisingly common about one in a thousand babies this happens and uh you know there wasn't a family history so it was a little bit surprising for us and again I feel like I immediately learned a lot it wasn't what we expected but boy do we learn so much first we learned sign language we learned about this whole new wonderful culture that exists in the US and around the world um and we learned a little bit about as a parent not having clear expectations
2:01
for the life your child is going to lead like they're always going to lead different lives than you than you designed for them they get to choose uh we just we're learning a lot about that a week too but then also an interesting thing is you know she has these things called Cochlear implants and you guys might have heard of those before um basically she has a microphone and that microphone goes to a processor the processor goes to a coil the coil sends a little signal to a receiver on the
2:27
inside of her head that's connected to her auditory nerve and it stimulates her auditory nerve so basically it's a microphone that stimulates directly this thing in the inner part of the ear and it's incredible if you didn't know the biggest breakthrough in this device happened here at Stanford actually in the ee department they figured out a whole bunch of key ideas to make this possible in humans and now she hears so well now it's such a hard story to tell because I was so ready to embrace not
2:55
hearing like signing was the coolest thing and I was really excited for that Journey too but now it looks like our journey has hearing and talking and dancing in fact every day starts with a dance party at 6am but you know I must say that's like one of the things that I'm very thankful for so going into Thanksgiving I'm just so thankful to have this wonderful soul in my life who's taught me so many things I am also thankful for the people who worked hard in Technologies to give her access to
3:25
this one facet of life that I have enjoyed and you know also thankful for all the dance parties and the hugs so that's my Friday story for getting us started bring us back into cs109 we are having this wonderful Capstone experience in cs109 where we are building up towards learning some of the fundamental algorithms that are currently changing the landscape of computer science and artificial intelligence uh we will be working up towards deep learning AKA neural
3:52
networks to get there we are going to start learning some algorithms on computer science and we've done a lot of work we've built a strong foundation of the core theory that you need to know and now it's time to celebrate use that core Theory to learn the algorithms that are powering the technologies that you hear so much about and today is going to be that first so exciting days and we're going to pick off one of these two critical AI algorithms called naive Bayes
4:19
now that we're getting to machine learning I thought it'd be helpful to just give you a picture of how machine learning fits into the world of probabilistic models a lot of times we think of machine learning as being a probabilistic model you'll imagine getting some inputs and then your probabilistic model will have some parameters and based on those parameters it will make a prediction and it'll often do so probabilistically and these parameters are just like all
4:44
the parameters we've seen in parameter estimation really you should still think about them as sliders and if you had the perfect settings for these sliders you'd have a good probabilistic model that could do this input output prediction quite well parameter estimation is that art form of setting sliders and that art form setting slider is going to be the core theoretical basis for making good probabilistic models and we really have two great ideas for how you could set
5:10
those sliders the first great idea is maximum likelihood estimation you're going to choose the slider values that make data in a training data set look as likely as possible and you work through some of the math that means we're going to set our sliders using this beautiful little equation that's only one perspective and on Wednesday's class we saw a totally different perspective and the totally different perspective was instead of choosing the sliders values that make
5:36
the data look as likely as possible we're going to choose the most likely slider values given the data that we've seen and they're both defensible people use both of them they have just one big difference when you get to the final equation in mle we're just going to have the log of the likelihood and we're going to be choosing the parameters that maximize this in map that's the fancy version for the Bayesian idea of choosing the most likely parameters you have basically the
6:07
same equation but you now are also going to have a term that's related to you How likely you thought the parameter value was to take on its current value before you saw any data a prior so you have a Bayesian prior and it's just like the prior uh in any of your Bayes equations that you've seen before and you'll have a term for that prior and the rest is exactly the same and so realistically these aren't all that different and the biggest 10 out of 10 takeaway is
6:38
you now have tools that could allow you to take data and any probabilistic model and choose good values for parameters important notation though that we're going to see a lot is even though there's always random variables like for example in this map equation there should be a random variable for the parameters there should be a random variable for the first data point there should be a random variable for the nthaded point and realistically the probabilistic statement should be
7:07
talking about equalities of the random variables taking on specific values it's too much to write nobody writes out the full expression instead people will often write that same expression using shorthand like before below or you say How likely are the parameters given the data points it implies that there is a random variable for each of these non-random observed variables so like X1 that's the observed X1 and it's implied that we're talking about the event of
7:38
the random variable X1 taking on that value I don't want to confuse anyone on notation certainly in lots of other probability classes they'll just show you this and work with it and people will just be like okay okay great it's the likelihood of the parameters given the data if you want to get really really specific this is the slide that you could use for making sure you're understanding the notation in this review I did want to just give you another perspective on map and I
8:05
wanted to combine it with what we learned about with betas so in a beta distribution you're estimating a single parameter which is the P of a Bernoulli or a binomial and where you're estimating that P of binomial after you've seen data and after you've Incorporated prior you calculate what we call the posterior beta and beta distributions story ended there maximum a posterior if you are estimating that particular parameter would then take this posterior and it's
8:35
going to choose whichever argument maximizes the likelihood of the parameter that's also called the mode so the mode is the value that is most likely okay I'm almost done with review and maybe if there is just one thing to really focus on in this review it would be this takeaway about map for Bernoulli so when we learned about betas we said if you're estimating the P of a Bernoulli or a binomial same thing you can imagine that before you see anything you could have your belief in
9:09
the probability expressed as a beta then you see some data and you end up with what we call the posterior belief your belief after data and that was a beta as well and if you took the mode of that beta then you get the map prediction which is given by this little formula it leaves this question for the user which is what was your prior belief can I just give you the prior belief that I always use if I don't have any other reason to choose a different prior
9:36
I use a particular prior which is a beta 2 2. that's imagining one imaginary success and one imaginary failure before I see anything and with this particular prior you end up with this particular posterior and the map estimate is just a simple equation so how many successes did you see in your data divide the add one to that and divide that by how many successes plus how many failures plus two and it's just a very very very reasonable estimate this particular prior has a fancy name
10:08
called LaPlace prior and LaPlace prior is just a fancy way of saying one imaginary success and one's imaginary failure before you get going yes question yeah yeah particular reason why you click two two instead of one one yeah because of the beta oh my gosh like if somebody says beta 2 2 so a beta 2 2 means that Alpha equals two do you remember what Alpha was it was number of successes plus one so two two means one imagine success one imagine failure if you had beta 1 1
10:44
that's zero imagine successes zero imagine failures the LaPlace actually has a really good intuition for why you don't want it or sorry why you would want the LaPlace you could never end up with a probability of zero or a probability of one and for some reason it's like no matter what I'm estimating whenever I'm messing in probability I never want to think it's impossible and zero or one can represent different versions of impossible but because of that LaPlace
11:13
has that nice property it's the least assumption you can make guaranteeing yield you'll never get a zero so maybe you get never going to divide by zero in your equation okay good good good question so yes what is it again so map at its core is a philosophy is a philosophy for how to estimate parameters in general if you applied that philosophy to estimating the parameter p in a binomial you would end up with the beta and you would end up with not just the beta but you would end up with this
11:51
posterior that's assuming a prior but with this prior and the map philosophy applied to the Bernoulli you get this posterior
12:07
yeah and map they're so related map will just choose one number whereas the beta represents a whole belief distribution but they're so related because they're both doing the exact same Bayesian thing good question okay so and big picture philosophically we have two ways of setting parameters and both of them give us numbers for every parameter they don't give us distributions they actually give a cold hard number for every single parameter they're supposed to estimate
12:35
okay and that's what we've got for review shall we jump into it let's see some machine learning so we've got our last estimator and it's time to start thinking about machine learning let me introduce you to the tasks you are going to be able to do on your final problem set on your final problem set you're going to write two machine learning algorithms and those two machine learning algorithms can all do tasks that will apply to these different data sets all the tasks are going to have training
13:04
data and the training data is going to have both inputs and outputs I'll talk about that a little bit more this is how I could introduce it ah sorry these aren't updating fast sorry I could introduce it with those equations but let's come back to these equations and let me explain to you what these equations are saying let's imagine your task is you have some input movies and whether or not users like them and you want to predict if the user will like a particular output movie
13:33
does that sound like a reasonable task for every single user you'll be given a whole bunch of training data and in that training data you'll give be given historical users and for every historical user you'll be told what movies did they like and you'll be told the truth about whether or not they like the output movie we think about this as a tuple a combination of the input things that you would use for your prediction and the true label of whether or not for this
14:05
historical example the person actually did like the movie and I'm going to give you a whole bunch of these and your machine learning task is to build a little system that could take the inputs and predict the output so um let's be clear the inputs in this case are all these movies and whether or not the user liked them and the output is whether or not the user liked a particular Target movie in this case it's Miss Congeniality um now a little bit about notation
14:37
notice how our inputs are x's and the thing we're trying to predict is y I will always be consistent about that notice this superscript I that means the ith person in our training example and there's a very specific reason why we use superscript for I and not subscript for I and we'll use this notation in 229 they'll use this notation 221 they'll use this notation is because you see this x it's a little bit weightier than the Y it's bold and does anyone know why you
15:07
would bold a random variable or a variable in general yeah it's a vector it's a vector why is it a vector because Vector is mathematics for a list and it's a list of numbers it's not just one number the X itself has a whole bunch of numbers in it because of that when we're writing it you'll sometimes see it bold and there's just one other thing I'd like to say about that Vector notation which is since x i is a list you may want to talk about a particular element in that list
15:38
and this is what the notation looks like and I'm giving you the full professional version so that in later classes you'll be able to follow along using the exact same notation but if you want to talk about this particular value well it's from the ice user and this could be the J uh the jth value in this particular case it's user number two and this is movie number m and because we use the superscript it's easy to differentiate between the particular training data point we're on
16:08
versus if you want to talk about a particular location within the list which is the inputs notation can be so complicated please what's confusing about this
16:24
yeah so if we were to apply to this case rule are we on this is row two and then the sub ject exactly exactly and um hey notice this computer science is like to be zero index and mathematicians like to be one index is cause all sorts of bugs everywhere but just know that by one index I mean they often think about user one user two in notation okay great so we've got some notation and the beautiful thing that we're going to do is we're going to talk about a lot
16:59
of different interesting tasks you might do that all have a very similar format another task you might care about is we're going to look at different regions of Interest that's what Roi stands for in someone's heart and based on whether or not we see abnormalities in those regions of Interest we're going to predict if they have a healthy heart or not so again this follows the exactly the same format if I talk about input so X from the first person and the second value within that list I might be
17:30
talking about this particular number which is a one so if I talk about this whole second person this whole second person has two things they have all their inputs the regions of interest from which we'll make our prediction and the output you're told whether or not this person had a healthy heart to be clear the interesting thing about this is going to be based on this training data you make a machine so that if someone doesn't tell you whether or not somebody has a healthy heart you can
18:00
predict it so you're going to build a machine that can take inputs and make a prediction about the output yeah um so just based on these two examples it seems like everything is quite binaries and it's just like a true or false for both the inputs and the outputs yes so if we were to make it um not binary so for example for the movies there was like some sort of rating that they could yeah how much more complicated would it be you know it's a good question not that much more common
18:26
so the question was hey Chris I noticed that everything's binary and you're astute everything is binary I'm going to keep it binary because I want to explain all the theory kind of keeping things as simple as possible and then your question was if you want to break that assumption how much more complicated will it be well once you see the algorithms you'll realize not that much more complicated though it is so helpful to understand these algorithms just thinking about the simplest case which
18:48
is binary yes Roi images that are going in are you just looking if like that feature is present on the heart and how does that actually work so I this is a real data set from real people's hearts and what doctors would do is um there'd be different Specialists who could look at different regions and say whether or not it was healthy or you know whether or not they saw something and no specialist was able to predict healthy Hearts but if you took all the Specialists together and their
19:15
perspective on each region it turns out that people were able to make much better predictions about healthy hearts just measuring whether the hearts overall or healthy it's not like given a new heart and that's casting and that's healthy yeah so but but once you build this machine you can imagine a new person comes in doctors look at each of the region of Interest we put those numbers those ones and zeros into the machine and it says this person's got an unhealthy heart we need to go look
19:39
further into it yes great question um a little bit more annotation you know just to make sure we're following along if I talk about X2 that's the input for the second person and if I talk about Y2 that's the thing we're trying to predict and it's the label that we're given in the second training example okay and then another data set was ancestry classifier so some companies can look at DNA and they can predict our ancestry and the sorts of data they have is whether or not there's a change at a
20:14
different particular nucleotide location we don't have to worry too much about that but you'll get be given M different nucleotide locations and for each user you'll say whether or not they have a change at that location and then you'll have an output of particular ancestry that you might want to predict so the question that was asked earlier everything I showed you was binary and certainly there's lots of algorithms that break this you could have continuous values you could have
20:42
discrete values you could mix continuous n binaries you could have predict things that are non-binary there's lots of cool extensions of this but first understand the core with binary and then it'll be easy to talk about these extensions so bringing all together this is how the problems formulated I'm going to give you a bunch of training data and from that training data your job is to build a classifying machine a machine that can take in an input and predict an output
21:11
every training data is an input output pair so we call it labeled because it's like I gave you the input and I label whether or not it's a one or a zero and I give you n of these we talk about how many features your training data has by looking at any input and saying how long was that list how big was that vector and that's how many features we say your training data set has okay um machine learning is this process of taking training data and learning parameters for a probabilistic model and
21:46
it's ubiquitous this is one particular version of machine learning that we call classification and we call it classification because you're predicting a one or a zero you're predicting the Y and since the Y is like one of a small set of classes that's where we get this name classification there is other versions of machine learning maybe you're predicting continuous numbers maybe you're predicting actions there are other versions but classification is the heart and soul and where it all starts
22:15
one metaphor I have for this task you are given is you're making the Harry Potter Sorting Hat and I love to think about this like everybody is like curious about this Harry Potter Sorting Hat what would be like to see it and Stanford not only do we get to think about it but we get to learn you know what could possibly go into making your own Sorting Hat this classification algorithm that we're going to you know use the Sorting Hat as a little metaphor for you can imagine it
22:44
looks at some input so it gets this list of features zeros and ones and its job is to predict a label a one or a zero are you guys following along the task ask questions if there's anything confusing certainly worth clarifying before we jump into how are we going to solve this
23:03
yeah certainly is how we're going to start by solve this okay so we've got these three different problems let's jump into one of them the Netflix one and let's think about this a little bit so I've got a very simple version of this problem my version for you is that for every user there's only one movie in the inputs that we're going to look at Independence Day and the output is going to be predicting if somebody likes Life is Beautiful so every single value in our feature
23:35
it's a zero one to be clear every single value in our predictions either a zero one one means they will like the movie Zero means they won't and I'm going to gently start us how could we build a machine learning algorithm to do this task if you only had one feature input and I have an algorithm for you it is called Brute Bayes classifier and no one ever uses this algorithm but my promise for you is this is easier to understand and if you understand this and you see
24:06
why it breaks then understanding naive Bayes will make a lot of sense so you guys want to hear my total hackie algorithm here's my hacky algorithm we are going to build this machine it's going to be a probabilistic machine learning machine and it's going to take in inputs whether or not somebody likes Independence Day and it's going to predict an output whether or not they like life is beautiful now in general the input will be more than one number but originally this
24:34
input is just going to be a single one or a zero what I'm going to put into my machine is I'm going to have a little function which calculates How likely is it that the output is a one given the inputs I observe and if the probability that the output is 1 given the inputs I observe is high enough then I'll predict a 1. and particularly I might do this if I could say put a zero into this and if I put a 0 into this and it says the probability that y equals zero given
25:12
the inputs I observe is 0.62 then maybe I should be predicting a zero does that make sense I'm just going to figure out the probability of the output given the input straightforward right seems like a reasonable thing to do you gave me an input value I calculate the probability of the output and if the probability output being zero is greater than 0.5 I predict zero otherwise I predict one now you know hopefully if I put in a zero and I got 0.62 then if I put Y in
25:42
as one the probability that y takes on the value 1 will be whatever makes those two things add up to one making sense yeah So when you say outfit does that mean significantly one or zero or any output yeah this whole machine learning algorithm has to give back a one or a zero one meaning you think they're gonna like the movie Zero mean you think they won't so classification you don't have to give me anything other than a one or a zero but the probability yeah I'm just
26:12
to get to the answer if the probability of y equals one is less than 0.5 then I predict zero so it's a step towards my final answer which will be a one or zero very good question okay now to put this a little bit mathematically one way of saying this is I'm going to choose a zero if the probability that y equals zero given X is greater then if you put a 1 in for this so if you put it in a one for probably y equals one given X if that's larger than if you put a 0
26:42
in for this y then we're going to be predicting one so just in some notation I'm just going to say it's the ARG Max over my choice of y's whichever one is larger for the probability of that value given X so here's how I want to make my prediction it's either going to be a zero one and it's going to be which everyone makes this probability large so what just be clear why hat is gonna be a prediction will they like life is beautiful and X is going to be whether or not they liked Independence Day
27:14
and I call this Brute Force Base because it turns out maybe estimating this probability is a little hard so I'm going to use some Bayes theorem just to be clear if y equals one that means they like life equals Life is Beautiful so I'm gonna use some Bayes theorem here I'm going to say okay this is the same as if I took that term and I replaced it with Bayes theorem the probability of x given y times probably of Y divided by probably of x beautiful thing about ARG Max is that
27:41
ARG Max doesn't care about constants so this normalization constant on the bottom it's a constant it doesn't change as y changes therefore it doesn't affect whichever 0 1 is going to be the argument which maximizes this expression it goes away fantastic so I haven't done too much here I've just basically done I'm going to do Bayes theorem and I'm going to get rid of the normalization constant because normalization constant gets lost in the arc Max questions about that
28:13
such a weird thing the normalization constantly why doesn't change as you put in if y was zero or Y was one it's crazy to think that the probability of X doesn't change that's mind-blowing but I promise you it doesn't change it is a constant that's why it's got its name because it's a constant uh it doesn't affect the ARG Max I don't really understand why we go from probability of why giving thanks to our maps of Hawaii oh yeah because the output of this little machine isn't
28:42
supposed to be a probability the output of this machine's got to be a zero or a one and so the arc Max is just a really fancy way of saying I'm going to turn this probability which is a continuous number between 0 1 I'm going to just discretize it into either or zero or a one that makes sense yeah if you go back to the machine okay here's my claim No it should make sense um the machine doesn't give you back a probability those machines got to give you back a zero one so if you can
29:13
calculate the probability that y equals one you're not done you have to do the simplest thing if you figure out the problem that y equals one like let's say I told you that probably y equals one is 0.7 what what do you predict
29:30
oh no much easier I just tell you the at least on your ex I told you that the probability that y equals one so if I say the probability that y equals one given the x that you observed if I tell you that this number is 0.7 I'm telling you that based on your inputs the probability that the output is 1 is 0.7 you have to predict something do you predict that Y is one or zero yeah so this gets turned into a prediction of one
30:07
kind of yeah exactly exactly it's like Arc Max is a fancy way of saying round it up now Arc Max is a little bit more elegant than just saying rounded up the reason ARG Max is a little bit more elegant than rounding it up is it's saying well I'm going to choose whichever one's bigger y equals zero or y equals one and the reason it's nicer to put it as an ARG Max is exactly this part where you know rounded up wouldn't allow you to get rid of a normalization constant whereas ARG Max which is doing
30:35
the same thing as rounding it up has this really nice property that if you ever have a constant it just doesn't come into your equation and you don't have to bother calculating probability of x good question does it make sense now yeah okay fantastically that's critical if there's something that doesn't make sense just stopping this is not too much content in this lecture I just want to make sure everybody understands it because you're gonna have to code it up okay
30:56
so here's my Brute Force Base it's just our warm up to naive Bayes and the simple idea is I've got a tiny little probability engine and it's going to predict one or zero now in order to do this I'm going to be able I need to be able to know these terms I have to know the probability of y equals one and probably y equals zero and I have to know the probability that x equals 0 given y equals zero they're probably x equals one given y equals zero probably x equals zero given y
31:25
equals one and probably x equals zero one given y equals one so what are the parameters I told you machine learning you'd have these little you know probabilistic machine we'd estimate the parameters and then using those parameters we could make predictions where are the parameters here
31:46
and my answer for you is that the parameters are in these two things that you have to calculate you know your Brute Force Base is going to make a prediction based off these and so you need to be able to when you're coding this up you have to say what's the probability that y equals zero and what's the probability of y equals one and then for any value in this conditional probability table you know if y equals zero and x equals zero you need to say what's the probability that
32:13
what x equals zero given that y equals zero so you need one two three four five six parameters and if you could estimate all these parameters from your training data then you'd have a probabilistic model and you could make predictions I'm going to take a moment here now that I've told you about the parameters and I want you to talk with a person next to you and I want you guys to do one of those like ask the person hey what's confusing about this and see if you can
32:39
generate a good question for me so what's confusing about this here's my parameters think about it for for a second with the person next to you and then we'll talk about it all together okay go for it
33:32
oh yeah
34:17
okay hopefully there's a good chance to come up with a good question I took some I took that moment to write up there's kind of three critical random variables here X the input movies in this case Independence Day did they like the input movies and that will take on some values why is do they like the target movie and I just want to point out that Y and Y hat are slightly different why is do they like the target movie and why hat is your prediction for whether or not
34:46
they like the target movie and so we do have slightly different notation for predictions versus the actual truth okay questions that came up yes
35:06
I could have a lot more data points I could give you hundreds I could give you actually this is Netflix I got a million data points for you no problem so I have a million data points but you there's still another question which is like do you actually need all these parameters I could hone in on these two parameters if I told you that this number was the probability that y equals zero if you want to probably y equals one but you knew the probability that y equals zero could you figure it out
35:35
there's a little bit of redundancy here we're not going to worry too much about it but you could have a slightly more compressed parameter set if you wanted to but this is the simple algorithm we're not going to worry about optimizations maybe you're representing a single you for like ah good question so the X you know on some level when you train you'll be given many users and for each user you could be given many movies in this case though X is going to be for the ith user
36:04
so we're going to talk about particularly for like this is after you've trained so a user comes in and they like list of movies X uh and in this case the list is just one because we're doing it for the simple case where there's only one thing we're basing our decision off of
36:24
exactly you would just for a loop over this and you'd make your prediction for each person yes good question yes um
36:37
you know what that's a really good question we're always told their history you don't have to guess at their history because I tell you for X's whether or not they like this movie there's no guessing involved
36:52
why yeah why okay good good good X is like I tell you this about the person and you have to predict this stuff so the x is the stuff you're told and why is the stuff you're predicting ah so you're gonna make a prediction and we have two things to separate the guests you made and what you know whether or not they actually turn out to like this movie this is what we call unobserved yeah you generally don't know if they like the movie uh and so you just make your prediction and then maybe in the
37:30
future you'll observe if you got it right okay I just want to be clear about those two things yes um could you explain again
37:40
yeah each of these is going to be a probability and so there's all these different things like you should know the probability that X um whether or not they like Independence Day given whether or not they like life is beautiful you should know that problem and if you know each of these probabilities then we'll be able to calculate this expression no matter what X or Y are if you told me each of these probabilities so yes we should estimate those all those probabilities every
38:07
Theta will be a probability if you want to know how we get those probabilities yeah yeah on some level counting is a very good answer um and just be clear I'm going to put all these into a conditional probability table which says you know condition on wise value the probability of X taking on these values and I'm just going to put it all into one little structure here okay there is a question how do you take your million users and estimate all of these probabilities and then you just
38:40
said it you're like counting what a reasonable thing to do um mle says you should just count you can think of this as a binomial and you're estimating the probability p and mle says just count you'll say what's the fraction of users who like uh this movie given whether or not they liked the movie why and if it turns out nobody did you'll get a probability of zero and you could end up with a probability of one if everybody who watched this movie liked it so mle says just count figure out you
39:15
know what fraction of people who like movie y also like movie X map has a different uh opinion map says just count but since this is a binomial like we talked about in review you can add in your imaginary trials for your beta prior and as I told you the imaginary number of trials that I like to use is What's called the LaPlace prior which is basically you add in one imaginary trial for each outcome so if y equals zero I'm going to add one imaginary trial for x equals zero and
39:46
one imaginary trial for x equals one so you can imagine you're like this here is a beta P for binomial that I'm estimating and I can use mle or I can use map for it map or mle they're both very very similar they're both basically just counting it's just map adds in one imaginary trial for each outcome at this point I've given you a theory I've told you how we can get training data and we can estimate the parameters what I haven't told you is what it actually looks like to make our
40:23
prediction so let's just go through this let's imagine you've learned all these probabilities from data you learned all your parameters here's how you could use it a new user shows up and they like Independence Day so that means that X1 is one and we can say okay we're going to ARG Max this and we're going to Loop over the value y equals 0 and Y equals one let's start with y equals zero this expression when you put in y equals zero and you take into account that X1 was one becomes
40:53
this it becomes probably X1 equals one given y equals zero times probably y equals zero and this is just going to be taking in two different numbers probably y equals zero we've got a parameter for that the probably that x one equals one given y equals zero we've got a parameter for that in our conditional probability table you just multiply those two things now we should also look into the case that maybe they do like life is beautiful so if we set y equals one
41:21
we can take what's the problem that y equals one well you know that parameter and we can know what's probably that X1 equaled one given that y equals one we know that parameter uh and so we can just multiply those two things and we get a different number this was the expression when y equals zero this was the expression when y equals one what value of y is the argument that maximizes you guys can just say it but say with confidence yeah fantastic it is in fact one notice
41:53
how I don't change X I was told that they like Independence Day I'm not going to be messing around with X1 I know it's a one what I'm trying to guess is y and so this ARG Max tries the argument y equals zero it tries the argument y equals one which everyone had a higher expression that will be my output so I'll be predicting in this case that y equals one they will in fact like like Vehicles life is beautiful yes y here but it should the law like total probability
42:21
say that both of those numbers should be adding up to one they will not add up to one why don't they act so one that's such an interesting question you're right they don't like you're glancing at this is like this is like less than five and that's point two they don't add it to one oh my god did we do our math wrong no everything about this math was fine what happened an idea I usually don't like independency and if we did and we usually call the conditional probabilities and then we
42:56
get to one that's a very good guess it's a very good guess that's not in fact it but that was a very very good guess there's another thing that we got rid of it's your question is it because we got rid of it it's because we got rid of the normalization this is no longer a probability If This Were to be the probability that y equals zero you'd have to divide it by the normalization constant similarly if you want this to be the probability that y equals one you'd have
43:24
to divide by the normalization constant because we got rid of those two numbers they're no longer true probabilities and it's no longer the case that this is the probability that y equals zero and this is probably y equals one instead these are the Expressions whichever one's largest will be our prediction Yeah question question
43:44
we're not trying to predicate this uh X is always one
43:52
life Independence yeah it was just um you know Bayes theorem flipped that conditional so Bayes theorem said it's going to be a problem like Independence Day given whether or not they're like why we actually calculate both terms because even when it's above 50 percent it doesn't mean exactly because you know when you calculate this one in this point too you're not done because you didn't do the normalization constant so you have to do this term and you have to do both of them otherwise or
44:21
alternatively you could go and figure out what the normalization constant was but we don't like to do that we like to avoid the normalization constant yes so can we use these results in like the actual probability context comparatively like saying it's twice as likely the thing like it then we don't or do we only say that we predicts that they don't at the moment all your job is to say predict they like it or not but it turns out you could in fact take these two numbers and figure out what is
44:48
a normalization constant because remember the normalization constant will be whatever constant you know this thing was divided by if we use the fact that we knew that the two probably should add up to one and that they have the same normalization constant once you have these two numbers you could backwards compute if you wanted a probability so yes we could get more insights but our job is so simple predict a zero or one for now okay but this isn't the real base
45:16
but it was just great that was fantastic there's like nothing wrong with that theory it was a really good way to make prediction are you guys ready for Brute Force Base m equals two what's m it's the number of features per user and by features I mean how many inputs do you have for user now I've got two users we're thrown in zootopia so now you're going to predict whether or not somebody liked life a beautiful but not just based on Independence Day also based on zootopia
45:43
and we use the same Theory we're gonna be like okay I'm going to either predict a zero one based on which one of these makes this term the largest the probability of Y given my inputs seems like a very nice Theory to start out with I like it fantastic and then we get to use base that makes me so happy you guys know whenever I get to use Bays like a little warmth in my heart grows so we're very happy here this is a great Theory we get to use bays and it you know leads to this expression and one
46:10
thing that makes us so so happy is that the only thing we don't like about base is normalization constant but because there's an ARG Max here we don't even need to bother with a normalization constant whatever value this is it won't change which argument maximizes the expression um and therefore we just need to calculate this this is exactly the same as when m equals one but now it's worth recalling that X is a vector in this case remember that X will have two numbers because there's now two
46:39
movies that are in our inputs make a sense okay so what are you gonna do this is the joint probability of the liking movie one and movie two given X and when you hear a joint you should be like ooh ooh joints don't those get big they do get big well let's look at all our parameters this doesn't include the parameter for probability y I'm just looking at all the parameters you need to be able to compute this expression to compute this expression you have to say if y equals zero What's the joint
47:09
probability of any combination of X1 X2 if y equals one what's the joint probability of any combination of X1 X2 but that's not so bad we have eight parameters for this term you know two more for this we've only got 10 parameters that's not too bad and if you want to estimate all of them you could do that Based on data you could say you know counting based on probability that y equals zero I could count for each of these and come up with a pretty reasonable estimate fine not a big issue
47:38
Brute Force Base m equals three we're throwing in a random TV show and now we have to make our prediction same Theory starts with that wonderful place of oh let's just predict which everyone's most likely given the inputs then we can use Bayes theorem and rewrite this and we can get rid of the normalization constant fun times like we've always been having and the only thing that's different now is that X is a list it will have whether or not they like movie One whether or not they like
48:09
movie two and whether or not they like movie three and we'll talk about the probably all three of those given y so we're going to have to have a parameter if y equals zero I'm going to have to know the probability of the joint assignment of X1 X2 X3 in that case so if y equals 0 I couldn't make a three-dimensional table but if I could I would have put a three-dimensional table here at three dimensional table say for any combination of X1 X2 and X3 I guess that is a three-dimensional
48:40
table well okay any column is X1 X2 and this is for X3 equals zero and this is X3 equals one you know there is these eight values to represent the case for y equals zero and eight values for the case for y equals one oh 16 parameters now that's fine 16 parameter is not a problem we've got millions of users we can estimate all 16 of those parameters just counting what if m equals 100 well we go back to her a lovely little Theory and it starts with the probability that Y is one or zero given
49:11
X fantastic we use Bayes theorem fantastic that makes us happy we get rid of the normalization constant we do our little normalization constant is gone Dance and then we end up with this final expression and we're like okay this just needs us to have a parameter for the probability of any assignment to the hundred movies given y like oh actually Chris oh might be pretty big there might be quite a lot of parameters how many parameters would there be and one way to ask that question is if y
49:44
equals zero how many unique assignments could you make to X1 X2 X3 X100 because you'll need a parameter for each unique assignment
49:56
somebody who hasn't said anything yet today
50:07
okay yes a lot yes because there's so many uh do you want to get more specific we can walk through it together okay X1 what are the values that X1 could take on exactly one or zero so okay there's two choices here what are the values that X2 can take on yeah and no matter what X1 is X2 can still be one or zero so there's two choices here two choices here two choices here and there's two choices for that hundredth one
50:41
oh that's a lot 2 to the power of 100 and that's just for y equals zero you'll need another two to 100 for y equals one so it's actually technically 2 to 101. that's a lot oops we have more parameters than number of atoms in the universe I hate when that happens that's going to take a lot to estimate there might be a lot of people on Netflix but there's not that many people and now there's Disney plus so there's like other issues Big O for number of parameters so if m is your number of features
51:15
and every feature can either take on the value 0 or 1. this Brute Force Base has a problem because the number of parameters will be big O2 to the power of M and that is just too much so even assuming each feature is binary this is not going to cut it Brute Force Base you are so kind to us you tried so hard but you try to use too much force for what should have been a more delicate problem okay a pedagogical pause think of the fire if there's something confusing come ask me or if you need to
51:50
run to the bathroom go run to bathroom I'll give you guys two minutes and um switch over to music I'm going to try and play
55:41
okay Okay so just to bring us back to the plot line this was going to be so cool we have this great idea it was going to allow us to completely uh calculate the whichever choice of zero one would maximize the probability of Y given s what a good good idea it just ran into this problem that this term here is in fact talking about the probability of the joint assignment to x given y and when computer scientists came across this problem they're like well that's exponential that's going to be a huge
56:21
problem and in very computer scientist fashion they're like well let's just hack it and they came up with an assumption assumption that is so wrong it might shake you to your core but assumption that is so helpful is going to make this very very straightforward they called this assumption the naive Bayes assumption and here's what the assumption is is this is hard to calculate what if we just assumed that every value of x I was independent of each other condition on y
56:59
so if you tell me whether or not somebody likes life is beautiful I'm going to assume that whether or not they like every other movie is independent of each other now first of all if you make that assumption it's got this sweet sweet payoff that this hard term becomes a product of a bunch of much easier to think about terms it's a product of thinking about each movie X on its own given y you don't have to think about anything jointly once you assume Independence so that's the good news
57:28
what's the bad news is there any yeah there kind of is the bad news is that's not right that's not true at all like let's say this is whether or not somebody likes zootopia uh and then this movie is whether like zootopia too like are those truly going to be independent of each other no whether or not you like zootopia one very much changes whether or not you like zootopia too now the Assumption says like oh oh but but if you condition off whether or not they like life is beautiful then it's
58:01
mostly mostly independent and it's just wrong but it makes the math a really sweet question don't we always assume Independence anyway so why why is it so awful in this case yes what we assume we've always been assuming IID samples and to be clear what that means is if we go back to our data set where's my mouse there's my mouse so if we go back to our data set the IID sample assumption is saying I assume user one is independent of user two or and they come from the same
58:37
distribution so you know maybe the data points can have some relationship because they're coming from the same distribution but I assume that they're independent from one another and assuming that people are independent is pretty reasonable everyone's very happy with that it's once you start assuming that the features are independent that it becomes a little bit like oh that's actually pretty wrong every assumption is wrong on some level but users being independent is a lot
59:03
less wrong and something we're much more happy with and features being independent feels very very very wrong that makes sense it's like it's fair to think about like each person being an independent pull from the distribution think about your people in Bhutan we assume that every pull is an independent pull from the distribution and Independence of each pull is a very reasonable thing so it's a great question but hopefully I gave some clarity there okay I'm seeing nine okay
59:31
so in parameters in the universe pedagogical pause naive Bayes Ascension okay so this is the last great idea and if you incorporate this great idea you'd have naive bands so we'll just take a little bit of time to unroll what this idea means but just to be clear naive Bayes is going to use the same correct mathematics that we've been using this whole class and then it's going to make a very wrong assumption that the joint probability of your inputs given the
59:58
thing you're trying to predict is equal to the product of the probability of each input feature on its own condition on y so remember each x sub I might be a particular movie so this is the joint probability of all movies in the inputs given Y and this is thinking about each movie on its own and just multiplying for those of you guys who are a fan of Bayesian networks there is an implied Bayesian Network here the implied Bayesian Network is there is a random variable for which is whether
1:00:29
or not you like the move the target movie and we're going to say that each of the input movies are random variables and each of those random variables are caused by whether or not you'd like Target movie but they're not affecting one another that's what it would look like if you were to draw it as a Bayesian Network and particularly this Bayesian Network tells you the joint probability of somebody liking the target movie and liking the input movies it says it's
1:00:57
going to be a probability that you like the target movie times the probability that you like the input movies given the target movie which becomes a big old product Wild and this leads to a naive based classifier naive base starts exactly the same way Brute Force Base did this GX is just a fancy thing people use when they're talking about your machine learning algorithm you can ignore it for now but you can just say the prediction I make is whatever value01 makes this as
1:01:25
the largest so if y equals one makes this largest we're going to predict a one Bayes theorem allows us to flip this and because ARG Max gets rid of the normalizing constant we only have to think about the numerator and then if we employ the naive Bayes assumption this is no longer The Joint probability of all of the inputs given y it's the probability of each feature on its own given y all multiplied together and then this term is exactly the same as before and just to be clear sometimes we're
1:01:59
going to have numerical stability problems so ARG Max of an expression is the same as the ARG Max of the log of expression so a lot of times people will actually do log probabilities and if you did log probabilities it would be whichever value 0 1 makes this expression the largest exact same thing as Brute Force Base is just when you come to calculate the probability of the inputs given y we're going to use this naive Bayes assumption let's break it on down you still need to do training but
1:02:29
training become much easier you have to estimate the probability that y equals one and the probability of y equals zero and that will just be counting if you want to know probably y equals one it's just out of all your training examples how many had y equals one not that complicated if you want to estimate the probably that x i equals one given y equals zero then we can just use conditional probability counting hey take all your examples where y equals zero how many of
1:02:54
those what fraction also had x i equal one that's mle mle says you should just do this Counting map that really complicated extension you guys ready to see how map changes from mle made a big deal about it bloop this is map with a LaPlace smoothing which sounds so fancy is that the fanciest way you've ever heard of somebody say add one to the numerator and add two to the denominator anyways it just has this prior belief that we've seen at least one example of
1:03:25
y equals one and one example of y equals two therefore it just adds one to your counting in your numerator and two you know both for the Y equals one and Y equals two case to your denominator and same thing over here you add one to the numerator and choose the denominator that's the LaPlace prior so beta 2 2. we have ways now to estimate all of our parameters and I'd like to take a moment to just show you how you could use this so let's imagine a case where X1 denotes like
1:03:55
Star Wars and X2 denotes likes Harry Potter and now we're going to try and predict the variable likes Lord of the Rings yes this is the nerdiest of movie examples what are you going to have to estimate first of all you have to estimate that probably y equals zero and Y equals one if this is the number of people who had y equals zero and this is the probably number of people who had y equals one then to estimate these using mle is just going to be counting it'll be what
1:04:19
fraction had y equals one and what fraction at y equals zero then we need to calculate the probability of X1 given y and for X1 given y you know we can think about all the cases where Y is 0 and X1 is zero all the cases where Y is one and X is zero and if you do mle it'll just be counting to figure out that you know um here there's 13 people with y equals zero and out of those 10 out of 13 had X1 equals one there's 13 people with y equals zero of which you know 23 percent had X1 equals zero
1:04:57
for both of your movies you'll create a table that's a four by four and this is going to be true if you had 10 movies you just have 10 tables that are four by four it's going to scale very nicely with number of movies cough cough night based assumption we know you're doing something wrong but I get that you're making it easier so now somebody actually walks in and they say they like Star Wars but they don't like Harry Potter and now you have to predict whether or not they like Lord
1:05:21
of the Rings again we're just going to be using the Brute Force Base idea it's just when we get to this term we're going to use a naive Bayes assumption which says we're going to think about each feature on its own multiplied together so we need probably that X1 takes on the value 1. given y x 2 takes on the value of 0 given Y and the probability of Y we'll try this both for y equals zero and Y equals one and we'll choose whichever one is bigger so it'll be the ARG Max uh we put in X1 is
1:05:52
1 x 2 equals zero we try what happens when X Y is zero and we get this expression we can look up all those terms multiply them together get a number we can think about when y equals one and then you get okay yes they liked uh movie one they didn't like movie two and now we're thinking about the case where they do like the predictor movie y equals one and then again it's three lookups you know for each of these probabilities we've got a parameter we can look them up in our tables multiply
1:06:23
them together and we get another number notice these two numbers don't add up to one because we dropped the normalization constant but it'll still be the case that whichever argument y equals one or y equals zero maximize this expression will be our prediction in this case y equals one maximize the prediction so in this case you know probably at y equals or we'll make the prediction that y equals one I mentioned this in words earlier but it's worth restating there is a
1:06:52
normalization constant there's some constant we didn't think about here and that exact same constant existed in the case for y equals zero because we know probab equals y equals one plus probably equal y equals zero equals should equal one we could solve for what the constant is and then you could figure out exactly what's probably y equals one but as I said our job isn't to do that our job is to break zero or one now that was mle what if we had to do map if we have to do map we have to choose a
1:07:22
prior and what prior better than LaPlace LaPlace is for every probability P I'm estimating I mean imagine one example of one and one example of a zero so if I'm you know predicting a pi I'm going to imagine one example of success and one example failure which is going to mean you know calculate how many times I happen divided by how many samples I had so it's very very similar it's just you know when you get here instead of thinking about 13 and 17 we're going to
1:07:52
add an imaginary trial for y equals zero imagining trial for y equals one and carry that on for the X's long story short that's naive Bayes training ideas is as simple as counting uh well actually this should be for uh for a binomial not a multinomial uh training is just counting okay A little bit of a fun aside uh if you ever get an email like this which is clearly spam if you look into the metadata especially at Stanford you'll see something that looks like this and it's hard to interpret but
1:08:33
at the very end you might see something that says like 8.0 Bays underscore 99 and then it'll have a tag which says the Bayesian span probability is 99 to 100 and you might wonder what is Bayes doing in my mail server and the answer to that is one of the first huge applications of naive Bayes was in spam classification and fun fact the person who did that was our very own meron sahami when he was working at Google or I think this is before he worked at Google got him a job at Google
1:09:03
and then they implemented it at Google and you know using naive Bayes they would try and predict whether or not an email was spam or not it's a one or a zero classification problem and even though spam became more and more prevalent as they got more and more data they got better and better at estimating their parameters they got very good even using naive Bayes at predicting whether or not something was spam um a source in case you're curious so if you want to predict spam emails you
1:09:33
could use this naive Bayes classifier what you need to do though is you need to take each email and particularly in your training emails you have to take that email and turn into x's in a y what are the X's going to be well what they did is they took in English a hundred thousand words in English and they would create their Vector of x to be how many times did word one occur how many times did the word to occur or sometimes just whether or not one word one was there or at all whether or not
1:10:05
word two is there whether or not word m was there so every variable X I was a one or a zero whether or not that word appeared in the spam in the email or not now just be clear m is huge so they had to make this naive Bayes assumption if you want to do the spam classification really quickly for every single email that came in this case what's y so if x is the indication of whether or not every single word in English is in the email Y is going to just be simple zero for not spam one for spam
1:10:39
this is going to be trained you're going to learn your parameters on historical data and so what they did is they took a whole ton of old emails manually decide if they're a Spam or not and then we use those historical data to train all of their parameters and you could have done this too so if we flash back 20 years you guys could have changed the world of spam classification just using what we learned in class today um and you know it's the exact same thing
1:11:07
fun fact they in fact used map with a plus estimation and one of the reasons that they wanted to use map with LaPlace estimation is in their trained data it was very believable that there could be some word that doesn't show up at all for spam or not spam which could lead to a probability of zero and a probability of zero becomes very problematic in naive Bayes because when you're multiplying all your probabilities of X sizes together so you know naive base has this term
1:11:37
which has the probability of over I probably of feature I given the true label if any single one of these terms ends up being zero it Just Hoses the whole thing it's like crash in the party it's like yeah something like that anyway so you don't want to have any of those terms be zero it's very problematic you lose all information if a single term is zero and so actually this LaPlace prior is very helpful LaPlace part gives you the guarantee that no probability will either be zero or one
1:12:15
okay and then classification you know a new email comes in you would say okay which words are in this email you would calculate the naive Bayes prediction and then you decide is the spam or not what a fun time and it basically comes down to this you know ARG Max over the inputs given y times the probability of Y apply the naive Bayes assumption and the naive Bayes assumption just to remind you is that this joint probability of your inputs given y remember there's a hundred
1:12:42
thousand of these can just be thought of each input on its own given y okay okay so Trinity base essay parameters just of bernoullis and it's just counting okay um now interesting question you might ask at this point we've kind of finished the plot line we want to do ml woohoo let's do classification yeah uh oh we can't just do the Brute Force Base sad times but if we make the naive Bayes assumption we've got a whole pipeline we can take a training data set estimate our parameters
1:13:19
then we've got a probabilistic model with parameters which means if we get a new example we can make a prediction but there's one step I haven't told you about how do we tell if our predictions are any good well hopefully they're good because they're based on data but maybe the Y hats and the Y's are actually different quite a lot what people do is they actually hold out some data that they call their test set so you train on some data with spammy emails and non-spammy emails and we're
1:13:50
going to hold out a special set of data where we know the answer we know if it's spam or not and we use that to quiz the machine learning model you just built so you just built a missionary model I've got a whole quiz to give your machine learning model I've got all these emails and I know if they're spam or not and I'm going to test the machine learning model I'll give the machine learning model each email one at a time and you'll predict spam or not spam and then I'll see if you're right
1:14:15
and if I take this whole quiz and I give it to machine learning model we call that testing and there's a couple of numbers that people really care about one is accuracy what was your raw score on the quiz like if there was a hundred emails in the quiz did you get 90 correct that would be an accuracy of 90. if there was 10 000 you got you know 9 000 correct that would still be an accuracy of 90 percent there's two other numbers that people sometimes care about one is precision and one is recall
1:14:47
and basically recall says how well do you do at predicting when uh when we think about you actually have uh spam so when something is spam how good are you at pulling it out that's the recall so out of all the quiz items that were spam how well did you do so on that particular subset Precision means hey you told me something was spam so take all the quiz items where the the ml model actually predicted spam and how well does it do when it predicts spam and you can think about that as if it
1:15:29
says spam should you trust it and this is if it really was stem did it find it uh they're kind of clunky ideas to get your head around but people do really care about these and one way of telling you this is you know Precision gets close to a hundred percent really people got really almost perfect on this measure of the quiz and recall was pretty high what does precision mean Precision means if I say it's spam it is spam and why might you care about that because you don't want to take that very
1:16:06
important email and call it spam so Precision means that when the machine learning model says it's spam you can trust it it probably is and recall means that if this was 100 node spam would end up in your inbox and if it's less than that some span will actually make it into your inbox and at the time that they were using naive Bayes and Gmail they were getting really high recall rates not a hundred percent um now just to be clear just using words as features was pretty good but it turns
1:16:37
out if you look at a couple other things like who was the sender is the email sign properly all those things were extra features that they threw in their naive Bays there you have it so in summary you have learned naive Bayes classification and you will go build it when you go build it here's what I want you to know training is just counting you have to estimate all of these parameters but it will be just counting in your trading data set mle is peer counting but it doesn't take account uh
1:17:09
the fact that maybe you want to imagine some successes and failures to avoid probabilities of zero map just adds in a couple other cases once you've done your parameter estimation you can make your prediction by doing the ARG Max of the probability of Y times the probability of each x i given y we will often use logs to avoid numerical underflow when it comes to computers and that is the end of the story and you know what that means I'm pretty sure this is your last class
1:17:39
which means I'm pretty sure we can start Thanksgiving break two minutes early have a fantastic Thanksgiving I'm so thankful for all of you guys thanks for working so hard in cs109 have a great break and see you back when you're done
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat