概率图模型课件中科院王珏

资源描述

《概率图模型课件中科院王珏》由会员分享，可在线阅读，更多相关《概率图模型课件中科院王珏（94页珍藏版）》请在金锄头文库上搜索。

1、中中中中国国国国科学院自动化研究所科学院自动化研究所科学院自动化研究所科学院自动化研究所Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009结构结构+平均平均 -读读Daphne Koller的的“概率图模型概率图模型”王珏王珏中国科学院自动化研究所中国科学院自动化研究所模式识别国家重点实验室模式识别国家重点实验室2011年年4月月7日日中中中中国国国国科学院自动化研究所科学院自动化研究所科学院自动化研究所科学院自动化研究所Machine Learning and Data Mining 2009M

2、achine Learning and Data Mining 2009一、引子一、引子二、表示二、表示三、推断三、推断四、学习四、学习五、结束语五、结束语讲座分为五个部分，开头一个引讲座分为五个部分，开头一个引子，说明讲座的动机，最后一个子，说明讲座的动机，最后一个结束语，从历史发展的角度讨论结束语，从历史发展的角度讨论关注概率图模型的原因，中间三关注概率图模型的原因，中间三个部分，介绍个部分，介绍Koller这本书的三这本书的三个部分：表示个部分：表示(representation)、推断推断(inference)和学习和学习(learning)的基本思想和主要方法。的基本思想和主要方法。

3、Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所标题，标题，AI与与ML采用采用“结构结构+平均平均”作为标题，没有使用作为标题，没有使用“结构结构+统计统计”或或者者“人工智能人工智能+统计学统计学”，或，或“图图+概率概率”。“结构结构”与与“统计统计”似乎不具有同等地位，似乎不具有同等地位，“人工智能人工智能”与与“统计学统计学”水火不相容，水火不相容，“图图+概率概率”直观确切，其本质对应直观确切，其本质对应“结构结构”与与“平均平均”，对中文

4、，对中文，“结构结构+平均平均”更美一些。更美一些。思考：人工智能思考：人工智能(AI)与统计机器学习与统计机器学习(ML)是否存在一个结是否存在一个结合点。但是，在理念上，合点。但是，在理念上，AI强调因果率强调因果率(结构结构)，不惜对排中，不惜对排中率破缺，统计方法强调排中率，不惜对因果率破缺，两者率破缺，统计方法强调排中率，不惜对因果率破缺，两者水火不相容。鉴于两者均已遇到根本性困难，有没有一种水火不相容。鉴于两者均已遇到根本性困难，有没有一种折衷的理念。折衷的理念。Koller这本书应该是这种折中的理念。这本书应该是这种折中的理念。Machine Learning and Data

5、Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所极端的例子极端的例子对任意三角形识别对任意三角形识别(最简单的图形最简单的图形)，如果采用句法，如果采用句法(单纯结单纯结构构)方法，需要方法，需要“上下文敏感文法上下文敏感文法”描述，没有描述，没有Parsing算法。算法。成都地区暴雨预报，十年的数据。神经网络成都地区暴雨预报，十年的数据。神经网络(平均平均)，获得模，获得模型，验证，误报型，验证，误报5%。误报中有一个样本，预报大暴雨，实。误报中有一个样本，预报大暴雨，实际是晴天，各种因素均说明有暴雨

6、，际是晴天，各种因素均说明有暴雨，但是但是，单纯结构或单纯平均需要满足严厉的条件，否则无效单纯结构或单纯平均需要满足严厉的条件，否则无效湿度指标低，湿度指标低，没有水没有水！当然没有暴雨！平均将这个重要指！当然没有暴雨！平均将这个重要指标与其他指标一起平均了。小学生不会犯的差错标与其他指标一起平均了。小学生不会犯的差错(80年代末年代末)Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所书中书中“学生学生”的例子的例子课程课程(D:难难=0，易，易=1)

7、智力智力(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)观察一组学生，获得样本集。基函观察一组学生

8、，获得样本集。基函数数L = 1D + 2I + 3G + 4S设计算法，确定设计算法，确定，获得模型。，获得模型。问题：模型为真需要多少样本，对问题：模型为真需要多少样本，对高维数据，不知道！模型不可解释高维数据，不知道！模型不可解释这就是统计机器学习遇到的难题。这就是统计机器学习遇到的难题。可以泛化，可以泛化，精度未知精度未知，不可解释。，不可解释。根据观察和专家经验，构造规则集根据观察和专家经验，构造规则集Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研

9、研究究所所问题本身的语义问题本身的语义课程难易程度与考试分数有关。课程难易程度与考试分数有关。学生智力与考试成绩有关。学生智力与考试成绩有关。学生智力与学生智力与SAT有关。有关。考试成绩与考试成绩与“推荐信强弱推荐信强弱”有关。有关。AI方案充分考虑了这种语义，方案充分考虑了这种语义，但是，将这种语义强化到唯但是，将这种语义强化到唯一表示程度一表示程度(当且仅当当且仅当)，缺，缺失灵活性。失灵活性。统计学习方案完全不考虑这统计学习方案完全不考虑这种语义，尽管具有灵活性种语义，尽管具有灵活性(泛泛化化)，但是，需要充分的观察，但是，需要充分的观察样本。样本。两者的共同代价是：维数灾难。前者，需

10、要考虑所有可能两者的共同代价是：维数灾难。前者，需要考虑所有可能的组合的规则集合，后者，需要考虑充分的样本集合。的组合的规则集合，后者，需要考虑充分的样本集合。这种语义可以根据统这种语义可以根据统计分布获得，也可以计分布获得，也可以根据常识经验获得。根据常识经验获得。中中中中国国国国科学院自动化研究所科学院自动化研究所科学院自动化研究所科学院自动化研究所Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009ML强调给定变量集合张成的空间上计算平均的方法，抹煞强调给定变量集合张成的空间上计算平均的方法，

11、抹煞变量之间的结构；变量之间的结构；AI强调变量的独立性，忽视变量之间的条强调变量的独立性，忽视变量之间的条件独立关系。是否可将变量子集件独立关系。是否可将变量子集(甚至一个变量甚至一个变量)的局部分布，的局部分布，根据变量之间内在的结构，转变为对变量集合整体的联合分根据变量之间内在的结构，转变为对变量集合整体的联合分布。这样，就可以既顾及了变量之间存在结构，又考虑了平布。这样，就可以既顾及了变量之间存在结构，又考虑了平均的必要性。概率图模型应该是一个这样的方案。均的必要性。概率图模型应该是一个这样的方案。这本著作包罗万象这本著作包罗万象(1200页页)，这个讲座是根据，这个讲座是根据我个人偏

