1 00:00:01,160 --> 00:00:06,541 We have previously shown that a graph structure encodes a set of independencies 2 00:00:06,541 --> 00:00:12,058 and that, that set of independencies then necessarily holds for every distribution 3 00:00:12,058 --> 00:00:17,686 that can be encoded as a Bayesian network over that graph. What we're going to talk 4 00:00:17,686 --> 00:00:23,348 about now is the question of how to take a distribution that has a certain set of 5 00:00:23,348 --> 00:00:29,149 independencies that, that it satisfies, and encode it within a graph structure. How 6 00:00:29,149 --> 00:00:34,811 well can we take that distribution and capture its independencies in the context 7 00:00:34,811 --> 00:00:40,552 of the graphical model. So first, let's understand what the independencies of a 8 00:00:40,552 --> 00:00:46,627 distribution are. So we're going define this notion of I(P) for distribution P, 9 00:00:46,627 --> 00:00:52,412 as the set of all independence statements. X is independent of Y, given Z. That 10 00:00:52,412 --> 00:00:58,053 hold for the distribution P. So one can write down, potentially, an 11 00:00:58,053 --> 00:01:04,146 exponentially large set of independence statements. Each of those is going to be 12 00:01:04,146 --> 00:01:10,013 either true in a given distribution P, or not. And what we're going to do is 13 00:01:10,013 --> 00:01:16,217 we're going to define I(P) to be the ones that are true in that distribution. Ok, so these 14 00:01:16,217 --> 00:01:32,630 are independencies that hold in P. And we've already seen that if P 15 00:01:32,630 --> 00:01:41,516 factorizes over a particular graph G, then, G is an I map for P, which means 16 00:01:41,516 --> 00:01:49,584 that every independence that holds in G, that is, is implied by the D separation 17 00:01:49,584 --> 00:01:57,960 statements, or the D separation properties in G, every such independence also holds in P. 18 00:01:59,980 --> 00:02:05,590 But that doesn't mean that the converse holds. That is, there can be 19 00:02:05,590 --> 00:02:12,259 independencies that hold in P that are members of I(P) . But are not 20 00:02:17,736 --> 00:02:23,213 encoded by the graph structure. So. Why does that matter? Because, if we have a 21 00:02:23,213 --> 00:02:29,058 graph that doesn't capture, some of the Independencies in P, then, it's 22 00:02:29,058 --> 00:02:34,503 unnecessarily complicated. And conversely the sparser the graph the more 23 00:02:34,503 --> 00:02:39,910 independencies it encodes then the sparser it is and therefore it has fewer 24 00:02:39,910 --> 00:02:45,247 parameters that we need to elicit or learn. Fewer edges also means that 25 00:02:45,247 --> 00:02:51,367 inference is more efficient and finally it means that the graph is intrinsically more 26 00:02:51,367 --> 00:02:57,201 informative about the properties of P. So we would like graphs that capture as much 27 00:02:57,201 --> 00:03:06,028 of the properties, independence properties of P as possible. So what do we want in 28 00:03:06,028 --> 00:03:12,296 terms of sparsity? Something that is fairly basic that we might choose to 29 00:03:12,296 --> 00:03:19,079 require is what's called a minimal IMAP. That is, we want an IMAP for the 30 00:03:19,079 --> 00:03:25,862 distribution P that at least doesn't have redundant edges. So for example, if we 31 00:03:25,862 --> 00:03:31,985 have a graph X. Y, where Y really doesn't depend on X in the sense that P of Y 32 00:03:31,985 --> 00:03:38,225 given, say, X zero in the CPD is equal to P of Y given X one, then we could remove 33 00:03:38,225 --> 00:03:44,542 this edge and still have something that was an iMAP for this distribution. And so 34 00:03:44,542 --> 00:03:50,782 this edge is now redundant, and so from our definition that would mean that this 35 00:03:50,782 --> 00:03:57,100 iMAP is not minimal because you can have an iMAP from which edges can be removed. 36 00:03:58,040 --> 00:04:03,850 So that might seem to be a reasonable strategy but it turns out that it's not 37 00:04:03,850 --> 00:04:09,734 sufficient in terms of insuring that our graph is as sparse as it might be. So to 38 00:04:09,734 --> 00:04:16,134 understand why that's the case let's look at a distribution such as that corresponds 39 00:04:16,134 --> 00:04:22,386 to this example that we've seen before where the student's grade G depends on these two 40 00:04:22,386 --> 00:04:28,125 variables I and D. So that in fact is a minimal iMAP for a distribution where D 41 00:04:28,125 --> 00:04:33,989 and I are independent and G depends on both of them. But it turns out that this is 42 00:04:33,989 --> 00:04:39,128 not the only minimal iMAP for distribution. A different minimal iMAP is 43 00:04:39,128 --> 00:04:47,550 this one. Where we have an edge that goes from D to I, from D to G, and from G to I. 44 00:04:47,550 --> 00:04:53,041 Let's convince ourselves that in fact this is a minimal iMAP. Let's try and remove 45 00:04:53,041 --> 00:04:58,734 any one of those edges and see if we still get an iMAP for the original distribution. 46 00:04:58,734 --> 00:05:04,226 So if for example we try and remove this edge, that would correspond to 47 00:05:04,226 --> 00:05:09,450 a statement that D is independent of G which is certainly not the case in our 48 00:05:09,450 --> 00:05:15,220 original distribution. So that one doesn't work. What about the second one. If we try 49 00:05:15,220 --> 00:05:22,353 and remove the second edge from G to I that would correspond to a statement that 50 00:05:22,353 --> 00:05:33,378 D, sorry, that G is independent of I, given D, which is also not the case in our 51 00:05:33,378 --> 00:05:40,332 original distribution. What about the final edge, the one that doesn't 52 00:05:40,332 --> 00:05:45,648 correspond to an edge in our original network. This one. Can we remove that one? 53 00:05:45,648 --> 00:05:52,123 That one seems most promising of the lot but if you remove that one it would 54 00:05:52,123 --> 00:05:58,255 correspond to the assumption that D is independent of I, given G. And that is 55 00:05:58,255 --> 00:06:03,840 exactly the dependence that is induced by inter-causal reasoning that we've seen 56 00:06:03,840 --> 00:06:09,012 before. So in fact, this is a minimal I Map. None of the edges can be reduced. 57 00:06:09,012 --> 00:06:14,667 There is a better minimal I Map, but this is a minimal I Map. So minimal I Maps are 58 00:06:14,667 --> 00:06:19,770 not necessarily the best tool for capturing structure in the distribution. 59 00:06:19,770 --> 00:06:25,262 What we'd really like is a perfect map. A perfect map is one where the independencies 60 00:06:25,262 --> 00:06:30,353 in G exactly corresponds to the independencies in P. So the G perfectly 61 00:06:30,353 --> 00:06:35,444 captures the independencies in P. And sure enough if we could get that, that 62 00:06:35,444 --> 00:06:41,382 would be ideal. Unfortunately perfect maps are often hard to come by. So here's an 63 00:06:41,382 --> 00:06:48,010 example of one scenario that doesn't have a perfect map. This is a distribution P 64 00:06:48,010 --> 00:06:54,398 that is actually represented by this pairwise Markov network that 65 00:06:54,398 --> 00:07:00,943 we've seen before. So, one where we have pairwise interactions ab bc cd and ad. 66 00:07:00,943 --> 00:07:07,297 So we know that this distribution satisfies certain independencies, because 67 00:07:07,297 --> 00:07:11,995 of the Markov network property. Specifically we know that, a is 68 00:07:11,995 --> 00:07:17,849 independent of c, given b and d, because b and d separate a and c in the graph, and 69 00:07:17,849 --> 00:07:23,228 at the same time we know that b is independent of d, given a and c. So now 70 00:07:23,228 --> 00:07:29,832 that we, let's imagine that we have a distribution P that satisfies these 71 00:07:29,832 --> 00:07:36,688 independencies, so P satisfies this pair of independencies, and now 72 00:07:36,688 --> 00:07:43,796 let's try and code those independencies using a Bayesian network as a perfect 73 00:07:43,796 --> 00:07:52,192 map. Let's try. One possible attempt would be to just try and direct the edges say 74 00:07:52,192 --> 00:08:00,947 this way. Is that an iMap for this distribution? Well, among other things one 75 00:08:00,947 --> 00:08:09,029 of the independencies implied by this graph would be that B is independent of D 76 00:08:09,029 --> 00:08:16,333 given A. And that's certainly not supported by the original distribution. So 77 00:08:16,333 --> 00:08:25,060 this in fact is not an iMap. So try a different way of organizing the edges. 78 00:08:26,220 --> 00:08:44,252 So, for example. Here we have, sure enough, and this is good, that B 79 00:08:44,252 --> 00:08:53,820 and D are independent given A and C. And that's one of our independencies that 80 00:08:53,820 --> 00:08:59,792 we had before so it captures correctly that one. But, if, but, not all, but, it 81 00:08:59,792 --> 00:09:06,424 doesn't capture the but it also makes other independent assumptions that are not 82 00:09:06,424 --> 00:09:12,740 true in the original distribution. For example, that A and C, are marginally independent. 83 00:09:14,020 --> 00:09:20,276 And, that's certainly not true in the original distribution. So once again, this 84 00:09:20,276 --> 00:09:28,023 is not, an I-map. What is an I-map for this distribution as a directed graph? 85 00:09:28,023 --> 00:09:35,491 Well, one possible iMAP for this distribution as directed graph. Here's 86 00:09:35,491 --> 00:09:45,428 several. Is this one? And, you can confirm that this distribution satisfies, that 87 00:09:45,428 --> 00:09:53,565 this graph implies that A is independent of C. Given B and D. And that's it in 88 00:09:53,565 --> 00:09:59,312 terms of independencies. And so this in fact is an iMap for the distribution 89 00:09:59,312 --> 00:10:05,512 because in this case I of D is a subset of I of P, which is this set over here. But 90 00:10:05,512 --> 00:10:10,805 it doesn't capture all of the independencies. It only captures one out 91 00:10:10,805 --> 00:10:16,855 of the two. So this is the distribution that does have a perfect map as a Bayesian 92 00:10:16,855 --> 00:10:22,815 network. Let's come up, let's provide another example of an imperfect map. And 93 00:10:22,815 --> 00:10:28,597 in fact this is a distribution that doesn't have a perfect map as 94 00:10:28,597 --> 00:10:33,745 either a Bayesian network or a Markov network. And this is the 95 00:10:33,745 --> 00:10:39,669 famous example of the XOR which is as we'll see a counter example to many, many 96 00:10:39,669 --> 00:10:45,381 things. Here we have two random variables X1 and X2 which were assuming are binary 97 00:10:45,381 --> 00:10:52,908 valued and say... Each of them takes the value 0,1 with probability 50-50. Y on the 98 00:10:52,908 --> 00:11:01,240 other hand is the Exclusive Or of X1 and X2, which means that Y is equal to one 99 00:11:01,240 --> 00:11:09,574 if and only if exactly one of X1 or X2, is equal to one. Okay, so let's talk 100 00:11:09,574 --> 00:11:16,194 about, this probability distribution P, looks like, here it is, we have that, 101 00:11:16,194 --> 00:11:23,424 there's four possible configurations, that have nonzero probability, and, each of 102 00:11:23,424 --> 00:11:29,522 them, has equal probability of 0.25, so X1, X2, can be, either, zero, or, one, 103 00:11:29,522 --> 00:11:37,293 with probability 50-50, and, here is the value of Y over here. But now 104 00:11:37,293 --> 00:11:43,029 let's think about other, so let's see some independent statements are true for this 105 00:11:43,029 --> 00:11:48,499 distribution. So most obviously looking at this graph we see that X1 is marginally 106 00:11:48,499 --> 00:11:54,771 independent of X2. But if you close your eyes, on this part of the image 107 00:11:54,771 --> 00:12:01,819 And just look at the right hand side. You'll see that really X1, X2, 108 00:12:01,819 --> 00:12:08,868 and Y are all symmetrical in terms of their structure. So it's not difficult to 109 00:12:08,868 --> 00:12:15,658 verify that we also have that X1 in fact is independent of Y and X2 is 110 00:12:15,658 --> 00:12:22,505 independent of Y. And all three of these pairwise independencies hold in this 111 00:12:22,505 --> 00:12:28,862 distribution. And, so this is not in fact the, the, the graph on the left is not a 112 00:12:28,862 --> 00:12:34,650 perfect map for this distribution because there are independencies that hold in P 113 00:12:34,650 --> 00:12:40,165 that are not visible in the graph. And in fact you can organize the nodes in this 114 00:12:40,165 --> 00:12:45,612 graph any which way and, but you cannot get all three of these independencies 115 00:12:45,612 --> 00:12:50,923 captured at the same time. Because the only way to do that would be to have X1, 116 00:12:50,923 --> 00:12:56,234 X2, and Y be separate variables. And of course that wouldn't be an IMAP for the 117 00:12:56,234 --> 00:13:02,862 distribution. So we've talked about Bayes nets as a perfect map. What about Markov networks 118 00:13:02,862 --> 00:13:07,689 as a perfect map? The definition here is the same except that we've replaced G by 119 00:13:07,689 --> 00:13:12,093 H, so a Markov network H is a perfect map if the independencies 120 00:13:12,093 --> 00:13:17,161 encoded by H exactly correspond to the independencies in P, and can we capture 121 00:13:17,161 --> 00:13:21,927 all possible distributions in terms of a Markov network as a perfect map? 122 00:13:21,927 --> 00:13:26,694 So I'm sure you're all expecting, expecting your answer to be no, and sure enough that's true. 123 00:13:26,694 --> 00:13:30,880 So here is an example of a distribution that has a perfect map, in this 124 00:13:30,880 --> 00:13:35,742 case is as a Bayesian network, but not as a Markov network. So this is the famous 125 00:13:36,000 --> 00:13:41,596 V-structure example, in this case the Difficulty, Intelligence, Grade 126 00:13:41,596 --> 00:13:49,173 V-structure and let's think about what in the, what we need to encode as in terms of 127 00:13:49,173 --> 00:13:55,925 edges for being an I-map of this distribution. So clearly we need 128 00:13:55,925 --> 00:14:03,105 to introduce an edge between D and G and between I and G. Because it's certainly 129 00:14:03,105 --> 00:14:10,375 not the case that we can make D and G independent given I or vice versa. And so 130 00:14:10,375 --> 00:14:17,914 this would be the obvious I map for this distribution but this example if we choose 131 00:14:17,914 --> 00:14:24,466 this as, as a candidate I map it would imply among other things that D is 132 00:14:24,466 --> 00:14:31,503 independent of I given G. And that of course is exactly wrong because we know 133 00:14:31,503 --> 00:14:38,692 that when we condition on G, D and I become dependent and 134 00:14:38,692 --> 00:14:45,152 so the only iMAP. For this distribution is one that has all three edges, and that 135 00:14:45,152 --> 00:14:50,817 loses the independence we had over here, which is D is marginally independent of I. So 136 00:14:50,817 --> 00:14:56,205 once again, there's no perfect map for this distribution as Markov network. The 137 00:14:56,205 --> 00:15:02,215 final question that we might ask ourselves is, the extent to which a representation 138 00:15:02,215 --> 00:15:07,397 of a distribution is, in fact, unique. And so say that we could represent the 139 00:15:07,397 --> 00:15:12,163 distribution using some graph, say, as a perfect map. Is that a unique 140 00:15:12,163 --> 00:15:19,456 representation? So, to understand that let's look first at the simplest example. 141 00:15:19,456 --> 00:15:27,710 One where we have two variables X and Y. And here we have one graph that captures 142 00:15:27,710 --> 00:15:36,589 in this case no independence assumptions so I of G is equal to the empty set. G1 and 143 00:15:36,589 --> 00:15:42,785 here's G2. It looks the same except that the edges are inverted, the one edge is 144 00:15:42,785 --> 00:15:48,746 inverted. And, once again, this is a different graph that has exactly the same 145 00:15:48,746 --> 00:15:55,624 vacuous set of independencies. So we can see that here we have two distinct graphs 146 00:15:55,624 --> 00:16:01,956 that have the exact same of independent assumptions and because of that they can 147 00:16:01,956 --> 00:16:17,389 represent exactly the same set.of distributions. Which in this case 148 00:16:17,389 --> 00:16:23,232 is all distributions over the variables X, Y. Now, one might think that this is a degenerate example, 149 00:16:23,232 --> 00:16:27,957 because, it's a fully connected graph. But it turns out to be not the case, 150 00:16:27,957 --> 00:16:32,936 there are many other situations, where, two distinct graphs, with edges going in 151 00:16:32,936 --> 00:16:37,724 different directions, represent the exact same set of independence 152 00:16:37,724 --> 00:16:42,896 assumptions. So, for example, when we look at graphs over three random variables, it 153 00:16:42,896 --> 00:16:48,194 turns out, that, of these four scenarios, one of those represents adifferent 154 00:16:48,194 --> 00:16:53,110 set of independent assumptions than all the others, but, all the others are the 155 00:16:53,110 --> 00:16:58,982 same. So, which is the odd man out? Which of these following graphs does not encode 156 00:16:58,982 --> 00:17:05,045 the same independence assumptions as the others? As I'm sure most of you realize, 157 00:17:05,045 --> 00:17:11,328 the answer here is the V-structure, which is one that we've seen before. So this one 158 00:17:11,328 --> 00:17:16,734 has the independence assumption X is independent of Z marginally, whereas 159 00:17:16,734 --> 00:17:23,057 these other three. Have the independent assumption that X is independent of Z., 160 00:17:23,057 --> 00:17:28,901 given Y. So these three graphs, again, represent the same set of independence 161 00:17:28,901 --> 00:17:34,208 assumptions, which is this set over here. And as such, they also can take 162 00:17:34,208 --> 00:17:39,651 any probability distribution that can be represented by one of these graphs, can 163 00:17:39,651 --> 00:17:44,958 also be represented by another, by the other. So the formal notion for this, the 164 00:17:44,958 --> 00:17:50,333 formal term for this notion is what's called I-equivalence. Where two graphs 165 00:17:50,333 --> 00:17:56,693 G1 and G2 over the same space are said to be I-equivalent if they make the exact 166 00:17:56,693 --> 00:18:05,274 same set of independence assumptions. And in the previous example we saw for example 167 00:18:05,274 --> 00:18:17,505 that X, Y, Z is I-equivalent to say. Y being a parent of both X and Z, and. This 168 00:18:17,505 --> 00:18:23,213 third one over here, whereas the V-structure is not I-equivalent. 169 00:18:23,213 --> 00:18:29,383 Now, why is I-equivalence an important notion? It's important because it tells us 170 00:18:29,383 --> 00:18:35,400 that there are certain aspects of the graphical model that are unidentifiable. 171 00:18:39,740 --> 00:18:44,742 Which means that if we end up, for whatever reason, thinking that, say, this 172 00:18:44,742 --> 00:18:49,881 is the graph that represents our probability distribution, it could just as 173 00:18:49,881 --> 00:18:54,952 easily be this one, or that one. So without prior knowledge of some kind or 174 00:18:54,952 --> 00:19:00,777 another, for example that we prefer X to be a parent of Y, there's no way for us to 175 00:19:00,777 --> 00:19:06,338 select among these different choices. And it turns out that this is not 176 00:19:06,338 --> 00:19:11,367 an exception, rather it's the rule. Most graphs have a large number of 177 00:19:11,367 --> 00:19:16,680 I-equivalent variants. And that turns out to be a complicating 178 00:19:16,680 --> 00:19:22,623 factor, especially when we get to learning models from data. So in summary, we prefer 179 00:19:22,623 --> 00:19:28,176 to have graphs that capture as much of the structure in I(P) as possible, because they 180 00:19:28,176 --> 00:19:33,336 are more compact. Therefore easier to learn and easier to inference with, and 181 00:19:33,336 --> 00:19:38,953 also provide us with more insight about the distribution. We talked about minimal I-maps, 182 00:19:38,953 --> 00:19:44,132 as one option for sparse graphs and we showed that, that's not a 183 00:19:44,132 --> 00:19:49,377 particularly good option because it might fail to capture structure even if 184 00:19:49,377 --> 00:19:54,753 it's present in the distribution and even if it is representable, as a Bayes net, or as 185 00:19:54,753 --> 00:20:02,366 a graphical model. A better notion is a perfect map, which is great, but there are many 186 00:20:02,366 --> 00:20:08,195 cases where a perfect map might not exist. And we've also seen that when we take a 187 00:20:08,195 --> 00:20:12,885 distribution that was naturally represented as a Bayes net, and tried to 188 00:20:12,885 --> 00:20:17,639 represent it as a Markov net, as a, we generally do not get a perfect map, we 189 00:20:17,639 --> 00:20:22,519 lose independencies and vice versa. Something that was naturally represented 190 00:20:22,519 --> 00:20:27,463 as a Markov net, you try and encode it as a Bayes net once again, you lose 191 00:20:27,463 --> 00:20:32,153 independencies. Specifically, when we go from a Bayes net to a Markov 192 00:20:32,153 --> 00:20:37,661 network, we lose the independencies in V-structures. And when you go from a 193 00:20:37,661 --> 00:20:44,781 Markov network to a Bayesian network, we need to add edges that inside, loops like 194 00:20:44,781 --> 00:20:52,914 the, A, B, C, D Loop. We had to add this edge in the middle. An edge typically 195 00:20:52,914 --> 00:20:59,480 called a triangulating edge, because it turns the loop into a pair of triangles.