KRR: CSPs and Inference
Recap of Last Week
♦ Constraint networks consist of variables associated with (usually finite) domains and constraints which are (binary) relations specifying allowed pairs (or tuples) of values.
Copyright By PowCoder代写 加微信 powcoder
♦ A partial assignment maps some variables to values; a total assignment does so for all variables. A partial assignment is consistent if it does not violate any constraint. A consistent total assignment is a solution.
♦ The constraint satisfaction problem (CSP) consists in finding a solution for a constraint network. Applications are everywhere!
♦ Backtracking instantiates variables one by one, cutting branches when inconsistent partial assignments occur.
♦ Inference
♦ Forward checking
♦ Variable and value ordering
♦ Arc Consistency and AC-3
♦ Tightening CSPs by learning from mistakes ♦ Problem structure: constraint graphs
Simple example: Graph colouring
7 7 7 ✖✕ ✖✕ ✖✕
✗ ✔ ✗ ✔ ✗ ✔
♦ Given an undirected graph with n nodes, given k colours, assign a colour to each node so that no two adjacent nodes (with an edge between them) are the same colour.
♦ Representation using binary constraints is easy.
♦ Problem is NP-complete, so difficult in the worst case.
Motivation for Inference
111111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
11 11 11 7 7 7 1 1 1
111111 7 7 7 111
♦ Assign values from the bottom left corner, going across the rows
Motivation for Inference
111111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
11 11 11 7 7 7 1 1 1
11 11 77 7 7
♦ Assign values from the bottom left corner, going across the rows ♦ Choose blue first
Motivation for Inference
111111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
11 11 11 7 7 7 1 1 1
♦ Assign values from the bottom left corner, going across the rows ♦ Choose blue first
♦ Inconsistent
Motivation for Inference
111111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
11 11 11 7 7 7 1 1 1
♦ Assign values from the bottom left corner, going across the rows ♦ Choose blue first
♦ Choose red next
Motivation for Inference
111111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
11 11 11 7 7 7 1 1 1
♦ Assign values from the bottom left corner, going across the rows ♦ Choose blue first, then red
♦ What can you tell about nodes 5 and 6???
Motivation for Inference
111111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
11 11 11 7 7 7 1 1 1
♦ Assign values from the bottom left corner, going across the rows ♦ Choose blue first, then red
♦ What can you tell about nodes 5 and 6??? Both must be green
Motivation for Inference
111111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
11 11 7 7 7
♦ Assign values from the bottom left corner, going across the rows ♦ Choose blue first, then red
♦ Nodes 5 and 6 must both be green
Motivation for Inference
111111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
11 11 7 7 7
♦ Assign values from the bottom left corner, going across the rows ♦ Choose blue first, then red
♦ Nodes 5 and 6 must both be green
Motivation for Inference
111111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
11 7 7 7
♦ Assign values from the bottom left corner, going across the rows ♦ Choose blue first, trhen red
♦ You are wasting your time!
Motivation for Inference
111111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
11 7 7 7
♦ Assign values from the bottom left corner, going across the rows ♦ Choose blue first, then red
♦ You are wasting your time!
Motivation for Inference
111111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
11 7 7 7
♦ Assign values from the bottom left corner, going across the rows ♦ Choose blue first, then red, then green
♦ It won’t work!!
Motivation for Inference
111111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
♦ Assign values from the bottom left corner, going across the rows ♦ Choose blue first, then red, then green
Motivation for Inference
111111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
♦ Assign values from the bottom left corner, going across the rows ♦ Choose blue first, then red, then green
Motivation for Inference
111111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
♦ Assign values from the bottom left corner, going across the rows ♦ Choose blue first, then red, then green
Motivation for Inference
♦ Choose blue first. then red, then green
111111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
♦ Assign values from the bottom left corner, going across the rows
♦ So a way of detecting the problem early could save work.
So could assigning the green ones before the red one to their left
More about inference
♦ Inference in CSP solving: deducing additional constraints that follow from the already known constraints.
♦ Hence a matter of replacing γ by an equivalent and strictly tighter con- straint network γ′.
♦ γ and γ′ with the same variables are equivalent iff they have the same solutions.
♦ γ′ = (V,D′,C′) is tighter than γ = (V,D,C) iff: (i)Forallv∈V,Dv′ ⊆Dv
( i i ) F o r a l l C u , v ∈ C , C u′ , v ⊆ C u , v
γ′ is strictly tighter than γ if it is tighter and γ ̸= γ′
♦ Inference reduces the number of consistent partial assignments
Inference as offline pre-processing
♦ Just once before search starts
Inference during search
♦ At every recursive call of backtracking
How to use inference
♦ Little runtime overhead, modest pruning power. Not considered here. — but important in SAT solving, for instance
♦ When backing up out of a search branch, retract any inferred constraints that were local to that branch because they depend on a
♦ Strong pruning power. May have large runtime overhead
Backtracking with inference
function Backtrack(γ,a) returns solution, or “inconsistent”
if a is inconsistent with γ then return “inconsistent” if a is total then return a
γ′ ←a copy of γ
γ′ ← Inference(γ′,a)
if exists v with Dv′ = { } then return “inconsistent” select variable v for which a is not defined
for each d in Dv′ do
a′←a ∪ {(v,d)}
a′′ ← Backtrack(γ′, a′)
if a′′ ̸= “inconsistent” then return a′′
return “inconsistent”
♦ Inference sets Dv = {d} for each (v, d) ∈ a and then delivers a tighter equivalent network.
Forward Checking
♦ Inference: for all variables v and u where a(v) = d is defined and a(u) is undefined, set Du to {d′ : d′ ∈ Du, (d′, d) ∈ Cu,v}.
♦ That is, remove from domains any value not consistent with those that have been assigned.
♦ Obviously sound: it does not rule out any solutions
♦ Can be implemented incrementally for efficiency: only necessary to
consider v to be the variable which has just been assigned.
♦ Simple to implement and low computational cost
♦ Almost always pays off (unless subsumed by stronger inferences)
Forward Checking example
111111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
11 11 11 7 7 7 1 1 1
111111 7 7 7 111
♦ As before, start in the bottom left corner and go across the rows
Forward Checking example
111111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
11 11 11 7 7 7
11 11 7 7 7
♦ Impossible values get removed from related domains
Forward Checking example
111111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
11 1 1 7 7 7
♦ So no inconsistent assignment actually gets reached
Forward Checking example
♦ We still don’t make two-step inferences
111111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
11 1 1 7 7 7
Forward Checking example
♦ We still don’t make two-step inferences
1111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
1 1 7 7 7
Forward Checking example
11 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
♦ Now there is a wipeout: a variable with an empty domain
Forward Checking example
1111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
1 7 7 7
♦ Backtrack and change – but now there is another wipeout
♦ So backtrack some more
Forward Checking example
111111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
Forward Checking example
♦ Continue to explore the branch
1111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
♦ Now some moves are forced
Forward Checking example
11 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
Forward Checking example
♦ Now some moves are forced, and still consistent
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
♦ Blue is the bad choice
Forward Checking example
7 7 17 ✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
Forward Checking example
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
♦ And we’re …
Forward Checking example
7 7 17 ✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
♦ And we’re done!
Forward Checking example
7 7 7 ✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
return “inconsistent”
call: Backtrack(γ, { })
Making choices
function Backtrack(γ,a) returns solution, or “inconsistent”
if a is inconsistent with γ then return “inconsistent” if a is total then return a
select some variable v for which a is not defined
for each d in Dv in some order do
a′←a ∪ {(v,d)}
a′′ ← Backtrack(γ, a′)
if a′′ ̸= “inconsistent” then return a′′
The size of the search space depends on the order in which we choose vari- ables and values.
Value ordering
♦ Common strategy: least constraining value
Choose a value d ∈ Dv that won’t conflict much with others, i.e., minimise |{d′ ∈ Du : a(u) undefined, Cu,v ∈ C, (d′, d) ∈/ Cu,v}|
♦ Minimise useless backtracking below current node
♦ Does it help if no solution exists below current node or if we want to
find all possible solutions??
♦ Does it help if a solution exists below current node???
Value ordering
♦ Common strategy: least constraining value
Choose a value d ∈ Dv that won’t conflict much with others, i.e., minimise |{d′ ∈ Du : a(u) undefined, Cu,v ∈ C, (d′, d) ∈/ Cu,v}|
♦ Minimise useless backtracking below current node
♦ Does it help if no solution exists below current node or if we want to find all possible solutions?? No because we have to go over the whole sub- tree anyway.
♦ Does it help if a solution exists below current node???
Value ordering
♦ Common strategy: least constraining value
Choose a value d ∈ Dv that won’t conflict much with others, i.e., minimise |{d′ ∈ Du : a(u) undefined, Cu,v ∈ C, (d′, d) ∈/ Cu,v}|
♦ Minimise useless backtracking below current node
♦ Does it help if no solution exists below current node or if we want to find all possible solutions?? No because we have to go over the whole sub- tree anyway.
♦ Does it help if a solution exists below current node??? Yes because we may be lucky and find the solution without backtracking on this value choice
Variable ordering
♦ Common strategy: most constrained variable (aka minimum-remaining- value (MRV) and “first-fail”)
Choose a variable v with the smallest (consistent) domain, i.e., minimise |{d ∈ Dv : a ∪ {(v, d)} consistent}|
♦ Minimises branching factor (at the current node)
♦ Extreme case: select variables with unique possible values first — Value is forced by the existing assignment
— Obviously should be done in all cases
— Compare unit propagation in SAT solving
Other variable ordering strategies
♦ Most constraining variable
Choose a variable v involved in as many constraints as possible, i.e., maximise |{u ∈ V : a(u) undefined, Cu,v ∈ C }|
♦ Seek biggest effect on domains of unassigned variables Detect inconsistencies earlier, shortening search tree branches
♦ Others include history-dependent strategies — e.g. involved in a lot of (recent) conflicts — or selected many/few times before
♦ Random selection can also help, especially for tie-breaking
Forward Checking plus First-Fail
111111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
11 11 11 7 7 7 1 1 1
111111 7 7 7 111
♦ Forward checking is rather weak on its own, but it combines well with the first-fail heuristic for variable ordering, to make a powerful technique.
♦ Unit propagation (selecting variables with singleton domains) is particularly important when forward checking is used.
Forward Checking plus First-Fail
111111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
11 11 11 7 7 7
11 11 7 7 7
♦ Impossible values get removed from related domains
Forward Checking plus First-Fail
♦ Note that there is only one value in the middle
111111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
11 1 1 7 7 7
Forward Checking plus First-Fail
1111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
♦ Colour that one green, as it has the smallest domain ♦ More domains are reduced to singletons
♦ Forced move
Forward Checking plus First-Fail
11 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
♦ Forced move
Forward Checking plus First-Fail
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
♦ Forced move
Forward Checking plus First-Fail
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
♦ Forced move
Forward Checking plus First-Fail
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
♦ Forced move
Forward Checking plus First-Fail
7 7 17 ✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
Forward Checking plus First-Fail
♦ Search was backtrack-free!
7 7 7 ✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
Announcement
Make-up class: 1st lecture after the break – Tuesday 19 April 3-4pm on Physics Lecture Theatre #39A
Arc Consistency
♦ A stronger inference rule: make all variables arc consistent
♦ Variable v is arc consistent with respect to another variable u iff for every
d ∈ Dv there is at least one d′ ∈ Du such that (d,d′) ∈ Cv,u.
♦ A CSP γ = (V, D, C) is said to be arc consistent (AC) iff every variable
in V is arc consistent with every other.
♦ Any d ∈ Dv which has no support in Du is incapable of being assigned
to v in any solution, so it can be removed from Dv.
♦ Removing all unsupported values makes γ AC. This is clearly a valid
constraint inference, as no solutions are lost.
♦ Enforcing AC subsumes both forward checking and unit propagation.
Is this CSP arc consistent??? Yes.
Arc Consistency
111111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
11 11 11 7 7 7 1 1 1
111111 7 7 7 111
♦ We chose blue for v1 as before
Arc Consistency
111111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
11 11 11 7 7 7
11 11 7 7 7
♦ We made v2, v4 and v6 arc consistent with v1 and the whole CSP is AC again.
♦ Now we progress by assigning red to v2
Arc Consistency
111111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
11 11 11 7 7 7
♦ Let’s enforce arc consistency between all variables until we obtain an arc consistent CSP
♦ Make v3, v5 and v6 arc consistent with v2
Arc Consistency
111111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
11 11 11 7 7 7
Arc Consistency
111111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
11 1 1 7 7 7
♦ Make v3, v5 and v6 arc consistent with v2. Done ♦ Make v4, v6, v8 and v9 are arc consistent with v5
Arc Consistency
1111 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
♦ Make v3, v5 and v6 arc consistent with v2. Done
♦ Make v4, v6, v8 and v9 are arc consistent with v5. Done ♦ Make v7 and v8 are arc consistent with v4
Arc Consistency
11 777 111
✚✙ ✚✙ ✚✙
✛✘ ✛✘ ✛✘
♦ Make v3, v5 and v6 arc consistent with v2. Done
♦ Make v4, v6, v8 and v9 are arc consistent with v5. Done ♦ Make v7 and v8 are arc consistent with v4. Done
♦ Make v3 and v9 are arc consistent with v6
Arc Consistency
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com