1 00:00:00,000 --> 00:00:04,347 We've already said that there is many different algorithms for inferencing 2 00:00:04,347 --> 00:00:09,043 graphical models. But the simplest and most fundamental is an algorithm typically 3 00:00:09,043 --> 00:00:13,101 known as variable elimination. Let's consider the variable elimination 4 00:00:13,101 --> 00:00:17,855 algorithm in the context of the simple example of a graphical model structured as 5 00:00:17,855 --> 00:00:22,608 a chain. Here we have we're interested, maybe, in computing the distribution over 6 00:00:22,608 --> 00:00:26,782 variable E. So we're interested in P of E. And as we've already said, that 7 00:00:26,782 --> 00:00:31,130 probability is proportional to the unnormalized measure, P tilde over 8 00:00:31,130 --> 00:00:36,213 A, B, C, D, and E, summing up. All of the variables except for E. So now let's see 9 00:00:36,213 --> 00:00:42,010 how we can do this more efficiently than simply constructing the joint distribution 10 00:00:42,010 --> 00:00:47,048 and then summing things out. So, the first thing we do is we write up this 11 00:00:47,462 --> 00:00:52,984 unnormalized measure as a product of the constituent factors. And for the moment, 12 00:00:52,984 --> 00:00:59,057 we're going to assume that we only have pairwise factors for the edges in this graph. So, 13 00:00:59,057 --> 00:01:04,509 we have a factor for AB, a factor for BC, CD, and DE. So those are the factors phi 1 14 00:01:04,509 --> 00:01:09,692 up to phi 4. Now what is the first observation that we have when we see the 15 00:01:09,692 --> 00:01:15,323 summation over A, B, C, and D of a product of factors? Well, we've already done this 16 00:01:15,323 --> 00:01:20,755 exercise previously, when we were doing some proofs related to graphical models. 17 00:01:20,755 --> 00:01:26,118 That, if you have a factor that doesn't mention a particular variable in it's 18 00:01:26,118 --> 00:01:31,412 scope, we can move it out of the scope of the summation. So specifically, phi 2 19 00:01:31,412 --> 00:01:36,982 of BC can be moved out of the summation over A, as can phi 3 of CD, and phi 4 20 00:01:36,982 --> 00:01:42,302 of DE. Which leaves us only with the summation over A, of phi 1 AB. So that 21 00:01:42,302 --> 00:01:49,410 gives us the expression over here. Now this is. Now this is a summation over a 22 00:01:49,410 --> 00:01:55,893 pair wise factor, and the result of this is a factor over a single variable B, 23 00:01:55,893 --> 00:02:03,640 which we're going to call tau 1 of B. So we end up with an expression that looks like this. 24 00:02:03,960 --> 00:02:09,070 So now let's continue this expression, developing this expression further. 25 00:02:09,272 --> 00:02:14,719 Knowing that we now have an expression that doesn't involve A only the variables 26 00:02:14,719 --> 00:02:19,964 B, C, D and E so that effectively we have eliminated E from the graph A we have 27 00:02:19,964 --> 00:02:26,089 eliminated A from the graphical model. So let's go back to this expression. We now 28 00:02:26,089 --> 00:02:33,145 have this product of four factors and once again we can look at what factors involve 29 00:02:33,145 --> 00:02:39,786 the variable B and which ones don't. And the ones that don't can be moved out of 30 00:02:39,786 --> 00:02:46,426 the summation, just as before, giving us this. For now we have an expression which 31 00:02:46,426 --> 00:02:53,150 is a product of these two factors, summed out over B. And this is going to give us 32 00:02:53,150 --> 00:02:58,970 an expression tau 2 whose scope is C. And so we now have an expression that does not 33 00:02:58,970 --> 00:03:04,147 involve the variable B, and so now we've eliminated B from this graphical model. 34 00:03:04,147 --> 00:03:09,718 And we can similarly continue to eliminate C and D so that ultimately we end up with 35 00:03:09,718 --> 00:03:14,764 an expression that involves only the variable E. And that expression is going 36 00:03:14,764 --> 00:03:20,682 to be proportional to the probably of the, to the marginal probability of E. Now is 37 00:03:20,682 --> 00:03:25,458 through this algorithm in the context of some of more complicated example which is, 38 00:03:25,458 --> 00:03:30,118 our enhanced student network that we played around with before. So lets imagine that 39 00:03:30,118 --> 00:03:34,836 our goal is to compute the probability of the variable J, this one. And in order to 40 00:03:34,836 --> 00:03:39,554 do that we are going to have to eliminate from the joint distribution all of the other 41 00:03:39,554 --> 00:03:44,792 variable except for J. So this is our, our expression. And note that we have this 42 00:03:44,792 --> 00:03:50,089 product of factors I've taken already in this expression the factors that we're, 43 00:03:50,089 --> 00:03:55,386 the CPDs and turned them into factors so that we can have a consistent notation. 44 00:03:55,386 --> 00:04:00,948 And now we need to eliminate every one of the variables except for J. So we're going 45 00:04:00,948 --> 00:04:08,154 to start with eliminating the variable C first. And, and so once again we're going 46 00:04:08,154 --> 00:04:15,542 to take the summation over C and we're going to push it in, leaving in the 47 00:04:15,542 --> 00:04:23,762 summation only the factors that involve C. And those are phi D and phi C. Multiplying 48 00:04:23,762 --> 00:04:31,101 them together and eliminating C is going to give us a factor which we are going to 49 00:04:31,101 --> 00:04:38,377 call tau 1 whose scope is D. Mm-hm. And by putting tau 1 into this expression and 50 00:04:38,377 --> 00:04:43,829 removing the ones that we've just multiplied together, we end up with this 51 00:04:43,829 --> 00:04:56,538 expression. Over here. Having eliminated C, we now go ahead and eliminate D. So, 52 00:04:56,538 --> 00:05:02,780 here we have the variable D, and which factor is involved D, well, tau 1 of D 53 00:05:02,780 --> 00:05:08,945 and phi G of G, I, and D. And, so, everything else is taken out of the summation and we 54 00:05:08,945 --> 00:05:16,165 just have this expression over here. And, that's going to give us, tau 2 whose 55 00:05:16,165 --> 00:05:24,839 scope is G and I, after having eliminated the variable D from this product, whose 56 00:05:24,839 --> 00:05:32,919 scope is G, I and D. And tau 2 gets put back into the bucket. Together, with 57 00:05:35,906 --> 00:05:38,894 everything else, [sound]. Moving forward we're now interested in eliminating I 58 00:05:38,894 --> 00:05:48,476 [sound]. And so the factors that involve I are tau 2 of G and I, and phi S 59 00:05:48,476 --> 00:05:59,338 of S and I, and phi I of I. And so we go ahead and multiply them together. To give us 60 00:05:59,338 --> 00:06:07,664 a factor, whose scope is G, I, S and eliminating I gives us a factor, tau 3 61 00:06:07,664 --> 00:06:17,328 whose scope is S and G. And so the process continues. And let's just finish 62 00:06:17,328 --> 00:06:24,829 it, all the way to the end. Now, our goal is to eliminate H. Well, H is a little bit 63 00:06:24,829 --> 00:06:31,807 of an interesting case. The only factor that mentions H is this factor, phi of H. And, 64 00:06:31,807 --> 00:06:38,155 if we think about what phi of H is, phi H, as it happens. Is P of H given G and J. And so 65 00:06:38,155 --> 00:06:43,655 for summing that up over H, we're actually summing up what is, in fact the 66 00:06:43,655 --> 00:06:49,682 conditional distribution. And since we know that a conditional distribution, when 67 00:06:49,682 --> 00:06:55,935 you sum up on the, the values on the left hand side, the summation is necessarily is 68 00:06:55,935 --> 00:07:01,761 equal to one. So in principal, we could have taken this entire expression. Erased 69 00:07:01,761 --> 00:07:06,291 it, and written one instead. And that would have given us something that is a 70 00:07:06,291 --> 00:07:10,649 factor that doesn't depend on anything would have just been, would have just 71 00:07:10,649 --> 00:07:15,064 disappeared. But for purposes of demonstration, we're not actually going to 72 00:07:15,064 --> 00:07:19,651 do that because in fact, not every algorithm is clever enough to notice these 73 00:07:19,651 --> 00:07:23,951 kinds of coincidences. It depends on whether they were designed to look for 74 00:07:23,951 --> 00:07:28,768 that. And so we're going to do this in the same way, in the same sort of naive way 75 00:07:28,768 --> 00:07:33,722 that we've done before, which is just. [inaudible]. Turn this in to a factor 76 00:07:33,952 --> 00:07:45,450 which is going to be Tau-4 of G comma J. So, so now we have that factor, which really 77 00:07:45,450 --> 00:07:51,225 is one, but we're not going to pay attention to that particular aspect for 78 00:07:51,225 --> 00:07:56,845 the purposes of demonstrating how the algorithm would work. Okay? Next is 79 00:07:56,845 --> 00:08:02,308 eliminating G, and we have this expression, which we inherited from the 80 00:08:02,308 --> 00:08:11,534 previous slide. And G is one of the big ones, because it appears in, phi L, 81 00:08:11,534 --> 00:08:18,828 tau 3 and tau 4. So when we think about the variables here in this 82 00:08:18,828 --> 00:08:25,941 scope, we see that this one actually has this product over here, actually has a 83 00:08:25,941 --> 00:08:32,871 scope of L, G, S, J which is the largest factor, the one with the largest scope 84 00:08:32,871 --> 00:08:40,622 that we've encountered so far. Summing out G, we end up with a factor whose scope is 85 00:08:40,622 --> 00:08:53,166 L, S, and J, so we're missing an S. And, and now we put that into. This expression, 86 00:08:53,166 --> 00:09:00,966 and out comes a now, product of two factors. And, really, at this point, we 87 00:09:00,966 --> 00:09:11,162 might as well just multiply them and end up with a factor over J and. Hold on. So 88 00:09:11,162 --> 00:09:16,868 that gives us variable elimination in its, naive form. What about variable 89 00:09:16,868 --> 00:09:22,722 elimination with evidence? Well, we've already basically established how to deal 90 00:09:22,722 --> 00:09:28,575 with evidence. If we're interested in, [inaudible] in, for example, solving the 91 00:09:28,575 --> 00:09:34,374 query probability of J, I= little i. Comma H equals little h, the way in which 92 00:09:34,374 --> 00:09:39,765 we do that is by, is by computing the probability of the joint event J, I 93 00:09:39,765 --> 00:09:45,641 equals little I, H equals little h and the way in which we do that is by reducing the 94 00:09:45,641 --> 00:09:51,794 factors to correspond to this scope. And so if these were, if, so we take each of 95 00:09:51,794 --> 00:09:57,371 the factors that involves I, and we basically instantiated to take the 96 00:09:57,371 --> 00:10:03,505 particular value for that I, the value little I, and similarly for H. And so we 97 00:10:03,505 --> 00:10:09,639 see here, for example, that, where as phi I initially depended on I, now it doesn't 98 00:10:09,639 --> 00:10:16,013 depend on anything. Because this is simply the value phi I of little I, which is a 99 00:10:16,013 --> 00:10:22,712 constant. And, whereas, for example, G depended on D and I, as we can see in the 100 00:10:22,712 --> 00:10:29,294 original example diagram. Here, phi G in the reduced factor doesn't depend on I, 101 00:10:29,294 --> 00:10:35,704 and is really probability of G, given little I and D. And the same reduction 102 00:10:35,704 --> 00:10:42,542 occurs for H=h, and so we end up with the following set of reduced factors. And now, 103 00:10:42,542 --> 00:10:49,380 once we have that set of reduced factors, we do elimination as, exactly as before. 104 00:10:50,240 --> 00:10:56,265 No changes whatsoever to the algorithm. The only aspect that's a little bit 105 00:10:56,265 --> 00:11:02,099 different is notice that we don't eliminate. No H and no I because there's 106 00:11:02,099 --> 00:11:07,206 no point in eliminating vat, a variable that has a single value. There's no need 107 00:11:07,206 --> 00:11:11,990 to sum up over it when it only has a single value. So, with, this gives us a 108 00:11:11,990 --> 00:11:17,421 unified framework for dealing with, with queries whether they involve evidence or 109 00:11:17,421 --> 00:11:23,153 not. And then how do we get the probability of J, given the evidence? 110 00:11:23,153 --> 00:11:30,855 Well, this is straight forward, we simply re-normalize. Because we, because we can 111 00:11:30,855 --> 00:11:37,622 take this. And simply divide by what it turns out to be, the probability, the 112 00:11:37,622 --> 00:11:57,607 normalizing constant. Is. [sound] So, let's see whether the same idea applies to 113 00:11:57,607 --> 00:12:02,535 Markov networks. So here's our simple Markov networks, n, network with four 114 00:12:02,535 --> 00:12:08,002 variables. Let's imagine that our goal is to compute P of D. And so in order to do 115 00:12:08,002 --> 00:12:13,860 that we need to eliminate A, B, and C from the unnormalized measures. So we have this 116 00:12:13,860 --> 00:12:19,724 being the unnormalized measure, and we're summing up over A, B, and C. And the 117 00:12:19,724 --> 00:12:26,056 process works in exactly the same way. So, if we want to sum out A first, then here 118 00:12:26,056 --> 00:12:32,674 is the factors that involve A, phi 1 of AB, this one. And phi 4 of A D, 119 00:12:32,674 --> 00:12:39,216 multiply them together, we've got a f, factor whose scope is A B D, and then we 120 00:12:39,216 --> 00:12:47,546 sum out A to get a factor whose scope is B D. That gives us a new set of factors 121 00:12:47,546 --> 00:12:53,867 where A has been effectively been eliminated from the graphical model. And 122 00:12:53,867 --> 00:13:00,980 at the end of the process, we get a factor over the single remaining variable D. So 123 00:13:00,980 --> 00:13:08,354 tau 3 of D and that factor is not the probability of D. It's proportional to the 124 00:13:08,354 --> 00:13:15,382 probability of D. It's actually equal to P tilde of D, which is the unnormalized 125 00:13:15,382 --> 00:13:24,744 measure. And so in order to get P of D, we renormalize. So to summarize this, the 126 00:13:24,744 --> 00:13:30,380 main routine in this algorithm, is something, is a routine which we call 127 00:13:30,380 --> 00:13:36,702 eliminate variable Z from a set of factors Phi. And what it does is the following. We 128 00:13:36,702 --> 00:13:42,568 first look within Phi, and we define the set of factors, Phi prime, which are all 129 00:13:42,568 --> 00:13:52,062 factors that involve Z. And that's what this mathematical expression says. The 130 00:13:52,062 --> 00:13:57,751 factors Phi I such that Zs in their scope. We take all those factors and we 131 00:13:57,751 --> 00:14:15,780 multiply them. And then we sum out the variable Z which is the one that we want 132 00:14:15,780 --> 00:14:20,767 to eliminate. Now, and here is the important point: we've already used up 133 00:14:20,767 --> 00:14:27,923 these factors, these ones over here have now been used. We don't want to reuse 134 00:14:27,923 --> 00:14:34,586 them. And so we take them out of the set of factors and instead we introduce the 135 00:14:34,586 --> 00:14:40,375 one that we just created by multiplying those factors and summing them up. This 136 00:14:40,375 --> 00:14:47,277 basic operation is what we use in the context of, the algorithm as a whole. We 137 00:14:47,277 --> 00:14:53,514 begin by reducing all factors by the evidence. In, which is just eliminating 138 00:14:53,514 --> 00:15:00,000 the rows that don't, that are not consistent with the observations. And that 139 00:15:00,000 --> 00:15:06,875 is what gets us our set of factors Phi. Now for each non-query variable we need 140 00:15:06,875 --> 00:15:12,724 to eliminate it. And so we have run one at a time something that eliminates the 141 00:15:12,724 --> 00:15:19,126 variable Z from the set of factors Phi. Each such step changes my set of factors. 142 00:15:19,126 --> 00:15:26,355 It adds factors and removes, so actually it starts by removing factors. Which we have 143 00:15:26,355 --> 00:15:32,396 Phi prime from the previous one, from the previous line, and it adds, and you factor 144 00:15:32,396 --> 00:15:38,395 tau. And then finally at the very end when all variables have been eliminated, 145 00:15:38,395 --> 00:15:42,890 there may be one or more factors remaining. So that point we multiply all 146 00:15:42,890 --> 00:15:47,954 of the remaining factors and then we normalize to get a distribution. So to 147 00:15:47,954 --> 00:15:52,872 summarize, this is a very simple algorithm. It works equally well for 148 00:15:52,872 --> 00:15:58,659 Bayes nets and Markov nets. And it uses, and, a factor product and factor 149 00:15:58,659 --> 00:16:04,085 summation steps. And it does that by ensuring that when you mult-, that when 150 00:16:04,085 --> 00:16:09,655 you sum out a factor, when you do the summation step over variable Z, then all 151 00:16:09,655 --> 00:16:15,369 factors involving Z have been multiplied in, which is the critical piece of the 152 00:16:15,369 --> 00:16:17,540 correctness of this algorithm.