机器学习系列——6朴素贝叶斯分类器下
在上一篇文章中，我们以3种策略结束了半朴素贝叶斯分类器，其意义在于，考虑了部分属性之间的依赖性，那我们能不能通过考虑属性间的高阶依赖，再进一步提高泛化性能呢？贝叶斯网(Bayesian Network)，亦称为信念网(belief network)，就是这么一种方法，它借助有向无环图(Directed Acyclic Graph,DAG)来刻画属性之间的依赖关系。为什么成为有向无环图呢？也是字面意思，就是属性之间是有直接依赖的关系，例如根蒂直接依赖于甜度，这是有向，具有方向的。无环就是指，这个结构不会构成一个闭环，就是方向是单一的，而且不存在说属性的依赖反而成了其依赖的说法。以下以图1中的网络结构为例子，联合概率分布定义为（公式偏长，可左右滑动）
图1：贝叶斯网络结构示例图
若网络结构已知（即属性间的依赖关系已知），则只需要通过该对训练样本技术，计算出每个节点的条件概率即可，而实际情况中我们往往不知道网络结构。于是，我们就要找出最适合的贝叶斯网。那怎么做呢？比较常用的方法是评分搜索，就是定义一个评分函数，然后基于这个分数来寻找最优结构。一般来说，评分函数是基于信息论准则，此类准则将学习问题看做是一个数据压缩任务，学习的目标就是找到一个能够以最短编码长度描述训练数据的模型（最小描述长度，Minimal Description Length, MDL）。
给定训练集D，贝叶斯网B在D上的评分可记为，
其中， 是贝叶斯网的个数， 表示描述每个参数 所需的编码位数，而 则是贝叶斯网B的对数似然。对于上面公式，其第一项是计算编码贝叶斯网B所需的编码位数，而后一项则是计算B所对应的概率分布 对D的描述情况。也就是说，学习任务就是寻找一个贝叶斯网B使得评分函数 最小。在这里，假设 ，则上面公式可改写为 ，这就是所谓的AIC评分函数；而若 ，则上面的公式可改写为 ，这就是所谓的BIC评分函数；若 ，则上面的公式相当于一个简单的负对数似然，问题就成了极大似然估计。可知，只要网络结构固定了， 即可确定，最小化上面公式就是一个极大似然估计的问题，而问题是，从所有可能的网络结构空间中搜索最优贝叶斯网络是一个NP难问题，解决的思路有两个，一个是贪心法，每次只调整一条边，直到评分函数不再降低为止；二是通过给网络施加约束来削减搜索空间，例如将网络结构限定为树形结构等。
在模型确定好之后，我们想通过一些属性变量的观测值来推测其他属性变量的值，一般只需要计算后验概率即可，而问题是，这样的“精确推断”也是NP难问题（就是说，当网络节点比较多、连接稠密时，难以进行精确推断），所以只能退而求其次找近似解。在现实应用中，常用吉布斯采样来完成，有 。其基本思想就是马尔科夫链，即每一步依赖于前一步的状态。也因此，是实际处理过程中，由于马尔科夫链通常需要很长时间才能区域平稳，吉布斯采样算法的收敛速度会比较慢。另外，若贝叶斯网中存在极端概率0或者1，则不能保证马尔科夫链存在平稳分布，此时吉布斯采样就会给出错误的估计结果。
另外一个问题是，这些过程中我们都假设所有属性变量的值都已被观测到，但是当部分数据不完整的时候，例如“根蒂”脱落之后，我们就不知道这个属性的值该是多少，这个时候该怎么办呢？我们将未观测变量称之为“隐变量”，令X表示已观测变量集，Z则是隐变量集， 表示模型参数，对 做极大似然估计，则应最大化对数似然
由于Z是隐变量，所以这个式子无法直接求解。此时，可通过对Z计算期望，来最大化已观测数据的对数“边际似然”。这里就要提到所谓的EM算法了，Expectation-Maximization，其基本思想是，若参数 已知，则可根据训练数据集推出最优隐变量Z的值（E步）；接着，若Z的值已知，则可对参数 做极大似然估计（M步）。具体说来就是以下两个步骤，
E步：以当前参数 推断隐变量分布 ,并计算对数似然 关于Z的期望，
M步：寻找参数最大化期望似然，即
总而言之，EM算法就是使用E和M进行交替计算，直至收敛到局部最优解。