概率图模型(Probabilistic Graphical Models) – 贝叶斯网络(Bayes Nets)
你可以大概形象的理解概率图模型的2种分类:
1.贝叶斯网络 — 结点与结点之间是以有向箭头相连接,代表是这个结点会影响下一个结点
2. 马尔可夫网络 — 结点与结点之间是以无向箭头相连接,代表是结点与结点之间会相互影响
今天我们来详细介绍下贝叶斯网络
贝叶斯网络
在介绍贝叶斯网络之前,我们先给出一个烂大街的例子,让你知道贝叶斯网络是什么样的。
是谁杀死了主人!
故事是这样的,有一天,一个大庄园的主人被人谋杀了,现在警方把嫌疑锁定在2个人身上,一个是服务主人10年的管家,另外一个是刚应聘不久并且曾经有着不好名声的厨师。
在搜索证据的时候,警方找到了3个可疑凶器,分别是菜刀,手枪和点火器
现在警方初步判断,厨师杀人的概率可能会更大点,于是乎初步设定2人分别为凶手的概率是:
警方进一步调查发现,管家原来是一名退伍军人并且他的柜子里有一把手枪,但是很老了身子板都不行了。厨子却有很多方式可以得到菜刀,并且更年轻。
于是乎,警方又画了个表,分别表示这2人可以接触这些凶器的大概概率:
这里Pistol是手枪,Knife是菜刀,Poker是点火器。
这时候,一名出色的学习了概率图模型的学生,给他们画了个简单的贝叶斯模型:
根据我们上一节讲到的Product Rule, P(x,y)=P(y|x)P(x) ,这个出色的学生:) 开始用上面那个 P(Weapon|Culprit) 条件概率表乘以对应的 P(Culprit) 得出了关于 P(Weapon,Culprit) 的联合概率分布表:
现在警方根据这个概率分布就更加怀疑这个厨子是不是凶手了。
这时,一个关键的证据表明,凶器是手枪,死者是被枪打死的。
听完这个,这个出色的学生淡定的划掉了菜刀和点火器这两列:
警方一看这个表,又突然感觉,管家的嫌疑更大。
以上这个简单的分析案例表示,不要太相信概率图模型。
不,说错了,这个案例表示,现实世界中的案例更加复杂从而会从更多信息中推断出更准确的结果。其实关于证据搜索这部分,大家还可以做的更多,形成一个更加复杂的模型,然后最后再根据已观察的变量来推断出我们想要的结果。
比如这个样子:
Anyway,只要了解了贝叶斯网络基本组成,你们就可以来自己建模型了,一个标准的概率图模型会有这样的表示方式,或者你可以利用Product Rule把下面5个表给合成一张联合概率分布图(不过这样做的的话,就会涉及数据储存大小和计算复杂度的问题,合成一张联合概率分布图的计算量很大,所以一般不这样做):
发现条件独立
现在我们有概率图模型了,也可以通过一些计算来推断出我们想要的变量概率。
但是,往往随着加入的变量越来越多,图的结点也越来越多,这时候计算量将会是指数型剧增。那么如何减少这些计算量呢?
这就是概率图模型一些图算法的重点所在,如何合理的消除变量和生成合理的消除顺序是非常重要的,这些算法我会在以后的章节里慢慢说明。
在此之前,你必须了解一个概念。还记得上一节谈到过的条件独立这个概念吗?
当两个变量与变量之间独立的时候,他们呢发生的概率是互不影响的:
P(x,y)=P(x)P(y)
当两个变量与变量之间,依靠另外一个以观察到的变量存在的时候,才独立:
P(x,y|z)=P(x|z)P(y|z)
我们可以通过这样的计算来计算两个变量是否独立,那除此之外,我们还可以通过已经画出来的概率图模型来看2个变量是否独立还是条件独立吗?
答案:当然是,这就是概率图大部分的图算法来解决的问题,如何更好的利用这些独立与条件独立来解决计算量剧增的问题。
首先,最简单的图就是这样的,X影响Y:
因为Y会被X影响力传播到,所以X和Y一定不独立,。
再看下面这张图,X与Y没有影响关系,所以X影响力传播不到Y,所以X,Y互相独立:
那比如这样呢:
X和Y是否独立呢?
X与Y依靠Z连接,假如Z没有被观察到的话,X的影响力只能传播到Z,Y的影响力也只能传播到Z,,X与Y之间不直接或间接传播,所以X,Y独立。
但假如Z被观察到了,X与Y就不独立了,如下图:
因为这时候,Z是已知的了,你可以想象一下,你可以根据X传播给Z的影响力和Y传播给Z的影响力,分别反推出X和Y的发生的概率。因为有了Z的存在,这时候X和Y发生的概率是互相相关的,所以X与Y不独立在给Z的情况下。
同样的情况如下图:
这时候因为Z的存在,X与Y分别被Z的影响力覆盖,所以当Z一定的时候,X与Y发生的概率也随之固定。
所以X与Y在Z被观察到情况下,条件独立!
再看下面这张图:
因为Z影响着X和Y,但是Z因为没有被观察到,所以Z到X与Y的影响力是和Z变量值相关,所以X和Y不独立。
总而言之,你可以记住,影响力在哪里被断了,被断的这两边就会条件独立。
下面这张图可以形象表示影响力是否被断了,我们称作是否是Active的:
你可以仔细看下这张图的两边,一个被叫做Active,另一个是Inactive。
如过你想要判断2个点之间是否独立或条件独立,你可以先找到这2个点的所有路径(路径指的是这个点到另外一点的所有连接路径,并不管方向),然后只要有任何一条路径是active,那么这2个点就不独立。
具体的过程我就不详细阐述了,具体的我可以贴一个链接在这里:
那么根据我们刚刚说的方法来写一个算法,来判断是否一个点与另外一个点是不是独立的算法就被叫做D-Separation,有向分离法:
{X} d-sep 从 {Y} 通过 {Z}
while True:
begin
删除所有不属于 X∪Y∪Z 的叶结点。
end
删除所有从Z出发的边。
我们可以看以下案例:
我们可以先看第一个,首先X={T,C}, Y={B}, Z={S,X}
我们删除不属于 X∪Y∪Z 的所有叶节点
在删除D点后,继续删除,发现没有符合要求的叶结点,结束循环。
再删除所有从Z出发的边:
我们可以看是不是X={T,C} 和 Y={B}是断开来的?
答案:当然是!所以X={T,C} 和 Y={B}是独立的。
下面第2个案例答案也是Yes,独立的!感兴趣的同学可以自己画图。
今天介绍了贝叶斯模型长什么样子,还有简单的一些变量独立概念和有向分离算法。
今天就这么多啦,如果有什么错误,请大家及时!
2020/1/8
Home