Graphical Model ●Gibbs distribution u over all o∈[q]': a(o)cΠ,(a,)Πg e(ou,O) G(V,E) v∈V e=(u,v)∈E Ising/Potts model: (ferromagnetic) if ou=oy or了 10.1 otherwise (anti-ferromagnetic) a,ow={eolee otherwise is a distribution over [g]( (arbitrary local fields)
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) • Ising/Potts model: ϕe(σu, σv) = { βe ∈ [0,1] if σu = σv 1 otherwise ϕe(σu, σv) = { 1 if σu = σv βe ∈ [0,1] otherwise ϕv is a distribution over [q] (ferromagnetic) (anti-ferromagnetic) or { (arbitrary local fields)
Dynamic Sampling ·Gibbs distribution u over all oe∈[q]': 4(o)x,(o,)中(oe) v∈V e∈E current sample:X~u dynamic update: adding/deleting a constraint e new distribution changing a factor y or e 儿 adding/deleting an independent variable v Question: Obtain X'~u'from X~u with small incremental cost
Dynamic Sampling • Gibbs distribution µ over all σ∈[q]V : ϕ ϕv e u v • adding/deleting a constraint e • changing a factor �v or �e • adding/deleting an independent variable v current sample: X ~ µ μ(σ) ∝ ∏ v∈V ϕv(σv) ∏ e∈E ϕe(σe) dynamic update: Obtain X’ ~ µ’ from X ~ µ with small incremental cost. Question: new distribution } µ’ ϕ′ e ϕ′ v
Dynamic Sampling instance of graphical model:=(V,E,g,) Gibbs distribution u over all oeg]: D u(o)xb(G)B.(G.) v∈V e∈E Ope constraint current sample:X~u ●V:variables 。EC2:constraints ·[q]={0,1,.,q-1}:domain ●Φ=（中v)eyU(中e)eeE:factors
Dynamic Sampling instance of graphical model: I = (V,E, [q], ) • V : variables • E ⊂ 2V: constraints • [q] = {0,1, …, q-1}: domain • Φ = (�v)v∈V ∪ (�e)e∈E: factors constraint e V ϕv ϕe • Gibbs distribution µ over all σ∈[q]V : current sample: X ~ µ μ(σ) ∝ ∏ v∈V ϕv(σv) ∏ e∈E ϕe(σe)
Dynamic Sampling instance of graphical model::Z=(V,E,[gl,Φ)） update:(D,D) D C VU2V is the set of changed variables and constraints ΦD=(φ，)vEVnD U(中e)e∈2 vD specifies the new factors (Y,E,[gl,Φ)Dg(Y,E,[ql,Φ) E'=EU(2V∩D) Φ'=(pa)a∈uE' where each is as specified in {8 ifa∈D otherwise
Dynamic Sampling instance of graphical model: I = (V,E, [q], ) update: (D, �D) (V, E, [q], Φ) (D,ΦD) (V, E′ , [q], Φ′) is the set of changed variables and constraints ΦD = (ϕv)v∈V∩D ∪ (ϕe)e∈2V∩D specifies the new factors D ⊂ V ∪ 2V E′ = E ∪ (2V ∩ D) Φ′ = (ϕ′ a)a∈V∪E′ where each ϕ′ a is as specified in { ΦD if a ∈ D Φ otherwise
Dynamic Sampling instance of graphical model:Z =(V,E,g,) update:(D,D) DC VU2V is the set of changed variables and constraints D=()vEVD U(e)eE2vD specifies the new factors (V,E,Iql,)VEIql) Input:a graphical model with Gibbs distribution a sample ~u,and an update (D,D) Output:X'~u'where u'is the new Gibbs distribution (D,p)is fixed by an offline adversary independently of X~u
Dynamic Sampling Input: Output: a graphical model with Gibbs distribution µ a sample X ~ µ, and an update (D, �D) X’ ~ µ’ where µ’ is the new Gibbs distribution instance of graphical model: I = (V,E, [q], ) update: (D, �D) (V, E, [q], Φ) (D,ΦD) (V, E′ , [q], Φ′) is the set of changed variables and constraints ΦD = (ϕv)v∈V∩D ∪ (ϕe)e∈2V∩D specifies the new factors D ⊂ V ∪ 2V (D, �D) is fixed by an offline adversary independently of X ~ µ