1 00:00:00,000 --> 00:00:04,578 So we previously presented the variable elimination algorithm, now let's think 2 00:00:04,578 --> 00:00:09,508 about what is the computational complexity of this algorithm. So let's first look at 3 00:00:09,508 --> 00:00:14,614 the basic operations that are used when we when we do an elimination step and there 4 00:00:14,614 --> 00:00:21,436 are these two basic operations. There is a factor product. And the actual 5 00:00:21,436 --> 00:00:26,424 marginalization. And so what we're going to do now, is we're going to count the 6 00:00:26,424 --> 00:00:32,158 operations used by each of them. So let's start with a factor of product. And first 7 00:00:32,158 --> 00:00:38,034 let's remind ourselves that what factor of product is doing. So factor of product is 8 00:00:38,034 --> 00:00:43,771 taking in this case, for example a factor who's scope is ab. And one's who scope is 9 00:00:43,771 --> 00:00:49,675 bc and producing a factor who's scope is abc. Now, let's think about how each of 10 00:00:49,675 --> 00:00:55,646 the numbers in this result is produced. So each of these is a product, in this case 11 00:00:55,646 --> 00:01:01,690 it's two numbers, one that comes from this table and one that comes from that table. 12 00:01:01,690 --> 00:01:08,370 >> So we've to produce every one of the rows in this new table, this new factor. 13 00:01:08,370 --> 00:01:15,651 So let's call Nk the number of the rows in this new table. And how many operations 14 00:01:15,651 --> 00:01:22,417 are there that we need to produce each such row. Well, if we need to multiply in, 15 00:01:22,417 --> 00:01:32,520 in this case mk, different factors so for each row. We have mk minus 1 products. 16 00:01:36,744 --> 00:01:39,729 And so total we get mk -1 times Nk multiplications. Now let's look at the 17 00:01:39,729 --> 00:01:46,445 factor marginalization. So here we have a factor whose scope was Xk, we summed out 18 00:01:46,445 --> 00:01:52,747 Z, and we end up with a factor whose scope is one less. So again, let's remind 19 00:01:52,747 --> 00:02:00,203 ourselves this is a marginalization in this case over B. So marginalize B. And we 20 00:02:00,203 --> 00:02:07,829 see that each of the rows in our output is produced in this case by a summation, of 21 00:02:07,829 --> 00:02:15,272 two of the rows in the original, in the original factor. But if we turn this on 22 00:02:15,272 --> 00:02:24,109 it's head we also see that each row Though each number in this factor, is used 23 00:02:24,109 --> 00:02:34,162 exactly once. Each one gets added to only one of the rows in the new factor. And so 24 00:02:34,162 --> 00:02:41,631 a simple upper bound on the amount of additions that we need to do is simply the 25 00:02:41,631 --> 00:02:48,812 size of this factor N k. So now let's total up the computational complexity of 26 00:02:48,812 --> 00:02:54,215 variable elimination. So let's assume that we start with m factors. For Bayesian 27 00:02:54,215 --> 00:03:00,512 networks, m is really effectively N because we have one factor. For every 28 00:03:00,512 --> 00:03:07,931 variable. Which is the CPD. And the reason I wrote less than or equal is because of 29 00:03:07,931 --> 00:03:12,751 the reduction by evidence. Now for Markov networks it's gonna actually be larger. So 30 00:03:12,751 --> 00:03:17,687 if you think of a grid Markov network or a fully connected Markov network, the number 31 00:03:17,687 --> 00:03:22,565 of factors might be so fully connected pairwise Markov network number of factors 32 00:03:22,565 --> 00:03:26,862 can actually be larger than number of variables. So that's why we have the 33 00:03:26,862 --> 00:03:32,485 complexity in terms of m as opposed to in terms of n. Now, so that's the set of 34 00:03:32,485 --> 00:03:38,867 factors that we start out with and then what happens as we do an elimination step. 35 00:03:38,867 --> 00:03:45,170 An elimination step takes some of those factors, and generates another factor. But 36 00:03:45,170 --> 00:03:52,815 each elimination step generates exactly one factor. How many elimination steps do 37 00:03:52,815 --> 00:03:58,231 we have? Well, each elimination step corresponds to elimination of one 38 00:03:58,231 --> 00:04:05,330 variable, so we have at most n elimination steps. So the total number of factors that 39 00:04:05,330 --> 00:04:11,995 we ever produce is which we're gonna call M star is going to be equal to at most m 40 00:04:11,995 --> 00:04:18,739 which is the set of initial factors plus the newly generated factors which is at 41 00:04:18,739 --> 00:04:26,284 most n and so all together M star is less than or equal to m plus n. So now that we 42 00:04:26,284 --> 00:04:32,061 figured that out let's look at what the complexity of the algorithm is in 43 00:04:32,061 --> 00:04:37,839 terms of various key quantities. So N is the size of the largest factor that I ever 44 00:04:37,839 --> 00:04:43,201 create which is the max of these different Nk's that I have. So 45 00:04:43,201 --> 00:04:48,642 now how many product operations do we have. Well, remember that we had the sum 46 00:04:48,642 --> 00:04:54,365 over the different elimination steps so sum over k and this was the number of 47 00:04:54,365 --> 00:04:59,805 product operations that we have. But now here's the critical observation. Each 48 00:04:59,805 --> 00:05:11,050 factor. Is multiplied in at most once. Because as soon as we multiply it in. As 49 00:05:11,050 --> 00:05:20,060 soon as we multiply it in, it goes away. Which means that the sum over K, mk -1, is, 50 00:05:20,423 --> 00:05:29,414 is at most the total number of factors. And so said otherwise we can write that this is less than or equal to 51 00:05:29,414 --> 00:05:36,396 N times the sum over k, mk - 1. 52 00:05:36,396 --> 00:05:43,929 This is less than or equal to m star. Because this is at most the total number of factors in my universe of factors. 53 00:05:43,929 --> 00:05:50,887 What about the number of summation operations? Well here, this is 54 00:05:50,887 --> 00:05:58,322 less than or equal to, the sum over k, Nk which when you, which is n times less 55 00:05:58,322 --> 00:06:09,106 than or equal to N times the number of elimination stats. Which is simply less than or 56 00:06:09,106 --> 00:06:16,394 equal to N times n. But altogether between these two steps, over here we have N times 57 00:06:16,394 --> 00:06:22,898 m star over here we have N times n which tells us that the total work that we have 58 00:06:22,898 --> 00:06:30,029 is linear in N and in m star. Great, linear time, aren't we lucky. Well 59 00:06:30,029 --> 00:06:39,089 not quite. Because the Nk which is the contribution to this quantity N is the 60 00:06:39,089 --> 00:06:48,370 total number of values in a factor. And so if we were, if we say for example just for 61 00:06:48,370 --> 00:07:00,370 simplicity, all variable have d values in their scope. So that, for example all 62 00:07:00,370 --> 00:07:07,598 variables are binary, that would be equal to two, for example. Then the number of 63 00:07:07,598 --> 00:07:14,917 values in the factor is exponential. Where the base of the exponent is d and the 64 00:07:14,917 --> 00:07:22,145 exponent is the cardinality of the scope of the kth factor. That is the number of 65 00:07:22,145 --> 00:07:33,922 variables. In the kth factor. And so this is, over here, our big source of 66 00:07:33,922 --> 00:07:45,574 exponential blow up. So, let's understand how this complexity manifests to the 67 00:07:45,574 --> 00:07:51,734 context of a real example. So, this is the run of variable elimination that we did 68 00:07:51,962 --> 00:07:58,403 that we did before. I've just written it out all in one in one slide. And so now 69 00:07:58,403 --> 00:08:04,765 let's see what the complexity of this is. When we see that we have produced several 70 00:08:04,765 --> 00:08:10,756 factors here and let's write down how many variables are in the scope of each of 71 00:08:10,756 --> 00:08:16,548 these factors, this one has two. This one has three, G, I, and D. This one has, 72 00:08:16,798 --> 00:08:22,878 three, S, G, and I. This one has three, H, G, and J. This one has four, L, G, S, and 73 00:08:22,878 --> 00:08:29,208 J. And this one has three, J, L, and S. And so the size of the largest factor is, 74 00:08:29,208 --> 00:08:36,038 it is, this one, that has four variables in it. And that is, what's going to, in 75 00:08:36,038 --> 00:08:42,701 general, drive the complexity of the algorithm. Not in an example as simple as 76 00:08:42,701 --> 00:08:48,508 this, but in more realistic examples. So, now let's understand how elimination 77 00:08:48,508 --> 00:08:53,670 ordering plays into this. We've previously said that variables can be eliminated in 78 00:08:53,670 --> 00:08:58,957 any order, so long as we're, careful about multiplying things in at the appropriate 79 00:08:58,957 --> 00:09:03,684 time. But now, let's see how elimination order might affect the complexity. So 80 00:09:03,684 --> 00:09:08,660 assume that in this example, I'm going to make a not very judicious decision. And 81 00:09:08,660 --> 00:09:15,776 I'm going to start by eliminating G. So which factors do I need to multiply in 82 00:09:15,776 --> 00:09:24,901 order to eliminate G. Well phi L of L and G, phi G of G, I and D and phi H of H, G and J. And 83 00:09:24,901 --> 00:09:30,936 so if I multiply all these together, it turns out that I now end up with a vari-, 84 00:09:30,936 --> 00:09:37,326 with a factor, whose scope is let's see, L. G, I, D, H and J. So total of six variables 85 00:09:37,326 --> 00:09:44,365 whereas before the largest factor that we ever generated had four variables. So 86 00:09:44,365 --> 00:09:50,958 that's maybe, you might say, six versus four, not a big deal. I mean, how much 87 00:09:50,958 --> 00:09:58,086 does, how much difference does it make? So let's convince ourselves that in other 88 00:09:58,086 --> 00:10:04,500 graphs it might make a bigger difference. So here's a graph that has it's simple 89 00:10:04,500 --> 00:10:10,376 pairwise mark of network with A and C and then bunch of variables in the middle B1 90 00:10:10,376 --> 00:10:16,251 up to Bk and imagine that I start by eliminating A first. What are the factors 91 00:10:16,251 --> 00:10:24,425 that involve A? [sound] Well we have a factor AB1, AB2, AB3, up to ABk and the 92 00:10:24,425 --> 00:10:34,874 total scope of the factors are is of this factor that we generate is going to be A, 93 00:10:34,874 --> 00:10:42,858 B1 up to Bk, So it's going to be exponential in k, so the size of the 94 00:10:42,858 --> 00:10:55,535 factor. Is exponential. In k. Maybe this is inevitable. Well no! So let's imagine 95 00:10:55,535 --> 00:11:03,426 that instead we're going to eliminate the Bi's first, so let's think for example 96 00:11:03,426 --> 00:11:11,613 that we're going to start by eliminating B1, well B1 is in a factor with A and in a 97 00:11:11,613 --> 00:11:19,504 factor with C, so we're going to end up with a product of say phi1, phiA1 of A, B1 98 00:11:19,504 --> 00:11:29,739 times phi C1 of C, B1 and that's going to give me a factor whose scope is A, B1 and C 99 00:11:29,739 --> 00:11:37,295 And the result of summing out B1 is going to be a factor tau 1 of A and 100 00:11:37,295 --> 00:11:43,950 C. We're going to get the exact same behavior when we now eliminate B2 and 101 00:11:43,950 --> 00:11:50,516 that's going to give me a factor tau 2 of A and C and so on and so 102 00:11:50,516 --> 00:11:57,891 forth until at the very end I'm going to have a bunch of factors tau i, of A and C 103 00:11:57,891 --> 00:12:04,546 that are all multiplied together. And I've done this without ever generating a factor 104 00:12:04,546 --> 00:12:11,392 whose size is bigger than three. So to summarize, the complexity of variable 105 00:12:11,392 --> 00:12:17,787 elimination is linear in the size of the model, the number of factors and number of 106 00:12:17,787 --> 00:12:23,593 variables. And, more importantly, in the size of the largest factor generated 107 00:12:23,593 --> 00:12:29,527 during the course of variable elimination. And unfortunately that size is exponential 108 00:12:29,527 --> 00:12:34,762 in it's scope. And that is the thing that drives the complexity of variable 109 00:12:34,762 --> 00:12:40,604 elimination. And we've also seen that this, the size of this factor is something 110 00:12:40,604 --> 00:12:45,343 that depends heavily on the elimination ordering. Which means the choosing of 111 00:12:45,343 --> 00:12:48,052 judicious elimination ordering is important.