Dynamic Sampling from Graphical Models Yitong Yin Nanjing University Joint work with Weiming Feng (Nanjing) Nisheeth Vishnoi EPFL)
Dynamic Sampling fom Graphical Models Yitong Yin Nanjing University Joint work with Weiming Feng (Nanjing) Nisheeth Vishnoi (EPFL)
Graphical Model instance of graphical model:=(V,E,g,) oD:variables ●EC2:constraints [g]=(0,1,...g-1:domain ●pe constraint（ ●Φ=（中v)eyU(中e)eeE:factors Gibbs distribution u over all oE[g]v: 4(o)x中，(o,)中(o。) v∈V e∈E
Graphical Model • Gibbs distribution µ over all σ∈[q]V : • V : variables • E ⊂ 2V: constraints • [q] = {0,1, …, q-1}: domain • Φ = (�v)v∈V ∪ (�e)e∈E: factors μ(σ) ∝ ∏ v∈V ϕv(σv) ∏ e∈E ϕe(σe) constraint e V ϕv ϕe instance of graphical model: I = (V,E, [q], )
Graphical Model instance of graphical model:=(V,E,g,) ● Each vEV is a variable with domain [g] and has a distribution中，over[q] 中：[q]→[0,1] ●Each e∈E is a set of variables and corresponds to a constraint (factor) e constraint φe:[q]e→[0,1] ● Gibbs distribution u over all olg]: 4(o)x中，(o,)中(oe) v∈V e∈E
Graphical Model • Each v∈V is a variable with domain [q] and has a distribution • Each e∈E is a set of variables and corresponds to a constraint (factor) ϕe : [q] e → [0,1] μ(σ) ∝ ∏ v∈V ϕv(σv) ∏ e∈E ϕe(σe) constraint e ϕv over [q] V ϕv ϕe ϕv : [q] → [0,1] instance of graphical model: I = (V,E, [q], ) • Gibbs distribution µ over all σ∈[q]V :
Graphical Model Gibbs distribution u over all oe[g]v: 4(o)cφ，(o,)Πp(a) v∈V e∈E is a distribution over [g] φe:[q]e→[0,1] ● each vE V independently samples XvE[g]according to ● each eEE is passed independently with probability e(Xe); X is accepted if all constraints e eE are passed
Graphical Model • Gibbs distribution µ over all σ∈[q]V : μ(σ) ∝ ∏ v∈V ϕv(σv) ∏ e∈E ϕe(σe) ϕv is a distribution over [q] ϕe : [q] e → [0,1] • each v ∈ V independently samples Xv∈[q] according to �v; • each e ∈ E is passed independently with probability �e(Xe); • X is accepted if all constraints e ∈ E are passed
Graphical Model ·Gibbs distribution u over all o∈[q]': a(o)cΠ中，(o,)Π.(o,) G(V,E) v∈V e=(u,v)∈E ●hardcore morel: V [q]={0,1} grve otherwise if oy=0 A>0 is (local)fugacity if o=1
Graphical Model • Gibbs distribution µ over all σ∈[q]V : μ(σ) ∝ ∏ v∈V ϕv(σv) ∏ e=(u,v)∈E ϕe(σu, σv) ϕ ϕv e u v G(V,E) • hardcore morel: [q] = {0,1} ϕe(σu, σv) = { 0 if σu = σv = 1 1 otherwise ϕv(σv) = 1 1 + λv if σv = 0 λv 1 + λv if σv = 1 λv > 0 is (local) fugacity