读DaphneKoller的“概率图模型”课件

中中中中国国国国科学院自动化研究所科学院自动化研究所科学院自动化研究所科学院自动化研究所Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009结构结构+平均平均-读读Daphne Koller的的“概率图模型概率图模型”王珏王珏中国科学院自动化研究所中国科学院自动化研究所模式识别国家重点实验室模式识别国家重点实验室2011年年4月月7日日中中中中国国国国科学院自动化研究所科学院自动化研究所科学院自动化研究所科学院自动化研究所Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009一、引子一、引子二、表示二、表示三、推断三、推断四、学习四、学习五、结束语五、结束语讲座分为五个部分，开头一个引讲座分为五个部分，开头一个引子，说明讲座的动机，最后一个子，说明讲座的动机，最后一个结束语，从历史发展的角度讨论结束语，从历史发展的角度讨论关注概率图模型的原因，中间三关注概率图模型的原因，中间三个部分，介绍个部分，介绍Koller这本书的三这本书的三个部分：表示个部分：表示(representation)、推断推断(inference)和学习和学习(learning)的基本思想和主要方法。的基本思想和主要方法。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所标题，标题，AI与与ML采用采用“结构结构+平均平均”作为标题，没有使用作为标题，没有使用“结构结构+统计统计”或或者者“人工智能人工智能+统计学统计学”，或，或“图图+概率概率”。“结构结构”与与“统计统计”似乎不具有同等地位，似乎不具有同等地位，“人工智能人工智能”与与“统计学统计学”水火不相容，水火不相容，“图图+概率概率”直观确切，其本质对应直观确切，其本质对应“结构结构”与与“平均平均”，对中文，对中文，“结构结构+平均平均”更美一些。更美一些。思考：人工智能思考：人工智能(AI)与统计机器学习与统计机器学习(ML)是否存在一个结是否存在一个结合点。但是，在理念上，合点。但是，在理念上，AI强调因果率强调因果率(结构结构)，不惜对排中，不惜对排中率破缺，统计方法强调排中率，不惜对因果率破缺，两者率破缺，统计方法强调排中率，不惜对因果率破缺，两者水火不相容。鉴于两者均已遇到根本性困难，有没有一种水火不相容。鉴于两者均已遇到根本性困难，有没有一种折衷的理念。折衷的理念。Koller这本书应该是这种折中的理念。这本书应该是这种折中的理念。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所极端的例子极端的例子对任意三角形识别对任意三角形识别(最简单的图形最简单的图形)，如果采用句法，如果采用句法(单纯结单纯结构构)方法，需要方法，需要“上下文敏感文法上下文敏感文法”描述，没有描述，没有Parsing算法。算法。成都地区暴雨预报，十年的数据。神经网络成都地区暴雨预报，十年的数据。神经网络(平均平均)，获得模，获得模型，验证，误报型，验证，误报5%。误报中有一个样本，预报大暴雨，实。误报中有一个样本，预报大暴雨，实际是晴天，各种因素均说明有暴雨，际是晴天，各种因素均说明有暴雨，但是但是，单纯结构或单纯平均需要满足严厉的条件，否则无效单纯结构或单纯平均需要满足严厉的条件，否则无效湿度指标低，湿度指标低，没有水没有水！当然没有暴雨！平均将这个重要指！当然没有暴雨！平均将这个重要指标与其他指标一起平均了。小学生不会犯的差错标与其他指标一起平均了。小学生不会犯的差错(80年代末年代末)Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所书中书中“学生学生”的例子的例子课程课程(D:难难=0，易，易=1)智力智力(I:聪明聪明=0，一般，一般=1)考试考试(G:A,B,C)SAT(S:好好=0，坏，坏=1)推荐推荐(L:强强=0，弱，弱=1)。以推荐作为查询变量以推荐作为查询变量(L)If D=0 G=A thenL=0If I=0 G=A thenL=0If D=1 I=1 G=A then L=1问题是：问题是：If D=1 I=0 G=A then L=?这就是人工智能遇到的难题！无这就是人工智能遇到的难题！无法泛化！法泛化！不同查询，不同规则！不同查询，不同规则！构造一个函数：构造一个函数：L=f(,D,I,G,S)观察一组学生，获得样本集。基函观察一组学生，获得样本集。基函数数L=1D+2I+3G+4S设计算法，确定设计算法，确定，获得模型。，获得模型。问题：模型为真需要多少样本，对问题：模型为真需要多少样本，对高维数据，不知道！模型不可解释高维数据，不知道！模型不可解释这就是统计机器学习遇到的难题。这就是统计机器学习遇到的难题。可以泛化，可以泛化，精度未知精度未知，不可解释。，不可解释。根据观察和专家经验，构造规则集根据观察和专家经验，构造规则集Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所问题本身的语义问题本身的语义课程难易程度与考试分数有关。课程难易程度与考试分数有关。学生智力与考试成绩有关。学生智力与考试成绩有关。学生智力与学生智力与SAT有关。有关。考试成绩与考试成绩与“推荐信强弱推荐信强弱”有关。有关。AI方案充分考虑了这种语义，方案充分考虑了这种语义，但是，将这种语义强化到唯但是，将这种语义强化到唯一表示程度一表示程度(当且仅当当且仅当)，缺，缺失灵活性。失灵活性。统计学习方案完全不考虑这统计学习方案完全不考虑这种语义，尽管具有灵活性种语义，尽管具有灵活性(泛泛化化)，但是，需要充分的观察，但是，需要充分的观察样本。样本。两者的共同代价是：维数灾难。前者，需要考虑所有可能两者的共同代价是：维数灾难。前者，需要考虑所有可能的组合的规则集合，后者，需要考虑充分的样本集合。的组合的规则集合，后者，需要考虑充分的样本集合。这种语义可以根据统这种语义可以根据统计分布获得，也可以计分布获得，也可以根据常识经验获得。根据常识经验获得。中中中中国国国国科学院自动化研究所科学院自动化研究所科学院自动化研究所科学院自动化研究所Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009ML强调给定变量集合张成的空间上计算平均的方法，抹煞强调给定变量集合张成的空间上计算平均的方法，抹煞变量之间的结构；变量之间的结构；AI强调变量的独立性，忽视变量之间的条强调变量的独立性，忽视变量之间的条件独立关系。是否可将变量子集件独立关系。是否可将变量子集(甚至一个变量甚至一个变量)的局部分布，的局部分布，根据变量之间内在的结构，转变为对变量集合整体的联合分根据变量之间内在的结构，转变为对变量集合整体的联合分布。这样，就可以既顾及了变量之间存在结构，又考虑了平布。这样，就可以既顾及了变量之间存在结构，又考虑了平均的必要性。概率图模型应该是一个这样的方案。均的必要性。概率图模型应该是一个这样的方案。这本著作包罗万象这本著作包罗万象(1200页页)，这个讲座是根据，这个讲座是根据我个人偏好我个人偏好，抽出最，抽出最基本的思考、研究方法，以及实现这个思考的基本理论。而书中基本的思考、研究方法，以及实现这个思考的基本理论。而书中罗列的大量具体的方法则认为：不是解决问题的唯一途径，而是罗列的大量具体的方法则认为：不是解决问题的唯一途径，而是存在的问题。这本著作数学符号体系繁杂，谈不上存在的问题。这本著作数学符号体系繁杂，谈不上“优美优美”。著。著作有四个部分：表示、推断、学习和作有四个部分：表示、推断、学习和action and decision，我们只，我们只讨论前三个部分。讨论前三个部分。中中中中国国国国科学院自动化研究所科学院自动化研究所科学院自动化研究所科学院自动化研究所Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009致谢致谢在我准备这个在我准备这个“笔记笔记”之前，王飞跃、宗成庆和我的之前，王飞跃、宗成庆和我的12个个学生参加了我们的一个讨论班，大家一起通读了学生参加了我们的一个讨论班，大家一起通读了Koller的这的这本书。这个讨论班对我准备这个本书。这个讨论班对我准备这个“笔记笔记”有很大的帮助，有很大的帮助，这些学生是：王飞跃教授的学生，顾原、周建英、陈诚和这些学生是：王飞跃教授的学生，顾原、周建英、陈诚和李泊；宗成庆教授的学生，庄涛和夏睿；我的学生韩彦军、李泊；宗成庆教授的学生，庄涛和夏睿；我的学生韩彦军、马奎俊、孙正雅、黄羿衡和吴蕾，以及吴高巍博士。在此马奎俊、孙正雅、黄羿衡和吴蕾，以及吴高巍博士。在此表示谢意。特别感谢韩素青和韩彦军帮助我检查和修改了表示谢意。特别感谢韩素青和韩彦军帮助我检查和修改了全部全部ppt。中中中中国国国国科学院自动化研究所科学院自动化研究所科学院自动化研究所科学院自动化研究所Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009一、引子一、引子二、表示二、表示三、推断三、推断四、学习四、学习五、结束语五、结束语Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所为什么为什么“表示表示”是一个专题是一个专题统计机器学习的表示统计机器学习的表示-基函数。确定基函数，没有表示问题。基函数。确定基函数，没有表示问题。给定变量集，完全图或给定变量集，完全图或完全不连接，完全不连接，平凡平凡！图的结构图的结构(不完全连接不完全连接)统计上条件独立统计上条件独立-因子因子条件独立的集合条件独立的集合(I-map)成为图结构的表征。成为图结构的表征。联合分布与边缘分布是图结构的概率描述联合分布与边缘分布是图结构的概率描述ABCDEBACDE不完全图不完全图-条件独立条件独立,两种表示两种表示。非平凡。非平凡Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所概率图模型概率图模型Bayes网网(Bayesian Network,BN)，有向图，有向图Markov网网(Markov Network,MN)，无向图，无向图各种局部概率模型各种局部概率模型(CPD)Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所从联合分布构造从联合分布构造Bayes网网(BN)学生问题，五个变量排成一个任意的序：学生问题，五个变量排成一个任意的序：I,D,G,L,S，其联合分布其联合分布(左左)，对应的完全，对应的完全BN(右右)：P(I,D,G,S,L)=difficultyIntelligenceGradeSATLetterP(I)P(S|I,D,G,L)P(D|I)P(G|I,D)P(L|I,D,G)构造构造Bayes网网因子因子完全图完全图节点节点G上的条件概率分布上的条件概率分布(CPD)Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所图上的独立性图上的独立性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)difficultyIntelligenceGradeSATLetterMachine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所分布分布P中的条件独立中的条件独立P(X)是随机变量集是随机变量集X中所有变量的联合分布，中所有变量的联合分布，P(Xi|Z)是是Xi关于关于Z的条件分布。的条件分布。Z X,Xi X且且Xi Z。条件独立：如果两个变量条件独立：如果两个变量Xi,Xj X，对条件，对条件Z独立，独立，iff P(Xi Xj|Z)=P(Xi|Z)P(Xj|Z)满足条件独立的所有断言满足条件独立的所有断言(Xi Xj|Z)，构成一个集合，构成一个集合，称为关于称为关于P的的I-map，记为，记为I(P)。对图对图G，所有彼此不相连的节点对集合为，所有彼此不相连的节点对集合为I(G)。如果如果I(G)I(P)，G是一个对独立集合是一个对独立集合I(P)的的I-map。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所BN上的独立上的独立YZXYZX (a)(d)绝对独立绝对独立(X Z),(d)。YZX(c)YXZ (b)YZX (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)如何？复杂！如何？复杂！Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所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上，两个节点之间没有连线，它们一定独立。上，两个节点之间没有连线，它们一定独立。YZXBN上判定独立的规则：上判定独立的规则：不满足条件，只能说不满足条件，只能说不能保证不能保证独立独立Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所因子化因子化(factorization)链式规则：链式规则：P(D,I,G,S,L)=P(I)P(D)P(G|I,D)P(L|G)P(S|I)满足条件独立假设的链式规则一般形式：令满足条件独立假设的链式规则一般形式：令PaX是图是图G上变上变量量X的所有父结点，变量集合的联合分布可以表示为：的所有父结点，变量集合的联合分布可以表示为：P(X1,Xn)=P(Xi|PaXi)，其中，其中P(Xi|PaXi)称为因子。称为因子。定理：如果图定理：如果图G是一个对是一个对I(P)的的I-map，则，则P可以根据可以根据G因子因子化化(注意注意，因子的定义，满足条件独立假设，因子的定义，满足条件独立假设)。逆定理成立。逆定理成立。注意：注意：仅是因子化，而不是任意仅是因子化，而不是任意P可以使用可以使用G描述。描述。I(G)I(P)Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所最小最小mapD,I,S,G,LL,S,G,I,DL,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，具有不，具有不同的结构。没有唯一性！这同的结构。没有唯一性！这个结论不成立！个结论不成立！Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所P-map(perfect)P-map：如果：如果I(G)=I(P)，G是一个是一个P-map。意义意义：对任何一个：对任何一个P，是否保证存在一个，是否保证存在一个G的的P-mapABDCDBCA对对P,(A C|B,D)与与(B D|A,C)。存在使得。存在使得A与与C，B与与D不相连接的不相连接的BN？考察考察(B D|A,C)：考察考察(A C|B,D)考察考察(A C|B,D):(A C|B)，ABC是是(b)，如果，如果B已知，成立已知，成立(A C|D)，ADC是是(b)，如果，如果D已知，成立已知，成立(B D|A)，DAB是是(c),A已知已知,成立。成立。(B D|C)，DCB(v-结构结构)，C已知，已知，B与与D不独立。不独立。(B D|C)不成立。不成立。(B D|A,C)不成立不成立(A C|B,D)成成立立CDA(c类类)，D已知，已知，(A C)，CBA，B已知，已知，(A C)。DCB(v)，C已知，已知，(D B)不成立不成立回答是不能保证回答是不能保证Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所概率图模型概率图模型Bayes网网(Bayesian Network,BN)，有向图，有向图Markov网网(Markov Network,MN)，无向图，无向图各种局部概率模型各种局部概率模型(CPD)Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所 Markov网网(MN)n尽管尽管MN(MN(无向图无向图)以完全子图的因子为基础，但是，以完全子图的因子为基础，但是，MNMN上的完全子图依赖条件独立，因为节点之间连上的完全子图依赖条件独立，因为节点之间连线的删除，将直接导致不同的完全子图。线的删除，将直接导致不同的完全子图。n因子是一个从变量因子是一个从变量D D子集到正实数域子集到正实数域+上的映射上的映射(函数函数)。中中中中国国国国科学院自动化研究所科学院自动化研究所科学院自动化研究所科学院自动化研究所Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009表示联合分布与因子表示联合分布与因子其中其中Di(i=1,k)是是MN H上的完全子图上的完全子图(典型是典型是clique)，=1(D1),k(Dk)称为分布称为分布P 的因子集合。的因子集合。1(D1),k(Dk)满足满足:P称为称为Gibbs分布分布Z称为划分函数称为划分函数与与BN比较，联合分布是对完全子图势能的平均。计算比较，联合分布是对完全子图势能的平均。计算Clique(最大完全子图最大完全子图)是是NPC。势能函数势能函数CADBMachine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所I-map与因子化与因子化I-map:I(P)是在是在P中形如中形如(X Y|Z)独立的集合。与独立的集合。与BN定义一致。定义一致。MN与与BN一样，有一个关于因子化的定理一样，有一个关于因子化的定理BNMN令令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)Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所“偶对偶对”独立独立IP(H)=(X Y|U-X,Y):XY H意味着：不连接的偶对节点在其他节点条件下相互独立。意味着：不连接的偶对节点在其他节点条件下相互独立。(A D|B,C,E)(B C|A,D,E)(D E|A,B,C)DABCEMachine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所Blanket独立独立这是这是“偶对偶对”独立的推广。令独立的推广。令B(X)是节点是节点X在在H(MN)的所的所有直接邻居节点集合。有直接邻居节点集合。IL(H)=(X U-X-B(X)|B(X):X H意味着：意味着：X在所有直接邻居条件下，与其他节点独立。在所有直接邻居条件下，与其他节点独立。DABCE对节点对节点B，B(B)=A,D,E,B与与C是是Blanket独立。独立。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所独立形式与构图方法独立形式与构图方法d-分离：分离：在任意节点在任意节点x X与与y Y通路上，存在一个节点通路上，存在一个节点Z已知已知,在在Z下，其他节点相互独立。下，其他节点相互独立。I(P)BCAD(D A,C|B)偶对：不连接的偶对独立，偶对：不连接的偶对独立，IP(P)IP(H)=(X Y|U-X,Y):X-Y H(A D|B,C,E)DABCEDABCEBlanket：对：对X的所有直接邻居，的所有直接邻居，X与其与其他节点独立。他节点独立。IL(P)节点节点B，B(B)=A,D,E,与与C是是Blanket独立独立IP(P)IL(P)I(P)如果如果P 0(正分布正分布)，则则IP(P)=IL(P)=I(P)构图方法：偶对或构图方法：偶对或Blanket。构成的构成的MN，均是唯一最小，均是唯一最小I-map。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所BN的的Moral图图-BNMNG是是BN的的Moral图是一个无向图，对两个节点图是一个无向图，对两个节点X与与Y满足：满足：(1)G中，连接的节点保持连接。中，连接的节点保持连接。(2)G中，中，X与与Y有共同子孙，有共同子孙，X与与Y连接。连接。v-结构。结构。BNBN的的Moral图图v-结构结构:DKI，如，如果果K未被观察，未被观察，D与与I独立，独立，K以被观察，以被观察，D和和I就相关。相连！就相关。相连！Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所概率图模型概率图模型Bayes网网(Bayesian Network,BN)，有向图，有向图Markov网网(Markov Network,MN)，无向图，无向图各种局部概率模型各种局部概率模型Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所各种各种CPD-局部概率模型局部概率模型讨论了网络的结构之后，需要关注附加在节讨论了网络的结构之后，需要关注附加在节点点(边边)上的各种不同描述的条件上的各种不同描述的条件(局部局部)概率概率分布分布(CPD)，如何确定因子。，如何确定因子。满足：满足：P(x|paX)=1。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所各种各种CPDTabular CPD：使用表描述：使用表描述P(X|PaX)0，判定判定CPD：判定函数：判定函数Logistic CPD：线性高斯线性高斯 CPD：树与规则树与规则CPD中中中中国国国国科学院自动化研究所科学院自动化研究所科学院自动化研究所科学院自动化研究所Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009网图有两个要素：其一，网图的结构，其二，网图有两个要素：其一，网图的结构，其二，网图节点上的条件概率分布。在学习时，这两网图节点上的条件概率分布。在学习时，这两个要素将成为学习的两个方面。结构可以由经个要素将成为学习的两个方面。结构可以由经验来构造。验来构造。对节点上的概率分布的学习，将基于这些对节点上的概率分布的学习，将基于这些CPD表示形式，可以理解为学习的表示形式，可以理解为学习的“基函数基函数”(局局部表示部表示)。经验知识可以无障碍地被引入。经验知识可以无障碍地被引入。中中中中国国国国科学院自动化研究所科学院自动化研究所科学院自动化研究所科学院自动化研究所Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009一、引子一、引子二、表示二、表示三、推断三、推断四、学习四、学习五、结束语五、结束语Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所查询问题查询问题-基于图的推断基于图的推断概率查询概率查询(Y边缘边缘)：根据：根据给定图给定图，计算，计算P(Y|E=e)，其中，其中，E是证据变量，是证据变量，Y是查询变量。读为：在证是查询变量。读为：在证据据e条件下，条件下，Y出现的概率出现的概率(边缘概率边缘概率)。MAP查询：计算查询：计算MAP(W|e)=arg maxw P(w,e)。其中，。其中，W=-E。读为：在证据。读为：在证据e条件下，在条件下，在W中求出最适合的赋值。中求出最适合的赋值。边缘边缘MAP查询：令查询：令Z=-Y-E，计算，计算MAP(Y|e)=arg maxY P(Y,Z|e)。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所边缘查询边缘查询-基于图的推断基于图的推断边缘查询原理边缘查询原理:(1)根据根据BN，计算联合分布，计算联合分布P()=P(Xi|PaXi)(2)计算在计算在E下，变量下，变量Y的边缘的边缘分布：分布：P(Y|E)=X-Y-EP()这个貌似简单的任务，由于计这个貌似简单的任务，由于计算边缘分布需要取遍非查询变算边缘分布需要取遍非查询变量所有值的组合。十分困难。量所有值的组合。十分困难。学生聪明学生聪明i1，不高兴，不高兴h0，BN下下，查询学生工作机会。查询学生工作机会。P(J|i1,h0)。变量集合变量集合:=C,D,I,G,S,L,J,H根据根据BN，计算联合分布，计算联合分布P()。在证据在证据E下的下的J的边缘分布：的边缘分布：P(J|i1,h0)=WP(),W=-J-H,I 精确推断是精确推断是NPC。中中中中国国国国科学院自动化研究所科学院自动化研究所科学院自动化研究所科学院自动化研究所Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009无论无论BN还是还是MN，其上的推断是，其上的推断是NPC问题，问题，计算近似推断也不能幸免。计算近似推断也不能幸免。近似推断：图近似近似推断：图近似(本质近似本质近似)，目标近似，目标近似和计算近似和计算近似(包括算法近似包括算法近似)。概率图模型推断研究的焦点是：概率图模型推断研究的焦点是：精度和效精度和效率率之间有效之间有效折中折中。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所“推断推断”问题的解法问题的解法提取公因子，提取公因子，以避免变量的以避免变量的重复计算，空重复计算，空间换时间，折间换时间，折中。动态规划中。动态规划动态规划动态规划Clique树法树法优化法优化法以相对熵为目标以相对熵为目标(多多种方法之一种方法之一)，将概，将概率查询变为有约束率查询变为有约束的优化问题，并使的优化问题，并使用拉格朗日乘子法用拉格朗日乘子法求解。求解。将无向图构成将无向图构成clique树，采用消息传播树，采用消息传播的方法，计算查询的方法，计算查询的分布。对图上任的分布。对图上任何节点的查询有效何节点的查询有效Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所BN变量消去法变量消去法-计算计算P(D)BN网：网：ABCD对对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)。ABCD联合分布：联合分布：P(A,B,C,D)=P(A)P(B|A)P(C|B)P(D|C)Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所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 是和积形式，是和积形式，它是从联它是从联合分布计算边缘分布的基本形式合分布计算边缘分布的基本形式Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所“推断推断”问题的解法问题的解法提取公因子，提取公因子，以避免变量的以避免变量的重复计算，空重复计算，空间换时间，折间换时间，折中。动态规划中。动态规划动态规划动态规划Clique树法树法将无向图构成将无向图构成clique树，采用消息传播树，采用消息传播的方法，计算查询的方法，计算查询的分布。的分布。对图上任对图上任何节点的查询有效何节点的查询有效中中中中国国国国科学院自动化研究所科学院自动化研究所科学院自动化研究所科学院自动化研究所Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009Clique树树2与与4有有G，通路上，通路上3,5也有。也有。2-4构成构成cluster图上的一个通路。图上的一个通路。注意，边是有向的，所有注意，边是有向的，所有cluster的消的消息流向一个息流向一个cluster(7)，计算出最后结，计算出最后结果，其称为根。果，其称为根。满足满足RIP的的cluster图称图称为为clique树。树。Ci与与Cj是是cluster图上一通路的两个图上一通路的两个cluster，至，至少存在一个变量少存在一个变量X，使得，使得X Ci且且X Cj，如果，如果这个通路上的所有这个通路上的所有cluster均将包含均将包含X，称其满，称其满足足“RIP”(Running Intersection Property)。一条通路满足一条通路满足RIP，将保证这条通路均有某个，将保证这条通路均有某个变量，同时，构成的变量，同时，构成的cluster图与图与MN具有相同的具有相同的连接形式连接形式(拓扑结构拓扑结构)。Clique树树 Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所基于基于clique树的变量消去法树的变量消去法(1)C1，根据，根据 C 1(C,D)，消去，消去C，并将其作为消息，并将其作为消息 12(D)送到送到C2。(2)C2，2(G,D,I)=12(D)2(G,D,I)，消去，消去D，23(G,I)送到送到C3。(3)C3，3(G,S,I)=23(G,I)3(G,S,I)，消去，消去I，35(G,I)送到送到C5。(4)C4，H 4(H,G,J)，消去，消去H，送消息，送消息 45(G,J)到到C5。(5)C5，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)Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所Clique变量消去算法变量消去算法-消息传播消息传播(1)每个每个clique Cj赋予初始势能赋予初始势能(每个因子对应一个每个因子对应一个clique)(2)计算计算Cj的邻居的邻居Ci向其传播消向其传播消息，总计为：息，总计为：(3)计算根节点的信度：计算根节点的信度：(计算计算联合分布联合分布)方法的优点：设定不同根节点，可以计算任意变量的边缘分布方法的优点：设定不同根节点，可以计算任意变量的边缘分布P(C)。改变根节点只涉及个别消息传播改变根节点只涉及个别消息传播(对传入多个消息的对传入多个消息的clique也是如此也是如此)(4)计算查询变量的边缘分布计算查询变量的边缘分布 消元消元步骤步骤 iMachine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所被校准的被校准的Clique树树-图近似图近似Clique树的主要问题之一是消息树的主要问题之一是消息 ik=ki可能不成立。可能不成立。满足右式的两个满足右式的两个cluster C1与与C2，称为被校准，称为被校准Clique树上所有树上所有cluster是被校准，这个是被校准，这个树称为被校准的树称为被校准的clique树。树。这样，连接两个节点的这样，连接两个节点的信度定义为：信度定义为：Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所被校准的被校准的clique树是联合分布的替代表示树是联合分布的替代表示被校准被校准clique树的联合分布树的联合分布(Gibbs)：其中其中将将 与与 代入上式代入上式分子分子分母分母因为每个因为每个 在分子分母只出现一在分子分母只出现一次，可以消去，联合分布为各个次，可以消去，联合分布为各个clique初始能量的乘积。初始能量的乘积。意义：意义：Clique树可以作为联合分布树可以作为联合分布的替代表示。但需假设校准成立。的替代表示。但需假设校准成立。近似！近似！Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所“推断推断”问题的解法问题的解法提取公因子，提取公因子，以避免变量的以避免变量的重复计算，空重复计算，空间换时间，折间换时间，折中。动态规划中。动态规划动态规划动态规划Clique树法树法优化法优化法将无向图构成将无向图构成clique树，采用消息传播树，采用消息传播的方法，计算查询的方法，计算查询的分布。对图上任的分布。对图上任何节点的查询有效何节点的查询有效以相对熵为目标以相对熵为目标(多多种方法之一种方法之一)，将概，将概率查询变为有约束率查询变为有约束的优化问题，并使的优化问题，并使用拉格朗日乘子法用拉格朗日乘子法求解。求解。(1)变量消去法与变量消去法与clique树消去法等价；树消去法等价；(2)后者后者可以同时获可以同时获得多个查询结果，且与变量序无关得多个查询结果，且与变量序无关(校准条件校准条件)。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所基于优化的推断基于优化的推断P与与Q分别是精确推断与优化推断，使得分别是精确推断与优化推断，使得Q与与P的的距离最小。距离最小。三个步骤：三个步骤：(1)距离；距离；(2)图结构的目标函数和约图结构的目标函数和约束函数束函数；(3)求解优化问题。求解优化问题。优化推断分为优化精确推断和优化近似推断，前优化推断分为优化精确推断和优化近似推断，前者是者是目标和约束空间目标和约束空间精确，后者是两者至少存在精确，后者是两者至少存在一个非精确。一个非精确。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所目标：相对熵最小目标：相对熵最小能量泛函最大能量泛函最大相对熵相对熵注意注意取对数取对数令能量泛函令能量泛函代入相对熵代入相对熵计算一个计算一个Q使得其与精确推断使得其与精确推断P 的相对熵最小，由于的相对熵最小，由于lnZ与与Q无关，这样，以相对熵最小的目标可以使用能量泛函最大无关，这样，以相对熵最小的目标可以使用能量泛函最大代替，由此，优化变为计算能量泛函最大的代替，由此，优化变为计算能量泛函最大的Q。其中其中X为所有变量的集合，为所有变量的集合，Q是是P 的近似。的近似。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所Clique树的因子能量泛函树的因子能量泛函上述泛函涉及所有变量的联合分布，不易设计优化算法。上述泛函涉及所有变量的联合分布，不易设计优化算法。Clique树使用树使用因子能量泛函，定义为：初始势能与传递的能量因子能量泛函，定义为：初始势能与传递的能量(消息消息)。Clique树节点树节点 Ci的的固有势能的期望固有势能的期望Clique树分布树分布(传递的能量传递的能量)的对数形式。的对数形式。是信度是信度(节点节点(cluster)上的信息上的信息)，是是i与与j传递的所有消息传递的所有消息(边上的信息边上的信息)这是研究校准这是研究校准clique树的原因之一。树的原因之一。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所Clique树的约束精确优化推断树的约束精确优化推断计算计算使得使得最大最大对约束对约束 是信度是信度(节点节点)是是i与与j传递的所有消息传递的所有消息(边上边上)Q是节点和边上信息的并集，是节点和边上信息的并集，即，消息的网图上的传播。即，消息的网图上的传播。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所基于基于clique树的优化推断算法树的优化推断算法使用拉格朗日乘子，将上述约束变为下述方程的优化问题使用拉格朗日乘子，将上述约束变为下述方程的优化问题以后类似感知机算法的推导，对以后类似感知机算法的推导，对 与与 计算偏导，获得下式计算偏导，获得下式这是一个迭代式，据此，可这是一个迭代式，据此，可以设计优化精确推断的算法以设计优化精确推断的算法Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所基于优化的近似推断基于优化的近似推断一般地说，基于优化的近似推理的直接考虑是两个一般地说，基于优化的近似推理的直接考虑是两个近似因素：其一，目标函数，其二，约束空间。近似因素：其一，目标函数，其二，约束空间。但是，其关键是：表示问题的图结构。如果为了计但是，其关键是：表示问题的图结构。如果为了计算等原因，使用了一种近似表示的图结构，这类图算等原因，使用了一种近似表示的图结构，这类图将更容易构造。相对精确描述，其目标函数和约束将更容易构造。相对精确描述，其目标函数和约束空间是近似的。空间是近似的。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所Cluster图图采用消息传播方法的前提：其一，图结构是树，其二，满足采用消息传播方法的前提：其一，图结构是树，其二，满足RIP。Cluster图放弃条件图放弃条件1，不要求树，但需要满足被扩展的，不要求树，但需要满足被扩展的RIP被扩展的被扩展的RIP：如果存在一个变量：如果存在一个变量X，使得，使得X Ci且且X Cj，则，则，在在Ci与与Cj之间，存在一个之间，存在一个单一单一的通路，在这个通路的所有边的通路，在这个通路的所有边e上，上，包含这个变量，包含这个变量，X Se。关键关键：对一个变量，两个：对一个变量，两个clusters之间只有一个单一通路，例如，之间只有一个单一通路，例如，3与与2之间，对变量之间，对变量B，3-4-2与与3-4-1-2两个通路，如果两个通路，如果1与与2的边上是的边上是B，就不满足扩展，就不满足扩展RIP。这是对图结构的约束。这是对图结构的约束。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所构造构造cluster图图对对Cluster图近似，不同的图可能导致完全不同的解答，这样，就图近似，不同的图可能导致完全不同的解答，这样，就存在一个选择哪个存在一个选择哪个cluster图的问题，一般的原则是在高效计算和图的问题，一般的原则是在高效计算和精度之间的折中。精度之间的折中。左图是一个问题的两个左图是一个问题的两个Cluster图。差别在于，上图的图。差别在于，上图的4-2连连线在下图不存在，在线在下图不存在，在1-2连线连线上的变量下图从上的变量下图从C变为变为B,C几种构图的方法，动机是容易几种构图的方法，动机是容易处理，但不能违反处理，但不能违反RIP：(1)偶对偶对MN。(2)Bethe Cluster图。图。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所构造构造“偶对偶对(Pairwise)MN”这类图有两类这类图有两类cluster，其一，单变量势能，其一，单变量势能 iXi，其二，变量偶对，其二，变量偶对势能势能(i,j)Xi,Xj，后者可以理解为，后者可以理解为cluster边上的势能。边上的势能。Cluster Ci与与Cj对应单变量对应单变量Xi与与Xj，cluster C(i,j)(Xi-Xj)对对应应XiXj边。边。可以证明，可以证明，“偶对偶对MN”是是cluster图。这样，这个图就可图。这样