Hi, in this module, I'm going to talk
about local search, strategy for approximately computing
the maximum weight assignment constraint satisfaction
problem.
So remember that a CSP is defined
by a factor graph, which includes a set of variables x1
through xn and a set of factors f1 through fm
where each factor is a function that
depends on a subset of the variables
and returns a non-negative number.
Each assignment to all the variables
has a weight given by the product
of all of the factors evaluated on assignment.
And the objective is to compute the maximum weight assignment
as usual.
So so far we've seen backtracking search and beam
search.
And both of these search algorithms
works by extending partial assignments.
You start with the empty assignments,
and then you assign one variable.
And you assign another variable until you
get to a complete assignment.
And then maybe you backtrack or maybe you don't.
So local search is going to be a little bit different.
It's going to modify complete assignments.
So you're going to start with a random assignment.
And then you're going to choose one variable and you change it.
You chose another variable and you change it,
more kind of like house maintenance
rather than building a house.
So one of the advantages of local search
is that gives you additional flexibility.
You can pick any variable and try to improve it.
Whereas backtracking search and beam search
you have to do things in a certain order.
For beam search, once you've assigned a variable,
you can't go back.
And backtracking search you can backtrack,
but you can't really kind of backtrack out of order.
So recall our running example, object tracking.
So at each time position, you observe a noisy sensor reading
of a particular object.
You observe 0, 2, and 2 as the positions of the object.
And you're trying to figure out where this object was.
So we demodel this as a CSP where
we have three of observational factors, o1,
which favors x1 equals plus 0, o2, which favors x2 equals 2,
o3, which favors x3 plus 2.
And we have two transition factors
that favor subsequent positions being close by.
So let's jump in.
And suppose we just have a complete assignment 0, 0,
1, OK?
My question is, how do we improve this?
Well, let's look at the weight of this assignment.
So the weight of this assignment is 2 because 0 agrees with 0,
times 2 because 0 agrees with 0, times 0--
oh-oh-- because these two are too far apart, times 1
because these only differ by 1, and times 1
because they differ by 1.
But you get a 0.
So that's not a very good assignment.
So how can we improve?
Let's try to reassign x2 to something else.
Let's try to assign it to some v where
we can set v equals 0, 1, or 2.
And for each of these, alternate assignments
and compute its weight.
And then we simply take the assignment
with the best weight.
In this case, it's this one, which sets x2 to 1.
Then we end up with a new assignment, which
is better than the old one.
So mission accomplished.
So we can refine this strategy a little bit more.
So suppose we're trying to assign x2.
The weight of a new assignment where x2 has been replaced
with some v is as follows.
So you're multiplying all the factors
in the CSP together, o1, t1, o2, t2, o3, t3.
But note that only some of the factors depend on v.
In particular, o1 and o3 don't depend
on v. So no matter what v is these
are the same, which means that we can ignore them and just
evaluate the factors that involve x2.
So this is like idea of locality, which leverages
the structure of the CSP.
When evaluating possible reassignments
to some variable xi, we only need
to consider the factors that depend on xi.
So in the factor graph where there's
lots and lots of variables-- and you're
trying to reassign one variable, which might
have a small neighborhood.
Then you're saving a lot of effort.
So now we're ready to define a local search
algorithm, which is called iterated conditional modes.
It sounds fancy, but it's really simple.
The idea is that we're going to start x to be
a random complete assignment.
And we're going to loop through x1 through xn.
And then keep on going until we converge or we run out of time.
What we're going to do is we're going to try to reassign xi.
OK, so we're going to consider each possible value
that xi could take on.
And then we're going to update the current assignment
x with that value.
OK, so this-- that produces an assignment xv.
And then we're going to compute the weights of each
of these xv's and choose the one with the highest weight.
Remember in computing the weight we only
need to evaluate the factors that touch xi.
And also notice that this looks remarkably like greedy search
or beam search.
There is a substantial difference
in that here x are complete assignments, not
partial assignments.
So this is not extending an assignment so much
as replacing xi with v. So pictorially what this looks
like is you start with x1.
So by convention, unshaded nodes are
the ones that are meant to be reassigned
and shaded ones are the ones that are fixed.
So you pick up x1.
And you say, can I change it to make it better?
And then you pick some value of x1.
Then you go to x2 and say, can I make--
change x2 to make this assignment better?
And then you go to x3.
And then you go back to x1 and say, hey,
can I make it better by changing x1 again?
You keep on going until it converges.
So here is a demo on the object tracking example.
So at the start of the algorithm,
we're just going to initialize this with a random assignment
0, 1, 2.
And it has a weight of 4.
And now I'm going to try to maximize variable 1--
x1 given everything else.
So let's consider alternative values of x1.
So it could be 0, 1, or 2.
For each of these, I'm going to compute its weight only
evaluating the factors that touch x1.
So in this case, it's only o1 and t1 that touch x1.
So I only need to evaluate those.
Compute the weights.
Choose the best one breaking ties arbitrarily.
So I choose x1--
0, which means I didn't change.
And now let me step.
So now I'm looking at 1 x2.
And can I change anything?
Nope.
What about here?
x3 assigned-- is assigned 2.
What can I do?
Well, I compute the weights.
And here I am choosing x3 to be 1, OK?
So I change that assignment.
And now I go back to x1 and iterate.
And it looks like I've converged because I'm not
changing anything.
So I've converged to an assignment
with a weight of 4, which, if you remember,
is not the optimum maximum weight assignment.
The maximum weight assignment is--
has weight 8.
So again iterative conditional modes
is going to give you an OK solution but not necessarily
the best one.
So convergence properties.
But the good news is that the weight of your assignment
is not going to go down.
It's going to always increase or stay the same each iteration.
And this is because when you're trying to reassign a variable,
you can always choose the old value
and maintain the same weight.
So any change must be increasing the weight.
So this means that it converges in a finite number
of iterations because there's only
a finite number of possible assignments.
So you can only increase the weight
a finite number of times.
This can get stuck in local optimum as we've seen.
And it's not generally guaranteed
to find the optimum assignment.
So just a quick note is that there's two ways around this.
One is that there is a variant of this
where you can change two variables or maybe
three variables at a time.
And that allows you to perhaps get out of a local optimum.
And another thing we can do is add randomness.
So at each step, we could just add--
choose the best option or just choose a random option.
And this will also allow us to escape these local optimum.
Or we can use something like Gibbs sampling, which
I'll talk about in a future module, which
will add stochasticity to ICM.
OK, so here is the summary.
So let me summarize actually all of the search algorithms
for CSP that we've encountered.
So first we looked at backtracking search.
There's a strategy is to extend partial assignments
and then backtrack when we get to the complete assignment.
The backtracking search is exact.
It computes the actual maximum weight of assignment.
And it's the only algorithm that we're considering
that does that in general.
But the main problem is that the time
can be exponential in the number of variables.
Then we looked at beam search, which extends--
also extends partial assignments.
And here we're trading off accuracy for time.
So this is approximate.
It will only give you an OK solution,
but it's linear in the number of variables.
And local search we saw iterative conditional modes,
which does local search by choosing
the best value of a variable at each given time.
It's a different strategy.
Here, we're starting with complete assignments
and modifying them to make them better.
So here it's also approximate, but it's fast just
like beam search.
OK, so that concludes this module.