东南大学 崇志宏:图概率和BP算法

所需积分/C币:10 2017-07-17 19:44:26 1.61MB PDF

概率和图的结合解决了概率推理和学习的复杂度的问题:通过factorization产生学习和推理的局部化方法。重点是factorization
图概率模型 nue 数据智能实验室 知识表示和推理的分高 不确定性知识表示和推理 表示的语义、推理的算法的独立 基本方法 用图结构化变量 好处 精简表示 算法和表示的分离 东南大学数据与智能实验室D& ntel lab 图概率模型:独立/赖关系的表示 nue Graph Representation 数据智能实验室 1 3 4 國 酸应 点 2 3 pendencies (F⊥H|S) C⊥S|F,H A⊥C|B,D) M⊥H,C|F (B⊥D|A,C) M⊥C|F) Factorization P(v=U,h=h) Zp(E(v, h) P(S, F, H, C, M)=P(SP(F S) P(A, B, C, D)=201(A, B) P(H S)(C F, H)P(M F) P2(B, C)3(C, D)P4(A, D) E(u,, h)=-bv-ch-v'wh P(am1c19000001∑∑xD{-E(,h iRepresentation, Inference, Learning! 东南大学数据与智能实验室D& ntel lab 图概率模型:联合分布的分解 A distribution Pp is a Gibbs distribution parameterized by a set of factors =[91(D1), .., PK(DK) if it is defined as follows P(x1,…,xn)=zP(x1,…,xn), where P(X1…,XMn)=1(D1)×¢2(D2)×…xpm(Dm) is an unnormalized measure and z=∑(X1,,X C E X X is a normalizing constant called the partition function CDHGLDHG.S/,LHHG We say that a set of nodes Z separates X and Y in H, denoted sep(X; Y| Z), if there is no active path between any node X E x andy y given Z. We define the global independencies associated with H to be I(h)=I(XIYI Z): sepr(X;Y| Z)) Eloi Xi l Non Descendants.I Pag P(X1, x)=ⅡPx:|果).Q P(Congestion Fus Hayfever, Season)=P(Congestion Hu, Hayfever) P(S, F, E, C,M= P(S)P(FIS EIsele- Pary(Congestion P(HI SP(CI F, HPCMIF) 图概率模型:注意点! nue 数据智能实验室 东南大学数据与智能实验室D& ntel lab 提纲 nue 数据智能实验室 图概率模型 图概率的BP算法 .图概率模型的训练 东南大学数据与智能实验室D& ntel lab 图概率推理算法:VE P A)P (C B P (D P 1 b 十 P( PPPP bbb 2 aaa ((( PPP B11 cc b2 PPPP Padd P( P 11112222 (c bb d P bl P b1 P d P P(6 P b1 P(dli c2 + P P P d1 P(b P b2 P P PP bl ( b b b l2 Pla P (b2|a1)P(c|b2)P(a2 +P(a2)P(b2|a2)P(c1|b2)P(a2|c) +P(a2)P(b1a1)P(c2|b1)P(d2|c2 +P(a2)P(b1|a2)P(c2|b1)P(d2 +P(a1)P(b2|a2)P(c2|b2)P(d2|c2 +P(a2)P(b2|a2)P(c2」b32)P(a2|c2) Figure 9.2 Computing P(D ) by summing over the joint distribution for a chair A→B→C→ D; all of the variables are binary valued ■■■■■■■■■■■■■■■■■■ The following problem is wp-hard: P(Y E=e=e(ye P(g, e)=2P(v, e, w) e)'P(e)=∑Pe, Given a Bayesian network B over xt, a uariable A e A, and a ulue i E va(X), find a number p that has relative error e for PB(X= a) 图概率推理算法:VE P(A)P(B)(C)(D C)P(D) M(A, B=P(AP(B A) 22(B, C)= TI(B)P(CIB) 7(B)=∑Av(A,B) 2()=∑v2(B, B T1(b) P(el b) P(dl I P(a)P(bla)p(elb)P(dId) (b2)P 2 (c1|b P(d +P(a2)P(2|a)P(-|)P(d-|c +Ti(b) P(c2b) P(d P(a)P(b2 a)p(e 1b2) P(d' el Ti(b2) P(c21b2) P(dl i c2 +P(a2)P(62 1a2)P(e! b) P(d! cl Ti(b) P(cl ib) P(d2c) P(al)P(b la)p(c1b)p(d c2) +n1(b2)P(c1|b2)P(d2 +n1(b1)P(c2|b3)P(a2c2) P(a2)P(b|a2) P(e1b )p(dl +n1(b2)P(e2|b2)P(a2lc2) P(a)P( a)P(162)P(d|c2 Figure 9.4 The second transformation on the sum of figure 9.2 +P(a)P(2|a2)P(c2|b2)P(d (Ti(b)P(e1b)+T(b2)P(e162)) P(di I 1 a)P(c bl)P(d2 (n(b1)P(c2|b3)+n1(b2)P(c2|b2)P(d P(a)P(b|)p(e bl)p(d2 I (n(3)P(a1b2)+n(2)P(e|b2))P(a1)+P(l)P(b2|a)P(cl62)P(d2l) (n(b1)P(c2|b1)+n1(b2)P(a2|b2))P(d2|c2) +P(2)P(31a)P(c1|)P(e2c) Figure 9.5 The third transformation on the sum of figure 9.2 +P(a )P(b|a)P(e2 6l)P(d2 c2) !=BB上(c3 P(dcl p(a2)p(b1a2)P(e2 1b1 )P(d2 c2 +m(c2)P(d|c2) +P(d)P(3|a)P(2|63)P(2|l2) aIC- vib.C) (a2) P(b2| a2)P(2 162) P(d21c2 (c1)P(a2 B?+n(2)P(d2 Figure 9.6 The fourth transformation on the sum of figure 9.2 概率图操作:VE算法 数据智能实验室 Algorithm 9.1 Sum-product variable elimination algorithm Procedure Sum-Product-VE 重,/ Set of factors Z. / Set of variables to be eliminated // Ordering on Z Let Z1,..., Zk be an ordering of Z such that 123456 Zi<Zj if and only if i <1 for 2= 1.,.ke Sum-Product-Eliminate-Var(4p, Zi ∏I∈φ中 returnφ Procedure Surm-Product-Eliminate- Var 0!·@2=2p I Set of factors Z / Variable to be eliminated ∑x∑=∑∑x Φ←{φ∈Φ:z∈ Scope[小} 12345 (19)9=:(c2y) v←Ⅱ φ∈〃g Tt一 ■■■■■ ∑(:4)=∑.X!SOm] return重∪{7}: X X 回■■■■ ■■■■■■■■■■

...展开详情
上传资源赚积分,得勋章
最新资源