Transcript

here we are uh down to the final Sprint three to go and we're going to take some of the last three maybe two of the last three to talk a little bit about stuff having to do with probabilistic approaches use of probability and artificial intelligence now for many of you this will be kind of a review cuz I know many of you learned about probability over the sand table and every year since then but maybe we'll put another little twist into it especially toward the end of the hour when we get into a discussion of uh that which has become to be called U belief Nets but first I was driving in this morning and I I was quite astonished to see as I drove in this thing here and my first reaction was oh my God it's the world's greatest hack and then I decided Well maybe maybe it's a piece of art so I'd like to address the question of how I could come to grips with that issue there's a distinct possibility that this thing is a um consequence of a hack possibly the result of some kind of art show and U in any event uh some sort of statue appeared and statues don't usually appear like that so I've got the possibility of thinking about how all these things might uh occur together or not occur together so the natural thing is to uh build my myself some sort of table and keep track of to keep track of my observations so I have three columns in my table I've got um the uh possibility of a statue appearing a hack having occurred and some sort of art show and so I can make a table of all of the combinations of those things that might appear and I happen to have already guessed that there going to be eight rows in my table so it's going to look like this and this is the set of combinations in this row where none of that occurs at all and down here is the situation where all of those things occur so after all it's possible that we can have an art show and and have a hack be a legitimate participant in the art show that's why we have that final rle then we have all manner of combinations in between so those are those combinations then we have fftt t f f TT ft ft f t f t so it's plain that the number of rows in the table for these binary possibilities is two to the number of variables and that can be that can be a big number in fact I'd love to do a bigger example but I don't have the I don't have the patience to do it but anyhow uh what we might do is in order to figure out how likely any of these com combinations are as we might have observed the area outside the student center and the rest of Campus over a long period of time and keep track of what happens on a thousand days or maybe a thousand months or a thousand years I don't know the trouble is these events don't happen very often so the the period of time that I use for measurement needs to be fairly long probably a day is not short enough in any case I can keep track of I can keep a tally of how often I see these various combinations so this one might be for example 405 this one might be 45 this one might be 225 this one might be 40 and so on and so having done all those measurements kept track of all that data then I can say well the the probability that in any given time period some one of these things occurs will just be the frequency of the the number of tallies divided by the total number of tallies so that would be a number between zero and one so that's the probability so that's the probability for each of these events and it's readily calculated from my data and once I do that then I can say that I've got myself a joint probability table and I can perform all manner of Miracles using that joint probability table so let me perform a few of those Miracles while we're at it there's the table and now what I want to do is I'm just going to count up the number of row I I want to count up the probability in all the rows where the statue appears so that's going to be the probability of a statue appearing so I'll just check check off those four boxes there and it looks like the probability of a statue appearing is about 355 in my model I don't think it's quite that frequent but this is a classroom exercise right so I can make up numbers I can make up whatever numbers I want now I could say well what's the probability of a statue occurring giving that given that there's an art show well I can limit my tall to those in which art show is true like so and in that case the probability just zoomed up so if I know there's an art show there's a much higher probability that this that the uh that statue will appear and if I know there's a hack as well as a art show going on goes up higher still to 0.

