朴素贝叶斯算法-贝叶斯网络

朴素贝叶斯算法：

一个假设：各特征之间相互独立

p(B|A)=(p(A|B1)+p(A|B2)+p(A|B3)+...)*p(B)/p(A)

(主要原因：大概是没有一个实例满足B，但各个分特征都存在不同实例可以分别满足，借此求出概率）

但假设很难满足条件，为此有了一个新的算法

贝叶斯网络算法：

也叫信息网络，有向无环图模型（数据结构中学过）—无向图就是另一种算法马尔科夫随机场或马尔科夫网络

单体形式：E->F，E为因，F为果，其中间存在一个概率p(F|E)

多个特征结构形式：

1.head to head

a- > c< - b

有概率公式p(a,b,c)=p(a)*p(b)*p(c|a,b)

2.tail to tail

a< - c- > b

有概率公式p(a,b,c)=p(c)*p(a|c)*p(b|c)

c已知时，p(a,b|c)=p(a,b,c)/p(c)=p(a|c)*p(b|c). a,b独立

c未知时，没办法得出上述式子，a,b不独立

3.head to tail

a- > c- > b

有概率公式p(a,b,c)=p(b|c)*p(c|a)*p(a)

c未知时，无法推出上述式子，a,b不独立

所以当前状态只与上一状态有关，与上上状态，或上上之前的状态无关—马尔科夫链（随机过程学过）

在之后的解决方案就是将其转化为因子图，然后利用sum-product算法求解

因子图：

将一个具有多变量的全局函数因子分解，得到几个局部函数的乘积，以此为基础得到的一个双向图叫做因子图

—其实就是对函数因式分解得到的一种概率图，一般有两个节点：变量节点和函数节点

如何转换成因子图：

1.贝叶斯网络中的一个因子对应因子图中的一个结点（应该就是各个分开的概率公式）

2.贝叶斯网络中的每一个变量在因子图上对应边或半边

3.结点g和边x相连当且仅当变量x出现在因子g中

Sum-product算法：

此算法主要用于计算边缘分布

就是将大规模的加法转化为少量的乘法（乘法由于树的结构可以用迭代的方法）

具体可以看文献factor graphs and the sum product algorithm[J].koski T,noble J M.bayesian networks 2009, 10.1002/978470684023:319-333