12、好我个人偏好，抽出最，抽出最基本的思考、研究方法，以及实现这个思考的基本理论。而书中基本的思考、研究方法，以及实现这个思考的基本理论。而书中罗列的大量具体的方法则认为：不是解决问题的唯一途径，而是罗列的大量具体的方法则认为：不是解决问题的唯一途径，而是存在的问题。这本著作数学符号体系繁杂，谈不上存在的问题。这本著作数学符号体系繁杂，谈不上“优美优美”。著。著作有四个部分：表示、推断、学习和作有四个部分：表示、推断、学习和action and decision，我们只，我们只讨论前三个部分。讨论前三个部分。中中中中国国国国科学院自动化研究所科学院自动化研究所科学院自动化研究所科学院自动化研究所M

13、achine Learning and Data Mining 2009Machine Learning and Data Mining 2009致谢致谢在我准备这个在我准备这个“笔记笔记”之前，王飞跃、宗成庆和我的之前，王飞跃、宗成庆和我的12个个学生参加了我们的一个讨论班，大家一起通读了学生参加了我们的一个讨论班，大家一起通读了Koller的这的这本书。这个讨论班对我准备这个本书。这个讨论班对我准备这个“笔记笔记”有很大的帮助，有很大的帮助，这些学生是：王飞跃教授的学生，顾原、周建英、陈诚和这些学生是：王飞跃教授的学生，顾原、周建英、陈诚和李泊；宗成庆教授的学生，庄涛和夏睿；我的学生韩彦军

14、、李泊；宗成庆教授的学生，庄涛和夏睿；我的学生韩彦军、马奎俊、孙正雅、黄羿衡和吴蕾，以及吴高巍博士。在此马奎俊、孙正雅、黄羿衡和吴蕾，以及吴高巍博士。在此表示谢意。特别感谢韩素青和韩彦军帮助我检查和修改了表示谢意。特别感谢韩素青和韩彦军帮助我检查和修改了全部全部ppt。中中中中国国国国科学院自动化研究所科学院自动化研究所科学院自动化研究所科学院自动化研究所Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009一、引子一、引子二、表示二、表示三、推断三、推断四、学习四、学习五、结束语五、结束语Machi

15、ne Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所为什么为什么“表示表示”是一个专题是一个专题统计机器学习的表示统计机器学习的表示-基函数。确定基函数，没有表示问题。基函数。确定基函数，没有表示问题。给定变量集，完全图或给定变量集，完全图或完全不连接，完全不连接，平凡平凡！图的结构图的结构(不完全连接不完全连接)统计上条件独立统计上条件独立-因子因子条件独立的集合条件独立的集合(I-map)成为图结构的表征。成为图结构的表征。联合分布与边缘分布是图结构的概率描述联

16、合分布与边缘分布是图结构的概率描述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 2009Ma

17、chine 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上

19、telligenceGradeSATLetterMachine 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

20、 | 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

21、)。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)如何？复杂！如何？复杂！Mach

22、ine 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已被

