概率图模型-学习与推断

概率图模型：学习与推断ProbabilisticGraphicalModel:LearningandInference主讲：耿阳李敖计算机与信息技术学院视觉智能实验室（VisInt）BeijingJiaotong

University概率图中的学习与推断学习：对于给定的观测数据，使用极大似然或后验概率对模型中参数进行估计。推断：基于概率图模型定义的分布，能对目标变量的边际分布（marginaldistribution）或给定某些可观测变量的条件分布（conditionaldistribution）进行推断。从贝叶斯角度下，模型参数亦可视为待推断的变量，则参数估计过程与推断过程是类似的，因此可以“统一”到推断问题中。本节介绍的推断算法同时适用于贝叶斯网络（有向概率图）和马尔科夫网络（无向概率图），它们的过程是类似的，以马尔科夫网络为例进行讲解。概率图推断例子公司组织员工聚餐，已知：小A、小B、小D投票吃火锅；小F、小G、小I、小J投票吃烤肉推理：

小C、小E、小H

的投票结果？

概率图

模型推断精确推断法能够获得概率分布的精确解朴素精确推断法计算开销随极大团的数量呈指数增长针对一些特殊的概率图结构（如树形结构）存在高效算法常见的包括有：变量消除法（VariableElimination）、消息传递法（MessagePassing）等。近似推断法能高效地进行近似估计获得解最有型缺乏理论上的保证常见的包括有：期望最大化（ExpectationMaximization，EM）、变分推断（VariationalInference）、马尔科夫链蒙特卡洛方法（MarkovChianMonteCarlomethod，MCMC）等变量消除法

！！！

变量消除法乘法对加法的分配率概率图的条件独立性

变量消除法概率图的条件独立性

变量消除法变量消除的顺序很重要树遍历定序

！以目标变量为根节点进行树的遍历，然后从叶节点开始从底向上进行变量消除。叶节点叶节点叶节点变量消除法

消息传播算法多个单变量边际分布计算的冗余性消息传播算法消息传播算法导出消息传播算法消息传播机制对于概率图中的每条边定义消息函数树遍历定序两次传播例子

以任意节点为根节点，遍历获得有向树，接着进行两次消息传播。首次传播自底向上，二次自顶向下。首次传播：二次传播：消息传播算法基于消息函数进行边际概率估计计算每个单变量边际分布的时间复杂度多变量情况对于多个变量的联合边际分布来说，消息传播算法和变量消除法一样不能提供计算复杂度的保证，最坏仍为指数级

变量消除法消息传播法

消息传播算法有圈情况当马尔科夫网络中包含圈，则前面介绍的树遍历定序方法将无法使用此时，对消息函数赋予适当的初始值，通过下式进行迭代近似求解：当迭代收敛时其是真实值的一个非常好的近似，但对于一般图来说迭代过程收敛性与收敛速度缺乏理论保证。扩展阅读带圈图中消息传播算法性能的验证与讨论：MurphyK,WeissY,JordanMI.Loopybeliefpropagationforapproximateinference:Anempiricalstudy[J].arXivpreprintarXiv:1301.6725,2013.YedidiaJS,FreemanWT,WeissY.Generalizedbeliefpropagation[C]//NIPS.2000,13:689-695.另一种用于处理带圈图的方法：联合树（JunctionTree）MadsenAL,JensenFV.Lazypropagation:ajunctiontreeinferencealgorithmbasedonlazyevaluation[J].ArtificialIntelligence,1999,113(1-2):203-245.求解最大后验概率的max-sum算法Bishop,ChristopherM.Chapter8