程序代写 KRR: CSPs and Inference

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􏰀 1􏰀1 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􏰀 1􏰀1 11 7􏰀􏰀 7 7 1 􏰀1 1
11 11 7􏰀7 7􏰀 7
♦ Assign values from the bottom left corner, going across the rows ♦ Choose blue first

Motivation for Inference
111111 777 111
✚✙ 􏰀✚✙ ✚✙ 􏰀 􏰀􏰀􏰀
􏰀􏰀 􏰀 􏰀􏰀 􏰀􏰀
✛✘ ✛✘􏰀􏰀 ✛✘
11􏰀 1􏰀1 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􏰀 1􏰀1 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􏰀 1􏰀1 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􏰀 1􏰀1 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
✚✙ 􏰀✚✙ ✚✙ 􏰀 􏰀􏰀􏰀
􏰀􏰀 􏰀 􏰀􏰀 􏰀􏰀
✛✘ ✛✘􏰀􏰀 ✛✘
􏰀􏰀 1􏰀1 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
✚✙ 􏰀✚✙ ✚✙ 􏰀 􏰀􏰀􏰀
􏰀􏰀 􏰀 􏰀􏰀 􏰀􏰀
✛✘ ✛✘􏰀􏰀 ✛✘
􏰀􏰀 1􏰀1 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􏰀 1􏰀1 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􏰀 1􏰀1 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􏰀 1􏰀1 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􏰀 1􏰀1 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􏰀 1􏰀1 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􏰀 1􏰀1 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􏰀 1􏰀1 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􏰀 1􏰀1 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