【机器学习基础】系列博客为参考周志华老师的《机器学习》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.前言
贝叶斯网（Bayesian network）亦称“信念网”（belief network），它借助有向无环图（Directed Acyclic Graph，简称DAG）来刻画属性之间的依赖关系，并使用条件概率表（Conditional Probability Table，简称CPT）来描述属性的联合概率分布。
贝叶斯网是一种经典的概率图模型。
为了简化讨论，本文假设所有属性均为离散型。对于连续属性，条件概率表可推广为条件概率密度函数。
具体来说，一个贝叶斯网$B$由结构$G$和参数$\Theta$两部分构成，即$B=<G,\Theta>$。网络结构$G$是一个有向无环图，其每个结点对应于一个属性，若两个属性有直接依赖关系，则它们由一条边连接起来；参数$\Theta$定量描述这种依赖关系，假设属性$x_i$在$G$中的父结点集为$\pi _i$，则$\Theta$包含了每个属性的条件概率表$\theta _{x_i \mid \pi _i}=P_{B(x_i \mid \pi _i)}$。
举个例子，从下图中网络结构可看出，“色泽”直接依赖于“好瓜”和“甜度”，而“根蒂”则直接依赖于“甜度”；进一步从条件概率表能得到“根蒂”对“甜度”量化依赖关系，如$P(根蒂=硬挺 \mid 甜度=高)=0.1$等。
2.结构
贝叶斯网结构有效地表达了属性间的条件独立性。给定父结点集，贝叶斯网假设每个属性与它的非后裔属性独立，于是$B=<G,\Theta>$将属性$x_1,x_2,…,x_d$的联合概率分布定义为：
\[P_B(x_1,x_2,...,x_d)=\prod ^d_{i=1} P_B (x_i \mid \pi_i)=\prod ^d_{i=1} \theta_{x_i \mid \pi _i} \tag{1}\]以第1部分的例子为例，联合概率分布定义为：
\[P(x_1,x_2,x_3,x_4,x_5)=P(x_1)P(x_2)P(x_3 \mid x_1)P(x_4 \mid x_1,x_2)P(x_5 \mid x_2)\]显然，$x_3$和$x_4$在给定$x_1$的取值时独立，$x_4$和$x_5$在给定$x_2$的取值时独立，分别简记为$x_3 \perp x_4 \mid x_1$和$x_4 \perp x_5 \mid x_2$。
这里并未列举出所有的条件独立关系。
例子中三个变量之间的典型依赖关系：
在“同父”（common parent）结构中，给定父结点$x_1$的取值，则$x_3$与$x_4$条件独立。在“顺序”结构中，给定$x$的值，则$y$与$z$条件独立。V型结构（V-structure）亦称“冲撞”结构，给定子结点$x_4$的取值，$x_1$与$x_2$必不独立；奇妙的是，若$x_4$的取值完全未知，则V型结构下$x_1$和$x_2$却是相互独立的。我们做一个简单的验证：
\[\begin{align} P(x_1,x_2) &= \sum_{x_4} P(x_1,x_2,x_4) \\&= \sum_{x_4} P(x_4 \mid x_1,x_2) P(x_1) P(x_2) \\&= P(x_1)P(x_2) \end{align} \tag{2}\]这样的独立性称为“边际独立性”（marginal independence），记为$x_1 \perp \!\!\! \perp x_2$。
对变量做积分或求和亦称“边际化”（marginalization）。
证明：【同父结构】在给定父结点$x_1$的条件下$x_3,x_4$独立。
\[\begin{align} P(x_3,x_4 \mid x_1) &= \frac{P(x_1,x_3,x_4)}{P(x_1)} \\&= \frac{P(x_1)P(x_3 \mid x_1)P(x_4 \mid x_1)}{P(x_1)} \\&= P(x_3 \mid x_1) P(x_4 \mid x_1) \end{align}\]证明：【顺序结构】在给定结点$x$的条件下$y,z$独立。
\[\begin{align} P(y,z \mid x) &= \frac{P(x,y,z)}{P(x)} \\&= \frac{P(z)P(x\mid z)P(y \mid x)}{P(x)} \\&= \frac{P(z,x)P(y\mid x)}{P(x)} \\&= P(z \mid x)P(y \mid x) \end{align}\]事实上，一个变量取值的确定与否，能对另两个变量间的独立性发生影响，这个现象并非V型结构所特有。例如在同父结构中，条件独立性$x_3 \perp x_4 \mid x_1$成立，但若$x_1$的取值未知，则$x_3$和$x_4$就不独立，即$x_3 \perp \!\!\! \perp x_4$不成立；在顺序结构中，$y \perp z \mid x$，但$y \perp \!\!\! \perp z$不成立。
为了分析有向图中变量间的条件独立性，可使用“有向分离”（D-separation，D是指“有向”（directed））。我们先把有向图转变为一个无向图：
- 找出有向图中的所有V型结构，在V型结构的两个父结点之间加上一条无向边；
- 将所有有向边改为无向边。
由此产生的无向图称为“道德图”（moral graph），令父结点相连的过程称为“道德化”（moralization）。
“道德化”的蕴义：孩子的父母应建立牢靠的关系，否则是不道德的。
基于道德图能直观、迅速地找到变量间的条件独立性。假定道德图中有变量$x,y$和变量集合$\mathbf z = \{z_i \}$，若变量$x$和$y$能在图上被$\mathbf z$分开，即从道德图中将变量集合$\mathbf z$去除后，$x$和$y$分属两个连通分支，则称变量$x$和$y$被$\mathbf z$有向分离，$x \perp y \mid \mathbf z$成立。例如，第1部分的图所对应的道德图如下所示，从图中能容易地找出所有的条件独立关系：$x_3 \perp x_4 \mid x_1 , x_4 \perp x_5 \mid x_2 , x_3 \perp x_2 \mid x_1 , x_3 \perp x_5 \mid x_1 , x_3 \perp x_5 \mid x_2$等。
3.学习
若网络结构已知，即属性间的依赖关系已知，则贝叶斯网的学习过程相对简单，只需通过对训练样本“计数”，估计出每个结点的条件概率表即可。但在现实应用中我们往往并不知晓网络结构，于是，贝叶斯网学习的首要任务就是根据训练数据集来找出结构最“恰当”的贝叶斯网。“评分搜索”是求解这一问题的常用办法。具体来说，我们先定义一个评分函数（score function），以此来评估贝叶斯网与训练数据的契合程度，然后基于这个评分函数来寻找结构最优的贝叶斯网。显然，评分函数引入了关于我们希望获得什么样的贝叶斯网的归纳偏好。
常用评分函数通常基于信息论准则，此类准则将学习问题看作一个数据压缩任务，学习的目标是找到一个能以最短编码长度描述训练数据的模型，此时编码的长度包括了描述模型自身所需的字节长度和使用该模型描述数据所需的字节长度。对于贝叶斯网学习而言，模型就是一个贝叶斯网，同时，每个贝叶斯网描述了一个在训练数据上的概率分布，自有一套编码机制能使那些经常出现的样本有更短的编码。于是，我们应选择那个综合编码长度（包括描述网络和编码数据）最短的贝叶斯网，这就是“最小描述长度”（Minimal Description Length，简称MDL）准则。
给定训练集$D=\{ \mathbf x_1,\mathbf x_2,…,\mathbf x_m \}$，贝叶斯网$B=<G,\Theta>$在$D$上的评分函数可写为：
\[s(B\mid D)=f(\theta) \mid B \mid - LL(B \mid D) \tag{2}\]这里我们把类别也看作一个属性，即$\mathbf x_i$是一个包括示例和类别的向量。
其中，$\mid B \mid$是贝叶斯网的参数个数；$f(\theta)$表示描述每个参数$\theta$所需的字节数；而
\[LL(B \mid D) = \sum^m_{i=1} \log P_B(\mathbf x_i) \tag{3}\]是贝叶斯网$B$的对数似然。显然，式(2)的第一项是计算编码贝叶斯网$B$所需的字节数（即结构风险），第二项是计算$B$所对应的概率分布$P_B$需多少字节来描述$D$（即经验风险）。于是，学习任务就转化为一个优化任务，即寻找一个贝叶斯网$B$使评分函数$s(B \mid D)$最小。
若$f(\theta)=1$，即每个参数用1字节描述，则得到AIC（Akaike Information Criterion）评分函数：
\[AIC(B \mid D)=\mid B \mid - LL(B \mid D) \tag{4}\]若$f(\theta)=\frac{1}{2} \log m$，即每个参数用$\frac{1}{2}\log m$字节描述，则得到BIC（Bayesian Information Criterion）评分函数：
\[BIC(B \mid D)=\frac{\log m}{2} \mid B \mid - LL(B \mid D) \tag{5}\]显然，若$f(\theta)=0$，即不计算对网络进行编码的长度，则评分函数退化为负对数似然，相应的，学习任务退化为极大似然估计。
不难发现，若贝叶斯网$B=<G,\Theta>$的网络结构$G$固定，则评分函数$s(B\mid D)$的第一项为常数。此时，最小化$s(B\mid D)$等价于对参数$\Theta$的极大似然估计。由式(3)和式(1)可知，参数$\theta_{x_i \mid \pi _i}$能直接在训练数据$D$上通过经验估计获得。
即事件在训练数据上出现的频率。
不幸的是，从所有可能的网络结构空间搜索最优贝叶斯网结构是一个NP难问题，难以快速求解。有两种常用的策略能在有限时间内求得近似解：第一种是贪心法，例如从某个网络结构出发，每次调整一条边（增加、删除或调整方向），直到评分函数值不再降低为止；第二种是通过给网络结构施加约束来削减搜索空间，例如将网络结构限定为树形结构等。
例如TAN将结构限定为树形（半朴素贝叶斯分类器可看作贝叶斯网的特例）。
4.推断
贝叶斯网训练好之后就能用来回答“查询”（query），即通过一些属性变量的观测值来推断其他属性变量的取值。例如在西瓜问题中，若我们观测到西瓜色泽青绿、敲声浊响、根蒂蜷缩，想知道它是否成熟、甜度如何。这样通过已知变量观测值来推测待查询变量的过程称为“推断”（inference），已知变量观测值称为“证据”（evidence）。
类别也可看作一个属性变量。
最理想的是直接根据贝叶斯网定义的联合概率分布来精确计算后验概率，不幸的是，这样的“精确推断”已被证明是NP难的；换言之，当网络结点较多、连接稠密时，难以进行精确推断，此时需借助“近似推断”，通过降低精度要求，在有限时间内求得近似解。在现实应用中，贝叶斯网的近似推断常使用吉布斯采样（Gibbs sampling）来完成，这是一种随机采用方法。
令$\mathbf Q=\{ Q_1,Q_2,…,Q_n \}$表示待查询变量，$\mathbf E=\{E_1,E_2,…,E_k \}$为证据变量，已知其取值为$\mathbf e=\{ e_1,e_2,…,e_k \}$。目标是计算后验概率$P(\mathbf Q=\mathbf q \mid \mathbf E = \mathbf e)$，其中$\mathbf q=\{ q_1,q_2,…,q_n \}$是待查询变量的一组取值。以西瓜问题为例，待查询变量为$\mathbf Q=\{好瓜,甜度 \}$，证明变量为$\mathbf E = \{ 色泽,敲声,根蒂 \}$且已知其取值为$\mathbf e=\{青绿,浊响,蜷缩 \}$，查询的目标值是$\mathbf q=\{是,高 \}$，即这是好瓜且甜度高的概率有多大。
如下图所示，吉布斯采用算法先随机产生一个与证据$\mathbf E = \mathbf e$一致的样本$\mathbf q^0$作为初始点，然后每步从当前样本出发产生下一个样本。具体来说，在第$t$次采样中，算法先假设$\mathbf q^t=\mathbf q^{t-1}$，然后对非证据变量逐个进行采样改变其取值，采样概率根据贝叶斯网$B$和其他变量的当前取值（即$\mathbf Z = \mathbf z$）计算获得。假定经过$T$次采样得到的与$\mathbf q$一致的样本共有$n_q$个，则可近似估算出后验概率：
\[P(\mathbf Q = \mathbf q \mid \mathbf E = \mathbf e) \simeq \frac{n_q}{T} \tag{6}\]
个人理解：第8步取属性$Q_i$概率最大的值作为$q_i^t$。
实质上，吉布斯采样是在贝叶斯网所有变量的联合状态空间与证据$\mathbf E =\mathbf e$一致的子空间中进行“随机漫步”（random walk）。每一步仅依赖于前一步的状态，这是一个“马尔可夫链”（Markov chain）。在一定条件下，无论从什么状态开始，马尔可夫链第$t$步的状态分布在$t\to \infty$时必收敛于一个平稳分布（stationary distribution）；对于吉布斯采样来说，这个分布恰好是$P(\mathbf Q \mid \mathbf E =\mathbf e)$。因此，在$T$很大时，吉布斯采样相当于根据$P(\mathbf Q \mid \mathbf E =\mathbf e)$采样，从而保证了式(6)收敛于$P(\mathbf Q =\mathbf q \mid \mathbf E =\mathbf e)$。
需注意的是，由于马尔可夫链通常需要很长时间才能趋于平稳分布，因此吉布斯采样算法的收敛速度较慢。此外，若贝叶斯网中存在极端概率“0”或“1”，则不能保证马尔可夫链存在平稳分布，此时吉布斯采样会给出错误的估计结果。