23、观察已被观察(a)(b)(c)。BN最麻烦的是最麻烦的是v-结构，用树结构近似结构，用树结构近似BN，就是删除，就是删除v-结构。这时，结构。这时，BN上，两个节点之间没有连线，它们一定独立。上，两个节点之间没有连线，它们一定独立。YZXBN上判定独立的规则：上判定独立的规则：不满足条件，只能说不满足条件，只能说不能保证不能保证独立独立Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所因子化因子化(factorization)链式规则：链式规则：P(D,

24、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因子因子化化(注意注意，因子的定义，满足条件独立假设，因子的定义，满足条件独立假设)。逆定理成立。逆定理成立。注意：注

25、意：仅是因子化，而不是任意仅是因子化，而不是任意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上移除任何一个单边，它将不再是

26、上移除任何一个单边，它将不再是I-map(不在不在I(P)中中)。如果如果G是一个最小是一个最小-map，我们似乎可以从中读出分布的所有结构，我们似乎可以从中读出分布的所有结构，即，从图上读出即，从图上读出P的所有独立的所有独立I(P)。由于图的生成依赖变量序，由于图的生成依赖变量序，即，不同的变量序将导致不即，不同的变量序将导致不同的图，而不同的图，可以同的图，而不同的图，可以分别具有最小分别具有最小I-map，具有不，具有不同的结构。没有唯一性！这同的结构。没有唯一性！这个结论不成立！个结论不成立！Machine Learning and Data Mining 2009Machine L

28、C是是(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中中国国科科学学

29、院院自自动动化化研研究究所所概率图模型概率图模型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上的完全子图依赖条件独立，因为节点上的

30、完全子图依赖条件独立，因为节点之间连线的删除，将直接导致不同的完全子图。之间连线的删除，将直接导致不同的完全子图。n因子是一个从变量因子是一个从变量D D子集到正实数域子集到正实数域 + +上的映射上的映射( (函数函数) )。中中中中国国国国科学院自动化研究所科学院自动化研究所科学院自动化研究所科学院自动化研究所Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009表示联合分布与因子表示联合分布与因子其中其中Di(i=1,k)是是MN H上的完全子图上的完全子图(典型是典型是clique)， = 1

31、(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中形如中形如 (

32、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中中国国科科学学院院自自动动化

33、化研研究究所所“偶对偶对”独立独立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)的所的所有直接邻居节点集

34、合。有直接邻居节点集合。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已知

35、已知,在在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，均是唯一

36、最小，均是唯一最小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以被观

37、察，以被观察，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中中国国科科

38、学学院院自自动动化化研研究究所所各种各种CPD-局部概率模型局部概率模型讨论了网络的结构之后，需要关注附加在节讨论了网络的结构之后，需要关注附加在节点点(边边)上的各种不同描述的条件上的各种不同描述的条件(局部局部)概率概率分布分布(CPD)，如何确定因子。，如何确定因子。满足：满足： P(x | paX) = 1。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所各种各种CPDTabular CPD：使用表描述：使用表描述P(X | PaX)0，判定判

39、定CPD：判定函数：判定函数Logistic CPD：线性高斯线性高斯 CPD：树与规则树与规则CPD中中中中国国国国科学院自动化研究所科学院自动化研究所科学院自动化研究所科学院自动化研究所Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009网图有两个要素：其一，网图的结构，其二，网图有两个要素：其一，网图的结构，其二，网图节点上的条件概率分布。在学习时，这两网图节点上的条件概率分布。在学习时，这两个要素将成为学习的两个方面。结构可以由经个要素将成为学习的两个方面。结构可以由经验来构造。验来构造。对

40、节点上的概率分布的学习，将基于这些对节点上的概率分布的学习，将基于这些CPD表示形式，可以理解为学习的表示形式，可以理解为学习的“基函数基函数” (局局部表示部表示)。经验知识可以无障碍地被引入。经验知识可以无障碍地被引入。中中中中国国国国科学院自动化研究所科学院自动化研究所科学院自动化研究所科学院自动化研究所Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009一、引子一、引子二、表示二、表示三、推断三、推断四、学习四、学习五、结束语五、结束语Machine Learning and Data Mi

41、ning 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中求出最适合的赋值

42、。中求出最适合的赋值。边缘边缘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( )这个貌似简单的任

43、务，由于计这个貌似简单的任务，由于计算边缘分布需要取遍非查询变算边缘分布需要取遍非查询变量所有值的组合。十分困难。量所有值的组合。十分困难。学生聪明学生聪明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

44、Learning and Data Mining 2009Machine Learning and Data Mining 2009无论无论BN还是还是MN，其上的推断是，其上的推断是NPC问题，问题，计算近似推断也不能幸免。计算近似推断也不能幸免。近似推断：图近似近似推断：图近似(本质近似本质近似)，目标近似，目标近似和计算近似和计算近似(包括算法近似包括算法近似)。概率图模型推断研究的焦点是：概率图模型推断研究的焦点是：精度和效精度和效率率之间有效之间有效折中折中。Machine Learning and Data Mining 2009Machine Learning and Data

45、Mining 2009中中国国科科学学院院自自动动化化研研究究所所“推断推断”问题的解法问题的解法提取公因子，提取公因子，以避免变量的以避免变量的重复计算，空重复计算，空间换时间，折间换时间，折中。动态规划中。动态规划动态规划动态规划Clique树法树法优化法优化法以相对熵为目标以相对熵为目标(多多种方法之一种方法之一)，将概，将概率查询变为有约束率查询变为有约束的优化问题，并使的优化问题，并使用拉格朗日乘子法用拉格朗日乘子法求解。求解。将无向图构成将无向图构成clique树，采用消息传播树，采用消息传播的方法，计算查询的方法，计算查询的分布。对图上任的分布。对图上任何节点的查询有效何节点的查

47、) 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. 无向无

48、向)，但是，在变量消去法上，没有本质，但是，在变量消去法上，没有本质区别。称为因子边缘化。区别。称为因子边缘化。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 2009Ma

49、chine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所“推断推断”问题的解法问题的解法提取公因子，提取公因子，以避免变量的以避免变量的重复计算，空重复计算，空间换时间，折间换时间，折中。动态规划中。动态规划动态规划动态规划Clique树法树法将无向图构成将无向图构成clique树，采用消息传播树，采用消息传播的方法，计算查询的方法，计算查询的分布。的分布。对图上任对图上任何节点的查询有效何节点的查询有效中中中中国国国国科学院自动化研究所科学院自动化研究所科学院自动化研究所科学院自动化研究所Machine Learning and Da

50、ta 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

51、，如果，如果这个通路上的所有这个通路上的所有cluster均将包含均将包含X，称其满，称其满足足“RIP” (Running Intersection Property) 。一条通路满足一条通路满足RIP，将保证这条通路均有某个，将保证这条通路均有某个变量，同时，构成的变量，同时，构成的cluster图与图与MN具有相同的具有相同的连接形式连接形式(拓扑结构拓扑结构)。Clique树树 Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所基于基于cliqu

52、e树的变量消去法树的变量消去法(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)是联合是联合分布，求分布，求

53、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向其传播消向其传播消

54、息，总计为：息，总计为：(3)计算根节点的信度：计算根节点的信度：(计算计算联合分布联合分布)方法的优点：设定不同根节点，可以计算任意变量的边缘分布方法的优点：设定不同根节点，可以计算任意变量的边缘分布P(C)。改变根节点只涉及个别消息传播改变根节点只涉及个别消息传播(对传入多个消息的对传入多个消息的clique也是如此也是如此)(4)计算查询变量的边缘分布计算查询变量的边缘分布消元消元步骤步骤 iMachine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所被校

55、准的被校准的Clique树树-图近似图近似Clique树的主要问题之一是消息树的主要问题之一是消息 ik= ki可能不成立。可能不成立。满足右式的两个满足右式的两个cluster C1与与C2，称为被校准，称为被校准Clique树上所有树上所有cluster是被校准，这个是被校准，这个树称为被校准的树称为被校准的clique树。树。这样，连接两个节点的这样，连接两个节点的信度定义为：信度定义为：Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所被校准的被

56、校准的clique树是联合分布的替代表示树是联合分布的替代表示被校准被校准clique树的联合分布树的联合分布(Gibbs)：其中其中将将与与代入上式代入上式分子分子分母分母因为每个因为每个在分子分母只出现一在分子分母只出现一次，可以消去，联合分布为各个次，可以消去，联合分布为各个clique初始能量的乘积。初始能量的乘积。意义：意义：Clique树可以作为联合分布树可以作为联合分布的替代表示。但需假设校准成立。的替代表示。但需假设校准成立。近似！近似！Machine Learning and Data Mining 2009Machine Learning and Data Minin

57、g 2009中中国国科科学学院院自自动动化化研研究究所所“推断推断”问题的解法问题的解法提取公因子，提取公因子，以避免变量的以避免变量的重复计算，空重复计算，空间换时间，折间换时间，折中。动态规划中。动态规划动态规划动态规划Clique树法树法优化法优化法将无向图构成将无向图构成clique树，采用消息传播树，采用消息传播的方法，计算查询的方法，计算查询的分布。对图上任的分布。对图上任何节点的查询有效何节点的查询有效以相对熵为目标以相对熵为目标(多多种方法之一种方法之一)，将概，将概率查询变为有约束率查询变为有约束的优化问题，并使的优化问题，并使用拉格朗日乘子法用拉格朗日乘子法求解。求解。(1

58、)变量消去法与变量消去法与clique树消去法等价；树消去法等价；(2)后者后者可以同时获可以同时获得多个查询结果，且与变量序无关得多个查询结果，且与变量序无关(校准条件校准条件)。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所基于优化的推断基于优化的推断P与与Q分别是精确推断与优化推断，使得分别是精确推断与优化推断，使得Q与与P的的距离最小。距离最小。三个步骤：三个步骤：(1)距离；距离；(2)图结构的目标函数和约图结构的目标函数和约束函数束函数；

59、(3)求解优化问题。求解优化问题。优化推断分为优化精确推断和优化近似推断，前优化推断分为优化精确推断和优化近似推断，前者是者是目标和约束空间目标和约束空间精确，后者是两者至少存在精确，后者是两者至少存在一个非精确。一个非精确。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所目标：相对熵最小目标：相对熵最小能量泛函最大能量泛函最大相对熵相对熵注意注意取对数取对数令能量泛函令能量泛函代入相对熵代入相对熵计算一个计算一个Q使得其与精确推断使得其与精确推断P

60、的相对熵最小，由于的相对熵最小，由于lnZ与与Q无关，这样，以相对熵最小的目标可以使用能量泛函最大无关，这样，以相对熵最小的目标可以使用能量泛函最大代替，由此，优化变为计算能量泛函最大的代替，由此，优化变为计算能量泛函最大的Q。其中其中X为所有变量的集合，为所有变量的集合，Q是是P 的近似。的近似。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所Clique树的因子能量泛函树的因子能量泛函上述泛函涉及所有变量的联合分布，不易设计优化算法。上述泛函涉及所

61、有变量的联合分布，不易设计优化算法。Clique树使用树使用因子能量泛函，定义为：初始势能与传递的能量因子能量泛函，定义为：初始势能与传递的能量(消息消息)。Clique树节点树节点 Ci的的固有势能的期望固有势能的期望Clique树分布树分布(传递的能量传递的能量)的对数形式。的对数形式。是信度是信度(节点节点(cluster)上的信息上的信息)，是是i与与j传递的所有消息传递的所有消息(边上的信息边上的信息)这是研究校准这是研究校准clique树的原因之一。树的原因之一。Machine Learning and Data Mining 2009Machine Learning and

62、Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所Clique树的约束精确优化推断树的约束精确优化推断计算计算使得使得最大最大对约束对约束是信度是信度(节点节点) 是是i与与j传递的所有消息传递的所有消息(边上边上)Q是节点和边上信息的并集，是节点和边上信息的并集，即，消息的网图上的传播。即，消息的网图上的传播。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所基于基于clique树的优化推断算法树的优化推断算法使用拉格朗日乘

63、子，将上述约束变为下述方程的优化问题使用拉格朗日乘子，将上述约束变为下述方程的优化问题以后类似感知机算法的推导，对以后类似感知机算法的推导，对与与计算偏导，获得下式计算偏导，获得下式这是一个迭代式，据此，可这是一个迭代式，据此，可以设计优化精确推断的算法以设计优化精确推断的算法Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所基于优化的近似推断基于优化的近似推断一般地说，基于优化的近似推理的直接考虑是两个一般地说，基于优化的近似推理的直接考虑是两个近

64、似因素：其一，目标函数，其二，约束空间。近似因素：其一，目标函数，其二，约束空间。但是，其关键是：表示问题的图结构。如果为了计但是，其关键是：表示问题的图结构。如果为了计算等原因，使用了一种近似表示的图结构，这类图算等原因，使用了一种近似表示的图结构，这类图将更容易构造。相对精确描述，其目标函数和约束将更容易构造。相对精确描述，其目标函数和约束空间是近似的。空间是近似的。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所Cluster图图采用消息传播方法

65、的前提：其一，图结构是树，其二，满足采用消息传播方法的前提：其一，图结构是树，其二，满足RIP。Cluster图放弃条件图放弃条件1，不要求树，但需要满足被扩展的，不要求树，但需要满足被扩展的RIP被扩展的被扩展的RIP：如果存在一个变量：如果存在一个变量X，使得，使得X Ci且且X Cj，则，则，在在Ci与与Cj之间，存在一个之间，存在一个单一单一的通路，在这个通路的所有边的通路，在这个通路的所有边e上，上，包含这个变量，包含这个变量，X Se。关键关键：对一个变量，两个：对一个变量，两个clusters之间只有一个单一通路，例如，之间只有一个单一通路，例如，3与与2之间，对变量之间，对变量

66、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图的问题，一般的原则是在高效计算和图的问题，一般的原则是在高

67、效计算和精度之间的折中。精度之间的折中。左图是一个问题的两个左图是一个问题的两个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中中国国科科学学院院自自动动化化研研究究所所构造构造“偶对偶

68、对(Pairwise)MN”这类图有两类这类图有两类cluster，其一，单变量势能，其一，单变量势能 iXi，其二，变量偶对，其二，变量偶对势能势能 (i, j)Xi, Xj，后者可以理解为，后者可以理解为cluster边上的势能。边上的势能。Cluster Ci与与Cj对应单变量对应单变量Xi与与Xj，cluster C(i, j)(Xi-Xj)对对应应XiXj边。边。可以证明，可以证明，“偶对偶对MN”是是cluster图。这样，这个图就可图。这样，这个图就可以使用消息传播的方式求解推以使用消息传播的方式求解推断。断。“对对MN”构造容易。构造容易。Machine Learning an

69、d Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所Bethe Cluster图图这类图有两层：其一，这类图有两层：其一，“大大”cluster，是表现，是表现MN结构的因子结构的因子 (Cluster或或clique)，其二，其二，“小小”cluster，是单变量。，是单变量。“大大”cluster包含的变量与对应包含的变量与对应“小小”变量变量cluster使用边连接。使用边连接。可以证明，这个图也是可以证明，这个图也是cluster图，可以使用消息传播方法图，可以使用消息传播方法求解推断

70、。这类图容易构造。求解推断。这类图容易构造。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所Cluster图的优化推断算法图的优化推断算法事实上，对事实上，对cluster图，因子能量泛函也不能优化成精确解，理由图，因子能量泛函也不能优化成精确解，理由: (1)对对边缘分布构成的多面体，每个边缘分布构成的多面体，每个cluster信度信度( )不一定在这个多面体上，不一定在这个多面体上，信度是对边缘分布的近似，信度是对边缘分布的近似，(2)判定信度集合

71、是否在多面体上是判定信度集合是否在多面体上是NP难解。难解。优化从多面体上变为局部一致优化从多面体上变为局部一致(定义如下定义如下)多面体上。伪边缘。多面体上。伪边缘。Cluster图的优化图的优化以下使用拉格朗日乘子推以下使用拉格朗日乘子推出具体算法，步骤如前。出具体算法，步骤如前。与与clique树优化约束的形式树优化约束的形式完全一样，其区别仅在：完全一样，其区别仅在：与与的作用域，的作用域，clique是在是在clique树上，这个约束是在树上，这个约束是在图的一个局部图的一个局部U上。上。中中中中国国国国科学院自动化研究所科学院自动化研究所科学院自动化研究所科学院自动化研究所Ma

72、chine Learning and Data Mining 2009Machine Learning and Data Mining 2009在图结构下推断的本质是：计算查询变量的边缘分布，在图结构下推断的本质是：计算查询变量的边缘分布，P=。关键是。关键是，是计算所有非查询变量取值的全组合。，是计算所有非查询变量取值的全组合。这个看似简单的问题，其复杂性远远超过我们的想象。这个看似简单的问题，其复杂性远远超过我们的想象。总结总结近似推断主要涉及三类近似的方法：近似推断主要涉及三类近似的方法：(1)研究对图结构描述的近似，这是本质近似。研究对图结构描述的近似，这是本质近似。(2)研究对目标

73、函数的近似，对给定图结构的近似。研究对目标函数的近似，对给定图结构的近似。(3)研究计算近似算法，精确算法无效，计算近似。研究计算近似算法，精确算法无效，计算近似。概率图模型近似推断核心是：概率图模型近似推断核心是：“精度和效率精度和效率”的折中。归的折中。归根结底是表示的研究。根结底是表示的研究。BN如何直接使用各种近似？如何直接使用各种近似？三类近似没有一个容易，特别是其误差性质，除了计算近三类近似没有一个容易，特别是其误差性质，除了计算近似之外，并没有本质进展。相当复杂，遍地问题！似之外，并没有本质进展。相当复杂，遍地问题！中中中中国国国国科学院自动化研究所科学院自动化研究所科学院自动化

74、研究所科学院自动化研究所Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009一、引子一、引子二、表示二、表示三、推断三、推断四、学习四、学习五、结束语五、结束语Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所概率图模型学习任务概率图模型学习任务假设：给定结构且样本是完整假设：给定结构且样本是完整(所有变量被赋值所有变量被赋值)的。的。任务：学习参数，参数估计

75、。任务：学习参数，参数估计。CPD方法：方法：(1)最大似然估计最大似然估计, (2)Bayes预测预测假设：结构未知，但是，样本完整。假设：结构未知，但是，样本完整。任务：学习结构和参数。任务：学习结构和参数。考虑一个可能结构的假设空间，结构选择变为优化问题。考虑一个可能结构的假设空间，结构选择变为优化问题。假设：样本不完整，或某些变量未知。假设：样本不完整，或某些变量未知。任务：发现非显现表现的变量，知识发现。任务：发现非显现表现的变量，知识发现。对对BN：工具：最大似然和工具：最大似然和Bayes估计。估计。特点：从局部到整体的学习。特点：从局部到整体的学习。困难：鲁棒性，泛化。困难：

76、鲁棒性，泛化。对对MN：工具工具:最大似然最大似然, Bayes估计估计,迭代优化迭代优化特点：鲁棒性，泛化。特点：鲁棒性，泛化。困难：整体的划分函数和推断。困难：整体的划分函数和推断。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所BN的学习的学习-目标函数目标函数学习就是计算使得学习就是计算使得L( : D)最大的最大的。似然函数：数据集合似然函数：数据集合D，BN的参数的参数或或(与与)图图G的似然函数的似然函数L( : D)其中其中可以是

77、参数可以是参数 (给定给定BN结构结构)，或者是，或者是(学习结构学习结构)学习就是计算使得学习就是计算使得P( | D)最大的最大的。由于后验概率依赖先。由于后验概率依赖先验概率与似然函数，问题变为计算这两个函数的问题。验概率与似然函数，问题变为计算这两个函数的问题。Bayes预测：数据集合预测：数据集合D，BN的参数的参数或图或图G的后验概率。的后验概率。P( | D)其中其中可以是参数可以是参数 (给定给定BN结构结构)，或者是图，或者是图G(学习结构学习结构)Machine Learning and Data Mining 2009Machine Learning and Dat

78、a Mining 2009中中国国科科学学院院自自动动化化研研究究所所BN的似然函数的似然函数假设假设BN结构给定，任务是确定参数。结构给定，任务是确定参数。令令Xi是给定是给定BN上的一个节点上的一个节点(变量变量)，其父辈节点集合为，其父辈节点集合为Pai。Xi的的CPD (因子因子)为为P(Xi | PaXi)。给定数据集合。给定数据集合D，P(Xi | PaXi)对对D的似然：的似然：其中，其中，xim是是D中变量中变量X的第的第m个样本的值。个样本的值。对给定样本集合，给定对给定样本集合，给定BN的似然为的似然为Machine Learning and Data Mining 200

79、9Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所基于基于MLE的学习算法的学习算法命题：令命题：令D是对变量是对变量X1,Xn的完全数据集合，的完全数据集合，G是定是定义在这个变量集合上的义在这个变量集合上的BN，令，令是使得是使得最大的参数，则最大的参数，则使得使得L( : D)最大。最大。意义：满足一定假设，意义：满足一定假设，BN的整体最大似然，可以从局的整体最大似然，可以从局部最大似然获得。部最大似然获得。学习算法：对学习算法：对BN的每个节点，在其父辈的条件下，根据数的每个节点，在其父辈的条件下，根据数据集

80、合，分别计算这个节点的最大似然。即，据集合，分别计算这个节点的最大似然。即，根据上述命题，即可获得最后解答。根据上述命题，即可获得最后解答。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所BN的的Bayes预测学习预测学习任务：计算后验概率分布任务：计算后验概率分布P( |D)，仅需计算似然函数，仅需计算似然函数P(D| )和先验概率分布和先验概率分布P( )。Bayes预测学习就是计算这两预测学习就是计算这两个函数个函数给定给定BN，参数考虑为随机变

81、量，表述为分布函数。，参数考虑为随机变量，表述为分布函数。似然函数：对样本逐一计算。根据当前参数，修正参数似然函数：对样本逐一计算。根据当前参数，修正参数(预测预测)。先验分布函数：希望先验与后验表示形式相同，先验分布函数：希望先验与后验表示形式相同，Dirichlet分布。分布。对对BN的预测学习，关键是需要将整体分布分解为局部分布。的预测学习，关键是需要将整体分布分解为局部分布。其中其中Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所似然计算似然计

82、算似然函数似然函数P(D| )的计算采用预测新样本的分布，给定的计算采用预测新样本的分布，给定BN，从，从DM获得参数获得参数的分布，对新的观察的分布，对新的观察xM+1，可以使用链式规则：，可以使用链式规则：其中其中DM是数据集合是数据集合D中，前中，前M个样本构成的集合。个样本构成的集合。DM( M)对对xM+1独立。独立。这暗示，从样本集学习参数，可以一个一个样本逐步进行这暗示，从样本集学习参数，可以一个一个样本逐步进行预测预测xM+1变为：根据后验，对所有参数平均变为：根据后验，对所有参数平均(期望期望)，Machine Learning and Data Mining 2009Ma

83、chine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所先验分布先验分布P( )的选择的选择Dirichlet分布：分布：满足先验概率与后满足先验概率与后验概率形式一致的要求。验概率形式一致的要求。 k：样本：样本k值出现频率。值出现频率。优点一：形式一致且紧凑。修改参数容易。优点一：形式一致且紧凑。修改参数容易。后验：后验：P(xM+1=xk | D) = EP( |D) k，对，对Dirichlet分布分布, E( k) = k / j j优点二：新参数是基于对已有参数的平均，这避优点二：新参数是基于对已有参数的平均，这避免某个

84、参数过学习的误差，带到新参数的估计。免某个参数过学习的误差，带到新参数的估计。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所学习学习MN对学习而言，对学习而言，MN与与BN的区别是：的区别是：MN的平均是在图结的平均是在图结构整体上构整体上(划分函数划分函数Z)，与图结构的所有参数相关联，与图结构的所有参数相关联，不能分解。由此，不得不使用迭代的优化方法不能分解。由此，不得不使用迭代的优化方法好消息：似然函数能够保证收敛到全局最优。好消息：似然函数能

85、够保证收敛到全局最优。坏消息：每次迭代需要推断。坏消息：每次迭代需要推断。注释注释：对图结构，：对图结构，BN学习依赖数据集合分布学习依赖数据集合分布P(D)，由于，由于D是给定的是给定的，因此，因此，BN可以分解为可以分解为部分求解部分求解(删除任何条件独立的边删除任何条件独立的边)；对；对MN则依赖则依赖划分函数，划分函数，Z=1(X1) , k(Xk)，这意味着，改变任何一个势函数，这意味着，改变任何一个势函数 j，Z将改变将改变，分解为局部是不可能的。这是，分解为局部是不可能的。这是MN不得不求助不得不求助优化优化的原的原因。因。Machine Learning and Data Mi

86、ning 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所MN的似然函数的似然函数MN已知，并表示为：已知，并表示为：将将写成权值和特征函数的形式：写成权值和特征函数的形式： i(Di)= ifi(Di)。似然函数为。似然函数为其中其中是表示变量关系的势函数，这里的是表示变量关系的势函数，这里的Di表示表示 i涉及的变量观测涉及的变量观测(在在MN上的完全子图上的完全子图)取对数取对数注意：在特征函数中，注意：在特征函数中， (zeta)表示第表示第m个样本中与个样本中与f有关变量的数值，这有关变量的数值，这恰恰

87、反映了恰恰反映了MN的结构。方括号内是的结构。方括号内是M个样本。个样本。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所MN参数估计算法参数估计算法对数似然函数对数似然函数为了计算最大似然，对为了计算最大似然，对求导，并令其为求导，并令其为0。右边第右边第1项是对所有样项是对所有样本的平均本的平均(经验经验)，第，第2项项是对参数是对参数的平均的平均(期望期望)如果如果是最大似然参数，是最大似然参数，iff 对所有对所有i，EDfi( )=E

88、fi。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所学习结构学习结构对一个由变量集合构成的图结构，有两个极端情况对一个由变量集合构成的图结构，有两个极端情况(平凡平凡)：所有变量两两相连所有变量两两相连ABECD所有变量不相连接所有变量不相连接ABECD学习：部分相连学习：部分相连ABECDABECD目标目标: (1)根据给定数据集发现变量之间的关系，知识发现；根据给定数据集发现变量之间的关系，知识发现；(2)密度估计，其本质是泛化。密度估计，其本质

89、是泛化。加边加边删边删边核心：从数据集发现变量之间的独立关系核心：从数据集发现变量之间的独立关系I-map。困难困难: (1)噪音，没有绝对独立，噪音，没有绝对独立，(2)稀疏解答。稀疏解答。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所结构学习的基本方法结构学习的基本方法(1)假设空间的模型选择：设计一个图结构对假设空间的模型选择：设计一个图结构对给定数据集合符合程度的评分准则。给定数据集合符合程度的评分准则。(2)Bayes模型平均：有些类似模型

90、平均：有些类似Bagging。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所假设空间假设空间-模型选择的学习模型选择的学习假设空间：假设空间：待选的图模型，评分函数间接描述假设空间待选的图模型，评分函数间接描述假设空间评分函数：模型复杂程度和对给定数据集合评分函数：模型复杂程度和对给定数据集合的符合程度。的符合程度。评分函数：评分函数：似然评分函数似然评分函数Bayes评分函数评分函数Machine Learning and Data Mining

91、2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所似然评分函数似然评分函数令令G是一个待选的图结构，是一个待选的图结构， G是这个图结构上的参数，对给是这个图结构上的参数，对给定数据集合定数据集合D，关于，关于G与与 G的似然函数：的似然函数：L( : D)。目标目标:从待选的图模型中选择似然最大的图模型从待选的图模型中选择似然最大的图模型(结构和参数结构和参数)似然评分函数：似然评分函数：，其中，其中l是是MLE参数下，参数下，对对G的似然函数的对数形式。的似然函数的对数形式。Machine Learning an

92、d Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所Bayes评分函数评分函数与与MLE的考虑类似，只是计算给定数据集合的图结构的考虑类似，只是计算给定数据集合的图结构G的的后验概率。后验概率。给定数据集合给定数据集合D，G表示图结构，计算表示图结构，计算G的后验概率：的后验概率：Bayes评分函数：评分函数：scoreB(G : D) = log P(D | G) + log P(G)其中似然函数其中似然函数第一项就是似然评分，第一项就是似然评分，Bayes评分就是增加了第二项，以使评分就是

93、增加了第二项，以使得我们获得更稀疏的图模型。得我们获得更稀疏的图模型。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所MN结构学习结构学习MN结构未知，与结构未知，与BN研究方法一样，考虑：研究方法一样，考虑：(1)假设空间，假设空间，(2)目标函数目标函数(评分函数评分函数)，(3)优化算法。优化算法。假设空间的形式假设空间的形式其中，其中，M是一个对数线性结构模型。任务就是根据给定样是一个对数线性结构模型。任务就是根据给定样本集合，选择一个结构稀疏

94、的本集合，选择一个结构稀疏的MN模型。模型。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所评分函数评分函数缺点：偏爱结构复杂的模型，需要限制，例如，如果缺点：偏爱结构复杂的模型，需要限制，例如，如果 M1M2，scoreL(M1:D) scoreL(M2:D)。这个限制太严厉，大。这个限制太严厉，大多数情况难以满足。多数情况难以满足。似然评分函数似然评分函数：其中，其中，dim是模型的维数，参数空间的自由度。缺点是这个是模型的维数，参数空间的自由度。

95、缺点是这个维数很难估计。维数很难估计。Bayes评分函数评分函数：中中中中国国国国科学院自动化研究所科学院自动化研究所科学院自动化研究所科学院自动化研究所Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009BN的优点是它的因子形式的优点是它的因子形式P(X | PaX)，这意味着，计，这意味着，计算任何节点的分布，只与它的父辈有关，而与其它节算任何节点的分布，只与它的父辈有关，而与其它节点无关，然而，这也是它的最大缺点，即，每个节点点无关，然而，这也是它的最大缺点，即，每个节点分布的计算必须准确，否

96、则误差将被传递。分布的计算必须准确，否则误差将被传递。总结总结MN的优点是它的因子形式与划分函数的优点是它的因子形式与划分函数Z有关，这意有关，这意味着，节点分布的误差，可以被整体平均消除。然而味着，节点分布的误差，可以被整体平均消除。然而，这也是它的最大缺点，使得学习结构与参数不得不，这也是它的最大缺点，使得学习结构与参数不得不与推断相关联。与推断相关联。中中中中国国国国科学院自动化研究所科学院自动化研究所科学院自动化研究所科学院自动化研究所Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009一、

97、引子一、引子二、表示二、表示三、推断三、推断四、学习四、学习五、结束语五、结束语Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所读读“表示表示”-耳目一新耳目一新概率图模型表示的核心问题是概率图模型表示的核心问题是“条件独立条件独立”，其中，其中“条件条件”是关键。在传统统计学中，独立往往是假设，这个假设是关键。在传统统计学中，独立往往是假设，这个假设满足，研究简化，但是，不会将其作为核心研究课题。满足，研究简化，但是，不会将其作为核心研究课题。条件概

98、率分布条件概率分布(CPD)因子与图结构对应，这样图结构上条件因子与图结构对应，这样图结构上条件独立断言集合独立断言集合I-map成为描述模型的标志和关键。经验知识成为描述模型的标志和关键。经验知识无论有向图还是无向图，局部概率模型无论有向图还是无向图，局部概率模型(即，即，CPD)通过图结通过图结构整合为整体概率模型，这是最有吸引力的思考。而构整合为整体概率模型，这是最有吸引力的思考。而CPD的描述可以多种多样，传统统计模型，传统人工智能模型的描述可以多种多样，传统统计模型，传统人工智能模型既可泛化又可解释的模型既可泛化又可解释的模型-望眼欲穿。结构望眼欲穿。结构+平均平均Machine L

99、earning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所读读“推断推断”-扼腕叹息扼腕叹息对问题使用带有复杂结构的表示，其推断就一定是一个复杂课题，对问题使用带有复杂结构的表示，其推断就一定是一个复杂课题，AI就是如此就是如此(定理证明定理证明)，而，而ML由于使用简洁的基函数作为表示由于使用简洁的基函数作为表示(例如，多项式基例如，多项式基)，因此，推断不会是其研究的问题。概率图模，因此，推断不会是其研究的问题。概率图模型的麻烦就在于推断。型的麻烦就在于推断。无论精确推断还是

100、计算近似推断，图模型上的推断均是无论精确推断还是计算近似推断，图模型上的推断均是NPC。近似图结构、近似目标函数和近似优化算法等近似被采用，近似图结构、近似目标函数和近似优化算法等近似被采用，全面全面近似近似！然而，从近似程度到有效计算，遍地问题。！然而，从近似程度到有效计算，遍地问题。NPC-当头一棒。没有免费的午餐！当头一棒。没有免费的午餐！与与AI和和ML相比较，这类模型的推断灵活，对不同查询，无需重新建模相比较，这类模型的推断灵活，对不同查询，无需重新建模Machine Learning and Data Mining 2009Machine Learning and Data Min

101、ing 2009中中国国科科学学院院自自动动化化研研究究所所读读“学习学习”-喜忧参半喜忧参半给定图结构的学习没有什么新的考虑，基于表示的研究，给定图结构的学习没有什么新的考虑，基于表示的研究，从给定结构派生似然函数或从给定结构派生似然函数或Bayes后验概率函数没有困难，后验概率函数没有困难，计算优化解将遇到推断的困难。计算优化解将遇到推断的困难。从给定数据学习结构就不是一件轻松的事情了，这类问题从给定数据学习结构就不是一件轻松的事情了，这类问题的可分解性需要严厉的条件，计算考虑迭代，遇到推断，的可分解性需要严厉的条件，计算考虑迭代，遇到推断，大麻烦！由于划分函数的整体性，大麻烦！由于划分函

102、数的整体性，MN一开始就遇到推断。一开始就遇到推断。图近似是关键图近似是关键。绕不开的推断绕不开的推断-五味俱全。机会乎，陷阱乎？五味俱全。机会乎，陷阱乎？Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所预测与描述预测与描述预测与描述是数据挖掘提出的两个任务，但是，数据挖掘的描述预测与描述是数据挖掘提出的两个任务，但是，数据挖掘的描述任务一直开展不好任务一直开展不好(啤酒和尿布啤酒和尿布)。被嘲笑！。被嘲笑！图模型既可以消除噪音且表示紧凑图模型既可以消

103、除噪音且表示紧凑(相对相对AI的穷举的穷举)，还可以对模，还可以对模型的各个部分可解释。前者是预测型的各个部分可解释。前者是预测(泛化泛化)，后者是描述，后者是描述(发现发现)。金融和生物等领域，计算机科学有两个策略：其一，代替领域专金融和生物等领域，计算机科学有两个策略：其一，代替领域专家家(从数据建立可靠从数据建立可靠(泛化泛化)的模型的模型)，其二，为领域提供工具，简，其二，为领域提供工具，简化专家的工作化专家的工作(知识发现知识发现)。对这些领域，描述可能更好。对网络、。对这些领域，描述可能更好。对网络、语言、图像等领域，泛化是重要的，但是，发现同样重要。语言、图像等领域，泛化是重要的

104、，但是，发现同样重要。概率图模型为数据挖掘的两个任务提供工具概率图模型为数据挖掘的两个任务提供工具!？思考：继续研究泛化，重启发现研究更重要思考：继续研究泛化，重启发现研究更重要?中中中中国国国国科学院自动化研究所科学院自动化研究所科学院自动化研究所科学院自动化研究所Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009概率图模型前景如何？概率图模型前景如何？历史的故事历史的故事Machine Learning and Data Mining 2009Machine Learning and Data

105、 Mining 2009中中国国科科学学院院自自动动化化研研究究所所线性感知机线性感知机基于最小二乘的基于最小二乘的Rosenblatt的的感知机感知机(1956)，其本质是，其本质是平均平均1943年，年，McCulloch和和Pitts的神经元工作方式，的神经元工作方式，1949年，年，Hebb的学习律。的学习律。只能解决线性问题，不能满足实际的需只能解决线性问题，不能满足实际的需要。埋下要。埋下“祸根祸根”。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研

106、研究究所所20世纪世纪70年代面临的选择年代面临的选择统计优化统计优化(平均平均)：感知机感知机统计模式识别统计模式识别复杂信息系统复杂信息系统(结构结构)：专家系统专家系统句法模式识别句法模式识别选择选择非线性问题非线性问题计算效率计算效率专家系统合理专家系统合理复杂问题求解复杂问题求解实现智能系统的理想实现智能系统的理想Duda and Hart73Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所AI1969年，年，M.Minsky发表颠覆性的报告

107、，发表颠覆性的报告， “Perceptron”。表象是以表象是以XOR问题向以平均为基础的感知机发难，本质是问题向以平均为基础的感知机发难，本质是试图以试图以结构结构方法代替方法代替平均平均。全书使用拓扑作为工具。全书使用拓扑作为工具。1956年，以复杂信息处理为契机，提出年，以复杂信息处理为契机，提出AI。其动机有二：。其动机有二：其一，其一，发展处理符号的方法发展处理符号的方法，其二，处理非线性问题。，其二，处理非线性问题。过分强调独立性，使得描述任何一个问题，需要穷举出过分强调独立性，使得描述任何一个问题，需要穷举出所有可能。所有可能。80年代，耗资巨大的年代，耗资巨大的CYC失败了。失

108、败了。“祸根祸根”。Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所20世纪世纪80年代面临的选择年代面临的选择概率图模型：概率图模型：Markov随机场随机场Bayes网网人工神经网络：人工神经网络：BP统计机器学习统计机器学习选择选择结构学习的困难结构学习的困难先验的结构先验的结构先验概率分布先验概率分布字符识别，网络数据建模字符识别，网络数据建模误差界指导算法设计误差界指导算法设计算法基于线性感知机算法基于线性感知机总之，总之，无需先验知识无需先

109、验知识Gibbs1902, Wright1935Clifford1971Pearl1988，89Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所ANN1991年，年，Vapnik借用在借用在AI中发展的中发展的PAC，给出了，给出了误差界，基于统计误差界，基于统计(平均平均)的方法开始成为主流。的方法开始成为主流。1986年，年， Remulhart等人发表了巨篇等人发表了巨篇PDP报告，其中报告，其中一章是一章是BP算法，使用非线性算法解决了算法，使

110、用非线性算法解决了XOR。其学术。其学术价值并不大，但是，人们开始重新尝试价值并不大，但是，人们开始重新尝试“平均平均”方法。方法。从从ANN到到SVM的发展得力于对字符识别的的成功的发展得力于对字符识别的的成功Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所SML其麻烦是借用其麻烦是借用PAC理论中有一个参数理论中有一个参数，误差界以，误差界以1- 概率成立。概率成立。这个参数很难在泛化意义下解释其含义这个参数很难在泛化意义下解释其含义(对对PAC

111、，其本意是描述，其本意是描述问题复杂性的参数问题复杂性的参数)。理想，。理想，应该趋于应该趋于0，但是，误差界将趋于，但是，误差界将趋于无穷，成为平凡界。无穷，成为平凡界。Vapnik的贡献：其一，误差界指导算法设计，其二，将算法设的贡献：其一，误差界指导算法设计，其二，将算法设计返回感知机，即，线性算法，寻找线性空间计返回感知机，即，线性算法，寻找线性空间(核映射核映射)。平均成为主流。平均成为主流。新世纪开始，统计学家加入新世纪开始，统计学家加入SML，完全放弃，完全放弃PAC。Machine Learning and Data Mining 2009Machine Learning a

112、nd Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所维数灾难维数灾难高维空间上的统计理论，多重积分是麻烦，补充高维空间上的统计理论，多重积分是麻烦，补充“合适合适”样本是麻烦。样本是麻烦。“同分布同分布”只能停留在假设上，无法实只能停留在假设上，无法实施。施。在高维空间在高维空间(成百上千成百上千)建模，最大的危险就是空间大建模，最大的危险就是空间大的程度使得再多的样本，在这个空间上也是稀疏的。的程度使得再多的样本，在这个空间上也是稀疏的。由于困难具有本质性，平均遇到大麻烦！由于困难具有本质性，平均遇到大麻烦！中中中中国国国国科学院自动化研究所科学院自动化研究所科

113、学院自动化研究所科学院自动化研究所Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009自自然然模模型型采样采样样本集样本集模型模型算法算法交叉验证交叉验证假设假设iid and PAC统计机器学习的麻烦统计机器学习的麻烦？设计实验设计实验问题：问题：模型是自然模型吗？模型是自然模型吗？统计机器学习统计机器学习如果数据不充分，在大变量集合下，如果数据不充分，在大变量集合下，如何设计实验，获得新数据。如何设计实验，获得新数据。统计机器学习的困难：分布计算上，存在多重积分计算的问题，统计机器学习的

114、困难：分布计算上，存在多重积分计算的问题，实验设计存在组合问题。实验设计存在组合问题。iid成为与自然模型无关的假设！成为与自然模型无关的假设！Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所概率图模型概率图模型将平均放在局部，避免了维数灾问题，同时保证了泛将平均放在局部，避免了维数灾问题，同时保证了泛化和模型的可解释性，关键是结构，即，如何将局部化和模型的可解释性，关键是结构，即，如何将局部的平均构造起来。的平均构造起来。基于平均的研究已经过去基于平

115、均的研究已经过去20余年，余年，2009年，年，Koller出版巨著出版巨著(近近1200页页)，概率图模型。，概率图模型。结构结构(全局全局) + 平均平均(局部局部)Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所历史进程历史进程-20年河东，年河东，20年河西？年河西？1986-今天今天平均平均(数值计算数值计算)统计机器学习统计机器学习1943-1969平均平均(数值计算数值计算)感知机感知机2000-今后今后平均平均+结构结构?概率图模型概率

116、图模型？1956-1986结构结构(符号计算符号计算)人工智能人工智能M. Minsky等等 Perceptrons: An introduction to computational geometry. 1969D. Rumelhart等等, Parallel Distributed Processing, 1986 V. Vapnik, The nature of statistical learning theory, 1995T.Hastie等等, The Elements of Statistical Learning, 2003D. Koller等等Probabilistic Gr

117、aphical Models: Principles and Techniques, 2009Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009中中国国科科学学院院自自动动化化研研究究所所概率图模型的前途概率图模型的前途前途需要等待两项研究结果：前途需要等待两项研究结果：其一，完成一个其一，完成一个ML与与AI均做不好，但是，概率图均做不好，但是，概率图模型却能够做好模型却能够做好(类似字符识别对类似字符识别对ML的作用的作用)的任的任务，其领域也许是网络，分子生物学，金融决策，务，其领域也许是网络，分子生物学，金融决策，预测问题或描述问题？感觉是，这个标志性的研预测问题或描述问题？感觉是，这个标志性的研究可能是描述性的任务。究可能是描述性的任务。其二，一本解决推断问题的著作其二，一本解决推断问题的著作(类似类似Vapnik的著的著作，作，BP也是也是NPC问题问题)，中中中中国国国国科学院自动化研究所科学院自动化研究所科学院自动化研究所科学院自动化研究所Machine Learning and Data Mining 2009Machine Learning and Data Mining 2009谢谢谢谢愚者浅谈，不足为凭愚者浅谈，不足为凭痴人梦语，切勿轻信痴人梦语，切勿轻信

展开阅读全文

概率图模型课件 中科院 王珏

最新文档

概率图模型课件中科院王珏