Hi, in this module, I'm going to formally define
constraint satisfaction problems and the more general notion
of a factor graph.
So let's begin with an example, a voting example.
So imagine there are three people.
Person one, person two, and person three, and each one
is going to cast the vote, either blue or red,
blue or red, blue or red, and we know
something about these people.
We know that person one is definitely
going to vote blue here, and we know that person three
is leaning red.
We also know that person one and person two
are really close friends, so they must agree on their vote,
whereas person two and person three are mere acquaintances,
and their votes only tend to agree.
So the question is how all these people
are going to influence each other,
and ultimately, cast votes?
So we can model this problem using a factor graph.
We're going to define a set of variables.
X1 for person one, X2 for person two, X3 for person three,
and we're going to define a set of factors
that capture each of these four constraints or preferences.
So let's begin with f1.
f1 is going to capture the fact that person one is definitely
blue.
So I'm going to write f1 as specifying as a table,
specifying for each value of x1.
I'm going to specify a number.
So f1 of x1 is going to be 0 if x1 as red,
and it's going to be 1 if x1 is B or blue.
And this captures the fact that a 0
means no way this is going to happen, and 1 means it's OK.
So mathematically, I can write this factor,
f1, as an indicator function of x1 equals B. So now,
I'm going to write these indicator functions without--
usually, you would write a 1 here,
because it's going to drop it for notational simplicity.
So let's look at leaning red.
So this factor is going to be x, f4,
and this is also going to correspond to a table
where for every possible value of x3,
I'm going to specify a value.
So R is going to be 2, and B is going to be a 1.
And mathematically, this is going
to be f4 is equal to x3 equals R. This indicator, a function,
plus a smoothing constant of 1.
So remember, this indicator is going
to return 1 or 0 depending on whether its condition is
true or false, and I'm adding 1, so I offset that to a 2 or a 1.
So intuitively, you can think about this
as person three prefers R to B maybe twice as much.
So now, let's look at these other factors.
So f2 is going to represent the fact that person one and person
two have to agree.
So again, I'm going to look at all the possible assignments
to the variables in the scope of f2.
So these two variables, x1, x2, and for every value,
I'm going to assign a particular non-negative number.
So here, R, R. I'm going to say that's 1.
It's OK.
They agree.
And if they don't agree, I'm going
to return 0, because I really don't like that,
and if they agree, return B. That's agreed.
So that's a 1.
So more succinctly, I can write this factor as f2
as x1 equals x2.
And now, finally, for f3. f3 is going
to capture whether x2 and x3 tend to agree,
and this table is going to look like this for x2 and x3.
If they're both R, I'm going to return 3.
If they're different, I'm going to return 2.
And if they're all both B, then I'm going to return 3.
So mathematically, this factor is
going to indicate a function of whether x2 equals
x3 plus a smoothing factor of 2, which makes it, instead of 1,
0, 0, 1, that gives me 3, 2, 2, 3.
So there's a kind of a mild preference for these two people
to agree compared to not agreeing.
So now, if you click on this demo in the slides here,
this is going to take you to a little JavaScript application
here where you can actually write your own factor graph,
and we're going to come back to this later.
So this is a first example of a factor graph capturing
this simple voting situation.
So now, let's look at a different example
that we looked at in the overview module.
So this is map coloring Australia.
So remember, Australia has these seven beautiful provinces,
and each one needs to be assigned a color.
So each of these provinces is going
to be represented as a variable.
And here, I'm going to give area a variable and name.
WA for Western Australia, NT for Northern Territory,
and so on, and I'm going to use big X usually
to denote the set of all variables.
Each variable is also going to take
on a set of values, which in this case,
is going to be red, green, or blue.
And now, I'm going to define the factors of this factor graph.
So for every two neighboring provinces,
I want to say that they can't have the same color.
So for example, f1 is going to say
WA and NT must be different.
That corresponds to this factor over here.
f2 says NT and Q must be different,
and that's going to correspond to this factor
here, and so on and so forth.
So now, we're ready to formally define a factor graph.
So a factor graph is going to consist
of a set of variables, x1 through xn in the general case.
Remember, big X is going to denote
the set of all variables, where each variable xi
takes on values in some set of possible values known
as the domain of variable i.
And a factor graph also consists of a set of factors generally
denoted f1 through fm.
Each fj is going to be a function that
takes as input an assignment to the variables
and going to represent-- return a non-negative number.
So it's really important that this function
return a non-negative number instead of a negative number,
because later, we'll see that we're going to multiply them
together.
So that's the definition of a factor graph.
So a bit of terminology here.
So I'm going to define the scope of a factor
as a set of variables it depends on.
So in the map coloring example, the scope of f1
is going to be simply WA and NT.
This corresponds to, visually, the set of variables
that this factor is touching.
The arity of a factor is number of variables in the scope.
So in this case, you just count how many variables are here.
The answer is two.
Some shorthand notation.
So unary factors are ones that have arity 1,
and binary factors are ones that have arity 2,
and constraints are factors that return 0 or 1.
So notice that factor can return any non-negative number,
but a special case is when it returns 0 or 1, which
means yes or no essentially.
And in this context, f1 is a binary constraint.
So one thing to remember about factors
is that each factor usually depends only
on a subset of the variables, and not all the variables,
and this is going to be kind of important when
we talk about an algorithmic efficiency.
So now, we fully define what a factor graph
is, I'm going to now talk about the notion of assignment
weight.
So let's go back to the voting example.
In the voting sample, we had four factors corresponding
to whether person one and person three
were voting a certain way, and whether person one, person
two, and person two and person three agreed or not.
So an assignment is going to be just assignment of values
to each of the variables.
In this case, there's three variables, x1, x2, x3,
and each assignment is going to be associated with a weight.
So here's how the weight is going to be calculated.
I'm going to go through each of these factors,
and I'm going to plug-in this assignment
and read out a particular number.
So let's take this factor, f1.
So what is x1?
It's r.
So I'm going to get a 0.
What about this factor?
What is x1 and x2?
It's going to R, R. I'm going to return a 1.
I'm going to copy that down here.
What about this factor? x2 and x3 are R,
R. I'm going to get a 3.
And finally, the fourth factor, f4, what is x3?
It's R. So I'm going to read out a 2.
And all of the outputs of the factors are numbers,
and I'm going to multiply all of them together.
I'm going to get a weight, and that weight in this case is 0.
So now, you can go through all of
the other possible assignments of values to all the variables.
In this case, there are eight possible assignments,
and each of them is going to have a particular weight.
So now, let's look at the demo.
If you click step here, that's going
to run this inference algorithm and produce
a weight for every possible assignment that
has non-zero weight.
So in this case, we verified that there
are two possible assignments that have non-zero weight,
assigning BBR and BBB.
OK, so now, let's switch over again
to the map-coloring example just to see
how weights are computed here.
So here is a possible assignment of colors to provinces.
So here, notationally, I'm going to make a slight change.
It's going to be sometimes convenient to be representing
assignments in this kind of dictionary format,
where the variables have names.
So here, I have WA is assigned red.
NT is assigned green, and so on and so forth.
So literally, you can think about this as a Python
dictionary if you like.
What is the weight of this assignment?
Well, in this particular case, all neighbors
have different colors, and remember,
each factor is just going to thumbs up,
return 1 if the two adjacent neighbors
have different colors.
So I'm just going to go 1 times 1 times 1, and that's just 1.
Now, consider an alternative assignment, where I simply
replace NT with red here.
So NT becomes red, and now, we can
see that the weight of this altered assignment
is going to be 0, because these two factors are
going to evaluate to 0.
These two here, and one thing you might realize very quickly
here is that all it takes is for one factor
to veto the entire assignment.
Because we're multiplying, if one of the factors returns 0,
then the product of all the factors is also going to be 0.
So here is a general definition of assignment weight.
Assignment little x is going to be x1 through xn has a weight,
and this weight is a function that takes an assignment
and returns the product over all possible factors of the factor
fj applied to an assignment.
And here, even though each factor only
depends on a subset of variables,
I'm kind of simplifying notation by just passing
in the entire assignment.
In practice, I would only pass in only the variables
that are in the scope of fj.
So a bit of terminology.
An assignment is consistent if its weight is greater than 0.
A weight can't be negative because all the factors return
non-negative numbers.
So if a weight is 0, that means the assignment is inconsistent.
And the objective of a constraint-satisfaction
problem, finally getting to what the point of all this is,
is to find the maximum weight assignment.
Mathematically, it's written arg max
over all possible assignments x of the weight of x.
And a constraint-satisfaction problem
is said to be satisfiable if the weight of a maximum weight
assignment is greater than zero.
Another way to say the same thing
is whether there exists some consistent assignment.
And note one thing is that the weight here
in the context of factor graphs and constraint-satisfaction
problems are not the same as a weight
that we study in machine learning.
Those weights can be negative or non-negative,
but these weights in constraint-satisfaction
problems or factor graphs have to be non-negative.
One other small comment is that here we are actually
defining a slight generalization of constraint-satisfaction
problems where factors can actually
have not just 0 or 1 weights, but actually
any non-negative value.
So constraint-satisfaction problems actually
is a general umbrella term that captures
several important cases.
So the first is Boolean satisfiability problems,
otherwise known as SAT.
So in these cases, the variables are Boolean valued,
and the factors are a logical formula
such as x1 or not x2 or x5.
So satisfiability problems are NP-complete problems,
which means that in the worst case
they're really, really hard, and we
don't have efficient algorithms for solving them.
But in practice, it turns out that there's
been an extraordinary amount of progress in SAT solving,
and we can actually routinely solve SAT problems
with many, many more variables than we
might be able to predict by theory alone.
So there's a joke that says, theoreticians
reduce a problem set if they want
to show that it's hard to solve, and practitioners
reduce a problem to set if they want to solve the problem.
Another class of problems that is important
is linear programming, and in linear programs,
the variables are real-value numbers,
and the factors are linear inequalities
such as x2 plus 3x5 less than or equal to 1.
And despite the fact that variables
can take on an infinite number of values,
linear programs have the special structure
that makes them especially efficient to solve,
and there's been a lot of work in solving
linear programs efficiently.
Integer linear programs are same as linear programs,
except for the variables are integer valued,
and the fact that they're integer values
makes these incredibly hard again, just
like satisfiability problems.
Mixed integer linear programs are
problems where variables are reals and integers,
and these problems are also hard to solve.
So in summary, we formally defined the notion
of a factor graph, which includes variables and factors.
So variables specify unknown quantities
that we need to ascertain, and factors
specify preferences or constraints
for partial assignments.
And one thing that's special about factor graphs
is that you're specifying constraints and preferences
in a local way.
So suppose you're modeling, and you
think of a particular preference that you have,
you can just simply write down a factor in terms
of the variables that matter and throw
that factor into the constraint-satisfaction
problem.
And now, the hard work comes in actually processing
all these set of factors.
So a key definition is the weight of a possible--
an assignment is the product of all the factors,
and this is where all the magic happens.
This is where you have to think globally
about all the factors together, and the point
of a constraint-satisfaction problem, again,
is to find the maximum weight assignment,
and this is, again, something that
requires global reasoning over all the factors.
And so the model here to remember
is specify locally if you're modeling and optimize
globally, which is what the inference algorithm will do.
That's the end of this module.