因子分解

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

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

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

对于我们可以遍历他们的概率空间:

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

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

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

则可推断出:

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

贝叶斯网

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

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

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

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

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

贝叶斯网的独立性

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

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

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

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