王珏-结构+平均-读Daphne Koller的“概率图模型”

,Machine Learning and Data Mining 2009,单击此处编辑母版标题样式,单击此处编辑母版文本样式,中,国,科学院自动化研究所,结构,+,平均,-,读,Daphne,Koller,的“概率图模型”,王珏,中国科学院自动化研究所,模式识别国家重点实验室,2011,年,4,月,7,日,一、引子二、表示三、推断四、学习五、结束语,讲座分为五个部分，开头一个引子，说明讲座的动机，最后一个结束语，从历史发展的角度讨论关注概率图模型的原因，中间三个部分，介绍,Koller,这本书的三个部分：表示,(representation),、推断,(inference),和学习,(learning),的基本思想和主要方法。,标题，,AI,与,ML,采用“结构,+,平均”作为标题，没有使用“结构,+,统计”或者“人工智能,+,统计学”，或“图,+,概率”。“结构”与“统计”似乎不具有同等地位，“人工智能”与“统计学”水火不相容，“图,+,概率”直观确切，其本质对应“结构”与“平均”，对中文，“结构,+,平均”更美一些。,思考：人工智能,(AI),与统计机器学习,(ML),是否存在一个结合点。但是，在理念上，,AI,强调因果率,(,结构,),，不惜对排中率破缺，统计方法强调排中率，不惜对因果率破缺，两者水火不相容。鉴于两者均已遇到根本性困难，有没有一种折衷的理念。,Koller,这本书应该是这种折中的理念。,极端的例子,对任意三角形识别,(,最简单的图形,),，如果采用句法,(,单纯结构,),方法，需要“上下文敏感文法”描述，没有,Parsing,算法。,成都地区暴雨预报，十年的数据。神经网络,(,平均,),，获得模型，验证，误报,5%,。误报中有一个样本，预报大暴雨，实际是晴天，各种因素均说明有暴雨，,但是,，,单纯结构或单纯平均需要满足严厉的条件，否则无效,湿度指标低，,没有水,！当然没有暴雨！平均将这个重要指标与其他指标一起平均了。小学生不会犯的差错,(80,年代末,),书中,“,学生,”,的例子,课程,(D:,难,=0,，易,=1),智力,(I: ,聪明,=0,，一般,=1),考试,(G: A, B, C) SAT (S: ,好,=0,，坏,=1),推荐,(L: ,强,=0,，弱,=1),。,以推荐作为查询变量,(L),If,D=0G=A,thenL,=0,If,I=0G=A,thenL,=0,If,D=1I=1G=A then L=1,问题是：,If,D=1I=0G=A then L=?,这就是人工智能遇到的难题！无法泛化！,不同查询，不同规则！,构造一个函数：,L = f (,D,I,G,S),观察一组学生，获得样本集。基函数,L = ,1,D + ,2,I + ,3,G + ,4,S,设计算法，确定，获得模型。,问题：模型为真需要多少样本，对高维数据，不知道！模型不可解释,这就是统计机器学习遇到的难题。可以泛化，,精度未知,，不可解释。,根据观察和专家经验，构造规则集,问题本身的语义,课程难易程度与考试分数有关。,学生智力与考试成绩有关。,学生智力与,SAT,有关。,考试成绩与“推荐信强弱”有关。,AI,方案充分考虑了这种语义，但是，将这种语义强化到唯一表示程度,(,当且仅当,),，缺失灵活性。,统计学习方案完全不考虑这种语义，尽管具有灵活性,(,泛化,),，但是，需要充分的观察样本。,两者的共同代价是：维数灾难。前者，需要考虑所有可能的组合的规则集合，后者，需要考虑充分的样本集合。,这种语义可以根据统计分布获得，也可以根据常识经验获得。,ML,强调给定变量集合张成的空间上计算平均的方法，抹煞变量之间的结构；,AI,强调变量的独立性，忽视变量之间的条件独立关系。是否可将变量子集,(,甚至一个变量,),的局部分布，根据变量之间内在的结构，转变为对变量集合整体的联合分布。这样，就可以既顾及了变量之间存在结构，又考虑了平均的必要性。概率图模型应该是一个这样的方案。,这本著作包罗万象,(1200,页,),，这个讲座是根据,我个人偏好,，抽出最基本的思考、研究方法，以及实现这个思考的基本理论。而书中罗列的大量具体的方法则认为：不是解决问题的唯一途径，而是存在的问题。这本著作数学符号体系繁杂，谈不上“优美”。著作有四个部分：表示、推断、学习和,action and decision,，我们只讨论前三个部分。,致谢,在我准备这个“笔记”之前，王飞跃、宗成庆和我的,12,个学生参加了我们的一个讨论班，大家一起通读了,Koller,的这本书。这个讨论班对我准备这个“笔记”有很大的帮助，这些学生是：王飞跃教授的学生，顾原、周建英、陈诚和李泊；宗成庆教授的学生，庄涛和夏睿；我的学生韩彦军、马奎俊、孙正雅、黄羿衡和吴蕾，以及吴高巍博士。在此表示谢意。特别感谢韩素青和韩彦军帮助我检查和修改了全部,ppt,。,一、引子二、表示三、推断四、学习五、结束语,为什么“表示”是一个专题,统计机器学习的表示,-,基函数。确定基函数，没有表示问题。,给定变量集，完全图或完全不连接，,平凡,！,图的结构,(,不完全连接,),统计上条件独立,-,因子,条件独立的集合,(I-map),成为图结构的表征。,联合分布与边缘分布是图结构的概率描述,A,B,C,D,E,B,A,C,D,E,不完全图,-,条件独立,两种表示,。非平凡,概率图模型,Bayes,网,(Bayesian Network, BN),，有向图,Markov,网,(Markov Network, MN),，无向图,各种局部概率模型,(CPD),从联合分布构造,Bayes,网,(BN),学生问题，五个变量排成一个任意的序：,I, D, G, L, S,，其联合分布,(,左,),，对应的完全,BN(,右,),：,P(I, D, G, S, L) =,difficulty,Intelligence,Grade,SAT,Letter,P(I),P(S | I, D, G, L),P(D | I),P(G | I, D),P(L | I, D, G),构造,Bayes,网,因子,完全图,节点,G,上的条件概率分布,(CPD),图上的独立性,P(I,D,G,L,S) =,P(I),P(D | I),P(G | I, D),P(L | I, D, G),P(S | I, D, G, L),P(I),P(D),I,与,D,相互独立,L,只与,G,有关，与其他独立,P(G | I, D),P(L | G),S,只与,I,有关，与其他独立,P(S | I),difficulty,Intelligence,Grade,SAT,Letter,分布,P,中的条件独立,P(X),是随机变量集,X,中所有变量的联合分布，,P(X,i,| Z),是,X,i,关于,Z,的条件分布。,ZX,X,i,X,且,X,i,Z,。,条件独立：如果两个变量,X,i,X,j,X,，对条件,Z,独立，,iff,P(X,i,X,j,| Z) =,P(X,i,| Z),P(X,j,| Z),满足条件独立的所有断言,(X,i,X,j,| Z),，构成一个集合，称为关于,P,的,I-map,，记为,I(P),。,对图,G,，所有彼此不相连的节点对集合为,I(G),。,如果,I(G)I(P),，,G,是一个对独立集合,I(P),的,I-map,。,BN,上的独立,Y,Z,X,Y,Z,X,(,a),(,d),绝对独立,(X Z), (d),。,Y,Z,X,(c),Y,X,Z,(,b),Y,Z,X,(,e),复杂的图可以考虑为由一些三个节点简单图构成，令,X,Y,与,Z,三个节点,学生例子：,X(,智力,),，,Z(,推荐信,), Y(,成绩,),。,(,a)(b,): Y,未被观察,(,成绩未知,),，从学生聪明,X,，推断学生分数高,Y,，,可能,强推荐。,Y,已被观察，,Z,只与,Y,有关，与,X,独立。,(X Z | Y),。,(c): Y,未被观察，从,X,可能,推断,Z,，,Y,已被观察，两者独立。,(e),如何？复杂！,v-,结构,(,e)XYZ,，成绩,Y,优秀，如果课程,X,困难，可以推出智力,Z,聪明，这样，,X,与,Z,相关。如果,Y,未知，,X,和,Z,独立。这个结构称为,v-,结构。,G,是,BN,，存在三个节点,X, Y, Z,。,X,与,Z,是独立，则：,(1),对,v-,结构，,Y,与它的全部子孙是未被观察,(e),。,(2)Y,已被观察,(,a)(b)(c,),。,BN,最麻烦的是,v-,结构，用树结构近似,BN,，就是删除,v-,结构。这时，,BN,上，两个节点之间没有连线，它们一定独立。,Y,Z,X,BN,上判定独立的规则：,不满足条件，只能说,不能保证,独立,因子化,(factorization),链式规则：,P(D,I,G,S,L) = P(I) P(D) P(G|I, D) P(L|G) P(S|I),满足条件独立假设的链式规则一般形式：令,Pa,X,是图,G,上变量,X,的所有父结点，变量集合的联合分布可以表示为：,P(X,1, ,X,n,) = ,P(X,i,|,Pa,Xi,),，其中,P(X,i,|,Pa,Xi,),称为因子。,定理：如果图,G,是一个对,I(P),的,I-map,，则,P,可以根据,G,因子化,(,注意,，因子的定义，满足条件独立假设,),。逆定理成立。,注意：,仅是因子化，而不是任意,P,可以使用,G,描述。,I(G) I(P),最小,map,D,I,S,G,L,L,S,G,I,D,L,D,S,I,G,分布的结构，就是将所有“独立”的边移除的图。,最小,map,：,令,G,是一个对,I(P),的最小,I-map,，如果它是对,I(P),的,I-map,，且从,G,上移除任何一个单边，它将不再是,I-map(,不在,I(P),中,),。,如果,G,是一个最小,-map,，我们似乎可以从中读出分布的所有结构，即，从图上读出,P,的所有独立,I(P),。,由于图的生成依赖变量序，即，不同的变量序将导致不同的图，而不同的图，可以分别具有最小,I-map,，具有不同的结构。没有唯一性！这个结论不成立！,P-,map(perfect,),P-map,：如果,I(G)=I(P),，,G,是一个,P-map,。,意义,：对任何一个,P,，是否保证存在一个,G,的,P-map,A,B,D,C,D,B,C,A,对,P,(AC|B,D),与,(BD|A,C),。存在使得,A,与,C,，,B,与,D,不相连接的,BN,？,考察,(B D | A, C),：,考察,(AC|B,D),考察,(AC | B, D),:,(AC | B),，,ABC,是,(b),，如果,B,已知，成立,(AC | D),，,ADC,是,(b),，如果,D,已知，成立,(BD | A),，,DAB,是,(c), A,已知,成立。,(BD | C),，,DCB(v,-,结构,),，,C,已知，,B,与,D,不独立。,(BD|C),不成立。,(BD|A,C),不成立,(AC|B,D),成立,CDA(c,类,),，,D,已知，,(AC),，,CBA,，,B,已知，,(AC),。,DCB(v,),，,C,已知，,(D B),不成立,回答是不能保证,概率图模型,Bayes,网,(Bayesian Network, BN),，有向图,Markov,网,(Markov Network, MN),，无向图,各种局部概率模型,(CPD),Markov,网,(MN),尽管,MN(,无向图,),以完全子图的因子为基础，但是，,MN,上的完全子图依赖条件独立，因为节点之间连线的删除，将直接导致不同的完全子图。,因子是一个从变量,D,子集到正实数域,+,上的映射,(,函数,),。,表示联合分布与因子,其中,D,i,(i,=1,k),是,MN H,上的完全子图,(,典型是,clique),，,=,1,(D,1,), , ,k,(D,k,),称为分布,P,的因子集合。,1,(D,1,), , ,k,(D,k,),满足,:,P,称为,Gibbs,分布,Z,称为划分函数,与,BN,比较，联合分布是对完全子图势能的平均。计算,Clique(,最大完全子图,),是,NPC,。,势能函数,C,A,D,B,I-map,与因子化,I-map: I(P),是在,P,中形如,(X, Y | Z),独立的集合。与,BN,定义一致。,MN,与,BN,一样，有一个关于因子化的定理,BN,MN,令,P, 0,，,G,是一个,P,的,I-map,，,iff,P,可被因子化为：,令,P 0,，,H,是一个,P,的,I-map,，,iff,P,可被因子化为,(,完全子图的势函数,),：,注意：,G(,或,H),是一个,P,的,I-map,就是,I(G) I(P),“偶对”独立,I,P,(H) = (X, Y |,U,-X,Y) : XY H,意味着：不连接的偶对节点在其他节点条件下相互独立。,(A,D | B,C,E),(B,C | A,D,E),(D,E | A,B,C),D,A,B,C,E,Blanket,独立,这是“偶对”独立的推广。令,B(X),是节点,X,在,H(MN),的所有直接邻居节点集合。,I,L,(H) = (X,U,-X-B(X) | B(X) : XH,意味着：,X,在所有直接邻居条件下，与其他节点独立。,D,A,B,C,E,对节点,B,，,B(B)=A, D, E, B,与,C,是,Blanket,独立。,独立形式与构图方法,d-,分离：,在任意节点,xX,与,yY,通路上，存在一个节点,Z,已知,在,Z,下，其他节点相互独立。,I(P),B,C,A,D,(D, A,C | B),偶对：不连接的偶对独立，,I,P,(P),I,P,(H)=(X,Y|,U,-X,Y):X-YH,(A,D | B,C,E),D,A,B,C,E,D,A,B,C,E,Blanket,：对,X,的所有直接邻居，,X,与其他节点独立。,I,L,(P),节点,B,，,B(B)=A, D, E,与,C,是,Blanket,独立,I,P,(P) I,L,(P) I(P),如果,P 0(,正分布,),，则,I,P,(P) = I,L,(P) = I(P),构图方法：偶对或,Blanket,。构成的,MN,，均是唯一最小,I-map,。,BN,的,Moral,图,-BN,MN,G,是,BN,的,Moral,图是一个无向图，对两个节点,X,与,Y,满足：,(1)G,中，连接的节点保持连接。,(2)G,中，,X,与,Y,有共同子孙，,X,与,Y,连接。,v-,结构。,BN,BN,的,Moral,图,v-,结构,:DKI,，如果,K,未被观察，,D,与,I,独立，,K,以被观察，,D,和,I,就相关。相连！,概率图模型,Bayes,网,(Bayesian Network, BN),，有向图,Markov,网,(Markov Network, MN),，无向图,各种局部概率模型,各种,CPD-,局部概率模型,讨论了网络的结构之后，需要关注附加在节点,(,边,),上的各种不同描述的条件,(,局部,),概率分布,(CPD),，如何确定因子。,满足：,P(x,|,pa,X,) = 1,。,各种,CPD,Tabular CPD,：使用表描述,P(X |,Pa,X,)0,，,判定,CPD,：判定函数,Logistic CPD,：,线性高斯,CPD,：,树与规则,CPD,网图有两个要素：其一，网图的结构，其二，网图节点上的条件概率分布。在学习时，这两个要素将成为学习的两个方面。结构可以由经验来构造。,对节点上的概率分布的学习，将基于这些,CPD,表示形式，可以理解为学习的“基函数”,(,局部表示,),。经验知识可以无障碍地被引入。,一、引子二、表示三、推断四、学习五、结束语,查询问题,-,基于图的推断,概率查询,(Y,边缘,),：根据,给定图,，计算,P(Y | E = e),，,其中，,E,是证据变量，,Y,是查询变量。读为：在证据,e,条件下，,Y,出现的概率,(,边缘概率,),。,MAP,查询：计算,MAP(W | e) =,arg,max,w,P(w, e),。其中，,W=-E,。读为：在证据,e,条件下，在,W,中求出最适合的赋值。,边缘,MAP,查询：令,Z=-Y-E,，计算,MAP(Y | e) =,arg,max,Y,P(Y, Z | e),。,边缘查询,-,基于图的推断,边缘查询原理,:,(1),根据,BN,，计算联合分布,P()=,P(X,i,|Pa,Xi,),(2),计算在,E,下，变量,Y,的边缘分布：,P(Y | E)=,X-Y-E,P(),这个貌似简单的任务，由于计算边缘分布需要取遍非查询变量所有值的组合。十分困难。,学生聪明,i,1,，不高兴,h,0,，,BN,下,，查询学生工作机会。,P(J | i,1, h,0,),。,变量集合,:=,C,D,I,G,S,L,J,H,根据,BN,，计算联合分布,P,(),。,在证据,E,下的,J,的边缘分布：,P(J | i,1,h,0,)=,W,P(,), W=-J-H,I,精确推断是,NPC,。,无论,BN,还是,MN,，其上的推断是,NPC,问题，计算近似推断也不能幸免。,近似推断：图近似,(,本质近似,),，目标近似和计算近似,(,包括算法近似,),。,概率图模型推断研究的焦点是：,精度和效率,之间有效,折中,。,“推断”问题的解法,提取公因子，以避免变量的重复计算，空间换时间，折中。动态规划,动态规划,Clique树法,优化法,以相对熵为目标,(,多种方法之一,),，将概率查询变为有约束的优化问题，并使用拉格朗日乘子法求解。,将无向图构成,clique,树，采用消息传播的方法，计算查询的分布。对图上任何节点的查询有效,BN,变量消去法,-,计算,P(D),BN,网：,A,BCD,对,D,的边缘分布：,P(D)=,C,B,A,P(A) P(B|A) P(C|B) P(D|C),(1) P(D) =,C,P(D|C),B,P(C|B),A,P(A) P(B|A),(2),令,1,(A, B),=,P(A) P(B | A),，,1,(B) = ,A,1,(A, B),，,(,消去,A),(3),计算,2,(B, C) =,1,(B),P(C | B),，,2,(C) = ,B,2,(B, C) (,消去,B),最后，计算出,P(D),。,A,B,C,D,联合分布：,P(A,B,C,D)=,P(A) P(B|A) P(C|B) P(D|C),MN,变量消去法,-,因子边缘化,对,BN,，条件概率,P(X | Y),为因子，在,MN,中，因子,(X, Y),，尽管图结构不同,(,有向,vs.,无向,),，但是，在变量消去法上，没有本质区别。称为因子边缘化。,P(D) = ,C,B,A,A, ,B, ,C, ,D,满足交换律和结合律,=,C,B,C, ,D, (,A,A, ,B,),= ,C,D, (,B,C, (,A,A, ,B,),其中，,Z: X-Y(A, B, C),即，从变量集合中删除查询变量的变量集合，是因子集合。,Z,是和积形式，,它是从联合分布计算边缘分布的基本形式,“推断”问题的解法,提取公因子，以避免变量的重复计算，空间换时间，折中。动态规划,动态规划,Clique树法,将无向图构成,clique,树，采用消息传播的方法，计算查询的分布。,对图上任何节点的查询有效,Clique,树,2,与,4,有,G,，通路上,3, 5,也有。,2-4,构成,cluster,图上的一个通路。,注意，边是有向的，所有,cluster,的消息流向一个,cluster(7),，计算出最后结果，其称为根。,满足,RIP,的,cluster,图称为,clique,树。,C,i,与,C,j,是,cluster,图上一通路的两个,cluster,，至少存在一个变量,X,，使得,X,C,i,且,XC,j,，如果这个通路上的所有,cluster,均将包含,X,，称其满足,“,RIP,”,(Running Intersection Property),。,一条通路满足,RIP,，将保证这条通路均有某个变量，同时，构成的,cluster,图与,MN,具有相同的连接形式,(,拓扑结构,),。,Clique,树,基于,clique,树的变量消去法,(1)C,1,，根据,C,1,(C, D),，消去,C,，并将其作为消息,12,(D),送到,C,2,。,(2)C,2,，,2,(G,D,I)=,12,(D),2,(G,D,I),，消去,D,，,23,(G,I),送到,C,3,。,(3)C,3,，,3,(G,S,I)=,23,(G,I),3,(G,S,I),，消去,I,，,35,(G,I),送到,C,5,。,(4)C,4,，,H,4,(H,G,J),，消去,H,，送消息,45,(G,J),到,C,5,。,(5)C,5,，,5,(G,J,S,L)=,35,(G,S),45,(G,J),5,(G,J,S,L),。,5,=P(G,J,L,S),是联合分布，求,P(J),只需计算,G,L,S,5,。,(C)=,是初始势能。对,BN,，,(C, D) = P(C) P(D | C),。,注意,:,消息,2-3,(G,I)=,D,2,(G,D,I),Clique,变量消去算法,-,消息传播,(1),每个,clique,C,j,赋予初始势能,(,每个因子对应一个,clique),(2),计算,C,j,的邻居,C,i,向其传播消息，总计为：,(3),计算根节点的信度：,(,计算联合分布,),方法的优点：设定不同根节点，可以计算任意变量的边缘分布,P(C),。改变根节点只涉及个别消息传播,(,对传入多个消息的,clique,也是如此,),(4),计算查询变量的边缘分布,消元步骤,i,被校准的,Clique,树,-,图近似,Clique,树的主要问题之一是消息,ik,=,ki,可能不成立。,满足右式的两个,cluster C,1,与,C,2,，称为被校准,Clique,树上所有,cluster,是被校准，这个树称为被校准的,clique,树。,这样，连接两个节点的信度定义为：,被校准的,clique,树是联合分布的替代表示,被校准,clique,树的联合分布,(Gibbs),：,其中,将与代入上式,分子,分母,因为每个在分子分母只出现一次，可以消去，联合分布为各个,clique,初始能量的乘积。,意义：,Clique,树可以作为联合分布的替代表示。但需假设校准成立。近似！,“推断”问题的解法,提取公因子，以避免变量的重复计算，空间换时间，折中。动态规划,动态规划,Clique树法,优化法,将无向图构成,clique,树，采用消息传播的方法，计算查询的分布。对图上任何节点的查询有效,以相对熵为目标,(,多种方法之一,),，将概率查询变为有约束的优化问题，并使用拉格朗日乘子法求解。,(1),变量消去法与,clique,树消去法等价；,(2),后者,可以同时获得多个查询结果，且与变量序无关,(,校准条件,),。,基于优化的推断,P,与,Q,分别是精确推断与优化推断，使得,Q,与,P,的距离最小。,三个步骤：,(1),距离；,(2),图结构的目标函数和约束函数,；,(3),求解优化问题。,优化推断分为优化精确推断和优化近似推断，前者是,目标和约束空间,精确，后者是两者至少存在一个非精确。,目标：相对熵最小,能量泛函最大,相对熵,注意,取对数,令能量泛函,代入相对熵,计算一个,Q,使得其与精确推断,P,的相对熵最小，由于,lnZ,与,Q,无关，这样，以相对熵最小的目标可以使用能量泛函最大代替，由此，优化变为计算能量泛函最大的,Q,。,其中,X,为所有变量的集合，,Q,是,P,的近似。,Clique,树的因子能量泛函,上述泛函涉及所有变量的联合分布，不易设计优化算法。,Clique,树使用因子能量泛函，定义为：初始势能与传递的能量,(,消息,),。,Clique,树节点,C,i,的固有势能的期望,Clique,树分布,(,传递的能量,),的对数形式。,是信度,(,节点,(cluster),上的信息,),，,是,i,与,j,传递的所有消息,(,边上的信息,),这是研究校准,clique,树的原因之一。,Clique,树的约束精确优化推断,计算,使得,最大,对约束,是信度,(,节点,),是,i,与,j,传递的所有消息,(,边上,),Q,是节点和边上信息的并集，即，消息的网图上的传播。,基于,clique,树的优化推断算法,使用拉格朗日乘子，将上述约束变为下述方程的优化问题,以后类似感知机算法的推导，对与计算偏导，获得下式,这是一个迭代式，据此，可以设计优化精确推断的算法,基于优化的近似推断,一般地说，基于优化的近似推理的直接考虑是两个近似因素：其一，目标函数，其二，约束空间。,但是，其关键是：表示问题的图结构。如果为了计算等原因，使用了一种近似表示的图结构，这类图将更容易构造。相对精确描述，其目标函数和约束空间是近似的。,Cluster,图,采用消息传播方法的前提：其一，图结构是树，其二，满足,RIP,。,Cluster,图放弃条件,1,，不要求树，但需要满足被扩展的,RIP,被扩展的,RIP,：如果存在一个变量,X,，使得,X,C,i,且,XC,j,，则，在,C,i,与,C,j,之间，存在一个,单一,的通路，在这个通路的所有边,e,上，包含这个变量，,XS,e,。,关键,：对一个变量，两个,clusters,之间只有一个单一通路，例如，,3,与,2,之间，对变量,B,，,3-4-2,与,3-4-1-2,两个通路，如果,1,与,2,的边上是,B,，就不满足扩展,RIP,。,这是对图结构的约束。,构造,cluster,图,对,Cluster,图近似，不同的图可能导致完全不同的解答，这样，就存在一个选择哪个,cluster,图的问题，一般的原则是在高效计算和精度之间的折中。,左图是一个问题的两个,Cluster,图。差别在于，上图的,4-2,连线在下图不存在，在,1-2,连线上的变量下图从,C,变为,B, C,几种构图的方法，动机是容易处理，但不能违反,RIP,：,(,1),偶对,MN,。,(,2)Bethe Cluster,图。,构造“偶对,(,Pairwise)MN,”,这类图有两类,cluster,，其一，单变量势能,i,X,i,，其二，变量偶对势能,(i,j),X,i,X,j,，后者可以理解为,cluster,边上的势能。,Cluster,C,i,与,C,j,对应单变量,X,i,与,X,j,，,cluster,C,(i,j),(X,i,-X,j,),对应,X,i,X,j,边。,可以证明，,“,偶对,MN”,是,cluster,图。这样，这个图就可以使用消息传播的方式求解推断。,“,对,MN”,构造容易。,Bethe,Cluster,图,这类图有两层：其一，“大”,cluster,，是表现,MN,结构的因子,(Cluster,或,clique),，其二，“小”,cluster,，是单变量。,“大”cluster包含的变量与对应“小”变量cluster使用边连接。,可以证明，这个图也是cluster图，可以使用消息传播方法求解推断。这类图容易构造。,Cluster,图的优化推断算法,事实上，对,cluster,图，因子能量泛函也不能优化成精确解，理由,: (1),对边缘分布构成的多面体，每个,cluster,信度,(),不一定在这个多面体上，信度是对边缘分布的近似，,(2),判定信度集合是否在多面体上是,NP,难解。优化从多面体上变为局部一致,(,定义如下,),多面体上。伪边缘。,Cluster,图的优化,以下使用拉格朗日乘子推出具体算法，步骤如前。,与,clique,树优化约束的形式完全一样，其区别仅在：与的作用域，,clique,是在,clique,树上，这个约束是在图的一个局部,U,上。,在图结构下推断的本质是：计算查询变量的边缘分布，,P=,。关键是，是计算所有非查询变量取值的全组合。这个看似简单的问题，其复杂性远远超过我们的想象。,总结,近似推断主要涉及三类近似的方法：,(1),研究对图结构描述的近似，这是本质近似。,(2),研究对目标函数的近似，对给定图结构的近似。,(3),研究计算近似算法，精确算法无效，计算近似。,概率图模型近似推断核心是：“,精度和效率,”的折中。归根结底是表示的研究。,BN,如何直接使用各种近似？,三类近似没有一个容易，特别是其误差性质，除了计算近似之外，并没有本质进展。相当复杂，遍地问题！,一、引子二、表示三、推断四、学习五、结束语,概率图模型学习任务,假设：给定结构且样本是完整,(,所有变量被赋值,),的。,任务：学习参数，参数估计。,CPD,方法：,(1),最大似然估计, (2)Bayes,预测,假设：结构未知，但是，样本完整。,任务：学习结构和参数。,考虑一个可能结构的假设空间，结构选择变为优化问题。,假设：样本不完整，或某些变量未知。,任务：发现非显现表现的变量，知识发现。,对,BN,：,工具：最大似然和,Bayes,估计。,特点：从局部到整体的学习。,困难：鲁棒性，泛化。,对,MN,：,工具,:,最大似然, Bayes,估计,迭代优化,特点：鲁棒性，泛化。,困难：整体的划分函数和推断。,BN,的学习,-,目标函数,学习就是计算使得,L( : D),最大的。,似然函数：数据集合,D,，,BN,的参数或,(,与,),图,G,的似然函数,L( : D),其中可以是参数,(,给定,BN,结构,),，或者是,(,学习结构,),学习就是计算使得,P( | D),最大的。由于后验概率依赖先验概率与似然函数，问题变为计算这两个函数的问题。,Bayes,预测：数据集合,D,，,BN,的参数或图,G,的后验概率。,P( | D),其中可以是参数,(,给定,BN,结构,),，或者是图,G(,学习结构,),BN,的似然函数,假设,BN,结构给定，任务是确定参数。,令,X,i,是给定,BN,上的一个节点,(,变量,),，其父辈节点集合为,Pa,i,。,X,i,的,CPD (,因子,),为,P(X,i,|,Pa,Xi,),。给定数据集合,D,，,P(X,i,|,Pa,Xi,),对,D,的似然：,其中，,x,i,m,是,D,中变量,X,的第,m,个样本的值。,对给定样本集合，给定,BN,的似然为,基于,MLE,的学习算法,命题：令,D,是对变量,X,1,X,n,的完全数据集合，,G,是定义在这个变量集合上的,BN,，令,是使得,最大的参数，则 使得,L( : D),最大。,意义：满足一定假设，,BN,的整体最大似然，可以从局部最大似然获得。,学习算法：对,BN,的每个节点，在其父辈的条件下，根据数据集合，分别计算这个节点的最大似然。即，,根据上述命题，即可获得最后解答。,BN,的,Bayes,预测学习,任务：计算后验概率分布,P(,|D),，仅需计算似然函数,P(D|,),和先验概率分布,P(,),。,Bayes,预测学习就是计算这两个函数,给定,BN,，参数考虑为随机变量，表述为分布函数。,似然函数：对样本逐一计算。根据当前参数，修正参数,(,预测,),。,先验分布函数：希望先验与后验表示形式相同，,Dirichlet,分布。,对,BN,的预测学习，关键是需要将整体分布分解为局部分布。,其中,似然计算,似然函数,P(D|),的计算采用预测新样本的分布，给定,BN,，从,D,M,获得参数的分布，对新的观察,xM+1,，可以使用链式规则：,其中,D,M,是数据集合,D,中，前,M,个样本构成的集合。,D,M,(,M,),对,xM+1,独立。,这暗示，从样本集学习参数，可以一个一个样本逐步进行,预测,xM+1,变为：根据后验，对所有参数平均,(,期望,),，,先验分布,P(,),的选择,Dirichlet,分布： 满足先验概率与后验概率形式一致的要求。,k,：样本,k,值出现频率。,优点一：形式一致且紧凑。修改参数容易。,后验：,P(xM+1=,x,k,| D) =,E,P(|D),k,，对,Dirichlet,分布,E(,k,) = ,k,/ ,j,j,优点二：新参数是基于对已有参数的平均，这避免某个参数过学习的误差，带到新参数的估计。,学习,MN,对学习而言，,MN,与,BN,的区别是：,MN,的平均是在图结构整体上,(,划分函数,Z),，与图结构的所有参数相关联，不能分解。由此，不得不使用迭代的优化方法,好消息：似然函数能够保证收敛到全局最优。,坏消息：每次迭代需要推断。,注释,：对图结构，,BN,学习依赖数据集合分布,P(D),，由于,D,是给定的,，因此，,BN,可以分解为,部分求解,(,删除任何条件独立的边,),；对,MN,则依赖划分函数，,Z=,1,(X,1,),k,(X,k,),，这意味着，改变任何一个势函数,j,，,Z,将改变,，分解为局部是不可能的。这是,MN,不得不求助,优化,的原因。,MN,的似然函数,MN,已知，并表示为：,将写成权值和特征函数的形式：,i,(D,i,)=,i,f,i,(D,i,),。似然函数为,其中是表示变量关系的势函数，这里的,D,i,表示,i,涉及的变量观测,(,在,MN,上的完全子图,),取对数,注意：在特征函数中，,(zeta),表示第,m,个样本中与,f,有关变量的数值，这恰恰反映了,MN,的结构。方括号内是,M,个样本。,MN,参数估计算法,对数似然函数,为了计算最大似然，对求导，并令其为,0,。,右边第,1,项是对所有样本的平均,(,经验,),，第,2,项是对参数的平均,(,期望,),如果是最大似然参数，,iff,对所有,i,，,E,D,f,i,()=,E,f,i,。,学习结构,对一个由变量集合构成的图结构，有两个极端情况,(,平凡,),：,所有变量两两相连,A,B,E,C,D,所有变量不相连接,A,B,E,C,D,学习：部分相连,A,B,E,C,D,A,B,E,C,D,目标,: (1),根据给定数据集发现变量之间的关系，知识发现；,(2),密度估计，其本质是泛化。,加边,删边,核心：从数据集发现变量之间的独立关系,I-map,。,困难,: (1),噪音，没有绝对独立，,(2),稀疏解答。,结构学习的基本方法,(1),假设空间的模型选择：设计一个图结构对给定数据集合符合程度的评分准则。,(2)Bayes,模型平均：有些类似,Bagging,。,假设空间,-,模型选择的学习,假设空间：,待选的图模型，评分函数间接描述假设空间,评分函数：模型复杂程度和对给定数据集合的符合程度。,评分函数：,似然评分函数,Bayes,评分函数,似然评分函数,令,G,是一个待选的图结构，,G,是这个图结构上的参数，对给定数据集合,D,，关于,G,与,G,的似然函数：,L( : D),。,目标,:,从待选的图模型中选择似然最大的图模型,(,结构和参数,),似然评分函数： ，其中,l,是,MLE,参数下，对,G,的似然函数的对数形式。,Bayes,评分函数,与,MLE,的考虑类似，只是计算给定数据集合的图结构,G,的后验概率。,给定数据集合,D,，,G,表示图结构，计算,G,的后验概率：,Bayes,评分函数：,score,B,(G,: D) = log P(D | G) + log P(G),其中似然函数,第一项就是似然评分，,Bayes,评分就是增加了第二项，以使得我们获得更稀疏的图模型。,MN,结构学习,MN,结构未知，与,BN,研究方法一样，考虑：,(1),假设空间，,(2),目标函数,(,评分函数,),，,(3),优化算法。,假设空间的形式,其中，,M,是一个对数线性结构模型。任务就是根据给定样本集合，选择一个结构稀疏的,MN,模型。,评分函数,缺点：偏爱结构复杂的模型，需要限制，例如，如果,M,1,M,2,，,score,L,(M,1,:D)score,L,(M,2,:D),。这个限制太严厉，大多数情况难以满足。,似然评分函数,：,其中，,dim,是模型的维数，参数空间的自由度。缺点是这个维数很难估计。,Bayes,评分函数,：,BN,的优点是它的因子形式,P(X,|,Pa,X,),，这意味着，计算任何节点的分布，只与它的父辈有关，而与其它节点无关，然而，这也是它的最大缺点，即，每个节点分布的计算必须准确，否则误差将被传递。,总结,MN,的优点是它的因子形式与划分函数,Z,有关，这意味着，节点分布的误差，可以被整体平均消除。然而，这也是它的最大缺点，使得学习结构与参数不得不与推断相关联。,一、引子二、表示三、推断四、学习五、结束语,读“表示”,-,耳目一新,概率图模型表示的核心问题是“,条件独立,”，其中“条件”是关键。在传统统计学中，独立往往是假设，这个假设满足，研究简化，但是，不会将其作为核心研究课题。,条件概率分布,(CPD),因子与图结构对应，这样图结构上条件独立断言集合,I-map,成为描述模型的标志和关键。经验知识,无论有向图还是无向图，局部概率模型,(,即，,CPD),通过图结构整合为整体概率模型，这是最有吸引力的思考。而,CPD,的描述可以多种多样，传统统计模型，传统人工智能模型,既可泛化又可解释的模型,-,望眼欲穿。结构,+,平均,读“推断”,-,扼腕叹息,对问题使用带有复杂结构的表示，其推断就一定是一个复杂课题，,AI,就是如此,(,定理证明,),，而,ML,由于使用简洁的基函数作为表示,(,例如，多项式基,),，因此，推断不会是其研究的问题。概率图模型的麻烦就在于推断。,无论精确推断还是计算近似推断，图模型上的推断均是,NPC,。,近似图结构、近似目标函数和近似优化算法等近似被采用，,全面近似,！然而，从近似程度到有效计算，遍地问题。,NPC-,当头一棒。没有免费的午餐！,与,AI,和,ML,相比较，这类模型的推断灵活，对不同查询，无需重新建模,读“学习”,-,喜忧参半,给定图结构的学习没有什么新的考虑，基于表示的研究，从给定结构派生似然函数或,Bayes,后验概率函数没有困难，计算优化解将遇到推断的困难。,从给定数据学习结构就不是一件轻松的事情了，这类问题的可分解性需要严厉的条件，计算考虑迭代，遇到推断，大麻烦！由于划分函数的整体性，,MN,一开始就遇到推断。,图近似是关键,。,绕不开的推断,-,五味俱全。机会乎，陷阱乎？,预测与描述,预测与描述是数据挖掘提出的两个任务，但是，数据挖掘的描述任务一直开展不好,(,啤酒和尿布,),。被嘲笑！,图模型既可以消除噪音且表示紧凑,(,相对,AI,的穷举,),，还可以对模型的各个部分可解释。前者是预测,(,泛化,),，后者是描述,(,发现,),。,金融和生物等领域，计算机科学有两个策略：其一，代替领域专家,(,从数据建立可靠,(,泛化,),的模型,),，其二，为领域提供工具，简化专家的工作,(,知识发现,),。对这些领域，描述可能更好。对网络、语言、图像等领域，泛化是重要的，但是，发现同样重要。,概率图模型为数据挖掘的两个任务提供工具,!,？,思考：继续研究泛化，重启发现研究更重要,?,概率图模型前景如何？,历史的故事,线性感知机,基于最小二乘的,Rosenblatt,的感知机,(1956),，其本质是,平均,1943,年，,McCulloch,和,Pitts,的神经元工作方式，,1949,年，,Hebb,的学习律。,只能解决线性问题，不能满足实际的需要。埋下“祸根”。,20,世纪,70,年代面临的选择,统计优化,(,平均,),：,感知机,统计模式识别,复杂信息系统,(,结构,),：,专家系统,句法模式识别,选择,非线性问题,计算效率,专家系统合理,复杂问题求解,实现智能系统的理想,Duda,and,Hart73,AI,1969,年，,M.Minsky,发表颠覆性的报告，,“,Perceptron,”,。,表象是以,XOR,问题向以平均为基础的感知机发难，本质是试图以,结构,方法代替,平均,。全书使用拓扑作为工具。,1956,年，以复杂信息处理为契机，提出,AI,。其动机有二：其一，,发展处理符号的方法,，其二，处理非线性问题。,过分强调独立性，使得描述任何一个问题，需要穷举出所有可能。,80,年代，耗资巨大的,CYC,失败了。“祸根”。,20,世纪,80,年代面临的选择,概率图模型：,Markov,随机场,Bayes,网,人工神经网络：,BP,统计机器学习,选择,结构学习的困难,先验的结构,先验概率分布,字符识别，网络数据建模,误差界指导算法设计,算法基于线性感知机,总之，,无需先验知识,Gibbs1902, Wright1935,Clifford1971,Pearl1988,，,89,ANN,1991,年，,Vapnik,借用在,AI,中发展的,PAC,，给出了误差界，基于统计,(,平均,),的方法开始成为主流。,1986,年，,Remulhart,等人发表了巨篇,PDP,报告，其中一章是,BP,算法，使用非线性算法解决了,XOR,。其学术价值并不大，但是，人们开始重新尝试“平均”方法。,从,ANN,到,SVM,的发展得力于对字符识别的的成功,SML,其麻烦是借用,PAC,理论中有一个参数,，误差界以,1-,概率成立。这个参数很难在泛化意义下解释其含义,(,对,PAC,，其本意是描述问题复杂性的参数,),。理想，应该趋于,0,，但是，误差界将趋于无穷，成为平凡界。,Vapnik,的贡献：其一，误差界指导算法设计，其二，将算法设计返回感知机，即，线性算法，寻找线性空间,(,核映射,),。,平均成为主流。,新世纪开始，统计学家加入,SML,，完全放弃,PAC,。,维数灾难,高维空间上的统计理论，多重积分是麻烦，补充“合适”样本是麻烦。“同分布”只能停留在假设上，无法实施。,在高维空间,(,成百上千,),建模，最大的危险就是空间大的程度使得再多的样本，在这个空间上也是稀疏的。,由于困难具有本质性，平均遇到大麻烦！,自,然,模,型,采样,样本集,模型,算法,交叉验证,假设,iid,and PAC,统计机器学习的麻烦,？,设计实验,问题：,模型是自然模型吗？,统计机器学习,如果数据不充分，在大变量集合下，如何设计实验，获得新数据。,统计机器学习的困难：分布计算上，存在多重积分计算的问题，实验设计存在组合问题。,iid,成为与自然模型无关的假设！,概率图模型,将平均放在局部，避免了维数灾问题，同时保证了泛化和模型的可解释性，关键是结构，即，如何将局部的平均构造起来。,基于平均的研究已经过去,20,余年，,2009,年，,Koller,出版巨著,(,近,1200,页,),，概率图模型。,结构,(,全局,) +,平均,(,局部,),历史进程,-20,年河东，,20,年河西？,1986-,今天,平均,(,数值计算,),统计机器学习,1943-1969,平均,(,数值计算,),感知机,2000-,今后,平均,+,结构,?,概率图模型,？,1956-1986,结构,(,符号计算,),人工智能,M.,Minsky,等,Perceptrons,: An introduction to computational geometry. 1969,D.,Rumelhart,等,Parallel Distributed Processing, 1986,V.,Vapnik,The nature of statistical learning theory, 1995,T.Hastie,等,The Elements of Statistical Learning, 2003,D.,Koller,等,Probabilistic Graphical Models: Principles and Techniques, 2009,概率图模型的前途,前途需要等待两项研究结果：,其一，完成一个,ML,与,AI,均做不好，但是，概率图模型却能够做好,(,类似字符识别对,ML,的作用,),的任务，其领域也许是网络，分子生物学，金融决策，预测问题或描述问题？感觉是，这个标志性的研究可能是描述性的任务。,其二，一本解决推断问题的著作,(,类似,Vapnik,的著作，,BP,也是,NPC,问题,),，,谢 谢,愚者浅谈，不足为凭,痴人梦语，切勿轻信,