Skip to main content
Loading Explore guides…
Probability & Federalist Papers · Acedra
Home
Explore
Computer Science
Probability & Federalist Papers
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
155 segments
Copy
Hide video
0:05
good afternoon cs109 how are you guys doing today what I like to hear uh uh okay we have a wonderful class we're going to do exciting things and learn important things actually debut a sense of how exciting a day it is not only are we going to be learning one of the profound ideas that takes us from basic probability Theory to being able to solve very interesting real world problems we're also going to get deep into one of the historical mysteries uh in the United States which is the
0:32
authorship of a particular set of important documents called The Federalist Papers we're going to learn a little bit of probability has an important theme to it and we're going to be able to solve this cool Problem by the end of today so a lot to look forward to but before we jump to that we're going to do a little bit of review and before we do any review I do want to just make one quick announcement the quick announcement is we have a midterm in cs109 it's not next Tuesday
0:59
it's the Tuesday after so it's a long time from now still we'll give you more details about it but I just wanted to let people know that there's a lot of classes that have midterms on exactly our day and after talking about it amongst the head ta team uh we decided that the most reasonable thing to do was to let there be two offerings of the midterm if you can make either of them you choose which one you go to you can either go to our normally scheduled midterm on the first
1:27
at 7 pm or you can go on the second you can go to the 8 PM midterm if you can't make either of these you will have to let us know so we imagine there'll be few people who can't make either time but if that is you then you should fill out this form but we have just one small detail that we need your help with if absolutely everyone comes to this midterm we would need a slightly bigger room so all we need to know is which one of these you believe you're going to go to
1:55
and we need to know that by next Wednesday if that's okay there's a little form on the Ed discussion forum please go fill that out just say which one you're going to and if for some reason you can't make it to either there's also a form there for letting us know does that sound pretty reasonable okay yay speaking about pretty reasonable some of our review oh we're in such a cool place in cs109 the cool place we're in cs109 is we have finished counting Theory we finished
2:23
core probability where we learned things like the law of total probability and conditional events then we learned about random variables and on Monday's class we learned about the last major random variable in our set of random variables and now that you've thought about random variables on their own it's time for this beautiful next section in cs109 called probabilistic models what an exciting moment now the last random variable we learned about is worth doing a little bit of
2:49
review on because it is pretty important that normal distribution shows up in so many assumptions and so many problems so many times in the real world so we learned about the normal distribution the normal distribution was the probably distribution that had this Oso canonical curve this curve is in fact the probably density function and we also learned in class that often when we solve problems we'll use this other thing called the CDF the CDF answers the question what's the probably the random
3:15
variable is less than an input number it's monotonic because as the input number grows the probability that your random variable is less than it can only go up so here's a plot of a classic CDF for a normal we learned a bunch of formulas but I want to just focus on one for now possibly the most important formula for a normal distribution if you have a normal distribution with those parameters and you want to ask the question what's the probability that by a random variable is less than some
3:42
input you use this wonderful formula you take your input you subtract the mean you divide by the standard deviation and you put that through this very important function called the Phi function Phi function is a pre-calculated function which is technically the CDF of a standard normal every computer has a pre-calculated there's lots of places where you can find it uh printed out and that's how you find the probably a normal random variable is less than a value it's so important that I wanted to
4:12
do a little bit more practice on it and I thought instead of giving you guys an easy problem I kind of want to show you guys a bit of a higher water mark for how hard a normal problem could be just using that one equation I have given you so far so to start up today we're gonna go dive deep into really challenging you on your knowledge of normals I'll write down that equation that you guys need to know so if you have a random variable that's a normal so X is a normal and it has a
4:41
mean and it has a variance then the probability that X is less than some value is equal to Phi of that value minus the mean divided by the square root of the variance aka the standard deviation okay you guys ready for it here's my problem I think it's actually quite interesting um it leads to a surprising result and the result has to do with how many computers do you need if you're running a website and you want to guarantee a certain amount of probability that you will not
5:17
be able to drop any requests so the story starts on this uh thing called singles day you guys have heard of Amazon right has anyone here heard of Alibaba Alibaba is like the Chinese equivalent and their Prime day equivalent is the thing called singles day on 11 11. that is their busiest day of the year they will buy computers to host their website and they want to buy a certain number of computers based on the busiest time of year and they want to buy enough
5:44
computers that they're pretty confident that they will not drop any requests that even if there's more requests than they expected they won't drop any does the story make sense okay let's talk about the problems of the details on that busiest minute of the busiest day we're going to assume that the number of requests you get are going to come as a gaussian gaussian might not be the true distribution but people might just make that assumption this is the Assumption we're going in with
6:11
you're going to buy case servers every server can handle 10 000 requests so it's basically you have to think about when you purchase your Hardware you can your Hardware can handle a certain fixed number of requests then you'll get a true number requests and if the true number request is more than you can handle you're gonna drop and we want to buy as many computers such that the probability that we don't drop anything is greater than 0.99999 so we want to be pretty sure and
6:43
just to start this problem altogether I probability of no drops is let's say R is the number of our computers we buy K computers sorry and that allows us to serve our requests and R is going to be very simply equal to 10 000 times okay the probability of no drop is the probability that the true number of requests that come in are less than the requests for the computers that we can handle so this is the same as the probability of no drop or yeah probably no drop that's just to start us off
7:26
as I said this is a little bit of a high water mark we want to figure out this we've got this equation I want you guys to think about it definitely take 10 take 30 seconds to think about on your own then I'm going to give you two minutes with the person next to you so just think about it okay talk about with the person next to you how could you figure out how many requests you need to be able to support such that the probability of no drop is greater than 0.9999999
7:56
how could you solve this problem really just using this one equation okay talk about what the person next to you this is going to push your knowledge and then we're going to solve it all together
8:08
okay this is a hard way to start a Wednesday but I guess I'm getting this like full speed into probability pretty fast oh man it's a little hard to get started but um you know one way of thinking about this is here I draw the CDF so this is the equation of the CDs but here I'm going to actually draw what that would look like if you were to plot it and somewhere out here you have this is the mean but as values of R increase the CDF of the random variable R will go
8:46
towards one if you say what's the problem of getting less than a billion requests well you know the probability of that will tend towards one is R gets bigger and bigger at some point the if this is on the x-axis R the CDF gives you the probability of getting less than our request so on Singles day at that busiest minute the probability that you get less than R requests as R is really small the probability you get less than two requests is basically nothing but eventually there will be a number
9:15
such that the probability you get less than R requests will be equal to 0.99999 and the way I wrote this up I actually took a moment and wrote it up as if it were uh problem set question and here's how I wrote it up I said the probability that R is less than r that is how you define the CDF and use the capital F to be CDF can you guys see that is that too small font folks in the back can you see huh yeah okay so the probability that the true requests that show up being less than
9:58
some input R that's what if CDF is a CDF answers that question and we use the capital f as our notation for the CDF and we're going to try and find the r such that this is equal to 0.9999 we want to find the CDF input that leads to this particular probability that's a little bit backwards from what we normally do we're normally calculating probabilities but now I'm trying to find what input leads to a particular probability if I put in the equation for a normalcdf
10:29
it looks like this it's the Phi of whatever the input is minus the mean divided by the standard deviation I know what the mean and I know what the standard deviation are so you know I put those two things into my equation and now this is a little bit uncomfortable normally we don't have a variable on this side of the equation normally the thing we're solving for is on this side of the equation but now we do we have that r and this is a bit of a cognitive leap if
10:58
you want to solve for that R you know what you can do you can start to invert this side and the first step is you don't necessarily want five of everything you want to do the inverse five both sides so Phi is a function that can be inverted you can ask what input into the standard normalcdf would give you 0.999999 Phi is an invertible function and there's this thing called the inverse Phi if you looked up what input to the normalcdf gives you 0.999999 the inverse
11:31
5 function would tell you 3.71902 the inverse 5 function it's a famous thing like if you go to our course reader you know you can even get a inverse Phi calculator right there uh sorry that's the Phi calculator inverse Phi calculator here so you can like put in 99999 it tells you the value that you could put into Phi that would lead to four nines is in fact 3.7 and did I lose my work okay so we can note inverse Phi is 3.7 and now you just have one equation one
12:10
unknown and if you solve for R you get that R is equal to that little expression and if you say the number of computers you need is that number divided by 10 000 the number of computers you need is 103.7 by 104 and the probability that you will drop a request is less than 0.00001 and the probability that you can handle all of them is greater than 0.99999 that's pretty tricky a bunch of you probably thought like wow that's tricky I felt a little bit comfortable about this idea of a CDF but
12:42
now you had me do this in verse five I guess I'm pushing you guys a little bit with this review concept but I just want to show you kind of like a higher Watermark of where you could go sounding good questions clarifications yes just as I'm alive and we're fighting with r here is the number of servers you want at Mass uh
13:08
yeah so R is how many requests we need to be able to handle and every machine can handle 10 000 requests on the maximum that distribution yeah so here we know if we want to not drop requests we need to have enough computers to handle this number of requests that's a really fancy number I think if you did 10 to the 6 Plus 3.7 times 10 to the fourth it's just like a million um and 37 000. so we need enough machines to handle one million thirty seven thousand requests
13:42
and then every machine can handle 10 000 requests we just divide that by ten thousand okay yeah
13:54
yes yeah so you know I said we want to be able to have a higher probability than 0.999 what if I said do you have to buy enough computers that you have a lower probability than 0.999 you'd be like I'm gonna buy zero computers and then you have a way lower probability than 0.99 you've got a zero probability um but the equals is an interesting one so if this question has said I kind of treated this question like it was an equals like there was a lesson sign and
14:21
then really quickly I just switched to what number is going to make this equal to um and I solved for that and then once I figured out this is how many requests I need to be able to handle I'd need computers to handle more than this this or more requests um I say exactly equal isn't so necessary here you just need to be able to handle this number or more
14:53
it's technically treated the same as probability of Big R less or equal oh my God that's such a good question so the probability that Big R is less than r that is the same as the probability that Big R is less than or equal to R that is because R is continuous and continuous random variables we think of the probability of R being precisely r as being zero though I guess number of requests even though we use the gaussian will probably be discrete but anyways
15:21
because for continuous random variables this is true for discrete random variables this is not true yeah gaussian continuous okay you guys rock thanks for playing along on that very hard review problem uh while it was probably a challenge you'll appreciate it and like either on the first or the second depending on which midterm you decide to go to okay so that's the end of practice I do have a little bit more review the normal distribution also had this other beautiful equation this
15:47
beautiful equation is not the CDF it doesn't give you the probability that your random variable is less than number it's the probability density so it's the derivative of the PDF or sorry the CDF and we find that to be very useful in cases that will show up later in this week um okay I do want to skip that here's a funny thing you're going to need to know if you're in a normal probability class I probably wouldn't teach you this but you're in probability computer scientist class and I think
16:12
because of that this is something that I would like to let you know about you've seen logs before if I have log of x that's a particular function that takes a number and returns me back another number and log of x equals y is an equivalent way of saying e to the power of Y equals X so it's kind of the inverse of the natural exponent you guys have seen this before the reason I need to bring it up though it's for two reasons One log has some beautiful identities if you've ever
16:41
worked with logs it turns out if you have the log of anything multiplied or divided or to the power then you get these very nice simplifications so logs are nice to work with but there's this really really important property that if you have the log of a product it's the sum of the logs so if you have the log of the product of many many many things it's going to be the sum of the logs of many many things and spoiler this is critical if you want to be a computer scientist using
17:11
probability and the reason is it turns out computers have problems representing very small numbers if you start multiplying if these are probabilities and you start multiplying them together you get under flow issues where your computer can't represent a number so small like there is an actual number there but your computer just can't represent it in its standard representation but computers do much better when you're adding logs of probabilities you end up in spaces where computers can actually
17:41
represent those numbers and so even though log probabilities wouldn't normally show up in an intro probability class they should show up an intro probability for computer scientist class because computers will be much better at representing logs of probabilities than probabilities on their own anyways this is like a little bit of just reminders will bring this up later again when we need it oh and then you guys we're going to have some more good times with some counting
18:05
States you guys remember we were doing counting some people were like no but I'll learn it again before November 1st or Wednesday November 2nd uh anyways we did counting and we did things like hey if you have indistinct objects there is n factorial ways of ordering them that will come up again today particularly this one counting problem is going to come up again today one of the things you could ask in counting is if you have n distinct objects and you're putting them to our buckets
18:31
and particularly you want N1 to go into bucket one and two to go into bucket two and are going to pocket R we talked about in class how this is the same as number of permutations of the letters of say Mississippi where you have like n1s M's and N1 twos and nrs's whatever and this is the number of letters in Mississippi and you can sometimes write you the notation I just want to remind you guys of that result before we jump into today's class anyways we'll bring this all up again when we need it
18:59
okay end of review so thank you guys for following along for my review session the next thing in cs109 that we want to learn is this beautiful topic called probabilistic models when you go beyond single random variables and you start thinking about random variables being random together it's such a beautiful topic it will allow you to solve big problems with larger data sets but even though this is where we're going to go we're going to be starting as simply as possible so
19:29
that you guys can build some fundamentals because when we go from one random variable to multiple random variables thinking about them at the same time we're going to want to do so very intentionally so we're going to start in the discrete world and I want some motivation though the world is filled with interesting probability problems there's so many of them and almost all of them involve more than one random variable some interesting problems just require one
19:54
random variable like maybe if you're thinking about that ride sharing problem that was just one random variable but many things require many random variables and one motivating example I'll give you is WebMD health this is an interesting website you go to this website and you put in all your symptoms and after you put in all your symptoms it tells you the probability that you have different diseases so you could say like I have dizziness and I have a one-sided headache and I'm a 30
20:19
year old male and it's like you probably have a migraine but you could be having a stroke and obviously this is a big probability engine and it's got a lot of random variables in fact it's going to have random variables for every possible symptom it's going to have random variables for every disease and it's going to be thinking about all these simultaneously and in order to do that it had to go from one random variable to many at the same time which is where
20:41
we're going in cs109 we're not going to start with WebMD that would be really cool if we could make it instead let's start with something a little bit more straightforward to think about our good friend dice single random variables is like we're thinking about a dice problem and you're just going to maybe roll the dice let X be the outcome and you can ask the probability of a particular assignment to the outcome if your dice has different outcomes you can ask what's the probably the x equals
21:11
one you can say what's probably x equals two probably x equals three and we would generalize it to this thing called the probability Mass function and ideally somebody would come up with an equation a function a graph that could summarize any query you could have about your single random variable into one function that sounds good do you guys want to see what it looks like when you have two random variables well if you had two random variables when we think about outcomes and events
21:38
the most common one and the one that's most General if you could answer this question you would know everything about your two random variables is the likelihood of assignments to one random variable at the same time as an assignment to the other random variable so what we call the joint assignment so x equals 1 and y equals six is the joint assignment to X and Y for this is the full probabilistic claim but you can remove the and and just put a comma and most people use that sort of notation
22:09
but if you could say if I roll two dice what's the probability that the first dice is the one and the second dice is a six you know it's just going to be 1 over 36. but more generally if you had two random variables the metaphorical equivalent of the probability Mass function that complete information function is what we call The Joint probability Mass function and the joint probably Mass function is now going to take in two inputs some assignment to the first random
22:37
variable some assignment to the second random variable and it should give you back a probability and if somebody gives you this thing called a joint they've told you everything you would ever need to know about your random variables so maybe that's the first major key when we get into probabilistic models which means you have more random variables than one the most useful information someone could ever give you is this thing called a joint now the joint distribution for two dice
23:05
isn't that exciting because no matter what assignment you have for x and what excitement you have for B it's 1 over 36. well I guess assuming a is in the range one to six and B is in the range one to six so if you were to draw this one way you could do it is you could make a three-dimensional graph but a lot of times we'll put these into tables so if we want to visualize this most important thing this joint distribution we might just draw out the table and that table has all the values assigned
23:37
to one random variable and all the values assigned to another random variable and then every entry here is the joint probability that the first random variable takes on this value and the second random variable takes on this value it's hilarious for dice because it's just filled with 1 over 36. you certainly didn't need to do this but obviously we're going to be thinking about random variables that would have more interesting entries questions concerns okay shall we take this up into level
24:05
I want to just have us think a little bit about this table and what properties it might have first of all you need to know what every single entry in this table means so if I gave you an entry over here hey typo I think it used to point one down this would be that the x is equal to 4 and Y is equal to 3 because it's in the y equals three row I put these typos in just to make sure everyone's paying attention but that's the most important thing to know first what does one cell mean okay
24:39
now that's kind of a boring random variable one of the reasons or boring joint probability table and one of the reasons is boring is because every entry is the same so I thought I would make it a little bit more exciting um this is real data that somebody collected a while ago in cs109 not me but now we have it a slightly more interesting combination of two different random variables run random variable was what year somebody was in cs109 so freshman sophomore junior senior and all
25:09
grad students we unfortunately get lumped together like nobody even cares about the nuances of our personalities and then we have the other random variable of their single in a relationship or is complicated and at least this is going to be like slightly more exciting than dice to think about this is a joint table so again you should be able to think about what one sells here means like if I say 0.1 here is that telling me that there's a 10 chance that somebody's a junior
25:35
no it's telling me that there's a 10 chance that somebody's both a junior and also in a relationship and this is the complete information that you'd want to know if you want to think about a model that involved these two random variables this thing called The Joint okay and that's your major key major joint distributions complete information you can actually answer any probabilistic question you want to about the combination of these two random variables somebody gives you a joint
26:01
conditional question you can answer it you want to just think about one random variable at a time you can answer it if somebody gives you a joint you have all the information you need to answer any question what a wonderful thing the joint is a couple small notes for intuition my claim is that let's say x is dating status and Y is here if you Loop over all values of dating status and you Loop over all values of years and for every single um iteration of that double for Loop you
26:30
look up the probability of a current year and a current relationship status if you add up all those numbers my claim is that it must sum to one if it's a proper joint distribution one way to think about that is any of these cells is mutually exclusive is not possibly both a senior and a five plus you can't beat both of those at the same time even if you're co-terming you're in one of these and so each of these categories is mutually exclusive so you should be able to think about if
26:58
you want to think about either this or that it should be just some and if you think about this or this or this or this or this or this or this or this it should be that sum and because they're all mutually exclusive and they cover all possible outcomes my claim is that if you summed up this whole table it should summed one yes question always representative that's such such a good question so this joints uh probably Mass function if you have two variables do you always
27:29
represent as a table that's pretty common but not always and there's lots of other representations which we'll get into table is just going to be the first one that we can visualize the easiest yes
27:43
themselves don't add up to one what that's such a good question why don't the rows add up to one if you add up this entire row it actually gives you something very interesting and very semantic I'm not sure if it's apparent to somebody but what happens if you add senior and single or single senior end relationship or senior and complicated because they're mutually exclusive this adding up is getting the ore so this or this or this what's that describing again yeah you describing the probably a
28:16
senior and is there one probability that somebody's a senior no yeah not everyone's a senior so that's why it doesn't add up to one but you're a little ahead of me because that's one of the things I did want to talk about in a second okay you know this never comes up but I just want to point out if somebody gave you a whole table but they hid one number I don't know why they would do that you're like why are you so cruel to me but they're like I'm just testing
28:38
your knowledge of this one fact you know of course this would be whichever number leads to the sum of one okay that's not that important now okay though this question is interesting is so related to the question you just had I claim that you can answer any probability questions so I'm going to just start showing you that the first one is can you figure out the probability that someone is in a relationship in cs19 so that's just a question I don't care about what you're there I
29:08
just care about whether or not they're in the relationship could you figure out that question uh from this table think about why don't you talk about a person next to you see if you come up with a question I'm just going to give you guys about 30 seconds to talk about it
29:28
okay because we had such a wonderful question a second ago and you guys thought this through hopefully this isn't so bad first of all semantically if you want to know somebody's a relationship you don't care if they're refreshment it's like this or this or this or this or this and because each cell is mutually exclusive you're just going to be adding up these five cells so it's this plus this plus this plus this plus this if you want to be really fancy uh you would write it like this you'd say
29:59
I'm going to sum and this is saying over every year I'm going to add up the probability where X is equal to in a relationship and Y takes on each of those values in the iterator of your Loop if you add it up this is a fancy way of saying just like add up these five values and if you added up these five values you a good number which is the probably that somebody's in a relationship and we can eyeball it's like uh 20 uh almost 30. wait let's say this is 30 38 yeah I
30:28
said 45. so there's like a 45 chance that somebody is in a relationship you can do this for lots of things you can say probably somebody's single you can say probably somebody's a freshman if you want to know somebody's a probably is a freshman you just kind of sum out the other way if you want to know somebody that probably is a freshman you some this direction uh and that would give you the probably a freshman if you want to know somebody's sophomore same thing
30:50
there's a fancy name for this this thing is called the marginal and marginalization is like somebody's giving you a probabilistic model which has many random variables and you want to extract just one random variable out of it well you marginalize out the other do you guys have a guess for why they call this the marginal not that you should know but it's just maybe somebody's like I have a cute idea anyone feeling cute yeah yeah
31:25
they used to like do this stuff by hand back in the day before computers and they would actually just write it in the margins so you'd be like point zero two plus point zero eight that's point one plus 0.13 that's 0.23 and they would just write it in the margin over here uh and so that's where it gets the name marginal and you'd write each of your answers in this margin uh and in this margin anyways fun fact not that important won't be on your midterm which could be on Tuesday or Wednesday
31:48
depending on your choice okay anyways welcome to Marginal um you know we can get really formal about it and I used to teach people by just showing people this equation be like it's the marginal but I think by now you've seen it on this real world example I think it's a little bit intuitive you know if you have a joint table and somebody wants you to just get one random variable on its own you just Loop overall assignments to the other random variable and you say okay you
32:12
want probably that X is equal to a let's Loop over all the values of Y and you get x equals a and Y equals each of those values in the iterator um kind of complicated equation for pretty straightforward idea that you guys already find intuitive um and anyways that's what the marginal is formally I did want to make a connection to something we learned earlier earlier in class we learned about the law of total probability and there was this general form of the law of Torah
32:40
probability that some people found scary and the general law of the general form of the law of total probability says you know if you have if you want to look up the probability of some event but there's some background event where that background event has different values and each of those values are mutually exclusive and they span the entire space then you can extract just this probability by thinking about the sum of you know your event and this background
33:06
event your event and this background event your event in this background event your event in this background event it's the law of total probability that has a theoretical justification for why marginalization exists in fact they're the same thing just expressed in two different ways so if you found law of total probability confusing but you found marginalization easy you can use that as intuition and the other way around if you find law of total probability easy that explains to you
33:30
why marginalization works so just a connection that you might want to go deeper into when studying we've already talked about it why it's called the marginal so these joint probability tables somebody asked is this the only way of representing probabilistic models and the answer is no it is a very common way because it's very complete and very easy to interpret but there's this key problem they can get so big let's give you an example in our previous models we had two random
33:59
variables but we're getting into the world where we want to think about lots of stuff like that WebMD had way more than two random variables so what if we bumped it up to three random variables so here I'm going to have a joint distribution between three random variables disease and disease has two values either zero you don't have disease or one you do s is for smell and smell can take on two values you either don't have smell or you do have smell and F is going to be
34:24
your fever status which is you can have no fever low fever high so we have a joint distribution over a disease and two possible symptoms the complete information if somebody was going to give you all the information you need to answer any probability question is the joint and in this case that means they have to give you one number for every assignment to each of the random variables so D equals 0 and S equals zero and f equals num there's one number D equals one and S equals zero
34:52
and f equals num there's one number so you need one number for every possible combination now this isn't too bad you've got one two three four five six you have 12 different numbers a computer can easily represent 12 somebody who's a scientist may be able to give you those 12 numbers this all seems pretty reasonable but where does 12 come from 12 comes from well there's three assignments to F times two assignments to S times two assignments to D so three times two times two gives you 12. so
35:23
even though 12 is not scary that multiplication is fun fact if you want to marginalize and just figure out what's the probability that somebody has a disease you could do a loop but this time not just over one variable but over all assignments to those two variables that are not disease so you Loop over all values of fever Loop over all values of whether or not people can sell and say what's the problem they have the disease and each of my values that I'm currently looping
35:50
over if you add those all up you get the marginal it works for more than two random variables okay so great though we've got this we can start to do some baby little WebMD how cute but we're like no our WebMD is going to have 10 random variables or have like four different diseases and six different symptoms is going to be fantastic and maybe each of those random variables can all take on five values so how many unique assignments are there to the end of every single random variable
36:21
simultaneously how many cells would there be in a joint probability table and a joint probability table should give you one probability for every assignment every assignment combination to all your random variables so what do we have oh a nice little counting problem yay okay I'll give you guys a second to think about it if you had one random variable with five values you'd need five probabilities if you had two random variables and each could take on five values you would have
36:53
a grid that's five by five that's five squared three random variables you know multiply that puppy by five because you need a grid for every assignment to the third random variable four random variables uh oh what happens if you have 10 random variables tiers all tiers just short circuiting your keyboard on your laptop from all the tiers that have come down because five to the tenth is an unreasonably large number now maybe five to the tenth can be stored in a computer but imagine the
37:30
poor scientist who has to think about the probability for every single five to the tenth assignment that's a bit of a problem and this motivates why we need models like this five to the 10th combination might be the perfect way to represent uh any assignment to all your random variables but we're going to have to make some simplifying assumptions both so that we can estimate probabilities more effectively and also so that we can represent them into computers because
37:56
even though five to the 10th could go into computers you know what if you had a hundred random variables that's pretty reasonable and five to the hundred becomes a real problem so joint tables they're your be-all Endo they tell you everything you need to know but they have this numerical issue in that if you have lots of random variables they're exponentially large okay welcome to the world of probabilistic models so sometimes the structure of a variable suggests a more efficient representation
38:24
than using a joint probability table and we're about to start exploring those because if we want to do cool problems we need to learn more efficient representations of the joint at the end of the day we still want to represent the joint we still want to have that be all end-all we just want more efficient ways than using this table does that sound good okay I'm going to start with a problem where there's a lot of structure and there's so much structure we could represent a
38:51
joint using something way more efficient than table okay here's my thing for you I'm going to not flip 100 coins but I'm not now going to roll 100 Dice and you're like well we never did that and the binomial would flip 100 coins but we never rolled 100 dice one of the reasons is because when you roll 100 dice some weirdness happens you don't just have number of heads as a random variable you instead could have six random variables as your outcome number of ones number of twos number of
39:22
Threes number four is number five is number sixes do you guys see how if I roll 100 dice that there's actually six random variables that come out of it if I flip 100 coins and I say how many tell tale or heads just one random variable but dice have six outcomes not two so there are six random variables someone who's really clever might be like wait a second if you tell me the assignment to five random variables I can know the sixth one uh so maybe there's a way of
39:49
getting rid of one random variable we're not going to go there right now but I want you guys to just appreciate that if you roll 100 dice you're now in the world of a probabilistic model you don't just have one random variable as an outcome you have six just checking if we want to use a probabilistic joint table how big would that be so you have six random variables and what are the values that this one can take on this one says how many fives did you roll in 100 dice can you get a zero
40:19
yeah maybe not that likely but you could get a zero totally valid assignment could you get a hundred yeah like one in a billion billion billion times you roll 100 Dice and they're just all fives and you're like what so the possible assignments to this random variable there's a hundred there's possible assignments this random variable 100 if you were to write this all into a table instead of having five to the power of ten what you have here if there is just one random variable
40:47
with 100 assignments your table would have 100 entries if there was just two you would have a hundred squared but since there's six if you tried to do this the naive way and you just said I'm gonna make a whole big joint table that joint table would be just a bit too large so you guys buy with me that this should be something we should be able to reason about for a joint probabilistic model The Joint probability massive Mass functions what we really want to know but this is too big okay
41:19
we are now going to learn our first probabilistic model that is more efficient than a joint table but first there's a question
41:34
right they should I always
41:45
that's right so it's so what you're saying it's absolutely okay to have like probably um you know during distributions that I speak sometimes yeah and these are split by one random variable like if you say these are all the ones where D equals one if you add these up you actually get the probability that D equals one and if you add these up you'll get the probability that D equals zero and the reason I had to split it was because with three random variables it should actually be a
42:15
three-dimensional table and I can't draw a three-dimensional table on a two-dimensional screen so that's why I split it yeah yeah very very good question uh I bet a lot of people were thinking about that and if I get to four random variables oh my God is that a problem I have to get into this like weird uh splitting up of my tables um but yes if we were super Advanced this would be like a cube of some sort with the 12 entries okay so we're going to learn for the dice a
42:42
more efficient representation and I promise you this will go way more interesting than dice just like a binomial distribution became much more interesting than just coin flips this is going to tell us who wrote The Federalist Papers and on that Cliffhanger why don't you guys take your pedagogical pause come back in two minutes and we'll continue this conversation about normal random variables
43:02
okay let's gently come back because a couple people went to the bathroom just before we jump into things can I ask you guys a question did any questions come up during the pedagogical pause do you guys think for two minutes you're like wait I really want to know something
43:24
yes
43:28
oh my god um so let's say there's like three options in one variable three options in a second variable oh god um I'm gonna draw my Cube this way oh now you find out how bad I am at drawing cubes this is very embarrassing uh uh what is this supposed to look like it should also go like three units out this way where you can choose your like X your Y and maybe your Z though realistically because I'm so bad at drawing cubes uh instead of doing this I would say this is the equal zero
44:07
and then draw Z equals one and I draw my three choices for X and Y and Z and I draw Z equals two and then you can imagine these three grids would be stacked on top of each other to make a cube so this is like Cube level zero Cube level one Cube level two uh for anybody who's played three-dimensional tic-tac-toe now it's finally coming into utility okay good question any other questions okay so today we're going to think about a beautiful probabilistic model called a
44:41
thing called a multinomial and it's like the big sister of the binomial the binomial asks if I run an independent coin flip experiments what's the problem of getting K successes but implicitly it always assumes that means you get n minus K failures and so coin flip is interesting it's got two outcomes a head or a tail so like if that's a binary outcome and this is the probability of getting a certain number of successes you're probably getting a certain number of
45:10
failures would just be one minus this it gets its name from this binomial coefficient and we thought about this probability very deeply when we were driving it we're now going to be learning about the big sister version of this called the multinomial and the multinomial doesn't think about coin flips that have two outcomes it thinks about things like rolling dice which could have six outcomes but you guys remember what we did the coin flips we didn't always set P to be
45:35
one half the metaphor was much more interesting when we let P be a parameter of the binomial then we could answer more interesting questions the multinomial is going to use the many dice rolls as its metaphor but just like in the binomial I'm going to allow there to be different probabilities of all of the different outcomes so the multinomial the big sister the binomial it instead of thinking about coin flips with two outcomes it thinks about things like dice rolls with M outcomes
46:05
if you gave me a binomial you would tell me the probability of a heads if you have M outcomes then dice roll at six you have to tell me the probability of each outcome well in this case it's easy it's probably of a 1 is 1 6. the probability of two so probably of outcome two would be 1 6. probably outcome three is one six they're all one six for a dice roll but to make this an interesting metaphor we're going to allow for the creator of our multinomial to tell us the probability of every
46:30
outcome on a single dice roll it must be the case that if you add up all the outcome probabilities it sums to one when I roll a dice I'm gonna get something so if you take the probability of one plus the probability of two plus the probability of three plus a probably four five six if you add those all together of course that comes to one so in particular it describes a joint probably Mass function where you have a random variable for outcome one a random variable for the number of outcomes of
46:56
outcome two and a random variable for the number of outcomes of outcome m m is six for a dice C is going to say that you know we saw this many of this outcome this many of this outcome and this many of that outcome if you sum of all the CIS it must be equal to n what was n again is our number of dice rules in a binomial it used to be our number of coin flips now it's our number of dice rolls so if you sum up all the CIS so you had like two ones two twos if you add up all the numbers of different
47:28
outcomes it should come out to how many dice you rolled and of course as we said before if you sum up the probability for one dice of each of the outcomes it should come to one ins if you had this particular probabilistic model you would not need to have a joint table with a hundred to the power of six outcomes instead you can represent all of that joint probability in a single equation you just need this one equation you don't need that mass of um you don't need that massive table and
48:00
this single equation looks a lot like a binomial probability Mass function it says what's the chance of outcome one and how many times did you see that what's the chance of outcome two and how many times did you see the outcome two what's the chance of outcome M and how many times did you see outcome n multiply those all together is not sufficient because you have to think about how many ways you could order all of these outcomes these n outcomes C of one of which are of outcome type 1 C2 of
48:29
which are welcome type 2 and CM of which are outcome Type M
48:36
let's try a concrete example so I have here seven dice so I'm going to roll my seven dice you guys ready rolling seven dice oh my God that's exactly the same as what's on the slides I can't believe it if I count I got exactly one one exactly one two zero threes two fours zero fives and look one two three sixes don't check please thank you the multinomial doesn't seem that helpful at the moment but just be precise what it's answering it's saying what's the chance of this exact set of
49:12
outcomes and you're like how is that different from the chance of getting like one of each and maybe two sixes it turns out you get different probabilities for different assignments at different numbers of outcomes wouldn't you know and the multinomial tells you okay there's six random variables being random together it's a joint and the probability that this random variable equals one while this random variable equals two while this random variable equals zero
49:40
while this random variable equals two well this random variable equals zero and while this random variable equals three we can think about that jointly using just a single equation the single equation says okay what's the probability of a one I saw that once what's it probably two I saw that once was probably three I saw that zero times was it probably a four I saw that twice was probably five I saw Zero times what's probably six I saw that three times now dice aren't interesting in that the
50:04
probabilities are the same here so you know that was going to be 1 6 to the power of seven no matter what you had uh because I rolled seven dice but this term will be different which says how many different orderings can you have of one one one two zero threes two fours zero fives and three sixes so it will change you know dice do have different outcomes depending on different assignments you put here okay pause here questions is it making sense if you roll and dice you now have
50:32
a way to talk about the probability of out of the number of outcomes of each outcome type dice are harder to talk about because there's six different outcomes not just two like a coin yes about what the first term is representing that seven choose six this one over here yes so this if you were to write it out B is the same as writing this is a multinomial term and it's shorthand for seven divided by one factorial divided by one factorial divided by zero factorial that's just one
51:04
two factorial zero factorial and three factorial so that term is the same as this and this is the same way of saying you know if you had you know how could you order um two A's two B's one two three four C D E one two three four five six seven and saying you know how many ways could you order these letters and you can think of that A's represent your outcomes of type one B's represent your outcomes of type two zacom type three four and five so the number of orderings
51:36
of those letters is an important part of calculating this probability just like the orderings in a binomial random variable you know you take the number of coin flips and you do n choose K which is the same as n factorial divided by K factorial times n minus K factorial so in the binomial you have this term in the multinomial you have this term and they are it's the generalization of that binomial term and the derivation for why you need it is the same as the reason for why you
52:06
need that choose term for the binomial good good question yes the probability of getting this exact world with guys yeah isn't that weird look at the probably an exact roll of dice where I'm talking about how many ones how many twos how many threes how many fours how many fives and how many sixes and implicit in your question is such an important question why would you do this and it's not that important for dice I don't think there's that many games where like this is a really critical idea
52:37
but it will be critical for figuring out who wrote The Federalist Papers so we will take this as a metaphor like the coin flips was a metaphor like how many times in life are you like I'm gonna flip a coin n times and I need to know the probability of getting five heads like never but how many times does the binomial showed up as a metaphor a ton of times so the exact same thing is going on here okay let's bump this up a notch you guys are ready um just to focus in on one thing
53:05
these are all random variables and this six random variable says the number of times that six appeared outcome six appeared was three and so that's what that assignment to that random variable means um okay and an important thing here is in this equation this over here would be the probability of getting a six in dice it's one over six for all outcomes but the multinomial allows for the generator of the multinomial to say what's the probability of each outcome in which
53:32
case you would put the probability of getting a six here if it was something other than one over six okay and you saw the six three times okay great great we've done this sorry we did the pedagogical pause already I'd like to bump this up a notch and actually make it useful so we're gonna give you guys an introduction to natural language processing but first there's a question example in the case do all the probabilities even if they're even sum up to one absolutely like if you say
54:06
here's the probability of alphab one here's the problem outcome two three four five six and you're telling me there's only six outcomes from a dice roll if I add up those probabilities it must be one because they must be mutually exclusive and they must span all outcomes that are possible from one dice roll
54:25
yeah it's it's this it's the multinomial uh which is just writing seven factor out of one one two this is called the multinomial yeah yeah so it's funny it's the whole thing's called the multinomial distribution that's the multinomial function yeah I can see the pattern of why the things on the bottom are why what they are but I can't immediately see like the proof behind it like why am I just putting those numbers there and why does that work yeah good question
54:53
um you know when you did coin flips and we did that very full derivation it's like we're gonna have this many outcomes that have one one one zeros um zero threes two fours and so it's like each of we have this many rows where you have the particular outcome quantities that we saw any one of those rows has this probability because this is the probability of that seeing that one one it's probably seen that one too they might have been in different orders but multiplication has this property
55:22
that they're all going to come to the same number and this is how many rows there are so if you go back to the coin flipping it'll be the exact same derivation good question yes you said that the binomial coefficient was like a special case of the multimodule but I don't really understand like the ad minus tape factorial part and how that comes from them okay um how many out if you think about the binomial we've been super cheeky when you flip end coins there's two random
55:49
variables how many heads and how many tails and if you have n heads how many Tails do you have sorry so if you can't have if you have K heads how many Tails do you have and minus K so it's kind of like there's two outcomes there's n experiments two outcomes types summer heads and summer tails good question yes so we're allowed to do for example some characters together four or five and six
56:17
yeah you could have one cat's Hall outcome which says it's like a bunch of these outcomes I'm going to put together that would be allowed as long as you can tell me the probability of that capsule okay you guys want to take this to the next level and do some natural language processing okay so probabilistic text analysis starts with a simple idea of just talking about words that people could write on English and for the longest time this was theoretical but then the internet was
56:48
invented and we scanned all the books and we looked at all the websites and we could actually figure out probabilities of words so you could take the entire internet and you could think about what's the chance that if you chose a random word on the internet it would be the word the and we won't get into that exact number because even though it's large it's pretty small there's lots of words I'll tell you that it's larger than the chance of getting the word Pokemon does
57:09
that you guys buy that another fun fact that you can tell your friends the probability is somebody writing the word Stanford on the Internet is greater than probably somebody writing the word Cal so you can talk about the probability of any particular word occurring on the internet if you take a paragraph of text or a document more generally it will have many words in it strip out all the punctuation and you can count how many times each word appears you can say how
57:37
many times did caliper how many times a Pokemon appear how many times did the appear you can think of those counts and if you think about the distribution of those counts we can model it using the multinomial and to give you a concrete vision in our multinomial we're rolling dice n times we're still going to be doing that but now our dice is this massive Dice and on this massive dice there's an outcome for every word in the English language and not every outcome is going to be
58:10
equally likely so you have this big dice with everywhere it's got Pokemon somewhere it's got Stanford Summer's got Cal somewhere and when you're writing your documents like you roll your dice and it says the you roll your dice again it says best you roll your dice against a class all you guys are going to get is roll your dice again cs109 and the claim is I'm just kidding the claim is if your document has n words if you looked at the counts of each words then we could use a multinomial to model
58:36
it it's just like the dice problem but hopefully more interesting the one big difference is instead of having six outcomes we have outcomes for every word and the probability of each outcome is not going to be one over six or even one over M it will be defined by How likely that word is to show up in an English document okay if people are curious there are just a bit under a million unique words in English it depends on the internet defining word is a hard thing but the
59:04
dictionary says there's about a little bit under a million real words LOL okay so let's give you an example document and this is a real case that people first use the multinomial for spam detection we'll talk a little bit before that here's a document pay for Viagra with a credit card Viagra is great so are credit cards risk-free Viagra click for free this has 18 words in it and so if you want to think about this as a multinomial you might say Okay Viagra showed up twice free shut up
59:35
twice wrist shows up One credit card so twice and four showed up twice now you could think about this as a multinomial and it turns out if you think about the probabilities you could think about if somebody was writing a spam email what's the probability that they would write each of these words and you get a slightly different dice shape than if you take a normal English language and you can say what's the probability of seeing this particular multinomial outcome in the
59:58
world where the writer is a spam author in that case you know we can just use the multinomial formula there are 18 factorial or 18 words so there's 18 factorial up here and then you do the counts for each words that gives you your coefficient then you would say okay what's the chance that a Spam writer writes Viagra square that because Viagra shows up twice what's the chance of spam writer writes free square that because free shows up twice and now we give you the
1:00:25
probability that someone would write this if they were using the spam dice and you could say also what's the problem would write this if they were just using the English language Dice and hopefully we get two numbers and fun fact this was the original spam classification was based off of this um okay so in the world where you thought about this particular author's dice this probability of seeing the document was a multinomial of counts of outcomes how many times you see this outcome outcome
1:00:52
outcome outcome outcome and we can use the multinomial joint probability to get our chance of seeing this exact document okay now we're not going to be doing classification today we're going to be doing something slightly different we're going to be trying to answer this deep historical question who wrote The Federalist Papers many of you guys might know what the Federalist part sorry but if you didn't when the US was just a baby country they're trying to ratify the
1:01:20
Constitution and there was a series of papers that were written to convince the public to ratify this comp this Constitution say like we should have a constitution and they were all written under the same pseudonym Publius they weren't just one author it was several authors writing these foundational papers that we now think of as a critical part in the history of this country but then later on we found out who was Publius and does anyone know who Publius was James Madison Alexander Hamilton
1:01:51
and uh this third guy look at the three people wrote all these papers and this sounds pretty straightforward and later on on their deathbeds they're like yeah it was totally me and I wrote papers one and seven there's a whole bunch of them I wrote 136 100 and generally that was a fine way to figure out who wrote them except on their Death Beds some of them claimed to have written the same one ooh drama so there's 85 essays as we mentioned they're all written on the same Publius
1:02:25
but the real authors were these three people and we want to know who wrote each essay and we're going to use probabilistic analysis of the words and the essays to figure out which of the authors actually wrote it and I'm going to focus on a particular one paper 53. Alexander Hamilton and Madison both claim to have written paper 53. here is Federalist Paper 53 please don't read it but there it is trust me that is in fact Fearless paper 53 and over here I have all the text from all the
1:02:57
Federalist Papers that I know Madison wrote and here I have all the texts from The Federalist Papers that I know Hamilton wrote and my question for you is can you tell me who wrote unknown.txt interesting okay where do we start this is your data you're going to write a program that's going to answer this question I've got the data for us and you have to figure out an approach for this you have a whole collection of words there's lots of ways of thinking about
1:03:35
probabilistic models of words but the one that we focused on in cs109 in this class is counts of words within a document you know how many times does a particular word show up in a document these documents would allow you to estimate the probability of these people writing any particular word and once you have an idea of like what's the chance that Hamilton would actually write divisions versus Madison's probably writing divisions then when you get over here you can think about how
1:04:03
many times a division show up here and who which author do I think is more likely based off of their probabilities of writing those words we're not just going to focus on the one word divisions instead we want to think about all the words that show up in known.txt so you have all these words you want to know the probability of authorship and using the documents that I gave you of Hamilton Madison you can know the probability of any word given the author this is a fun problem to think about so
1:04:34
I will give you guys just a moment to to stare at this and think about what you would do don't talk about with a partner for a second and then you do talk about it for two minutes so just think for yourself
1:04:50
okay talk about it with a friend if you want to how would you approach this problem okay
1:05:03
oh how fun
1:05:10
well hello again says pays and why does Bayes show up here you can think using a multinomial about the probability of seeing a document given a particular author but what we would really like to solve in this problem is the conditional the other way around we want to know the probability of an author given a particular document and Bayes theorem which we learn in our core probability is also going to apply where you get into the world of random variables and probabilistic models
1:05:41
particularly what we would really like to know is how likely it is that Hamilton uh that the probability of Hamilton writing this document given all the words I'm gonna use D for all the words it's my shorthand form we don't know this direction but the multinomial gives us this direction it says if I know Hamilton's the author I can talk about How likely is this collection of words using the multinomial I have to have a prior belief of Hamilton I have to have a this weird
1:06:12
term for the probability of document what about prior belief that it's Hamilton let's start with that because that we can argue about there's two things one could do you could say based on my long history of understanding The Federalist Papers I have this prior belief that it's more likely to be Hamilton I'll Express that as a 0.8 or you could say I want to be pretty fair to everybody so before I go into this analysis the probability of Hamilton is going to be 0.5 it's going
1:06:41
to I'm going to say before I look at any words my belief as Hamilton is equal to my belief that is Madison I'm going to set that to be one half so if you set this to be one half you can think about this as the probability of a collection words given Hamilton that will be a multinomial and religious left with this awful term at the bottom which we'll deal with somehow this awful turn at the bottom though I'd like to talk about it for a second because it shows up in Bayes theorem a
1:07:07
lot so normally if you have you know probably H given d equals probability of D given h times one half because we're going to say the probability that he wrote it before we see any data is one half normally what you do on the bottom is you find some sort of expansion for probability of D and what we've often done in the past is probability of D given h times the probability of H plus the probability of D given Madison times the probability it's Madison and again we're going to say the
1:07:42
probability of H is one-half and the probability of Madison is one half that's what we'd normally do and that's totally fine that's a good way of getting rid of probability of D this thing we call it the normalization constant and we're all thin thinking about cool tricks to get it to go away this is going to be the probability of the document given Hamilton and we can just use a multinomial we can say here is this document we can look at how many times every word
1:08:08
shows up so this is the probably the joint probably Mass function of the multinomial and it's got this multinomial coefficient and then it has probability of each word type raised to the power of how many times that word type goes and we're just going to instead of multiplying the six times we're going to multiply it over every kind of word that we see in the document it will just be a straight multinomial we can put a one-half for probably of H but we still have this problem of probability of D
1:08:35
can I show you something cute that we can do sometimes I just don't like that probability of d so I can solve this equation for probably of H given D I could do the same thing for probably of Madison given d and in both of these equations I'll end up with a probability of D and what if I was feeling super cheeky and super cute I'm like I don't want that probably of D but if instead of thinking about the exact probably of Hamilton if I just looked at the ratio is it probably
1:09:02
Hamilton greater than Madison I could know it by no dividing these two terms we've never done this before but you know I can take this term divide by that term and if it's greater than one I know probability of H must be greater than the probability of M given d so I can calculate this term and then figure out authorship does that sound cool the coolest thing about that is when you write these two things you're like audio is probability of D I'm never seeing you again and the one has cancel
1:09:25
out and you get that this ratio is just going to be equal to these terms one more beautiful thing comes out this multinomial coefficient is the same whether or not you're thinking about Madison or Hamilton is the author because you're looking at the same unknown document and the same undone document has the same count of every type of word and those two coefficients are just going to go away and this whole problem is just going to reduce to this a very fundamental um
1:09:53
a well-justified approach leaves us with if you can calculate the ratio of these two terms you should be able to figure out who wrote this document how to the code now I'm going to give you this calculation I'm going to calculate for Madison and I'm going to calculate the multinomial I'm going to Loop over my unknown document get the probability of every word see how many times it shows up so first this probability will be Hamilton is the author writing word I then next
1:10:28
time I call this function will be Madison the author work writing word I and I'm going to calculate exactly what I had on the slides and we will know once and for all who wrote this this is starter.py now if you look at some things I just pull out from the dictionary before I show you any results I first say I look up I compute Madison's probability of every word so the probability that Hamilton writes the word Congress is 0.001 that's very high I do not write Congress that much
1:10:58
Madison either Madison's probably writing the word Congress is 0.00016 Congress shows up once in the documents hmm it's looking a little bit like Hamilton anyways there is a 2172 words in this document and then I calculate this term and I calculate this term we'll go over the exact details of this code later but when I calculate those two terms I get the probability of the document given Hamilton is zero and the probability of the document given Madison is also zero
1:11:32
heartbroken I'm heartbroken does this tell me who wrote it is it because probability is zero for everything no these should not be zero probabilities what has gone wrong what a mystery the mystery continues come back on Friday we'll figure the true Ashton who wrote this document and think about it in the next couple of days what has gone wrong here don't forget let us know when are you taking the finals
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