机器学习理论与实战（十三）概率图模型01

         01 简单介绍

         概率图模型是图论和概率论结合的产物，它的开创者是鼎鼎大名的Judea Pearl,我十分喜欢概率图模型这个工具，它是一个很有力的多变量而且变量关系可视化的建模工具，主要包括两个大方向：无向图模型和有向图模型。无向图模型又称马氏网络，它的应用很多，有典型的基于马尔科夫随机场的图像处理，图像分割，立体匹配等，也有和机器学习结合求取模型参数的结构化学习方法。严格的说他们都是在求后验概率:p(y|x)，即给定数据判定每种标签y的概率，最后选取最大的后验概率最大的标签作为预测结果。这个过程也称概率推理(probabilistic inference）。而有向图的应用也很广，有向图又称贝叶斯网络(bayes networks),说到贝叶斯就足以可以预见这个模型的应用范围咯，比如医疗诊断，绝大多数的机器学习等。但是它也有一些争议的地方，说到这就回到贝叶斯派和频率派几百年的争议这个大话题上去了，因为贝叶斯派假设了一些先验概率，而频率派认为这个先验有点主观，频率派认为模型的参数是客观存在的，假设先验分布就有点武断，用贝叶斯模型预测的结果就有点“水分”，不适用于比较严格的领域，比如精密制造，法律行业等。好吧，如果不遵循贝叶斯观点，前面讲的所有机器学习模型都可以dismiss咯，我们就通过大量数据统计先验来弥补这点“缺陷”吧。无向图和有向图的例子如（图一）所示：

图一 (a)无向图（隐马尔科夫） (b)有向图

 

         概率图模型吸取了图论和概率二者的长处，图论在许多计算领域中扮演着重要角色，比如组合优化，统计物理，经济等。图的每个节点都可看成一个变量，每个变量有N个状态（取值范围），节点之间的边表示变量之间的关系，它除了可以作为构建模型的语言外，图还可以评价模型的复杂度和可行性，一个算法的运行时间或者错误界限的数量级可以用图的结构性质来分析，这句话说的范围很广，其实工程领域的很多问题都可以用图来表示，最终转换成一个搜索或者查找问题，目标就是快速的定位到目标，试问还有什么问题不是搜索问题？树是图，旅行商问题是基于图，染色问题更是基于图，他们具有不同的图的结构性质。对于树的时间复杂度我们是可以估算出来的，而概率图模型的一开始的推理求解方法也是利用图的结构性质，把复杂图转换成树（容易处理的图）的形式来求解，这个算法被称为联合树算法（junction tree algorithm）。联合树算法简单的说就是利用图的条件独立性质把图分解，然后以树的形式组织，最后利用树的良好操作性进行推理求解（消息传递），联合树算法是后续章节的重要的推理算法之一。但并不是所有的图都能拆分成树的形式，一般只有合适的稀疏边的图才能转成树，因此联合树算法也有一定的限制。不能构建联合树，那怎么推理求解？好在还有其他几种方法，概率图模型的第二个成分：概率，既然进入了概率空间，那基于蒙特卡洛（MCMC）的采样方法也就可以使用了，反正就是求最大后验概率，MCMC的求解方法也是经常利用的工具，还有一些基于均值场(mean field)以及变分方法(variational method)的求解工具。这几个求解方法的算法复杂度比较如（图二）所示：

(图二)  推理求解算法性能比较

       （图二）中的几种求解方法也都是概率图模型或者统计机器学习里经常使用的方法，MCMC方法和变分方法都起源于统计物理，最近很火的深度学习也算是概率图模型的一个应用，尽管你要反对，我也要把它划到概率图模型下^.^，RBM,CRBM,DBM都是很特殊的概率图模型，整个思路从建模到求解方法都是围绕着求取图模型节点的最大后验概率来开展的。MCMC求解方法就不说了，深度学习里已经用的很多咯，而变分方法（variational method）很有吸引力，andrew ng的师傅Michael Jordan认为把变分方法用在统计机器学习中的有希望的方法是把凸分析和极家族分布函数链接起来，既然有凸分析，那么就会伴随着凸松弛(convex relaxtion),因为数据是离散的，具体可以看前面的关于凸松弛的博文介绍。另外还有一些图模型特有的求解方法，比如belief propagation(sum-product algorithm)n或者expectation propagation等求解方法。

       上面算是对概率图模型做了个简单的介绍，接下的来的博文就是按照下面的提纲来记录一下学习笔记，在尽量不违背honor code的情况下，用原来Daphne koller教授的作业来做辅助介绍。

        一、介绍图模型定义

        二、利用基于变分方法的极家族和凸分析来求边缘概率

        三、逼近求解方法，如belief-propagation、expectation-propagation等

        四、均值场求解方法等各种优化求解方法

        五、结构化学习

 

参考文献：

    [1]Graphical models, exponential families, and variational inference. Martin J . Wain wright and Michael  I.  Jordan

    [2]Probabilistic Graphical Models. Daphne Koller

    [3]The Design and Analysis of Computer Algorithms.Alfred V.Aho