n but we can also do other kinds of things for example we can go back to the original table and instead of counting up the probability that we've got an art show going on we can the probability we've got a statue as we just did we're we're going to calculate the probability that there is a art show I guess that would be that one and that one not that one but that that one so the probability there's an art show is one chance in 10 or we can do the same thing with a hack in that case we get that one off that one on that one off that one on that one off that one on that one off so the probability of a hack on any given time period is about 50/50 so I've cooked up this little demo so it does the ands of all these things it could do ores too with a little more work but these are just the ands of these various combinations but you can ask more complicated questions like for example you can say what is the probability of a hack given that there's a statue and that would be limiting the calculations to those rows in which the statue thing is true and then the uh and then what I get is 781 now what do you think the probability uh that it would be a hack would what would happen to the probability that it's a hack if I know that there's an art show will that number go up or down I well let's try it oh went down so that's sort of because the existence of the art show sort of explains why the why the uh why the statue might be there now just for fun I'm going to switch to another situation very similar the situation here is that um the neighbor's dog uh uh often barks it might be because of a burglar it might be because of a raccoon sometimes it's a burglar and a raccoon uh sometimes a damn dog just barks so let's do some calculations there and calculate the probability that the um that it's a a raccoon the probability of a raccoon is true similar to what we did last time uh it looks like on any given night it's a kind of a wooded area there a high probability of raccoon showing up and then then that we can ask well what is the what is the uh what is the probability uh of uh the dog barking given that a raccoon shows up well in that case we want to just limit the number of rows to those where a raccoon or where the dog is barking looks like the probability of the dog barking knowing nothing else is about 37 uh that's now but now we want to know the probability of the raccoon that's this these guys here need to get checked these are off so that's the probability of a raccoon um is that did I get that right true oh that's probability of a burglar sorry that was too H so let me go back and calculate I want I want to get the probability of of a raccoon uh that's true false true false true false true so the probability of raccoon Knight as I said before is5 but now what's what happens that probability if the dog if I know the dog is barking well all I need to do is limit my rows to those where the dog is barking those bottom four and I'll click that there and you notice all these tallies up above the median line the midpoint have gone to zero as I'm only considering those cases where the dog is barking in that case the probability that there's a raccoon just the number of tallies over the total number of talls it's um G I guess it's 225 plus 50 divided by 370 that turns out to be 743 so about 75% of the time the dog barking is accounted for uh well the probability that a raccoon under those conditions is is pretty high and now uh once again I'm going to ask well what is the probability of a raccoon given that the dog is barking and there's a burglar and guess what will happen there we did this once before uh with the uh with the Statue probability first went up and we saw the statue and then went down when we saw another explanation here's this one here wow look at that it went back to its original Condition it's priori probability so somehow uh the existence of the burglar and the dog barking means that the probability of a raccoon is just what it was before we started this game so those are kind of interesting questions and there's a lot we can do when we have this table by way of those kinds of calculations and in fact the whole Miracle of probabilistic inference is right in front of us it's the table so why don't we go home uh well because there's a little problem with this with this table with these two tables that I've shown you by way of illustration and um the problem is the problem is that there are a lot of rows and I had a hard time making up those numbers I didn't have the patience to wait and make observations that would take too long so I had to kind of make some guesses and I could kind of manage manage it with with eight rows those are up there I could you know put in some tallies it wasn't that big a deal so I I got myself those all of those eight numbers up there like like that and similarly for the art show calculations produced eight numbers but what if I added something else to the mix what if I added the the day of the week or um uh what I had for breakfast uh each of those things would double the number of rows if they're binary variables so if you have to consider the possibility that if I have to consider 10 influences um all working together then I'd have two to the 10th i' have a thousand numbers to to to to deal with and that would be hard but if I had a pro joint probability table then I can do these kinds of Miracles uh but Dave if I could have this little projector now please I just want to emphasize that although we're talking about probabilistic inference and it's a very powerful Tool uh it's not the only tool we need in our bag trouble with most ideas and artificial intelligence is if their hardcore proponents think that they're the only thing to do and probabilistic inference has a role to play in developing a theory of human intelligence and it certainly has a practical value but it's not the only thing and to illustrate that point I'd like to imagine for a few moments that U MIT were founded in 1861 BC instead of 1861 ad and if that were so then um it might be the case that there would be a research program on what floats and this of course would be an experimental problem in experimental physics and we can imagine that those people back there in the in that early MIT would uh be experimental minded try some things ah I didn't know that would happened it looks like chalk floats here's a rock no it didn't float here's some money doesn't float here's a pencil no it doesn't float here's a pen here's a piece of tin foil I got from Kendra that floats that's a metal the other stuff's metal too now I'm really getting confused here's a Little W of paper here's a self oh no I've tried actually I've tried that before they don't float and they also don't work afterward either I don't need to do any of that in the in the MIT of 1861 ad and Beyond because I know that arimed has worked this all out and all I have to do is measure the volume of the stuff divide that by the weight and if that ratio is um big enough then the thing will float but back in the old days I would have to try a lot of stuff and make a big table taking into account such factors as how hard it is how big it is how heavy it is whether it's alive or not most things that are alive float some don't uh fish don't for instance so it would be full hearty to to uh to do that that sort of a probab probabilistic inference on the other hand there are lots of things where I don't know all the stuff I need to know in order to make the calculation I know all the stuff I need to know in order to side if something floats but not all the stuff I need to know in order for example to um for example to decide if the child of a republican is likely to be a republican uh there are a lot of subtle influences there and it is the case that if that the children of Republicans and their children of Democrats are more likely to share the political party of their parents but I don't have any any direct way of calculating whether that will be true or not I I can all I can do in that case is what I what I've done over here is do some measurements get some frequencies take some take some snapshots of the way the world is and incorporate that into a set of probabilities that can help me determine if any given parent is a republican given that I've observed the voting behavior of their children so probability has a place uh but it's not the only tool we need and that is an important and preamble to all the stuff we're going to do today now we're really through because this joint probability table is all that there is to it except for the fact that we can't either record all those numbers and it becomes quickly a pain to guess at them there are two ways to think about all this we can think about these probabilities as probabilities that come out of looking at some data that's a frequentist view of the probabilities or we could say well we can't do those measurements so I can just make them up uh that's sort of the subjective view of where these probabilities come from and in some cases there's a there some people like to talk about natural propensities like in quantum mechanics but for our purposes we either make them up or we or we do some tallying trouble is we can't deal with this kind of table so as a consequence of not being able to deal with this kind of table a gigantic uh industry has emerged uh for dealing with probabilities without the need to work out work up this this full table and that's where we're going to go for the rest of the hour and here's the path we're going to take we're going to talk about some basic review of basic probability then we're going to move ourselves step by step toward these so-called belief networks which make it possible to deal to make this a practical tool so let's let us begin uh the first thing is a basic probability uh let us say um basic and basic probability all of probability flows from a small number of axioms uh we have the probability of some event a has got to be greater than zero and less than one that's axium number one uh things uh have a probability of being in a binary World things have a probability of being true some have a probability of being false but the true event doesn't have any possibility of being anything other than true so the probability of true is equal to one and the probability of false the false event the false condition uh has no possibility of being true so that's zero and then the third of the axioms of probability is that the probability of a plus the probability of B minus the probability of A and B is uh equal to the probability of A or B yeah that makes sense right I guess it make would make more sense if I didn't switch my notation in Midstream A and B so those are the axioms and mathematicians love to start up that way and they can derive everything there is to derive from that but I I don't uh I I never can deal with stuff that way I have to draw a picture and think of this stuff in a more intuitionist type of way so that's the formal uh approach to dealing with probability and it's mirrored by an an intuitions intuitions that have the with discussions of spaces like so in which we have circles or areas representing A and B and to keep my notation consistent I'll make those lowercase so you can think of those those are spaces of all possible worlds in which these things might occur or you can think of them as sample spaces but in any any event you associate with the probability of a the size of this area here relative to the total area uh in the rectangle the universe so the probability of a is the size of this circle divided by the size of this rectangle in this picture so now all these axioms make sense the probability that a is certain is just when that fills up the whole thing uh there's no other place for a sample to be that means it has to be a so that's probability uh goes all the way up to one on the other hand if the size of a is just a infimal DOT then the chances of Landing in that world is zero and so that's the the bound on the other end so this axium number one makes sense in terms of that picture over there likewise axium number two what about axium number three does that make sense in terms of all all this stuff and the answer is sure because we can just look at those areas with a little bit of colored shock and so the probability of a is just this area here the probability of B is this area here and if we want to know the probability that we're in either A or B then we just have to add up those areas but when we add up those areas this intersection part is added in twice so we got to subtract that off in order to make this thing make a rational equation so that that makes sense and axium 3 makes sense just as axium one and two didn't so that's all there is to basic probability and now it's now you can do all sorts of algebra on that and it's elegant because it's like circuit Theory or electromagnetism because from a very small number of axioms in this case three you can build An Elegant mathematical system and that's what probability subjects do but we're not going to go there because we're sort of focused on getting down to a point where we can deal with that joint probability table that we currently can't deal with so we're not going to go into a whole lot of algebra with these things just just what we need in order to go through that Network so the next thing we need to deal with uh is conditional probability and whereas those are aums this is a definition we say that the probability of a given B is equal to by definition the probability of A and B I'm using that common notation to mean and as is conventional in the field and then we're going to divide that by the probability of B and you can take that as a definition and then it's just a little bit of mysterious algebra or you can do like we did up there and take an intuitionist approach and ask what that stuff means in terms of a circle diagram in some sort of space and let's see what does that mean it means that um we're going to restrict the probability of a to those circumstances where B is known to be so and we're going to say that we got this part here and then we've got the intersection of a with b and so it does make sense as a definition because it says that if you've got B then the probability you're going to get a is the size of that intersection the pink and orange stuff divided by the the whole of B so it's as if we restricted the universe of of consideration to just that part of the original universe that's covered by B so that that makes sense as a as a definition and we can rewrite that of course as uh P of A and B uh is equal to the probability of a given B times the probability of B that's all basic stuff now we do want to do do a little bit of algebra here and because I want to consider not just two two cases but what if we divide the space up into three parts then we'll say that the probability of a b and c is equal to what well one way to there are lots of ways to think about that but one way to think about it is that we are restricting the universe to that part of the world where B and C are both true so let's say that Y is equal to B and C the inter the the the the union the sorry the intersection of of of B and C where A and B are both true then we can use this formula over here to say that probability of a given probability of a b and c is equal to the probability of a and Y which is equal to the prob ility of a given y times the probability of Y and then we can expand that back out and say that P of a given B and C is equal to the probability or sorry times the probability of Y but Y is equal to probability of um B and C like so ah but wait B and C uh we can we can run this idea on that over that one too and we can say this whole works is equal to the probability of a given B and C times the probability of B given c times the probability of c and now when we look stand back and let that snc to us we can see that some magic is beginning to happen here because we've taken this probability of all things being so and we broke it up into a product of three probabilities the first two are conditional probabilities so they're really all conditional probabilities the last one's conditional on on nothing but look what happens as we go from left to right a is dependent on two things B is only dependent on one thing and nothing to the left C is dependent on nothing and nothing to the left so you can sense a generalization coming so let's write it down so let's go from here over to here and say that the probability of a whole bunch of things X1 to xn is equal to Su product of probability ities we'll let the index I run from n to one probability of X the last one in the series conditioned on all the other ones sorry that's probability of I IUS one down to X1 like so and for the first one in this product I will be equal to n for the second one I will be equal to n minus one but you'll notice that as I as I go from n toward one these conditionals get smaller the number of conditional things I'm condition on gets smaller and and none of these things are on the left they're only stuff that I have on the right so what I mean to say is all of these things have an index that's smaller than this index none of the ones that have a a higher index are appearing in that conditional so it's a way of taking a probability of a whole bunch of of the end of a whole bunch of things and writing as a product of probabilities conditional probabilities so we're making good progress we've done one we've done two and now we've done three because this is the chain Rule and we're about halfway through our diagram halfway to the point where we can do something fun but we still have a couple more Concepts to deal with and the next concept is the concept of conditional probability so that's uh that's all this stuff up here oops all this all this stuff here is a definition of conditional probability and now I want to go to the definition of Independence in d n d s so that's another definitional deal but it's another definitional deal that makes some sense with with the diagram as well as well so the definition goes like this we say that P of a given B is equal to P of a if a independent of B so that says that the probability of a doesn't depend on what's going on with B it's the same either way so it's independent B doesn't matter so what does that what does that look like if we try to do an intuitionist diagram well let's see here's a here's B now the probability of of a given B well let's see that must be this part here divided by this part here right so the ratio of those areas is the probability of a given B so that's the probability of this way divided by the probability of both ways so what's the probability of a in terms of these areas well probability of a in terms of these areas is the probability let's see if I got this right I got this upside down the probability of a given B is the probability of the stuff in the intersection so that's both ways divided by the probability of the stuff in B which is going this way and let's see the probability of a not conditioned on anything except being in this universe is all these hash marks like oops like so divided by the universe so when we say that something's independent it means those two ratios are the same that's all it means in the intuitionist point of view so it says that this little area here divided by this whole area is the same as this whole area for a divided by the size of the universe so that's what Independence means now that's quite a lot of work but we're not done with Independence because we' got conditional Independence to deal with and that too can be viewed as a definition and what we're going to say is that the probability of a given B and Z is equal to the probability of a given Z what's that mean that means if you know that we're we're dealing with z then the probability of a doesn't depend on b b doesn't matter anymore once you're restricted to to being in Z so you can look at that this way here's a and here's B and here is z so what we're saying is that we're restrict in the world to being in this part of the universe where Z is so the probability of a given B and Z is this piece in here a given B and Z is that part there and the probability of a given Z is this part here divided by all of Z so we're saying that the ratio of this little piece here to this part which I'll mark that way the ratio of this to this is the same as the ratio of that to that so that's conditional Independence so you can uh infer from these things with a little bit of algebra algebra that P of A and B uh given Z is equal to P of a given Z * P of B given Z oh boy well that's been quite a quite a journey but we got all the way through one two three four and five and now the next thing is belief Nets and I'm going to ask you to forget everything I've said for a minute or two then we'll come back to it I want to talk about the dog and the burglar and the um and and the raccoon again and now forgetting about probability I can say the look uh the dog barks if the if a raccoon shows up the dog barks if a burglar shows up a burglar doesn't show up because a dog is barking a raccoon doesn't show up because a dog is barking so the causality flows from the burglar and the raccoon to The Barking so we can make a diagram of that and our diagram will look like this here's the burglar and here's the raccoon and these have causal relations to the dog barking so that's an interesting idea because now I can say that well I can't say anything yet because I want to add a little more complexity to it I'm going to add two more variables you might call the police depending on how vigorous the dog is barking I guess and the raccoon has propensity to knocking over the trash can so now I've got five variables how big a joint probability table am I going to need to keep my Tally straight well I'll be 2 to the 5ifth that's 32 but what I'm going to say is that uh is that this diagram this diagram is a statement that every node in it depends on its parents and nothing else that's not a descendant now I need to say that about 50 times because you got to say it right every node there is independent of every non- descendant other than its parents no that's not quite right given its parents every node is independent of all other non-descendants well what does that mean here's the deal with calling the police here's it's one and only parent so given this parent the probability that we're going to call the police doesn't depend on anything like b r or T it's because all of the causality is flowing through this dog barking I'm not going to call the police dep in a way that's depend on anything else other than whether the dog is barking or not because this guy has this as a parent and these are not descendants of calling the police so this is independent of B R and T all right so let's go walk through the others here's the dog the dog's parents are burglar appearing and raccoon appearing so the probability that the dog appears is independent of that trash can over there because that's not a descendant it is dependent on these parents how about the trash can it depends only on the Raccoon it doesn't depend on any other it doesn't depend on any other non descendant so therefore it doesn't depend on d b or P how about B it has no parents so it depends on nothing else because everything else is either a a non- descendant because everything sorry because B does not depend B does not depend on R and T because they're not descendants okay it's interesting that b might depend on D and P because those are descendants okay so it's important to understand that uh there's this business of Independence given the parents Independence given the parents of all other non-descendants and you'll see why that funny strange language is important in a minute but now let's see I I want to make a model of what's going to going to happen here so uh let me see what kind of probabilities I'm I'm going to have to uh figure out this guy doesn't depend on anything Upstream so we can just say that all we need there is the probability that burglar is going to appear let's say it's a fairly high crime neighborhood One Chance in 10 one day in 10 burglar appears the raccoon doesn't depend on anything uh other other than its own propensity so its probability we'll say is 0.5 uh raccoons love the place so it shows up about one day and two so what about the dog barking that depends on the whether there's a burglar and the other parent is whether there's a raccoon so we need to keep track of the probability that the dog will bark for all all four combinations so this will be the burgler and this will be the raccoon and this will be false false true true uh oops false false true false false true true true so let's say it's a wonderful dog and it always barks if there's a burglar so that would say that the probability here is 1.0 and the probability here is 1.0 and if there's neither a burglar nor a raccoon the dog still likes to bark just for fun so we'll say that's chance of one and 10 and then uh the case there's a burglar let's say that's the burg there's no burglar but there is a raccoon I he's tired of the raccoons so he only barks half the time do these numbers by the way have to add up to one they clearly don't these numbers don't add up to one what what adds up to one is this is the probability that the dog barks and then the other Phantom probability is out here and these have to add up to one so that would be 0.9 that would be 0.0 that would be 0.5 and this will be 0.0 so because those are just one minus the numbers in these columns I don't bother to to write them down well we still have a couple more things to do the probability uh that we'll call the police depends only on the dog so we'll have a Callum for the dog and then we'll have a probability of calling the police there's a probability for that being false and a probability for that being true so if the dog doesn't bark there's really hardly any chance we'll call the police so we'll make that 001 if the dog is barking if he darks vigorously enough maybe one chance in 10 here we have the trash can the final thing we have to think about there's the trash can there's the rather the raccoon and here's the trash can probability depends on the raccoon being either present or not present if the trash can if the raccoon is not present the probability the trash can is knocked over by say the wind is one in the Thousand if the raccoon is there well man that guy always liked to go in there so that's 08 so now I'm done specifying this model and the question is how many numbers did I have to specify well let's see I had to specify that one that one that one that one that one that one that's six 7 8 9 10 so I had to specify 10 numbers if I just try to build myself a joint probability table straight away how many numbers would I have to supply well it's two to the two to the end so it's 2 to the 5ifth that's 32 considerable saving oh by the way how do you suppose I made that table not by doing all those numbers but by making this this belief Network and then using the belief Network to calculate those numbers and that's why this is a miracle because with these numbers I can calculate those numbers instead of making them up or making a whole lot of tally type measurements so i' like like to make sure that that's true that I can use this this uh this stuff here to calculate the joint the full joint probability table so here's how this works I have the probability of some combination uh let's say the police the dog the burglar the trash can and the raccoon that's you know some combination all the combinations that are possible there will give me an entry in the table one row but let's see using where there's some miracle here oh this chain rule let's use the chain rule we can write that as the probability that we call the police given E B T and R and then the next one in my chain is probability of D given B T and R and then the next one in the chain is probability of B given T and R and the next one in my chain is p of t given R and the final one of my chain is chain is p of R now we have some conditional Independence knowledge too don't we we know that this probability here depends only on D because there are no descendants so therefore we don't have to think about that and all the numbers we need here are produced by this table how about this one here probability that the dog barks depends only on its parents B and R so it doesn't depend on T So Pro B in turn depends on what does it depend on it doesn't depend on anything so we can scratch those probability of T given R yeah there's a probability there but we can get that from the table and finally P of R so that's why we went through all that probability junk because if we arrange things in the expansion of this from bottom to top then we arrange things so that none of these guys depends on a descendant in this formula and we have a limited number of things that it depends on above it so that's the way we can calculate back the full joint probability table and that brings us to the end of the discussion today but the thing we're going to think about is how much how much saving do we really get out of this in this case in this particular case we only had to calc we only had to devise 10 numbers out of 32 what if we had 10 Properties or 100 properties how much saving would we get then that's what we'll take up next time after the quiz on Wednesday