0:00

When we discussed Variable Elimination. We said the Variable Elimination is

Â correct no matter the elimination ordering that's used.

Â But we it also showed that the elimination ordering can make a very

Â significant difference in the computation complexity of the algorithm.

Â So that embeds the question of how we find a good elimination ordering.

Â Fortunately, the computational analysis based on graphs that we recently did

Â gives us an intuition into how to find good elimination orderings.

Â Because it turns out that the [INAUDIBLE] used graph and it, the way in which it.

Â In the case the complexity of Variable Elimination can allow us to construct

Â good me- methods for finding elimination orderings with good computational

Â properties. How good of an elimination ordering can

Â we construct? So, here's yet another example of the

Â fact that any interesting problem is empty heart.

Â So the following problem is empty heart also.

Â For graph H, determining whether there exists any elimination ordering alpha for

Â which the induced width in less than or equal to some fixed value K, that problem

Â is NP complete. So you might say to yourself, well that's

Â not surprising. I mean, probabilistic inferences end

Â incomplete so obviously finding a really good elimination ordering is going to be

Â NP complete. Turns out, that this is a separate NP

Â NP-hardness problem. That is, even if you could solve this

Â problem, even if somebody gave you the best elimination ordering, you're still

Â going to have graphs for which the width is sufficiently large so that you can't

Â actually solve the problem polynomial type.

Â So finding the best induced width, or, sorry, the elimination ordering that

Â gives you the best induced widths does not, give you polynomial type

Â performance, in general, and so these are two separate NP-hardness problems.

Â 1:58

So how do you find a good elimination ordering? Fortunately simple heuristics

Â actually do pretty well. So one standard way of finding good

Â illumination ordering is to simply do a greedy search eliminating one variable at

Â a time. Where at each point in the elimination,

Â you've used some kind of heuristic cost function to decide which variable your

Â going to eliminate next. And there's some obvious cost functions

Â to use and it turns out that surprisingly they work pretty well.

Â So, for example, one cost function is what's called min-neighbors.

Â Which is to pick the node that has the minimal number of neighbors in the

Â current graph. So you want to pick the variable that's

Â connected to the fewest friends so it has the smallest party or produces um., the

Â smallest factor. So this corresponds to the smallest

Â factor or the one whose cardinality is smallest,

Â enters number of variables. Min-weight accounts for the fact that

Â sometimes you have variables that have 100 values and others that have two

Â values, and if you just count variables, you're going to ignore that distinction.

Â So min-weight computes the weight or the total number of values in the factor

Â form. So min-weight is a way of capturing the

Â fact that if you have two variable each of which has 100 value you might prefer

Â to never the less take a factor that has five variables each of which has only two

Â values. so these just look at the size of the

Â factors formed and they ignore the fact that some of these factors might be

Â inevitable. So a different strategy is to look at how

Â much extra work is caused by the elimination ordering.

Â So min-fill is a strategy that says, if I eliminate this node, how many nodes that

Â weren't friends before become friends due to this elimination step?

Â So here basically, I'm counting added complexity above and beyond the

Â complexity that I would have had from the edges that I previously generated.

Â And finally, again you have a weighted version of the fill heuristic that takes

Â into account not just the number of edges but also how heavy they are.

Â That is how big are the what's the car, what's the domain size of the variables

Â that they connect. And it turns out that min-fill which is

Â actually quite often used in practices a pretty good heuristic Now once important

Â way of understanding the issues of finding elimination orderings is by is by

Â looking at the following result. And the result tells us that the induced

Â graph that is produced by Variable Elimination, regardless of the

Â elimination ordering, is triangulated. So what does triangulated mean?

Â Triangulated means that you cannot have a loop of size more than three that doesn't

Â have a bridge an edge that goes in one direction or another.

Â So that there is a way of crossing across that loop without going all the way

Â around. Let's convince ourselves that this is

Â true. So here's here's a simple proof.

Â So once again assume, assume, so consider a set of variables that, and assume by

Â contradiction that there is a loop like this.

Â So for example assume that we have a loop,

Â outsize greater than three. And again, one of these variables has to

