Very important insights about variable elimination and how to best pick the elimination ordering is provided by thinking about the operations of variable elimination execute as operations on a graph. So let's see what that does. So let's consider the initial graph in our example. And let's, first view this graph in terms of the factors that it involves. so if this is the set of factors that we have in in our analysis, viewed as undirected, view, viewed as, simply as factors. so what is the structure of the graph that corresponds to the set of factors. Well, first, we're going to make all of the edges undirected, but that's not enough, because we see, for example, that we have a factor here, which is a factor over G, I, and D, and so, what we need to do is we need to add an edge between I and D to represent the fact that they're together in the factor. Other examples in the other cases where we need to correspond to the other V structures that we have in the scruff. So here for example we have a V structure involving J so we're going to need to connect J's two parents and similarly for H's two parents. This step, by the way, is called, not by me, a moralization. Because of the dubious moral value of marrying the parents of a child, no matter how many of them there are. and so I did not invent that name. So having moralized the graph, we now have this version of it. And this is what we previously defined to be the induced Markov network for the current set of factors. So now let's think about a variable elimination step and what it does to this graph. So let's begin by eliminating c. And if you remember that involved this operation. And so first eliminating c is hey changing the set of factors. It removes these two factors over here from the set and introduces a new factor tau 1 of d. So the induced graph is now going to look like the following. We've taken C out, and this, the remainder is the induced graph over the set of tau. Okay? Now, we're going to continue. We're going to eliminate d. So, once again, we're going to take the two factors that we've now introduced. sorry. These two factors that in-, are involved here, which is tau 1 of d, and phi g of g, I, and d, going to to multiply them, and going to eliminate d. And so, the resulting, and then the resulting graph is now going to look like this. Were again, the the nose, with the, with the dashes edges are not really there. They're just there to remind us that they were there before. Continuing on, we're going to eliminate I. And that involves multiplying in, this term, this term, and this term. And now, something interesting is going to happen. The factor that we introduced, which is tau 3 of S and G is a factor that doesn't have an edge in the current graph. So, if we're interested in having this graph represent our current set of factors, we're going to need to introduce this edge between G and S. Because that edge and, is necessary because S and G are together in the same factor. So that edge is called a fill edge. It's an edge that I have to introduce. Because of the elimination ordering. So one way to think about this is is using the following example. Imagine that every variable that's eliminated is going off on a trip around the world. And when it's doing that it's throwing a big goodbye bash, and inviting all of its friends to come an join it. And when it does that all of its friends get to meet each other and say, oh. You, you guys are nice. I'm going to be your friends to. And so all, of the, friends of the variable that's eliminated become friends, as a consequence of the elimination step. Okay? So let me write that down, all variables. Connected. Two. In this case I, become connected, after it's eliminated. So become connected directly. And that's a general, consequence of the elimination step process. It's just that the previous ones didn't happen to introduce filedges. 'Kay? Let's continue. so now we're going to eliminate H. H also doesn't introduce any fill edges and so we're going to end up with that. And basically the remaining steps are pretty mundane. We're going to eliminate G, L and S and we're going to end up with the following graph. So this particular variable elimination process only introduced one fill edge which is a fairy conservative thing. It shows that we, that we selected a pretty good elimination ordering in this case. So we can now take and put all of these edges that we that we ended up using, together in a single graph. And that graph is called, the induced graph. And the induced graph which is denoted I for induced. Phi comma alpha over a set of factors phi. And induced by a particular ordering, alpha, because you remember that we were getting different complexities. And we're going to have different fill edges. depending on the order in which variable are eliminated. So this variable, this induced graph has the following properties. It's an undirected graph, where we connect every pair of variables xi and xj, if they ever appeared in the same factor, when we ran variable elimination using alpha as the ordering. And so, in this case, all of the original, all of the black edges were there to begin with, and we ended up introducing just one of those additional, new, or fill edges. So now, let's, there's some interesting properties of the induced graph that are worth noting. First of all, there's some, there's properties that relate factors produced during variable elimination. And cliques in the induced graph, so first of all let's define what a clique is. A clique is a maximal. Fully connected sub-graph. So lets parse that to. So for example, DIG here, is a fully connected subgraph, because all of its three nodes are connected to each other. And it's maximal, because I can't add any other variable to this and still have that property whole. So if I try and add S, for example, then S is not connected to D. If I try and add C, C is not connected to I or G. So I can't add any other variable to this particular clique. So it's a clique. here's a clique that's not maximal. So, here is, so it's not a clique, so GLA is a connect, fully connected subgraph. But it's not maximal, because I can add S, and still have that hold. So here is another clique in this graph. So we have GID being one clique, GSL and J being another clique. we're going to have a third one, which is G, S, and I. Another one which is CD. And let's see if I have enough colors to do this. And a final one, which is g, h and j. And, if we now look at the factors that we produced in the in the course of variable elimination, we see that there is an exact correspondence between the factors and those cliques. So here, for example, the yellow one is CD, which is this one over here. this one over here, which is GID, is the red one. This one. So that's the red one. This one has sig, so that's the green one, this one. This one is a to d j, which is the brown one. Tau 5 induces the big factor, the one that involves four variables, and that's the blue factor over G, S, L and J. And this one doesn't actually introduce any new kleeks which is why it doesn't have any kleeks, associated with it. So every factor produced during variable elimination is a kleek in the induced graph. Hm. We can equally well check, and we saw that in the previous slide already, that every maximal clique in the induced graph is a factor that's produced during variable elimination. So we've demonstrated this to ourselves by inspection. But let's actually do a proof of this. So let's consider a maximal clique in this induced graph. So let's consider, for example, G, S, L, and J. That's a maximal clique, and now it's considered the run of variable elimination and one of those variables has to be, oops. One of those variables has to be the one to be eliminated first. So, some variable in this clique. One variable is first to be eliminated. Well what happens when a variable is eliminated? Once it's eliminated it it doesn't have anymore edges to, that get added to it. So once a variable is eliminated, it has no more, no new neighbors are added to it. Which means, that at the time that it was eliminated. It has all the neighbors that it had in the clique. All the clique members as neighbors. But, if that's the case. Then it means that it had factors involving all of those other guys. So it participated. In factors, with all these other values. And that means that when I multiply them all together. We're going to end up with a factor over all of them. And that is a proof that every maximal clique in the induced graph must correspond to a factor produced during a variable elimination algorithm. So now that we've constructed a graphical view of variable elimination, we can go ahead and construct a measure of the complexity of variable elimination. And that is a measure known as an induced, as the induced width. So, first we're going to define the width of an induced graph. Is the number of nodes in the largest clique in the graph, by convention minus one. Why minus one? No good reason, but that's what people that's the definition of induced width. The minimal induced width of the graph, is the minimum over all possible elimination orderings, alpha, of the width of the induced graph. So this is the best achievable complexity that one can aspire to with any elimination ordering. You can think of the minimal induced width of the graph as a lower bound on the best performance of variable elimination for any model that factorizes over the graph k. In summary we've seen that the variable elimination algorithm can be viewed quite intuitively as taking a set of steps, each which transforms the graph. Specifically a variable elimination step for a variable X takes all of X's neighbors that may or may not have been connected before and connects them to each other. The result of all this is something called the induced graph and we've seen that the induced graph is possibly quite connected as a result of this variable elimination process and that the cliques in this induced graph, that is the maximally connected subsets, maximally fully connected subsets, correspond directly to the complexity of the variable elimination algorithm and as we'll see can therefor help us analyze its computational properties.
