贝叶斯网

因子分解

对于两个特征I与S,都属于二项分布,我们若想描述I与S的联合分布,可以遍历整个概率空间:

I S P(I,S)
i^0 s^0 0.665
i^0 s^1 0.035
i^1 s^0 0.06
i^1 s^1 0.24

上表中用4个参数描述了P(I,S)的概率空间.其实我们只用3个参数就可以描述这个概率空间,因为总概率为1,只要确定其中3个概率,最后一个概率也就确定了.

我们把上述内容类推到n个特征的情况,并且假设所有特征都属于二项分布,那么需要用 2^{n} -1 个参数确定整个概率空间,参数的个数与特征数乘指数增长,这对计算的压力非常大,有没有办法减少计算量呢?回顾一下条件概率的链式法则:

P(I,S) = P(I)P(S | I)

对于 P(I),P(S | I=i^0),P(S | I= i^1) 我们可以遍历他们的概率空间:

P(I)
i^0 0.7
i^1 0.3
P(S \mid I=i^0)
------------ ------------
s^0 0.95
s^1 0.05
P(S \mid I=i^1)
------------ ------------
s^0 0.2
s^1 0.8

同样因为总概率为1,所以每个概率空间可以少使用一个参数,此时总共只需要3个参数就可以描述整个概率空间.

我们把上述内容类推到n个特征的情况,并且假设所有特征都属于二项分布,那么只需要 2n -1 个参数就可以确定整个概率空间.可见对概率空间因子分解可以大大降低计算量.

朴素贝叶斯算法就是使用这种方法减小计算量,它首先假设各特征之间独立:

p(f_{1},\dots ,f_{n})=\prod_{i=1}^{n}P(f_{i})

则可推断出:

p(y,f_{1},\dots ,f_{n})=P(y)\prod_{i=1}^{n}P(f_{i}|y)

不过特征之间相互独立是个很强的假设,有没有方法可以不做特征独立假设,又能使用因子分解降低计算量呢?

贝叶斯网

贝叶斯网是一个有向无圈图.什么是有向无圈图?

有向图很好理解,就是有方向的图,那么什么是圈?

image

圈是一个由同一方向组成的闭合图形,上图中第一个是,而第二个是.

我们来看一个例子,一名学生的学习成绩(G)取决于学生的智商(I)及课程难度(D),而入学考试成绩(S)仅取决于智商,学生的推荐信(L)取决于学生的成绩.根据此关系我们可以得出贝叶斯网:

image

图中反应了各变量的依赖关系,由此我们可以计算出联合分布:

P(I,D,G,S,L) = P(I)P(D)P(G \mid I,D)P(S \mid I)P(L \mid G)

贝叶斯网的独立性

在贝叶斯网中,在给定父节点的条件下,每个节点 X_i 与其非后代节点条件独立,这个性质被称为局部独立性.

比如在上面的学生贝叶斯网中,给定L的父节点G,那么L与D,I,S条件独立;如果给定S的父节点I,那么S与D,G,L条件独立.

符合局部独立性的图被称为独立图(I-map).要注意的是一个分布的独立图可能有多个.


参考:
Daphne Koller<概率图模型>

posted @ 2018-10-21 18:36:32
评论加载中...

发表评论

😃😄😁😆😅🤣😂🙂😉😊🥰😍😘😜🤪😝🤑🤔🤨😏😒🙄😮‍💨🤮😵‍💫🥳😎😳🥺😭😡(这里的表情可以复制)