CSPs
Constraint Satisfying Problems (CSPs)
CSPs are factor graphs where each factor are constraints. That is, our factor returns 0 if the constraint is not satisfied, or 1 if it is.
- Thus, if all constraints are satisfied, then the weight of that assignment is 1 (that assignment is consistent). Else, if even a single constraint is not satisfied, weight = 0 (that assignment is inconsistent).
Factor Graphs
Variables (X1, X2, ...)
Each variable is assigned a value within its domain.
Factors (f1, f2, ...)
Given input variables, a factor f returns a non-negative number. If the factor is not satisfied, then the convention is to return 0.
Scope
The scope of a factor f is the set of variables the factor depends on.
Arity
The arity is simply the number of variables within the scope.
Examples
- Unary factors (arity 1)
- Binary factors (arity 2)
Assignment
An assignment is when we specify values (within each variable's domain) for each variable.
Weight
Given an assignment, weight is simply a product of all factors.
Objective: Maximum Weight Assignment
We want to find the optimal assignment, such that the weight is maximized. I.e.:
How to solve?
Backtracking
This is the generic backtracking algorithm:
What is this doing on a high level?
Basically, keep assigning variables until you've got a consistent assignment.
Dynamic ordering (Choosing an Unassigned Variable Xi)
Can be either the most constrained variable (fail early), least constrained value (try to succeed quickly).
Lookahead/Forward Checking
Once we've assigned value to a variable, we can look ahead at variable domains that could be affected by the current variable's assignment.
- Not necessary, but by eliminating values in the other variables' domains, we reduce the search space.
- If some variable has an empty domain, then we know we can quit early, since there's no value that can be assigned to that variable.
Arc Consistency (AC3)
Key idea: eliminate values from domains, which reduces branching and thus the search space.
- Algorithm: For each variable, and enforce arc consistency on that variable with each one of its neighbors.
Can we do better?
Beam Search
Basically a greedy search. I.e. make locally optimal decisions in hope of finding a globally optimal solution.
- In the case of CSPs, we take our partial assignment, and make an additional variable assignment such that the current weight of the partial assignment is maximized. We repeat the process until we've got a full assignment.
Time Complexity
Even with the optimizations described in the red boxes on the right, we still have the same worst-case time complexity.
CS221 - Stanford University
Major Drawback
Not guaranteed to find an optimal solution!
Candidate List
To increase the chance of finding a globally optimal assignment, maintain a candidate list. That is, instead of maintaining a single best partial assignment, maintain the top K partial assignments.