Stanford概率图模型（Probabilistic Graphical Model）L2
Stanford概率图模型（Probabilistic Graphical Model）—第二讲Template Models and Structured CPDs概率图模型（Probabilistic Graphical Model）系列来自Stanford公开课Probabilistic Graphical Model中Daphne Koller 老师的讲解。（https://https://www.doczj.com/doc/d12426427.html,/pgm-2012-002/class/index）主要内容包括（转载请注明原始出处https://www.doczj.com/doc/d12426427.html,/yangliuy）1. 贝叶斯网络及马尔可夫网络的概率图模型表示及变形。2. Reasoning 及Inference 方法，包括exact inference(variable elimination, clique trees) 和approximate inference (belief propagation message passing, Markov chain Monte Carlo methods)。3. 概率图模型中参数及结构的learning方法。4. 使用概率图模型进行统计决策建模。第二讲. Template Models and Structured CPDs.1 Template Models模版图模型，是对图模型更加紧凑的描述方式。模版变量是图模型中多次重复出现的变量，例如多个学生的智商、多门课程的难度。而模版图模型描述了模版变量如何从模版中继承依赖关系，典型的TemplateModels有动态贝叶斯模型DBN、隐马尔科夫模型HMM及PlateModels。动态贝叶斯模型主要是在贝叶斯网络中引入了马尔科夫假设和时间不变性。这几个模型将在后面几讲中再深入介绍，下面看
一个TemplateModels的习题
2 CPDCPD即条件概率分布，表格方式不适合表示CPD。如果某个结点有K个parent，那么表格有O（2exp(k)）行。下面给出一般CPD的定义
主要包括以下几种模型
Deterministic CPD又称为Context Specific Independence,如下式所示
给定变量C的值后，随机变量X与随机变量Y条件独
立,Given Z。3 TreeStructured CPD树形结构CPD，在树形结构中不同的路径选择会导致不同的条件独立性。如下例中，给定J和C1,即已知某人选择了推荐信1，那么能否取得工作只取决于推荐信L1的效力概率分布，则L2→J这条路径变得spurious，因此L1与L2之间不再有active trails，L1与
L2条件独立。我们称L1与L2属于d-separated, Given J和context C=c1.这种条件独立关系也称为CSI-separation,即上
下文相关的条件独立。
4 Noisy OR CPD如下图所示，Y结点有父亲结点Z1到Zk，OR关系的意思即只有Z1到Zk全部不发生，那么才有Y=0，而Zi是否发生受到随机变量Xi的影响，如果把最后Y看成教授的推荐信，那么X1到Xk可以看做学生的某项表现，学生第i项表现优异的情况下被教授欣赏的概率为λi，这个图的意思就是如果教授至少欣赏了学生的某一项优异表现，则
有推荐信。那么Z0是什么呢？这个概率称为leak probability，可以认为是教授某天心情好，即使某个学生每项表现都一塌糊涂，他同样给推荐信，即这个变量不受学生表现Xi的影响，完全取决于教授本身。于是Y=0即没有推荐信的概率是学生每项都表现很差的概率乘以教授心情不好的概率，于是有图下面的条件概率公式。
5 Sigmoid CPD搞清楚Sigmoid函数，这种条件概率很好理解，如下图：练习题
6 线性高斯模型Y服从高斯分布，其均值为父亲结点Xi的线性组合，方差与父亲结点无关。
在线性高斯模型中，如果均值中线性组合中的各个系数取决于随机变量A，方差与取决于随机变量A，称为条件线性高斯模型。
Koller 教授把决策作为一种单独的模块进行讲解，但我认为，决策和推理本质上是一样的，都是在假设已知CPD或者势函数的情况下对模型给出结论。 1、决策==逐利 决策的基本思想很intuitive，并且非常有用。在赌博行为中，最后获得的钱与硬币的正反，赌注的大小有关。硬币的正反显然是随机变量，而赌注的大小却是决策量。显而易见的是，决策的最终目的是使得某个期望最大化。再举一个视觉中的例子，对于双目配准算法而言，左相机对应右相机的像素可以认为是随机变量。但是否将两个像素配在一起却可以认为是一个决策（假设像素一一对应，如果甲配了乙就不能配丙了，希望配准的最终结果是尽可能正确的）。故决策的数学表达为： 其中，P(X|A)表示在给定决策下，随机变量X的概率。U(x,a)表示给定决策下，x发生所获得的收益。简单的决策如图所示：
2、决策的方法 显然从上面的分析可知，我们要做的决策就是使得期望最大化的那个。换一个角度来看，如果每次的决策都是未知的，决策取决于已知信息，决策影响最终结果，如果决策也是随机变量，我们应该把获利最多的那个决策组作为我们所需采取的决策库。换而言之，凡事应有a,b,c三策，不同的策略对应不同的情况。显然，我们所需要采取的策略取决于已知的信息（Action的父节点）。而策略组本身就是一个随机变量。 如图所示，如果变量真实值无法观测，只能通过一个传感器（survey）来进行推测时，决策应该取决于S的值。S的值又和其所有父节点（M）的值相关。MEU表示所选择的策略。
显然，我们需要P(S)deta(F|S)U(F,M)，然后P(S)需要对P(M,S)进行边际获得。故表达式如上。带入数据发现
软件学报ISSN 1000-9825, CODEN RUXUEW E-mail: jos@https://www.doczj.com/doc/d12426427.html, Journal of Software,2013,24(11):2476?2497 [doi: 10.3724/SP.J.1001.2013.04486] https://www.doczj.com/doc/d12426427.html, +86-10-62562563 ?中国科学院软件研究所版权所有. Tel/Fax: ? 概率图模型研究进展综述 张宏毅1,2, 王立威1,2, 陈瑜希1,2 1(机器感知与智能教育部重点实验室(北京大学),北京 100871) 2(北京大学信息科学技术学院智能科学系,北京 100871) 通讯作者: 张宏毅, E-mail: hongyi.zhang.pku@https://www.doczj.com/doc/d12426427.html, 摘要: 概率图模型作为一类有力的工具,能够简洁地表示复杂的概率分布,有效地(近似)计算边缘分布和条件分 布,方便地学习概率模型中的参数和超参数.因此,它作为一种处理不确定性的形式化方法,被广泛应用于需要进行 自动的概率推理的场合,例如计算机视觉、自然语言处理.回顾了有关概率图模型的表示、推理和学习的基本概念 和主要结果,并详细介绍了这些方法在两种重要的概率模型中的应用.还回顾了在加速经典近似推理算法方面的新 进展.最后讨论了相关方向的研究前景. 关键词: 概率图模型;概率推理;机器学习 中图法分类号: TP181文献标识码: A 中文引用格式: 张宏毅,王立威,陈瑜希.概率图模型研究进展综述.软件学报,2013,24(11):2476?2497.https://www.doczj.com/doc/d12426427.html,/ 1000-9825/4486.htm 英文引用格式: Zhang HY, Wang LW, Chen YX. Research progress of probabilistic graphical models: A survey. Ruan Jian Xue Bao/Journal of Software, 2013,24(11):2476?2497 (in Chinese).https://www.doczj.com/doc/d12426427.html,/1000-9825/4486.htm Research Progress of Probabilistic Graphical Models: A Survey ZHANG Hong-Yi1,2, WANG Li-Wei1,2, CHEN Yu-Xi1,2 1(Key Laboratory of Machine Perception (Peking University), Ministry of Education, Beijing 100871, China) 2(Department of Machine Intelligence, School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China) Corresponding author: ZHANG Hong-Yi, E-mail: hongyi.zhang.pku@https://www.doczj.com/doc/d12426427.html, Abstract: Probabilistic graphical models are powerful tools for compactly representing complex probability distributions, efficiently computing (approximate) marginal and conditional distributions, and conveniently learning parameters and hyperparameters in probabilistic models. As a result, they have been widely used in applications that require some sort of automated probabilistic reasoning, such as computer vision and natural language processing, as a formal approach to deal with uncertainty. This paper surveys the basic concepts and key results of representation, inference and learning in probabilistic graphical models, and demonstrates their uses in two important probabilistic models. It also reviews some recent advances in speeding up classic approximate inference algorithms, followed by a discussion of promising research directions. Key words: probabilistic graphical model; probabilistic reasoning; machine learning 我们工作和生活中的许多问题都需要通过推理来解决.通过推理,我们综合已有的信息,对我们感兴趣的未 知量做出估计,或者决定采取某种行动.例如,程序员通过观察程序在测试中的输出判断程序是否有错误以及需 要进一步调试的代码位置,医生通过患者的自我报告、患者体征、医学检测结果和流行病爆发的状态判断患者 可能罹患的疾病.一直以来,计算机科学都在努力将推理自动化,例如,编写能够自动对程序进行测试并且诊断 ?基金项目: 国家自然科学基金(61222307, 61075003) 收稿时间:2013-07-17; 修改时间: 2013-08-02; 定稿时间: 2013-08-27
概率图模型中的推断 王泉 中国科学院大学网络空间安全学院 2016年11月
?推断问题回顾 ?精确推断：信念传播 –信念传播算法回顾 –信念传播在HMM中的应用?近似推断：吉布斯采样–吉布斯采样算法回顾 –吉布斯采样在LDA中的应用
?推断问题回顾 ?精确推断：信念传播 –信念传播算法回顾 –信念传播在HMM中的应用?近似推断：吉布斯采样–吉布斯采样算法回顾 –吉布斯采样在LDA中的应用
?已知联合概率分布 P x 1,?,x n ，估计 –x Q 问题变量；x E 证据变量；x Q ∪x E =x 1,?,x n P R =1 P R =0 0 P R =1G =1= ? P B =0.001 P E =0.002 P A B ,E =0.95 P A B ,?E =0.94 P A ?B ,E =0.29 P A ?B ,?E =0.001 P J A =0.9 P J ?A =0.05 P M A =0.7 P M ?A =0.01 P B =1E =0,J =1=? P x Q x E =x Q ,x E x E
?已知联合概率分布 P x 1,?,x n ，估计 –x Q 问题变量；x E 证据变量；x Q ∪x E =x 1,?,x n P x Q x E =x Q ,x E x E 观测图片 y i 原始图片 x i y ?=argmax P y x 朴素贝叶斯 x ?=argmax P x y 图像去噪
?精确推断：计算P x Q x E的精确值 –变量消去 (variable elimination) –信念传播 (belief propagation) –计算复杂度随着极大团规模的增长呈指数增长，适用范围有限?近似推断：在较低的时间复杂度下获得原问题的近似解–前向采样 (forward sampling) –吉布斯采样 (Gibbs sampling) –通过采样一组服从特定分布的样本，来近似原始分布，适用范围更广，可操作性更强
读懂概率图模型：你需要从基本概念和参数估计开始 选自statsbot作者：Prasoon Goyal机器之心编译参与：Panda 概率图模型是人工智能领域内一大主要研究方向。近日，Statsbot 团队邀请数据科学家Prasoon Goyal 在其博客上分两部分发表了一篇有关概率图模型的基础性介绍文章。文章从基础的概念开始谈起，并加入了基础的应用示例来帮助初学者理解概率图模型的实用价值。机器之心对该文章进行了编译介绍。 第一部分：基本术语和问题设定 机器学习领域内很多常见问题都涉及到对彼此相互独立的 孤立数据点进行分类。比如：预测给定图像中是否包含汽车或狗，或预测图像中的手写字符是0 到9 中的哪一个。 事实证明，很多问题都不在上述范围内。比如说，给定一个句子「I like machine learning」，然后标注每个词的词性（名词、代词、动词、形容词等）。正如这个简单例子所表现出的那样：我们不能通过单独处理每个词来解决这个任务——「learning」根据上下文的情况既可以是名词，也可以是动词。这个任务对很多关于文本的更为复杂的任务非常重要，比如从一种语言到另一种语言的翻译、文本转语音等。 使用标准的分类模型来处理这些问题并没有什么显而易见
的方法。概率图模型（PGM/probabilistic graphical model）是一种用于学习这些带有依赖（dependency）的模型的强大框架。这篇文章是Statsbot 团队邀请数据科学家Prasoon Goyal 为这一框架编写的一份教程。 在探讨如何将概率图模型用于机器学习问题之前，我们需要先理解PGM 框架。概率图模型（或简称图模型）在形式上是由图结构组成的。图的每个节点（node）都关联了一个随机变量，而图的边（edge）则被用于编码这些随机变量之间的关系。 根据图是有向的还是无向的，我们可以将图的模式分为两大类——贝叶斯网络（?Bayesian network）和马尔可夫网络（Markov networks）。 贝叶斯网络：有向图模型 贝叶斯网络的一个典型案例是所谓的「学生网络（student network）」，它看起来像是这样： 这个图描述了某个学生注册某个大学课程的设定。该图中有5 个随机变量：课程的难度（Difficulty）：可取两个值，0 表示低难度，1 表示高难度 学生的智力水平（Intelligence）：可取两个值，0 表示不聪明，1 表示聪明 学生的评级（Grade）：可取三个值，1 表示差，2 表示中，3 表示优
概率图模型介绍与计算 01 简单介绍 概率图模型是图论和概率论结合的产物，它的开创者是鼎鼎大名的Judea Pearl,我十分喜欢概率图模型这个工具，它是一个很有力的多变量而且变量关系可视化的建模工具，主要包括两个大方向：无向图模型和有向图模型。无向图模型又称马氏网络，它的应用很多，有典型的基于马尔科夫随机场的图像处理，图像分割，立体匹配等，也有和机器学习结合求取模型参数的结构化学习方法。严格的说他们都是在求后验概率:p(y|x)，即给定数据判定每种标签y的概率，最后选取最大的后验概率最大的标签作为预测结果。这个过程也称概率推理(probabilistic inference）。而有向图的应用也很广，有向图又称贝叶斯网络(bayes networks),说到贝叶斯就足以可以预见这个模型的应用范围咯，比如医疗诊断，绝大多数的机器学习等。但是它也有一些争议的地方，说到这就回到贝叶斯派和频率派几百年的争议这个大话题上去了，因为贝叶斯派假设了一些先验概率，而频率派认为这个先验有点主观，频率派认为模型的参数是客观存在的，假设先验分布就有点武断，用贝叶斯模型预测的结果就有点“水分”，不适用于比较严格的领域，比如精密制造，法律行业等。好吧，如果不遵循贝叶斯观点，前面讲的所有机器学习模型都可以dismiss咯，我们就通过大量数据统计先验来弥补这点“缺陷”吧。无向图和有向图的例子如（图一）所示： 图一(a)无向图（隐马尔科夫）(b)有向图 概率图模型吸取了图论和概率二者的长处，图论在许多计算领域中扮演着重要角色，比如组合优化，统计物理，经济等。图的每个节点都可看成一个变量，每个变量有N个状态（取值范围），节点之间的边表示变量之间的关系，它除了
第11章图与网络模型 习题1 配送的最短距离。用解：这是一个最短路问题，要求我们求出从v1到v 7 Dijkstra算法求解可得到这问题的解为27。我们也可以用此书附带的管理运筹学软件进行计算而得出最终结果为： 从节点1到节点7的最短路 ************************* 起点终点距离 ------------ 124 2312 356 575 此问题的解为:27 → 12357 习题2 解：这是一个最短路的问题，用Dijkstra算法求解可得到这问题的解为4.8，即在4年内购买、更换及运行维修最小的总费用为：4.8万元。 最优更新策略为：第一年末不更新 第二年末更新 第三年末不更新 第四年末处理机器 我们也可以用此书附带的管理运筹学软件进行求解，结果也可以得出此问题的解为4.8。 习题3 解：此题是一个求解最小生成树的问题，根据题意可知它要求出连接v1到v8的最小生成树。解此题可以得出结果为18。也可以使用管理运筹学软件，得出如下结果： 此问题的最小生成树如下： ************************* 起点终点距离 ------------ 132 342 124 252 573
习题4 782 763此问题的解为:18 解：此题是一个求解最大流的问题，根据题意可知它要求出连接v1到 v6 的最 大流量。解此题可以得出最大流量为 出结果为： 22。使用管理运筹学软件，我们也可以得v1从节点1到节点6的最大流 ************************* 起点终点距离 ------------ 126 146 1310 240 256 345 365 455 466 5611 此问题的解为:22 即从v1到v6的最大流量为：22 习题5 解：此题是一个求解最小费用最大流的问题，根据题意可知它要求出连接v1到v6的最小费用最大流量。解此问题可以得出最大流为5，最小费用为39。使用管理运筹学软件，我们也可以得出结果如下： 从节点1到节点6的最大流 ************************* 起点终点流量费用 ---------------- 1213 1341 2424 3211 3533 4624
?贝叶斯概率图模型是有向图，因此可以解决有明确单向依赖的建模问题，?而?二?马尔可夫概率图模型是?无向图，可以适?用于实体之间相互依赖的建模问题。这两种模型以及两着的混合模型应?用都?非常??广泛。概率图模型可以很清晰的表达实体之间的依赖以及导出联合概率以及条件概率的计算公式。 ?贝叶斯概率图依赖分析及联合概率因?子分解。 ?马尔可夫概率图依赖分析及联合概率因?子分解。 (B ⊥C|A) (D ｜B,C) P(A,B,C) = P(A)P(B ｜A)P(C ｜A)P(D ｜B,C)1234
对于朴素?贝叶斯模型来说，特定的类别样本在不同的特征属性上具备不同的数据表征，?而且特征之间有着独?立性假设，即特征之间是?无关联的。 对于隐?马尔可夫模型来说，隐状态之间满?足?马尔可夫性假设，即当前状态只和前?一状态有关，?而与历史状态和后续状态?无关；另外，还假设特征之间也是相互独?立的，且特征只由当前隐状态产?生。 对于最?大熵?马尔可夫模型来说，与隐?马尔可夫模型相?比，每个隐状态只依赖前?一状态和当前观测，?而且每组这样三者的组合都是独?立的，且采?用最?大熵模型建模。 对于条件随机场模型来说，当前状态依赖于上下?文状态和上下?文观测，所以没有过多的独?立性假设，可以?自由搭配特征以及标注。 在概率图模型知识框架中，涉及的相关知识点?非常多。我们熟知的很多模型都可以纳?入到这个框架下，也使得我们?自?己积累的知识得以汇总并在此基础之上进?一步爬坡。 学习概率图模型时，我们可以了解到每?一种模型的特点是什么、之间对?比有哪些，以及每?一种模型各?自涵盖的知识点。 ?比如： 总结
在之前的消息传递算法中，谈到了聚类图模型的一些性质。其中就有消息不能形成闭环，否则会导致“假消息传到最后我自己都信了”。为了解决这种问题，引入了一种称为团树（clique tree)的数据结构，树模型没有图模型中的环，所以此模型要比图模型更健壮，更容易收敛。 1.团树模型 链模型是一种最简单的树模型，其结构如下图所示，假设信息从最左端传入则有以下式子。 假设要对变量CD 进行推断，则应该求Belief(3) = deta 2->3 *deta 4->3 * phi(3). 从这里可以看出，团树算法是一种精确推断算法。它和变量消除算法在理论推导上是等价的。 上面的例子只是一种非常简单的团树，团树的本质还是聚类图，只不过是一种特殊的聚类图。对于更一般的概率图，也可以生成团树图。
其中，每个cluster都是变量消除诱导图中的一个最小map。 2.团树模型的计算 从上面分析可知，团树模型本质上和变量消除算法还有说不清道不明的关系（团树模型也是精确推理模型）。但是这个算法的优势在于，它可以利用消息传递机制达到收敛。之前提过，聚类图模型中的收敛指的是消息不变。除此之外，聚类图的本质是一种数据结构，它可以储存很多中间计算结果。如果我们有很多变量ABCDEF，那么我们想知道P(A)，则需要执行一次变量消除。如果要计算P(B)又要执行一次变量消除。如果中途得到了某个变量的观测，又会对算法全局产生影响。但是使用团树模型可以巧妙的避免这些问题。 首先，一旦模型迭代收敛之后。所有的消息都是不变的，每个消息都是可以被读取的。 每个团的belief，实际上就是未归一划的联合概率，要算单个变量的概率，只需要把其他的变量边际掉就行。这样一来，只需要一次迭代收敛，每个变量的概率都是可算的。并且算起来方便。 其次，如果对模型引入先验知识比如A = a 时，我们需要对D 的概率进行估计。按照变量消除的思路又要从头来一次。但是如果使用团树结构则不用，因为A的取值只影
概率图模型 过去的一段时间里，忙于考试、忙于完成实验室要求的任务、更忙于过年，很长时间没有以一种良好的心态来回忆、总结自己所学的东西了。这几天总在想，我应该怎么做。后来我才明白，应该想想我现在该做什么，所以我开始写这篇博客了。这将是对概率图模型的一个很基础的总结，主要参考了《PATTERN RECOGNITION and MACHINE LEARNING》。看这部分内容主要是因为LDPC码中涉及到了相关的知识。概率图模型本身是值得深究的，但我了解得不多，本文就纯当是介绍了，如有错误或不当之处还请多多指教。 0. 这是什么？ 很多事情是具有不确定性的。人们往往希望从不确定的东西里尽可能多的得到确定的知识、信息。为了达到这一目的，人们创建了概率理论来描述事物的不确定性。在这一基础上，人们希望能够通过已经知道的知识来推测出未知的事情，无论是现在、过去、还是将来。在这一过程中，模型往往是必须的，什么样的模型才是相对正确的？这又是我们需要解决的问题。这些问题出现在很多领域，包括模式识别、差错控制编码等。 概率图模型是解决这些问题的工具之一。从名字上可以看出，这是一种或是一类模型，同时运用了概率和图这两种数学工具来建立的模型。那么，很自然的有下一个问题 1. 为什么要引入概率图模型？ 对于一般的统计推断问题，概率模型能够很好的解决，那么引入概率图模型又能带来什么好处呢？ LDPC码的译码算法中的置信传播算法的提出早于因子图，这在一定程度上说明概率图模型不是一个从不能解决问题到解决问题的突破，而是采用概率图模型能够更好的解决问题。《模式识别和机器学习》这本书在图模型的开篇就阐明了在概率模型中运用图这一工具带来的一些好的性质，包括
教学大纲 统计推理和学习（Statistical Inference and Learning）是信号处理、模式识别、通信系统等工程应用中处理不确定性的一个重要方法。新兴的（概率）图模型是概率论与图论相结合的产物，为各种统计推理和学习提供了一个统一的灵活框架。 本课程介绍图模型基本理论，包括：图论相关知识，图模型上条件独立性，有向图模型（贝叶斯网络）、无向图模型（马尔可夫随机场），图模型的统计推理算法，图模型的学习算法（参数学习和结构学习）等，以及图模型在语音识别、图像处理、计算机视觉、通信信道编码（Turbo-coding）等应用中的具体实例。具体包括如下内容：第一章引言 统计推理和学习的概念 第二章图模型 图论相关知识（简介） 图模型上条件独立性（d-separation，Bayes ball） 有向图模型（贝叶斯网络），无向图模型（马尔可夫随机场） 在图模型框架下介绍： 多元高斯模型、 主成分分析（PCA）、 混合分布（Mixtures）、 因子分析（FA）、 隐马尔科夫模型（HMM） 第三章图模型上的推理（Inference） 图论知识深入：簇（Cliques）、可分解图（Decomposable graph），连接树（Junction tree），规范化（Moralization），三角化（Triangulation）等概念 Junction Tree算法 对HMM的前向-后向算法、Viterbi算法，线性动态系统的Kalman滤波的统一描述 1
第四章图模型的参数学习（Parameter Learning） 完整数据下的最大似然（ML）参数估计 不完整数据（Incomplete Data）下的ML参数估计（EM算法） 完整数据下的贝叶斯学习 不完整数据下的贝叶斯学习 第五章图模型的结构学习（Structure Learning） 模型选取准则，包括最小描述长度（Minimum Description Length，MDL），贝叶斯信息准则（Bayesian Information Criterion，BIC）等 结构EM算法（Structural EM） 结构的贝叶斯学习 第六章图模型的应用选讲 图模型在语音识别应用中的实例 图模型在图像处理应用中的实例 图模型在计算机视觉应用中的实例 图模型在通信信道编码（Turbo-coding）应用中的实例 （前面各章中配合理论的讲解，相应有应用实例的介绍。） 2
概率图模型介绍与计算． 概率图模型介绍与计算 01 简单介绍概率图模型是图论和概率论结合的产物，它的开创者是鼎鼎大名的Judea
Pearl,我十分喜欢概率图模型这个工具，它是一个很有力的多变量而且变量关系可视化的建模工具，主要包括两个大方向：无向图模型和有向图模型。无向图模型又称马氏网络，它的应用很多，有典型的基于马尔科夫随机场的图像处理，图像分割，立体匹配等，也有和机器学习结合求取模型参数的结构化学习方法。严格的说他们都是在求后验概率:p(y|x)，即给定数据判定每种标签y的概率，最后选取最大的后验概率最大的标签作为预测结果。这个过程也称概率推理(probabilistic inference）。而有向图的应用也很广，有向图又称贝叶斯网络(bayes networks),说到贝叶斯就足以可以预见这个模型的应用范围咯，比如医疗诊断，绝大多数的机器学习等。但是它也有一些争议的地方，说到这就回到贝叶斯派和频率派几百年的争议这个大话题上去了，因为贝叶斯派假设了一些先验概率，而频率派认为这个先验有点主观，频率派认为模型的参数是客观存在的，假设先验分布就有点武断，用贝叶斯模型预测的结果就有点“水分”，不适用于比较严格的领域，比如精密制造，法律行业等。好吧，如果不遵循贝叶斯观点，前面讲的所有机器学习模型都可以dismiss咯，我们就通过大量数据统计先验来弥补这点“缺陷”吧。无向图和有向图的例子如（图一）所示：
图一 (a)无向图（隐马尔科夫） (b)有向图 概率图模型吸取了图论和概率二者的长处，图论在许多计算领域中扮演着重要角色，比如组合优化，统计物理，经济等。图的每个节点都可看成一个变量，个状态（取值范围），节点之间的边表示变量之间的关系，它除N每个变量有． 了可以作为构建模型的语言外，图还可以评价模型的复杂度和可行性，一个算法的运行时间或者错误界限的数量级可以用图的结构性质来分析，这句话说的范围很广，其实工程领域的很多问题都可以用图来表示，最终转换成一个搜索试问还有什么问题不是搜索问题？目标就是快速的定位到目标，或者查找问题，树是图，旅行商问题是基于图，染色问题更是基于图，他们具有不同的图的结 构性质。对于树的时间复杂度我们是可以估算出来的，而概率图模型的一开始
Stanford概率图模型（Probabilistic Graphical Model）L2 Stanford概率图模型（Probabilistic Graphical Model）—第二讲Template Models and Structured CPDs概率图模型（Probabilistic Graphical Model）系列来自Stanford公开课Probabilistic Graphical Model中Daphne Koller 老师的讲解。（https://https://www.doczj.com/doc/d12426427.html,/pgm-2012-002/class/index）主要内容包括（转载请注明原始出处https://www.doczj.com/doc/d12426427.html,/yangliuy）1. 贝叶斯网络及马尔可夫网络的概率图模型表示及变形。2. Reasoning 及Inference 方法，包括exact inference(variable elimination, clique trees) 和approximate inference (belief propagation message passing, Markov chain Monte Carlo methods)。3. 概率图模型中参数及结构的learning方法。4. 使用概率图模型进行统计决策建模。第二讲. Template Models and Structured CPDs.1 Template Models模版图模型，是对图模型更加紧凑的描述方式。模版变量是图模型中多次重复出现的变量，例如多个学生的智商、多门课程的难度。而模版图模型描述了模版变量如何从模版中继承依赖关系，典型的TemplateModels有动态贝叶斯模型DBN、隐马尔科夫模型HMM及PlateModels。动态贝叶斯模型主要是在贝叶斯网络中引入了马尔科夫假设和时间不变性。这几个模型将在后面几讲中再深入介绍，下面看
教学日历 上课时间：第四大节（15:20~16:55） 上课地点：六教6A403 大节课次内容 （1）9月13日第一章引言 统计推理和学习的概念 （2）9月20日第二章图模型 图论相关知识 有向图模型（贝叶斯网络） （3）9月27日图模型上条件独立性（d-separation，Bayes ball）无向图模型（马尔可夫随机场） （4） 10月4日 国庆放假 （5）10月11日在图模型框架下介绍： 多元高斯模型、 主成分分析（PCA）、 混合分布（Mixtures）、 （6）10月18日因子分析（FA）、 隐马尔科夫模型（HMM） （7）10月25日第三章图模型上的推理（Inference） 图论知识深入：簇（Cliques）、可分解图（Decomposable graph），连接树（Junction tree），规范化（Moralization），三角化（Triangulation）等 （8） 11月1日 图论知识深入（续） 1
（9） 11月8日 Junction Tree算法 （10） 11月15日 Junction Tree算法（续） （11） 11月22日 HMM的前向-后向算法、Viterbi算法 （12） 11月29日 线性动态系统的Kalman滤波 （13）12月6日第四章图模型的参数学习（Parameter Learning） 完整数据下的最大似然（ML）参数估计 不完整数据（Incomplete Data）下的ML参数估计（EM算法）完整数据下的贝叶斯学习 不完整数据下的贝叶斯学习 （14）12月13日第五章图模型的结构学习（Structure Learning） 模型选取准则，包括最小描述长度（Minimum Description Length，MDL），贝叶斯信息准则（Bayesian Information Criterion，BIC）等 结构EM算法（Structural EM） 结构的贝叶斯学习 （15）12月20日第六章图模型的应用选讲 图模型在语音识别应用中的实例 图模型在图像处理应用中的实例 （16）12月27日图模型在计算机视觉应用中的实例 图模型在通信信道编码（Turbo-coding）应用中的实例 2
基于采样的推理算法利用的思想是概率= 大样本下频率。故在获得图模型以及CPD的基础上，通过设计采样算法模拟事件发生过程，即可获得一系列事件（联合概率质量函数）的频率，从而达到inference的目的。 1、采样的做法 使用采样算法对概率图模型进行随机变量推理的前提是已经获得CPD。举个简单的例子，如果x = x1,x2,x3,x4的概率分别是a1,a2,a3,a4.则把一条线段分成a1,a2,a3,a4，之后使用Uniform采样，x落在1处，则随机变量取值为a1...依次类推，如图所示。 显然，采样算法中最重要的量就是采样的次数，该量会直接影响到结果的精度。关于采样次数有以下定理： 以简单的贝叶斯模型为例，如果最终关心的是联合概率，条件概率，单一变量的概率都可以使用采样算法。
下图共需要设置1+1+4+2+3 =11 个uniform采样器，最终得到N个结果组合（d0i1g1s0l1等）。最后计算每个组合出现的频率即可获得联合概率分布。通过边缘化则可获得单一变量概率。如果是条件概率，则去除最终结果并将符合条件的取出，重新归一化即可。 总结可知，采样算法有以下性质： 1.精度越高，结果越可靠，需要的采样次数也越多。 2.所关心的事件发生的概率很小，则需要很大的采样次数才能得到较为准确的结果。 3.如果随机变量的数量很多，则采样算法会非常复杂。故此算法不适用于随机变量很多的情况。 2、马尔科夫链与蒙特卡洛算法 马尔科夫链是一种时域动态模型，其描述的随机变量随着时间的推进，在不同状态上跳跃。实际上，不同的状态是随机变量所可能的取值，相邻状态之间是相关关系。引入马尔科夫链的目的是为了描述某些情况下，随机变量的分布无法用数学公式表达，而可利用马尔科 夫链进行建模。把随机变量的取值视为状态，把随机变量视为跳蚤。马尔科夫链如下图所示：
概率图模型及求解方法 本文介绍概率图模型的定义和几个相关算法，概率图模型是贝叶斯统计和机器学习中的一个常用方法，在自然语言处理和生物信息中也有重要应用。关于概率图模型更详细全面的介绍参见[1],[6]。 1.1什么是概率图模型 概率图模型简单地说是用图作为数据结构来储存概率分布的模型。图中的节点表示概率分布中的随机变量，图中的边表示它连接的两个随机变量之间存在的某种关系（具体是什么关系将在后文提到）。概率图模型可以简洁的表示复杂的概率分布，并且可以利用图论中的算法来求解概率分布中的某些特性（条件独立性和边际概率），因此得到了广泛应用。 1.2有向图模型 1.2.1定义 概率图模型根据模型中的图是否为有向图分为有向图模型和无向图模型两种。有向图模型也叫贝叶斯网络。我们考虑的有向图模型中的图是有向无圈图，有向无圈图是指图中两点之间至多存在一条有向路径。我们可以对有向无圈图中的节点排序，使得图中的边都是从序号小的节点指向序号大的节点，这种排序称为拓扑排序。在有向图中，我们称存在有向边指向节点x 的节点为x 的父节点，节点x 的边指向的节点为x 的子节点。存在由节点x 到节点y 的一条有向路径，并且路径的方向指向节点y 的所有y 的集合称为x 的后代节点。容易看出，在拓扑排序下父节点的序号总是小于子节点的序号。如果图G 中存在有向圈，则节点x 可能既是节点y 的父节点又是节点的子节点，因此父节点、子节点只对有向无圈图有意义。 称概率分布P 可以由有向无圈图G 表出，如果概率分布可以分解为： 1 (x)(x |pa )k k K k P P == ∏ (1.1) 其中，pa k 表示x k 在图G 中所有父节点组成的集合。
第40卷第6期自动化学报Vol.40,No.6 2014年6月ACTA AUTOMATICA SINICA June,2014 概率图模型学习技术研究进展 刘建伟1黎海恩1罗雄麟1 摘要概率图模型能有效处理不确定性推理,从样本数据中准确高效地学习概率图模型是其在实际应用中的关键问题.概率图模型的表示由参数和结构两部分组成,其学习算法也相应分为参数学习与结构学习.本文详细介绍了基于概率图模型网络的参数学习与结构学习算法,并根据数据集是否完备而分别讨论各种情况下的参数学习算法,还针对结构学习算法特点的不同把结构学习算法归纳为基于约束的学习、基于评分搜索的学习、混合学习、动态规划结构学习、模型平均结构学习和不完备数据集的结构学习.并总结了马尔科夫网络的参数学习与结构学习算法.最后指出了概率图模型学习的开放性问题以及进一步的研究方向. 关键词概率图模型,贝叶斯网络,马尔科夫网络,参数学习,结构学习,不完备数据集 引用格式刘建伟,黎海恩,罗雄麟.概率图模型学习技术研究进展.自动化学报,2014,40(6):1025?1044 DOI10.3724/SP.J.1004.2014.01025 Learning Technique of Probabilistic Graphical Models:a Review LIU Jian-Wei1LI Hai-En1LUO Xiong-Lin1 Abstract Probabilistic graphical models are powerful techniques to deal with uncertainty inference e?ciently,and learning probabilistic graphical models exactly and e?ciently from data is the core problem to be solved for the application of graphical models.Since the representation of graphical models is composed of parameters and structure,their learning algorithms are divided into parameters learning and structure learning.In this paper,the parameters and structure learning algorithms of probabilistic graphical models are reviewed.In parameters learning,the dataset is complete or not is also considered.Structure learning algorithms are categorized into six principal classes according to their di?erent characteristics.The parameters and structure learning of Markov networks are also presented.Finally,the open problems and a discussion of the future trend of probabilistic graphical models are given. Key words Probabilistic graphical models,Bayesian network,Markov network,parameter learning,structure learning, incomplete dataset Citation Liu Jian-Wei,Li Hai-En,Luo Xiong-Lin.Learning technique of probabilistic graphical models:a review.Acta Automatica Sinica,2014,40(6):1025?1044 概率图模型能简洁有效地表示变量间的相互关系,为不确定性推理体系提供强有力的工具,近年来已成为人工智能和机器学习的热门研究领域.目前,概率图模型已在图像分析、生物医学和计算机科学等多个领域成功应用.在利用概率图模型进行不确定推理之前,需要先根据领域知识构造出概率图模型.过去,概率图模型的构造通常由领域专家利用专业知识进行人工构造,但是该过程耗时长而且实现 收稿日期2013-06-05录用日期2013-08-01 Manuscript received June5,2013;accepted August1,2013 国家重点基础研究发展计划(973计划)(2012CB720500),国家自然科学基金(21006127),中国石油大学(北京)基础学科研究基金(JCX K-2011-07)资助 Supported by National Basic Research Program of China(973 Program)(2012CB720500),National Natural Science Founda-tion of China(21006127),and Basic Subject Research Fund of China University of Petroleum(JCXK-2011-07) 本文责任编委刘成林 Recommended by Associate Editor LIU Cheng-Lin 1.中国石油大学(北京)自动化研究所北京102249 1.Research Institute of Automation,China University of Petroleum,Beijing102249过程复杂.在当今的信息时代,从样本数据中学习概率图模型已成为主要的构造手段. 目前,常用的概率图模型主要有贝叶斯网络(Bayesian network,BN)和马尔科夫网络(Markov network,MN).BN是有向图模型,而MN是无向图模型,两者的学习算法存在一定的区别.由于概率图模型的表示分参数表示和结构表示两个部分,因此学习算法也分为参数学习与结构学习两大类. BN的参数学习假设结构已知,然后从样本数据中学习每个变量的概率分布.概率分布的形式一般已预先指定,如多项式分布、高斯分布和泊松分布等,只需利用一定的策略估计这些分布的参数.学习过程中需要注意样本数据集的观测程度.若每一个样本都是所有随机变量的充分观测样例,则数据集为完备数据集;若样本中缺失某些变量的观测样例或者存在不可能被观测的隐变量,则数据集为不完备数据集.而不完备数据集的数据缺失假设有三种情况:随机缺失、完全随机缺失和非随机缺失.根据
收稿日期：2009-10-1 基金项目：本课题得到国家重点基础研究发展计划项目(973计划)(2012CB720500)；国家自然科学基金项目(21006127)，中国石油大学(北京)基础学科研究基金项目资助(JCXK-2011-07)。作者简介：刘建伟，男，1966年生，博士，副研究员，主要研究方向：智能信息处理,概率图模型表示理论 刘建伟1 ，黎海恩1 ， 罗雄麟1 （中国石油大学（北京）自动化研究所，北京 100249）1 摘 要 概率图模型结合概率论与图论的知识，利用图来表示与模型有关变量的联合概率分布，近年已成为不确定性推理的研究热点，在人工智能、机器学习和计算机视觉等领域有广阔的应用前景。主要研究概率图模型的表示方法，讨论如何利用概率网络中的独立性来简化联合概率分布的方法表示。首先介绍单个节点上的条件概率分布的表示模型及其引起的独立性，包括表格CPD 、确定性CPD 、特定上下文CPD 、因果影响CPD 、高斯模型和混合模型，并把单个分布模型推广到指数分布族中。然后详细介绍贝叶斯网络中的独立性以及图与概率分布的关系，讨论高斯分布和指数分布族的贝叶斯网络表示理论。再详细描述马尔可夫网络的参数化问题及其独立性，也讨论高斯分布和指数分布族的马尔可夫网络表示理论。还给出两种局部有向图模型：条件随机场和链图。并且描述基于模板的概率模型表示，包括动态贝叶斯网络和状态观测模型这两种暂态模型，以及盘模型和概率关系模型这两种对象关系领域的有向概率模型，而且给出对象关系领域的无向表示。最后对概率图模型表示理论和方法所面临的问题及前景进行展望。 关键词 概率图模型；贝叶斯网络；马尔可夫网络；动态贝叶斯网络；概率关系模型；条件随机场；链图；指数分布族；局部概率模型 中图分类号：TP181 文献标识码：A Representation theory of Probabilistic Graphical Models LIU Jian-Wei 1， LI Hai-En 1， LUO Xiong-Lin 1 （Research Institute of Automation, China University of Petroleum, Beijing 102249, China ）1 Abstract Probabilistic Graphical models bring together graph theory and probability theory in a formalism, so the joint probabilistic distribution of variables in the model can be represented using graph. In recent years, probabilistic graphical models have become the focus of the research in uncertainty inference, because of its bright prospect for the application in artificial intelligence, machine learning, computer vision and so forth. This work introduces the representations of probabilistic graphical models and discusses how to represent the joint probabilistic distribution compactly using the independences in the network. First, models of the conditional probabilistic distribution of single node and their independences are introduced, including tabular CPD, deterministic CPD, context-specific CPD, CPD of causal influence, Gaussian models and hybrid models, and a general framework called the exponential family that encompasses a broad range of distributions are defined. Then Bayesian network representation and its independence properties are described in detail, as well as the Bayesian network of Gaussian distribution and exponential family. This work also introduces Markov network representation, independence properties in Markov network and Markov network of Gaussian distribution and exponential family. We also give two partially directed models, conditional random fields and chain graph models. In addition, this work discusses template-based representations, including temporal models that contain dynamic Bayesian network and state-observation models, directed probabilistic models for object-relational domains which contain plate models and probabilistic relational models, and undirected representation for object-relational domains. Finally, this work raises some questions that probabilistic graphical models are facing with and discusses its development in the future. Key words probabilistic graphical model; Bayesian network; Markov network; dynamic Bayesian network; probabilistic relational model; conditional random field; chain graph; exponential family; local probabilistic model 1 引言 概率图模型把概率论与图论结合在一起，为多变量统计建模提供有力的框架。它利用图来表达随机变量间的依赖关系。概率图模型由两部分组成：网络结构图和参数模型。 网络结构图()E N ,=G 由节点集N 和边集E 构成。N 中的节点表示随机变量集{}n X X ,,1K =χ中的变量，变 量集的取值为{}n x x ,,1K =x 。 边集E 表示两个变量间的概率关系，可以是有向的或者无向的。图1给出随机变量集 {}54321,,,,X X X X X =X 上的一个网络结构图。 参数模型是网络结构图的概率分布表示。整个网络结构图的概率分布为联合概率分布，即所有变量的联合概率分 布。联合概率分布的显式表示难以得到且不便于推理。因此， 通常需要把概率图模型参数化，即利用网络结构中的独立性，把高维联合概率分布分解为低维概率分布的乘积。例如，利用贝叶斯链式法则，图1的联合概率分布可简单分解为 () ()()() ()()43215321421312154321,,,|,,|,||,,,,X X X X X P X X X X P X X X P X X P X P X X X X X P = (1) 贝叶斯网络中隐含着局部条件独立假设()G I l ，即已知父 节点时节点条件独立于其非子节点，那么利用该独立性，联 合概率分布可进一步简化为