Hi.
In this module, I'm going to talk
about beam search, a really simple algorithm
for finding approximate maximum weight assignments efficiently
when you're in a hurry and don't want
to incur the full cost of backtracking search.
So just to review, remember a constraint satisfaction,
or a CSP, is defined by a factor graph, which
consists of a set of variables, X1 through Xn,
where each Xi is some element of a domain,
i, and a set of factors, f1 through fm,
where each factor function, fj, is
a function that takes a assignment
and returns a non-negative number.
And usually, the factor function depends only
on a subset of the variables.
So each assignment, little x, to all the variables has a weight.
And that weight is given by simply the product
of all the factors applied to the assignment.
And the objective is to find the maximum weight assignment.
So let us revisit the object tracking example.
So in this example, we're trying to track an object over time.
And at each time step we record a noisy sensor
reading of its position.
So at time step 1 we see 0.
Time step 2 we see 2.
Time step 3 we see 2.
And the question is, what was the trajectory
that object took?
Is it this one, or this one, or something else?
We model this a problem as a CSP with x1, x2, and x3.
We defined factors that captured our intuitions
about the problem.
o1 captures the fact that the actual position should
be close to the sensor reading.
So 2 is the weight assigned to 0.
So 0X1 equals 0 as favored.
And x1 equals 2 is disallowed.
Similarly, o2 favors x2 equals 2.
o3 favors x3 equals 2.
And finally, the transition factors, t1 and t2
favor adjacent xi's, which are close.
So a distance of 0 will get a weight of 2.
Whereas, a distance of 1 will get 1, and so on.
And you can click on this demo to actually play with this CSP.
We'll come back to this in a bit.
OK, so this is the object tracking example.
So now, so far, we've seen backtracking search
as a way to compute maximum weight assignments.
And backtracking search essentially
does a exhaustive depth-first search
of the entire tree in the worst case, which can
take a very, very long time.
So how can we avoid this?
Well, we have to give up on something.
And what we're going to give up on is correctness.
So what we're going to do is simply not backtrack.
So let's start with something called the greedy search
algorithm.
So again, we start with an empty assignment.
We consider possible settings of, let's say, x1.
So let's say there's two possible settings.
And we're just going to choose one of them, whichever
ones has the highest weight.
And the weight, remember, of a partial assignment
is the product of all the factors
that you can evaluate so far.
Well, let's pick this one.
Again, let's set X2.
There's two possible ways to set it.
Let's pick the better one and keep
on going until we reach a complete assignment.
And then we just return that.
So formally, what greedy search is doing
is starting with a partial assignment, which is empty.
And then it's going through each of the variables, X1
through Xn.
I'm going to try to extend the partial assignment to set Xi.
So for each possible value that I can assign Xi,
I'm going to form a potential candidate partial assignment
and call it Xv.
And then I'm going to compute the weight of each
of these Xv's, and then choose the one with the highest
weight.
So an important caveat is this is definitely not guaranteed
to find the maximum weight assignment,
even though locally it appears to be optimizing and finding
the value with the best weight.
So let's look at this demo to see how
it works on object tracking.
OK, so here we have the CSP that's defined.
And I'm going to step through this algorithm.
So initially, I extend the empty assignment
to assignments that only fill in X1.
So X1 could be 0, 1, or 2.
And these are the weights of these three
partial assignments.
Remember, the sensor reading was 0.
So therefore, X1 equals 0 has a larger weight.
So next step, I prune.
I keep only the best candidate, which in this case,
is X1 equals 0.
So then I go to i equals 2.
And I extend that assignment to three possible settings of X2,
compute their weights.
And then I keep the best one, which in this case is 0, 1.
And now I extend again to X3.
Three possible values to set X3, compute
the weights of these now complete assignments.
And then I choose the best one.
So in this case, greedy search ends up with assignment 0, 1,
1, with a weight of 4.
And if you remember this example,
the best weight assignment have weight 8.
So 4 is definitely not the right answer.
But it's not 0 either.
It found something.
OK, so what's the problem with greedy search
is that it's too myopic and only keeps the single best
candidate.
So beam search is just the natural generalization
of greedy, where I'm keeping at most K candidates
at each level.
So let's say K equals 4.
So I'm going to start with empty assignment.
I'm going to extend.
And then I don't need to prune.
Because there's only two possible partial
assignments here.
And I have a capacity of 4.
I'm going to extend again.
Again, I don't need to prune.
But then next, I'm going to extend
each of the elements on my beam, the partial assignments,
extend each of these.
And now, I have 8.
And now, I need to reduce the 8 partial assignments to 4.
And to do this, I'm going to simply compute
the weight of each of these 8 partial assignments,
and then take the four which have the highest weight.
And now let's suppose those are these four.
And then I continue only expanding the ones I've kept
and then keeping the ones, again, the top four,
and then keep on going.
So notice that visually I'm exploring only a very, very
small fraction of the tree.
But I'm doing this kind of holistically,
looking down the tree at kind of multiple--
I could be exploring different parts
of the tree at the same time.
So formally, beam search keeps most K candidates
of partial assignments.
I'm going to initialize the candidate set
to be just the single partial assignment, which is empty.
Now again, like greedy search, I'm
going to go through the variables one at a time.
I'm going to extend.
In this case, I'm going to consider
each partial assignment in C and each possible value
that it can assign Xi.
And I'm going perform the extend the assignment.
And I'm just going to keep track.
C prime is going to be the new set of candidates.
And then now I'm going to prune that set
by computing the weight for each element of C prime
and just keeping the top K elements.
So this is not guaranteed to find the maximum weight
assignment either.
But sometimes it works better.
So let's look at this example, object tracking and extend
from the empty assignment to get three partial assignments
to X1.
I prune to the top three, so nothing gets removed.
I then extend.
So each of these three partial assignments
gets extended into three additional ones.
Now I have nine.
And now, I'm going to prune down from nine to three.
So that will keep all the assignments here
with a positive weight.
And now I extend again to find settings of X3,
compute each of these weights.
And then I'm going to take the top assignments.
OK, so now, notice that the top assignment
that I have right now is 1, 2, 2 with a weight of 8.
And in this case, I got lucky.
And I found actual max weight assignment.
But in general, you won't be guaranteed that.
OK, so what is the time complexity of beam search?
Because one of the advantages is that it's supposed to be fast.
So let's do a simple calculation here.
So suppose we have n variables, which
is the depth of this tree.
And suppose that each of the variables
has b elements, which is going to be
the branching factor here.
And then the beam size is K. So what is the time that it
takes to run beam search?
It's going to be for each of the variables, each level
of this tree, we're going to have a set of candidates which
is of size K. And the extension phase
is going to take each of these K and extend it
into b candidates.
So then I'm going to end up with Kb extended candidates total.
And then I'm going to have to take the top K.
So the time it takes to take a list of Kb elements
and select the top K elements is Kb log K by building a heap.
So the total time is nKb log K. And importantly,
this is linear in the number of variables.
Whereas, backtracking search would
be exponential in the number of variables.
OK, so let us summarize now.
So beam search is a fairly simple heuristic
to approximate maximum weight assignments.
And it's really done if you're really in a hurry and you
don't really care about getting maximum weight assignment,
because you probably won't.
So the nice thing about beam search
is it has this parameter, K, which
allows you to control the trade off between efficiency
and accuracy.
So if you're really in a hurry, you set K equals 1.
You just get greedy search, which sometimes actually gets
you pretty good answers.
And if as you increase K more and more,
if you increase K to infinity, then you'll
definitely search the entire search tree.
And you will get the optimal answer.
But this is basically exponential time.
One thing to know about beam search with K
equals infinity it is performing a breadth first search
of the tree.
Because it performs level by level.
And it explores all of the nodes in a tree systematically.
So using this analogy, I want to end with a final note here,
which is that backtracking search is really
like doing a depth first search on the search tree.
It dives deeply into one complete assignment,
and then backtracks, and then finds
another complete assignment and backtracks,
looking kind of one assignment at a time.
Whereas, beam search is more akin to breadth first search,
where we're proceeding level by level.
But the main difference with breadth first search
is that we're doing this heuristic pruning at each level
to make sure that we don't have too many candidates.
And the way it's using that, doing that pruning
is based on the factors that it can evaluate so far.
So for beam search to work, you really
need it to be the case that the factors are local
and they can be evaluated as much as possible along the way,
and not all at the very end.
All right, so that's the end of this module.