数据挖掘|概率图模型（一）
下来我们将花两篇小专栏的时间对概率图模型进行简单的介绍，主要是一些概率的基础与证明，比较理论化。但个人觉得还是很有必要。因为后期的一些算法是以这个为模型基础的，所以现在首先构建一个理论基础，后面谈到应用的时候可能会更好的理解。
本篇可能写的有些抽象，如果有更好的建议，欢迎提出~
------------------------萌萌哒的分割线------------------------
- 贝叶斯网络基础
为了将事件的关联性用图的方式，清楚的呈现在我们眼前，Pearl开发了一种叫概率图（PGM）的模型。这个模型抽象了一些事件，还有他们的联系。简而言之，就是把一系列事件画成圆圈，如果事件相互之间有联系，那么就在在两个圈上连上一条线。如果是因果关系的话，那么就在这个线上标个箭头。
基本的概率图模型主要是：贝叶斯网络，马尔科夫随机场。其中，贝叶斯网络通过有向无环图(Directed Acyclic Graph)来表现。有向指的是因果关系（就是图中的箭头），无环指的是因果关系不构成环状，也就是没有A→ B,B→ C,C→ A的这种情况。整个贝叶斯网络反映的就是：在一系列随机事件中，一些事件的发生对另一些事件概率的影响。（这里也可以理解为条件概率，或者是因果关系，就像感到饿了的这个事件会对吃东西这个事件产生影响一样）。
下面是一个简单的贝叶斯网络：
我们用
P(x1,x2,x3,x4,x5,x6,x7)表示上图的七个时间全部发生，那么这个图的概率模型为：
P(x1,x2,x3,x4,x5,x6,x7)=P(x1)P(x2)P(x3)P(x4|x1,x2,x3)P(x5|x1,x3)P(x6|x4)P(x7|x4,x5)公式推广可以得到：P(X)=\prod_{k=1}^{K} P(x_{k}|pa_{k} ) 其中，pa_{k}表示x_{k}的所有父节点（也就是所有对这个事件有影响的因）这个公式就代表，上面的7个事件全部都发生了。
在概率上，如果事件a和b独立，也就是说a的发生对b没有影响，就成立：P(a,b)=P(a)P(b)如果已经发生了c，那么说明a,b独立的式子将变为：P(a,b|c)=P(a|c)P(b|c)
我们考察a,b两个事件是否有关系，就是看，是否能证明上面的式子。对于任意的一个贝叶斯网络，我们为了考察中其中a,b两个事件是否在c发生的情况下独立（也可以说a,b是否对于从独立），那么首先从这个图的基础的结构来分析。
下面有三种基础结构，证明将从图概率公式出发，考察ab是否独立：
- tail-to-tail
1）c未知：a,b不独立。证明如下：
P(a,b)=\sum_{c}^{}{P(a|c)P(b|c)P(c)}此式子不能推出：P(a,b)=P(a)P(b) 所以，a,b不独立。
2）c已知：a,b独立。证明如下：
P(a,b|c)=\frac{P(a,b,c)}{P(c)}=P(a|c)P(b|c)也就是说tail-to-tail的情况下，a,b对于c独立。可以看成c把a到b的线给砍断了。
- head-to-tail
1）c未知：a,b不独立。这个和上面的情况一样。
2）c已知：a,b独立。证明如下：
P(a,b|c)=\frac{P(a,b,c)}{P(c)}=\frac{P(a)P(c|a)P(b|c)}{P(c)}=P(a|c)P(b|c)也就是说head-to-tail的情况下，a,b对于c独立。同理，也可以看成c把a到b的线给砍断了。
- head-to-head
1）c未知：a,b独立。这个直接有图的概率公式就可以得到。
2）c已知：a,b不独立。证明如下：
P(a,b|c)=\frac{P(a,b,c)}{P(c)}=\frac{P(a)P(b)P(c|a,b)}{P(c)}无法得到P(a,b|c)=P(a|c)P(b|c)
也就是说head-to-head的情况下，如果c未知，那么a，b独立，或者可以理解为a，b之间没有通路。
对于所有复杂的有向无环图(Directed Acyclic Graph)图，都是由上面的三种基础结构拼接而成的，当我们考察一个复杂的有向无环图中的a，b是否对于c独立时候，我们可以给出一个普遍意义上的结论 ，也就是 D-Seperation。
- D-Seperation
对于有向无环图 ，如果A，B，C是三个集合（可以是单独的节点或者是节点的集合），为了判断 A 和 B 是否是 C 条件独立的（也就是C发生的时候，A和B是否独立）， 我们考虑图中所有 A 和 B 之间的无向路径 （不管箭头朝向，只要是把A,B通过几个点最终连接到一起的）。对于其中的一条路径，如果它满足以下两个条件中的任意一条，则称这条路径是 阻塞（block） 的：
1）路径中存在某个节点 X 是 head-to-tail或者 tail-to-tail 节点（上图的c的位置），并且 X 是包含在 C 中的；（因为A到B的连接是一条线，上面已经证明 head-to-tail或者 tail-to-tail的节点c可以把联系给砍断，多一说这条路径被block了）
2）路径中存在某个节点 X 是 head-to-head 节点（上图的c的位置），并且 X 或 X 的子节点是不包含在 C 中的； （这个是head-to-head的情况，C未知，则A，B没有联系）
如果 A，B 间所有的路径都是关于C阻塞的，那么 A，B 就是关于 C 条件独立的；否则， A，B 不是关于 C 条件独立的。
我们来举一个例子：
判断图（a）中a与b是否在c条件下独立？a与b是否在f条件下独立？
判断 a 和 b 是否是 c下条件独立的： a 到 b 只有一条路径 a->e->f->b 。 考虑路径上的点 e 和 f ：其中e 是 head-to-head 类型的，且 e 的儿子节点就是 c ，根据 2），e不阻断，那么就是a，b对于c不独立。如果在多考虑一下f，f是tail-to-tail类型节点，根据 1），f不在c中，所以并没有切断这条路径，所以有a，b不是c条件下独立。
判断 a 和 b 是否是 f 下条件独立的：路径 a->e->f->b 上的所有节点。考虑路径上的点e和f：节点 e 是head-to-head 类型的，e 和她的儿子节点 c 都不在 f 中，所以 2），e是阻断路径的节点。节点 f 是tail-to-tail类型节点，且 f 节点就在 f中，所以 f 节点阻断了路径。 结论：a 和 b是 f 下条件独立的。
搬了下面网址的内容，感谢作者啦~：
【1】
https://my.oschina.net/dillan/blog/134011【2】
http://www.norsys.com/tutorials/netica/secA/tut_A1.htm------------------------萌萌哒的分割线------------------------
更多项目介绍，请关注我们的项目专栏：China's Prices Project - 知乎专栏
项目联系方式：
