Inference (Local Counting) w:uniform distribution of independent sets in G. g:marginal distribution at v conditioning on o e0,1)5. y∈{0,1}：g(y)=Pr[Y=y|Ys=o] ●Each y∈S receives ov as input. ● Each v E D returns a marginal distributionsuch that: drv(g,hg)≤poim Z=40-ΠyX.=01<i:X,=0 i=1 network G(E) Z:of independent sets
Inference (Local Counting) network G(V,E) µ: uniform distribution of independent sets in G. • Each v ∈ S receives σv as input. • Each v ∈ V returns a marginal distribution such that: µ ˆ v dTV(ˆµ v , µ v ) 1 poly(n) : marginal distribution at v conditioning on σ ∈{0,1}S µ . v 0 1 1 0 8y 2 {0, 1} : µ v (y) = Pr Y ⇠µ [Yv = y | YS = ] 1 Z = µ(;) = Y n i=1 Pr Y ⇠µ [Yvi = 0 | 8j<i : Yvj = 0] Z: # of independent sets
Gibbs Distribution (with pairwise interactions) Each vertex corresponds to a variable with finite domain g. network G,E): ● Each edge e=(u,v)EE has a matrix (binary constraint): Ae:[q]×[q→[0，l] bN ●Each vertex ve∈has a vector (unary constraint): bm:[g小→[0,1] Gibbs distribution u:Voelg] u(o)xIAe(o,o）Ib(ou) e=(u,v)∈E u∈V
Gibbs Distribution network G(V,E): • Each vertex corresponds to a variable with finite domain [q]. • Each edge e=(u,v)∈E has a matrix (binary constraint): • Each vertex v∈V has a vector (unary constraint): µ() / Y e=(u,v)2E Ae(u, v) Y v2V bv(v) Ae u bv v (with pairwise interactions) Ae: [q] × [q] → [0,1] bv: [q] → [0,1] • Gibbs distribution µ : ∀σ∈[q]V
Gibbs Distribution (with pairwise interactions) Gibbs distribution u:o∈[g]' network G,E): L(a)Ae(ou;ou)bo() e=(u,v)∈E u∈V independent set: bN 4=上日成-日 local conflict colorings: [Fraigniaud,Heinrich,Kosowski,FOCS'16] Ae:[q]×[q]→{0,1} Ae:[q]×[q]→[0,1] b:[q]→{0,1} bm:[q]→[0,1]
Gibbs Distribution • Gibbs distribution µ : ∀σ∈[q]V µ() / Y e=(u,v)2E Ae(u, v) Y v2V bv(v) • independent set: bv = 1 1 Ae = 1 1 1 0 • local conflict colorings: [Fraigniaud, Heinrich, Kosowski, FOCS’16] network G(V,E): Ae u bv v Ae: [q] × [q] → {0,1} bv: [q] → {0,1} Ae: [q] × [q] → [0,1] bv: [q] → [0,1] (with pairwise interactions)
Gibbs Distribution Gibbs distribution u:o∈[g]' network GE): u(a)f(os) (f,S)∈F each(f,S)∈F is a local constraints(factors): f:[gs→R≥o SC Vwith diamG(S)=O(1)
Gibbs Distribution • Gibbs distribution µ : ∀σ∈[q]V network G(V,E): S µ() / Y (f,S)2F f(S) is a local constraints (factors): f : [q] S ! R0 S ⊆ V with diamG(S) = O(1) each (f,S) 2 F
A Motivation: Distributed Machine Learning ●Data are stored in a distributed system. Distributed algorithms for: sampling from a joint distribution(specified by a probabilistic graphical model); ● inferring according to a probabilistic graphical model
A Motivation: Distributed Machine Learning • Data are stored in a distributed system. • Distributed algorithms for: • sampling from a joint distribution (specified by a probabilistic graphical model); • inferring according to a probabilistic graphical model