作者:CHEONG
公众号:AI机器学习与知识图谱
研究方向:自然语言处理与知识图谱
阅读本文之前,先注意一下两点:
1、机器学习系列文章常含有大量公式推导证明,为了更好理解,文章在最开始会给出本文的重要结论,方便最快速度理解本文核心。需要进一步了解推导细节可继续往后看
2、文中含有大量公式,若读者需要获取含公式原稿Word文档,可关注公众号【AI机器学习与知识图谱】后回复:概率图模型第三讲,可添加微信号【17865190919】进公众号讨论群,加好友时备注来自CSDN。原创不易,转载请告知并注明出处!
本文主要介绍无向图中的条件独立性和因子分解。若需了解有向图中的条件独立性和因子分解请看上一篇【机器学习系列】概率图模型第二讲:深入浅出有向图中的条件独立性和D划分
本文结论
知识点1:无向图条件独立性体现在全局马尔可夫性、局部马尔可夫性和成对马尔可夫性三个方面。并且三个方面是相互存在,即其中任一个成立均可推出另外两个成立;
知识点2:概率图的条件独立性和概率图的因子分解不是相互独立的,因子分解式是可以推导出概率图的条件独立性假设;
知识点3:无向图的因子分解比有向图因子分解要复杂,有向图根据拓扑结构可直接写出因子分解式,而无向图中引入了最大团的改进进行因子分解。
一、无向图条件独立性
无向图模型的条件独立性体现在以下三个方面:
1、 全局马尔可夫性:
如下图所示,无向图的条件独立性很简单,如果在给定集合XBX_BXB情况下,集合XAX_AXA和XCX_CXC相互独立,则必须满足如下条件:节点a属于集合XAX_AXA,节点c属于集合XCX_CXC,若存在节点b和节点a和c之间均连接,则节点b必须存在于集合XBX_BXB中。
2、局部马尔可夫性:
如下图所示,局部马尔可夫性是指节点a在给定邻居节点b,c,d情况下和非邻居节点是相互独立的。
3、成对马尔可夫性:
注意:全局马尔可夫性,局部马尔可夫性和成对马尔可夫性之间是相互依存的,即其中一个成立可推导出另外两个也是成立的。
二、无向图因子分解
有向图的因子分解根究图的拓扑结构很容易写出因子分解式,但无向图因子分解较复杂,无论是有向图或无向图,因子分解必须要体现图的条件独立性,因子分解和图的条件独立性是等价的。
为了解决无向图因子分解,先引入团和最大团的概念。团是指无向图中节点的集合,且节点之间都是相通的,最大团是指团中再多加入一个节点所有节点就不是相通的,即无向图中最大团的概念。
下面先直接给出基于最大团的无向图因子分解的公式:
其中xcix{c_i}xci既是值团cic_ici对应图中的节点集合,ϕ\phiϕ函数是势函数,ϕ(xci)=exp(−E(xci))\phi(x{c_i})=exp({-E(x{c_i})})ϕ(xci)=exp(−E(xci)) ,必须为正,E(xci)E(x{c_i})E(xci)表示能量函数,而ZZZ是归一化因子,计算方式如下:
可以通过Hammesley-Clifford定理证明上述的因子分解方式是可以推导出无向图的条件独立性,从侧面说明基于最大团的无向图分解的合理性。
总结:有向图的因子分解,条件独立性;无向图的因子分解,条件独立性。
参考视频资料:【机器学习】【白板推导系列】 作者:shuhuai008
参考书籍资料:Pattern Recognition and Machine Learning 作者:Christopher Bishop