Â be the first to be eliminated. So assume that C is first to be

Â eliminated. Well once we eliminate C we end up

Â introducing an edge between B and D and so there has to be and edge between those

Â two neighbors of C. Because when C is eliminated the CD edge

Â must exist the CB edge must exist because as we observe the before you don't add

Â any neighbors to C once you eliminate it. And so at that point a fill, a fill edge

Â must be added. Though, it turns out that one way to find

Â an elimination ordering, an alternative to the heuristic that I mentioned

Â earlier, is to find a low-width triangulation of the original graph. And

Â there's been a lot of work in the graph theory literature on triangulating graphs

Â which we're not going to talk about, but it turns out that you could use all that

Â literature for finding good low-width triangulations and then use that for

Â constructing an elimination order. So now, let's convince ourselves that

Â this can make a big difference. So let's consider a practical application

Â and this is an application to Robot Localization & Mapping.

Â So what we're going to see here is a robot moving around and at each point in

Â time, it sees several landmarks, and it knows which landmarks it sees,

Â it can recognize them. And what it senses at each point is some

Â kind of approximate distance to the closest landmark.

Â So lets, write that down as a graphical model.

Â The graphical model looks something like this.

Â We have, at each point in time, a robot pose.

Â Which is the robot pose at time zero one up to the end of the trajectory T. And we

Â have a set of landmarks, whose positions are fixed the landmarks

Â don't move. So notice that these are not random

Â variables that change over time. They're just there, and they're, and

Â they're constant. And what you see here in gray are the

Â observations, so this, for example, assumes that at Time one,

Â Robot saw landmark one. And so what we have here is the

Â observation the observe distance is the function of the robot pose,

Â and the landmark position. And here at time two, we have that the

Â robot saw landmark two so we have this dependency over here.

Â And it lent at time three the robot also saw landmark two so you have two

Â observations for the same landmark. In here, I didn't draw the fact that you

Â could actually see the same landmark so you can see more than one landmark at any

Â at a given point in time but that also is easy to add in,

Â 9:01

okay? So now, if we take the previous robot

Â trajectory that we saw and we write down the, the Markov network that represents

Â the factors, we see that we have these light blue little dots.

Â That represent the robot pose at every point in time.

Â We see that we have these temporal persistence edges that represent the fact

Â that the robot pose at time T is correlated with this position of time T1.

Â plus one. And we have these dark blue robot pose

Â variables that, sorry these dark blue landmark position

Â variables where we see that a landmark is connected to all of the positions at

Â which it was visible by the robot. And this is an edge that's induced by the

Â V structure that we have over here. So this is an edge that's induced by this

Â V structure which we have because Z1's been observed,

Â okay? So, does landmark, does elimination

Â ordering matter? Oh boy.

Â This is what you get when you eliminate the robots poses first, and then the

Â landmark. And this, what you see here, is the

Â induced graph. And you can see that you get this huge

Â spaghetti where most of the landmarks are connect to every, to all other landmarks,

Â okay? What about a different elimination

Â ordering? This one's already better.

Â This is what happens when you eliminate landmarks and then poses and you see the

Â induced graph that you get over poses. And you can see that it's still pretty

Â densely connected but it's not nearly as bad as the spaghetti that we had before.

Â And finally, let's look at the result of min-fill elimination, so this is what you

Â are seeing is the fill edges being constructed.

Â And you can see that it's actually very sparse.

Â Lets look at it again, very few fill edges are actually added

Â over the course of the trajectory. And so there is, so the elimination

Â ordering makes a very big difference. In summary, we've seen that finding the

Â optimal elimination ordering is an NP-hard problem.

Â And that is an NP-hardness that is different from the intrinsic difficulty

Â of inferencing graphical models. However, we've also shown that the graph

Â based view variable of elimination gives us a very, a set of very and intuitive,

Â heuristics, that allow us to construct good elimination orderings.

Â And those work by looking at the induced graph as it's constructed in the course

Â of Variable Elimination. And trying to keep it snall and sparse.

Â These heuristics although simple and certainly potentially not providing not

Â the performance in the worst case are often quite reasonable in practice and

Â are very commonly used.

Â