作者：CHEONG

公众号：AI机器学习与知识图谱

研究方向：自然语言处理与知识图谱

阅读本文之前，先注意一下两点：

1、机器学习系列文章常含有大量公式推导证明，为了更好理解，文章在最开始会给出本文的重要结论，方便最快速度理解本文核心。需要进一步了解推导细节可继续往后看；

2、文中含有大量公式，若读者需要获取含公式原稿Word文档，可关注公众号【AI机器学习与知识图谱】后回复：概率图模型第六讲，可添加微信号【17865190919】进公众号讨论群，加好友时备注来自CSDN。原创不易，转载请告知并注明出处！

本文主要介绍概率图中的两类图：因子图和道德图。

一、本文结论

1、因子图作用：有向图有时需要转为无向图，但在转化过程中会引入环，图中存在环不好处理，因子图的作用是：一方面因子图可以将图中的环去掉；另一方面因子图会使得图计算变得简便；

2、道德图含义：道德图是指在有向图转化为无向图时，这个无向图就又被称为道德图，主要需要掌握的是如何将一个有向图转化为道德图，具体看正文。

二、因子图Factor Graph

有向图可以转为无向图，但转为无向图过程中可能会引入环。例如Belief Propagation算法只能处理树形结构，含有环便不好处理。因此因子图的引入有以下两个作用：

1、首先因子图可以将图中的环去掉，转化为无环图，2、因子图会使得计算变得简便

对于图G={x1,x2,...,xn}G=\{x_1,x_2,...,x_n\}G={x1​,x2​,...,xn​}，因子图可表达成：

其中SSS是图中节点子集，xsx_sxs​是sss的随机变量子集。因式分解本身就对应一个特殊的因子图。一个无向图可以存在多个因子图，在无向图中加入因子节点，以下展现了一个有环无向图两种因子分解图的形式：

三、Moral Graph道德图

将有向图转化为无向图时，该无向图又被称为道德图Moral Graph，为什么要将有向图转化为无向图：因为无向图更加Generalize一些，更方便处理。有向图GGG转化为无向图有两大准则：

1、∀xiϵG\forall x_i \epsilon G∀xi​ϵG，将Parent(xi)Parent(x_i)Parent(xi​)两两连接起来；

2、将GGG中的有向边替换成无向边。

下面展现了四种有向图转化为无向图的例子：

上图中有向图因式分解：p(a,b,c)=p(a)⋅p(b∣a)⋅p(c∣b)p(a,b,c)=p(a)\cdot p(b|a)\cdot p(c|b)p(a,b,c)=p(a)⋅p(b∣a)⋅p(c∣b)，转化后的无向图因子分解为：p(a,b,c)=ψ(a,b)⋅ψ(b,c)p(a,b,c)=\psi(a,b)\cdot \psi(b,c)p(a,b,c)=ψ(a,b)⋅ψ(b,c)，其中ψ(a,b)\psi(a,b)ψ(a,b)相当于有向图中的p(a)⋅p(b∣a)p(a)\cdot p(b|a)p(a)⋅p(b∣a)，ψ(b,c)\psi(b,c)ψ(b,c)相当于有向图中的p(c∣b)p(c|b)p(c∣b)；

上图中有向图因式分解：p(a,b,c)=p(a)⋅p(b∣a)⋅p(c∣a)p(a,b,c)=p(a)\cdot p(b|a)\cdot p(c|a)p(a,b,c)=p(a)⋅p(b∣a)⋅p(c∣a)，转化后的无向图因子分解为：p(a,b,c)=ψ(a,b)⋅ψ(a,c)p(a,b,c)=\psi(a,b)\cdot \psi(a,c)p(a,b,c)=ψ(a,b)⋅ψ(a,c)，同理：ψ(a,b)\psi(a,b)ψ(a,b)近似p(a)⋅p(b∣a)p(a)\cdot p(b|a)p(a)⋅p(b∣a)，ψ(a,c)\psi(a,c)ψ(a,c)近似p(c∣a)p(c|a)p(c∣a)。

上图这种情况较为特殊，不仅仅将有向边替换成无向边还需要将父节点两两相连接，可以从有向图和无向图因子分解证明其合理性。

简单说明一下，例如上式为有向图因子分解，将p(a)⋅p(b)⋅p(c∣a,b)p(a)\cdot p(b)\cdot p(c|a,b)p(a)⋅p(b)⋅p(c∣a,b)用ψ\psiψ函数替换则合理的近似是p(a)⋅p(b)⋅p(c∣a,b)=ψ(a,b,c)p(a)\cdot p(b)\cdot p(c|a,b)=\psi(a,b,c)p(a)⋅p(b)⋅p(c∣a,b)=ψ(a,b,c)，则说明节点a,b,c是一个团，所以两两相连，符合转化后的结果。

参考视频资料：【机器学习】【白板推导系列】 作者：shuhuai008

参考书籍资料：Pattern Recognition and Machine Learning 作者：Christopher Bishop