1 00:00:00,000 --> 00:00:03,958 So far, we've talked a lot about the representation of probabilistic graphical 2 00:00:03,958 --> 00:00:07,662 models. We've defined different classes of probabilistic graphical models, 3 00:00:07,662 --> 00:00:11,062 Bayes Nets, Markov Nets, and talked about their independence 4 00:00:11,062 --> 00:00:15,071 assumptions. Now let's operationalize probabilistic graphical models, and figure 5 00:00:15,071 --> 00:00:18,725 out how to use this declarative representation to answer actual queries. 6 00:00:18,725 --> 00:00:22,784 It turns out that there's many queries that one can use a PGM to answer. 7 00:00:22,784 --> 00:00:26,590 But perhaps one of the most commonly used one is what's called conditional 8 00:00:26,590 --> 00:00:30,840 probability query. So let's define a conditional probability query. In a 9 00:00:30,840 --> 00:00:38,679 conditional probability query we have some set of observations. E = little e, about a 10 00:00:38,679 --> 00:00:44,350 set of variables, big E These are the set of variable that we happen to 11 00:00:44,350 --> 00:00:50,832 observe. We also have a particular query that we care about. Which is usually which 12 00:00:50,832 --> 00:00:57,009 we're going to denote as a set of variables Y. So our goal here is to 13 00:00:57,009 --> 00:01:02,002 compute the. Conditional probability of the variables Y, given the evidence equals 14 00:01:02,002 --> 00:01:06,447 little e, or a conditional probability. This type of query is useful for a 15 00:01:06,447 --> 00:01:10,893 variety of different applications. For example, in the medical or fault diagnosis 16 00:01:10,893 --> 00:01:15,507 domains that we've spoken about, we might have observations about certain symptoms 17 00:01:15,507 --> 00:01:20,008 or test results. And we're interested in predicting the probability of different 18 00:01:20,008 --> 00:01:24,622 failure modes or different diseases. In the pedigree analysis example that we also 19 00:01:24,622 --> 00:01:29,011 talked about, we might have observations about the phenotype, or maybe even the 20 00:01:29,011 --> 00:01:33,420 genotype of some individuals in a family and are interested in reaching conclusions 21 00:01:33,420 --> 00:01:38,317 about other individuals. So unfortunately like most interesting problems, the problem of 22 00:01:38,317 --> 00:01:43,139 inference in probabilistic graphical model is NP Hard. So before we talk about that 23 00:01:43,139 --> 00:01:47,781 let's first remind ourselves what NP hardness is. I am not going to define it 24 00:01:47,781 --> 00:01:52,724 formally in this course but as a rough intuition if the problem is shown to be NP 25 00:01:52,724 --> 00:01:57,366 Hard it means that it is extremely unlikely to have an efficient solution. 26 00:01:57,366 --> 00:02:02,189 Slightly more formally, it means that all algorithms that people have devised for 27 00:02:02,189 --> 00:02:07,313 this problem and a bunch of problems that are equally hard require at the very least 28 00:02:07,313 --> 00:02:12,124 time exponential in the size of the representation of the problem which means 29 00:02:12,124 --> 00:02:17,904 that it's unlikely to be solvable for any problem that is bigger than a small 30 00:02:17,904 --> 00:02:23,997 handful of same variables in our context. So, which particular problems in the 31 00:02:23,997 --> 00:02:30,089 context of PGM inference are NP hard? Well, first, the basic problem of exact 32 00:02:30,089 --> 00:02:36,263 inference in the PGM is NP hard. So, given a PGM, P of Phi defined by a set of 33 00:02:36,263 --> 00:02:41,867 factors Phi and a particular target variable X, and the value, little X. 34 00:02:41,867 --> 00:02:47,185 Computing the probability of the, the event X=little X is NP hard. In fact, 35 00:02:47,185 --> 00:02:52,239 even a simpler special case of this problem, one where we just want to figure 36 00:02:52,239 --> 00:02:56,852 out whether this probability is even positive. That too, is NP hard. So one 37 00:02:56,852 --> 00:03:01,570 might then say well okay. Exact inference is, is intractable. But what if 38 00:03:01,570 --> 00:03:05,875 we compromise a little bit in accuracy. What if we're just looking for an 39 00:03:05,875 --> 00:03:10,593 approximate answer. After all, we don't necessarily care about the tenth 40 00:03:10,593 --> 00:03:14,780 significant digit in this probability. Does it make the problem easier? 41 00:03:14,780 --> 00:03:20,955 Unfortunately turns out that the answer is no. And there's many different variants of 42 00:03:20,955 --> 00:03:26,695 NP hardness results for approximate inference. This is just one of them. This 43 00:03:26,695 --> 00:03:32,217 one says that again. Given a PGM an event. X equals little x. And some set of 44 00:03:32,217 --> 00:03:37,996 observations. The problem of finding. A, an approximate answer P, for which, we are 45 00:03:37,996 --> 00:03:44,244 guaranteed that this approximate answer is with an Epsilon of the truth is NP hard. 46 00:03:44,244 --> 00:03:49,814 And this is true for any Epsilon, this is less than 0.5 and note 47 00:03:49,814 --> 00:03:56,137 that Epsilon equal to 0.5 can be obtained by simply random guessing or guessing the 48 00:03:56,137 --> 00:04:01,331 value equal to 0.5. So any nontrivial approximation for this kind of 49 00:04:01,331 --> 00:04:07,802 conditional probability query. Is also intractable. So it's a rather depressing 50 00:04:08,032 --> 00:04:13,771 observation and might want, might want to make us give up on using PGMs for 51 00:04:13,771 --> 00:04:19,280 inference. But it turns out that one shouldn't get depressed too quickly 52 00:04:19,280 --> 00:04:25,632 because importantly, this is a worse case result which means we can construct these 53 00:04:25,632 --> 00:04:31,906 bizarre PGMs for which exponential time is the best we can do, but it doesn't mean 54 00:04:31,906 --> 00:04:37,768 that in the general case one can't do better, and the rest of the inference 55 00:04:37,768 --> 00:04:42,332 section of this course will be devoted to showing a variety of algorithms that, 56 00:04:42,332 --> 00:04:47,242 whether for exact inference or approximate inference, can do considerably better than 57 00:04:47,242 --> 00:04:52,424 this worst case result would suggest. So, first let's to understand where these 58 00:04:52,424 --> 00:04:57,752 results might be getting, where these algorithms might be getting their power, 59 00:04:57,752 --> 00:05:03,081 let's drill down into the inference question a little bit more. And here is a 60 00:05:03,081 --> 00:05:08,617 slightly elaborated version of our student network where we now have additional 61 00:05:08,617 --> 00:05:14,222 variables. For example, the coherence of a course influences its difficulty and a 62 00:05:14,222 --> 00:05:19,832 variety of other variables that we're not going to talk about, so. Inference in of 63 00:05:19,832 --> 00:05:25,745 this model. And in general. Inference for probabilistic graphical models. Uses the notion 64 00:05:25,745 --> 00:05:31,518 of factors that we've talked about before. And it turns out that it's convenient to 65 00:05:31,518 --> 00:05:37,083 use factors. Because it means that the algorithms apply equally well to Bayes nets and Markov networks 66 00:05:37,083 --> 00:05:42,949 members. And, and it's a very useful instruction. So let's think about this 67 00:05:43,194 --> 00:05:49,729 Bayesian network in the context of the set of factors. So here for example, we 68 00:05:49,729 --> 00:05:56,591 had initially a prior probability over the c variable p of c. That translates into a 69 00:05:56,591 --> 00:06:02,473 factor whose scope is C. We had, for example, P of G given I and D. And that 70 00:06:02,473 --> 00:06:08,123 translates into this factor whose scope is G, I, and D. In general, each one of 71 00:06:08,123 --> 00:06:13,915 the CPDs in this network converts to a factor over the scope of the family, that 72 00:06:13,915 --> 00:06:20,214 is the variable and its parents. So now lets assume that our goal to compute the 73 00:06:20,214 --> 00:06:27,057 probability of the variable j. And so we'd like to compute p of j. And what we see 74 00:06:27,057 --> 00:06:33,731 here is the joint distribution. So, this is the joint distribution which we have 75 00:06:33,731 --> 00:06:40,161 defined using the chain rule for Bayesian networks. In order to compute P of J, 76 00:06:40,161 --> 00:06:46,224 what we need to do is only to eliminate or marginalize out all of the variables 77 00:06:46,224 --> 00:06:52,059 except for J. And so, we end up with a summation that looks like this. Which is 78 00:06:52,059 --> 00:06:58,046 why this problem of inference of conditional probability inference is often 79 00:06:58,046 --> 00:07:05,143 called sum products because we have sum over a product of the factors. The inference 80 00:07:05,143 --> 00:07:10,129 problem for Markov networks takes exactly the same form. So here we have, 81 00:07:10,129 --> 00:07:15,452 once again, a product of factors. In this case, the factors are the form in which 82 00:07:15,452 --> 00:07:20,910 the network are, is originally defined. So we have the factors phi one over AB, phi 83 00:07:20,910 --> 00:07:26,436 two, phi three, and phi four. And if we're interested in computing the probability P 84 00:07:26,436 --> 00:07:31,691 of D, then once again we need to compute the product of these factors and then 85 00:07:31,691 --> 00:07:38,136 marginalize out. Now, what I wrote here is not actually quite right. Because the 86 00:07:38,136 --> 00:07:44,802 prod-, the product of the factors isn't actually in Markov networks. P of ABCD. 87 00:07:44,802 --> 00:07:51,553 Rather, it's P tilde of ABCD. Which is the, unnormalized measure. And in order to 88 00:07:51,553 --> 00:07:58,241 get the normalized measure, we need to norm-, we need to normalize, or. Divide by 89 00:07:58,241 --> 00:08:04,409 the partition function. So, how do we deal with that, if our goal is to compute 90 00:08:04,409 --> 00:08:10,803 P of D? Well, the point is, that, if what we have computed, if we ignore the 91 00:08:10,803 --> 00:08:18,163 partition function, and rather, we compute P tilde of D. We can infer that P of D 92 00:08:18,163 --> 00:08:25,164 is actually equal to one over Z. P tilde of D, because, the normalizing 93 00:08:25,164 --> 00:08:32,254 [inaudible] constant is a constant. And so, if we've computed P tilde of D, 94 00:08:32,254 --> 00:08:40,060 we can obtain P of D by a simple process of renormalization. Of P tilde of D. 95 00:08:40,740 --> 00:08:48,025 [sound] What about evidence? Well, evidence it turns out can be done by 96 00:08:48,025 --> 00:08:53,827 simple preprocessing step of factor reduction. So, here if we're trying to 97 00:08:53,827 --> 00:08:59,391 compute the probability of a set of variables Y given evidence. That by 98 00:08:59,391 --> 00:09:05,590 definition is the ratio between the probability of y and the evidence divided 99 00:09:05,590 --> 00:09:11,550 by the probability of the evidence. And if we look at the numerator of this 100 00:09:11,550 --> 00:09:19,748 expression over here. And define a set of variable, define W to be all the variables 101 00:09:19,748 --> 00:09:30,173 that are neither query. Nor evidence. Then we can, once again, consider this as a 102 00:09:30,173 --> 00:09:37,825 sum-product expression. So p of y, and e, we're going to introduce the variables w, 103 00:09:37,825 --> 00:09:44,782 into this expression. So this probability, over here, is the sum, of this 104 00:09:44,782 --> 00:09:55,990 probability, marginalizing out the w. Now if we, now, re-write this expression. Over 105 00:09:55,990 --> 00:10:02,158 here we can view it as a product of factors and that's the case whether it's a 106 00:10:02,158 --> 00:10:08,171 Bayesian network or a Markov network. And that product of factors is only those 107 00:10:08,171 --> 00:10:14,651 factors which are only the components of those factors that are consistent with my 108 00:10:14,651 --> 00:10:21,054 evidence, E equals little e, which means I, reduce the factors by the evidence. So 109 00:10:21,054 --> 00:10:27,423 to understand what that means, let's look at this example over here. And, let's 110 00:10:27,423 --> 00:10:34,282 imagine, for example, that we have an observation Say A equals little A, and we 111 00:10:34,282 --> 00:10:40,339 want to compute the probability of the distribution in the context of this 112 00:10:40,339 --> 00:10:46,707 observation. What that means is that we're going to take every single one of those 113 00:10:46,707 --> 00:10:53,012 factors. Say A equals, say A equals a zero, we're going to remove. From every 114 00:10:53,012 --> 00:10:58,883 factor that involves, the entries that correspond to A=little a1. Because those 115 00:10:58,883 --> 00:11:04,595 are not going to be consistent with our observation, A=little a zero. Once we've 116 00:11:04,595 --> 00:11:10,387 reduced those factors to be consistent with those elements, we have, now, a, 117 00:11:10,387 --> 00:11:17,051 still a product of factors. And we can go ahead and treat it in exactly the same way 118 00:11:17,051 --> 00:11:25,309 as we did before. And so we now have a sum over the variables W that need to be 119 00:11:25,309 --> 00:11:33,971 eliminated of the product of the reduced factors. And once again we can ignore the 120 00:11:33,971 --> 00:11:42,317 partition function by computing this probability and then renormalizing at the 121 00:11:42,317 --> 00:11:52,581 end. [sound]. This applies equally well in the context of, Bayesian networks. So here 122 00:11:52,581 --> 00:11:57,153 we might have, say, the observation I=little I, H=little h. So now this is no 123 00:11:57,153 --> 00:12:03,096 longer an equality, but rather, a, because we have not yet conditioned on the 124 00:12:03,096 --> 00:12:09,191 evidence. And so if we want to make this equal, we have to reduce each one of the 125 00:12:09,191 --> 00:12:14,601 factors involving I and H, based on the evidence. And so this turns into 126 00:12:14,601 --> 00:12:19,829 Phi i of little i. Which as it happens is a constant because there is no 127 00:12:19,829 --> 00:12:27,435 other variable in the scope. And similarly here. And here, and for the H equals 128 00:12:27,435 --> 00:12:32,807 little h. We do the same thing. Which in this case involves only this factor over 129 00:12:32,807 --> 00:12:39,568 here. And now it's back to being an equality. And if we want to compute 130 00:12:39,568 --> 00:12:47,195 probability of J, given. I equals little I, and H equals little h, we take this 131 00:12:47,195 --> 00:12:56,292 summation. And we normalize [sound]. Just like before. [sound]. So to summarize the 132 00:12:56,292 --> 00:13:04,487 sum product algorithm can be done as follows. It looks at, you convert the 133 00:13:04,487 --> 00:13:15,708 conditional probability into a ratio that the numerator of this ratio is a product 134 00:13:15,708 --> 00:13:31,161 of reduced factors, summed out over the remaining variables. The denominator of 135 00:13:31,161 --> 00:13:40,480 this is simply the numerator summed up over the variables, over the query variables y. 136 00:13:41,620 --> 00:13:49,257 And if we divide these two together, we realize that we can get away by computing 137 00:13:49,257 --> 00:13:58,256 simply this product of reduced factors and normalizing at the end. There are many 138 00:13:58,256 --> 00:14:05,235 algorithms for computing conditional probability queries. One of those involves 139 00:14:05,235 --> 00:14:11,958 pushing the summations into the factor product. This gives rise to an algorithm 140 00:14:11,958 --> 00:14:18,426 called variable elimination. It turns out to be a special case of a class of 141 00:14:18,426 --> 00:14:25,765 algorithms called dynamic programming. And it's a form of exact inference. A 142 00:14:25,765 --> 00:14:31,454 generalization of this algorithm performs message passing over a graph that also 143 00:14:31,454 --> 00:14:36,737 effectively deals with summations and factor product and factor summation. And 144 00:14:36,737 --> 00:14:42,088 there's many variants of this algorithm, some of which are exact and others are 145 00:14:42,088 --> 00:14:47,371 approximate. Here are some names of algorithm only some of which we'll have 146 00:14:47,371 --> 00:14:52,518 [inaudible] opportunity discussed. And then, finally, there's a very different 147 00:14:52,518 --> 00:14:57,801 class of algorithms that uses random sampling as the key for as the key technique 148 00:14:57,801 --> 00:15:03,212 [inaudible]. And its sample. Complete instantiations or assignments in a variety 149 00:15:03,212 --> 00:15:08,448 of different ways and uses those assignments to approximate the probability 150 00:15:08,448 --> 00:15:14,551 of, of a particular query. So here we have. Both exact and approximate. Methods, 151 00:15:14,551 --> 00:15:19,667 and, and this is an approximate method. And we'll talk about some of these in the 152 00:15:19,667 --> 00:15:22,226 remaining part of the section of course.