贝叶斯网

贝叶斯网（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|\pi_i} = P_B(x_i,|\pi_i)\)。

1. 结构

贝叶斯网结构有效地表达了属性间的条件独立性。给定父节点集，贝叶斯网假设每个属性与它的非后裔属性独立，于是\(B = <G, \Theta>\)将属性\(x_1,x_2,\cdots,x_d\)的联合概率分布定义为 \[P_B(x_1,x_2,\cdots,x_d) = \prod_{i=1}^d P_B(x_i|\pi_i) = \prod_{i=1}^d \theta_{x_i|\pi_i}\]

在“同父”（common parent）结构中，给定父节点\(x_1\)的取值，则\(x_3\)与\(x_4\)条件独立。
在“顺序”结构中，给定\(x\)的值，则\(y\)与\(z\)条件独立。
V型结构也称作“冲撞”结构，给定子节点\(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) \nonumber \\ &= \sum_{x_4} P(x_4|x_1,x_2)P(x_1)P(x_2) \nonumber \\ &= P(x_1)P(x_2) \nonumber \end{align}\]

这样的独立性称为“边际独立性”（marginal independence）。
在同父结构中，如果\(x_1\)的取值未知，则\(x_3\)和\(x_4\)就不独立；在顺序结构中，如果\(x\)未知，则\(y\)和\(z\)不独立。
为了分析有向图中变量间的条件独立性，可使用“有向分离”（D-separation），先把一个有向图转变为一个无向图：

找出有向图中的所有V型结构，在V型结构的两个父节点之间加一条无向边；
将所有的有向边改为无向边。

由此产生的无向图称为“道德图”（moral graph），令父节点相连的过程称为“道德化”（moralization）。
基于道德图能直观、迅速地找到变量间的条件独立性。假设道德图中有变量\(x,y\)和变量集合\(\pmb{z} = \{z_i\}\)，如果把变量集合\(\pmb{z}\)去除后，\(x\)和\(y\)属于两个连通分支，则称变量\(x\)和\(y\)被\(\pmb{z}\)有向分离，\(x \perp y | \pmb{z}\)成立。

2. 学习

如果网络结构已知，即属性间的依赖关系已知，则贝叶斯网的学习过程相对简单，只需通过对训练样本“计数”，估计出每个节点的条件概率表即可。但在现实应用中往往不知晓网络结构，于是，贝叶斯网学习的首要任务就是根据训练数据集找出结构最“恰当”的贝叶斯网，“评分搜索”是求解这一问题的常用方法。
评分搜索：先定义一个评分函数，以此来评估贝叶斯网与训练数据的契合程度，然后基于这个评分函数来寻找结构最优的贝叶斯网。显然，评分函数引入了获得怎样的贝叶斯网的归纳偏好。
常用评分函数通常基于信息论准则，此类准则将学习问题看做一个数据压缩问题，学习的目标是找到一个能以最短编码长度描述数据的模型，此时编码的长度包括了描述模型自身所需的字节长度和使用该模型描述数据所需的字节长度。对于贝叶斯网学习而言，模型就是一个贝叶斯网。同时，每个贝叶斯网描述了一个在训练数据上的概率分布，自有一套编码机制能使那些经常出现的样本有更短的编码。我们应选择综合编码长度（包括描述网络和编码数据）最短的贝叶斯网，这就是“最小描述长度”（Minimal Description Length，MDL）准则。
给定训练集\(D = \{\pmb{x}_1, \pmb{x}_2, \cdots, \pmb{x}_m\}\)，贝叶斯网\(B = <G, \Theta>\)在\(D\)上的评分函数可写为 \[s(B|D) = f(\theta)|B| - LL(B|D)\] 其中，\(|B|\)是贝叶斯网的参数个数；\(f(\theta)\)表示描述每个参数\(\theta\)所需的字节数；而 \[LL(B|D) = \sum_{i=1}^m \log P_B(\pmb{x}_i)\] 是贝叶斯网\(B\)的对数似然。显然，公式中的第一项是计算编码贝叶斯网\(B\)所需的字节数，第二项是计算\(B\)所对应的概率分布\(P_B\)对\(D\)描述得有多好。此时，学习任务转化为优化任务，寻找一个贝叶斯网\(B\)使评分函数\(s(B|D)\)最小。
若\(f(\theta) = 1\)，即每个参数用1个字节描述，则得到AIC（Akaike Information Criterion）评分函数： \[AIC(B|D) = |B| - LL(B|D)\] 若\(f(\theta) = \frac{1}{2} \log m\)，即每个参数用\(\frac{1}{2} \log m\)字节描述，则得到BIC（Bayesian Information Criterion）评分函数： \[BIC(B|D) = \frac{\log m}{2} |B| - LL(B|D)\] 若\(f(\theta) = 0\)，即不计算对网络进行编码的长度，则评分函数退化为负对数似然，相应的，学习任务退化为极大似然估计。
如果贝叶斯网\(B=<G,\Theta>\)的网络结构\(G\)固定，则评分函数的第一项为常数。此时，最小化\(s(B|D)\)等价于对参数\(\Theta\)的极大似然估计，参数\(\theta_{x_i|\pi_i}\)能直接在训练数据\(D\)上通过经验估计获得，即 \[\theta_{x_i|\pi_i} = \hat{P}_D (x_i|\pi_i)\] 其中\(\hat{P}_D(·)\)是\(D\)上的经验分布，所以为了最小化评分函数\(s(B|D)\)，只需对网络结构进行搜索，而候选结构的最优参数可直接在训练集上得到。
然而，从所有可能的网络结构空间搜索最优贝叶斯网结构是一个NP难问题，难以快速求解。有两种常用的策略能在有限时间内求得近似解：

贪心法：从某个网络结构出发，每次调整一条边（增加、删除、或调整方向），直到评分函数值不再降低为止；
通过给网络结构施加约束来削减搜索空间，例如将网络结构限定为树形结构等。

3. 推断

贝叶斯网训练好之后就能用来回答“查询”，即通过一些属性变量的观测值来推测其他属性变量的取值，这样通过已知变量观测值来推测待查询变量的过程称为“推断”，已知变量观测值称为“证据”。
最理想的是直接根据贝叶斯网定义的联合概率分布来精确计算后验概率，然而这样的“精确判断”已被证明是NP难的。当网络节点较多、链接稠密时，难以进行精确推断，此时需要“近似推断”，通过降低精度要求，在有限时间内求得近似解，在现实应用中，贝叶斯网的近似推断常使用吉布斯采样（Gibbs sampling）来完成，这是一种随机采样方法。
令\(\pmb{Q} = \{Q_1,Q_2,\cdots, Q_n\}\)表示待查询变量，\(\pmb{E} = \{E_1,E_2,\cdots,E_k\}\)为证据变量，已知其取值为\(\pmb{e} = \{e_1,e_2,\cdots,e_k\}\)，目标是计算后验概率\(P(\pmb{Q} = \pmb{q}|\pmb{E} = \pmb{e})\)，其中\(\pmb{q} = \{q_1,q_2,\cdots,q_n\}\)是待查询变量的一组取值。以西瓜问题为例，待查询变量为\(\pmb{Q}=\{好瓜，甜度\}\)，证据变量为\(\pmb{E}=\{色泽，敲声，根蒂\}\)且已知其取值为\(\pmb{e}=\{青绿，浊响，蜷缩\}\)，查询的目标值是\(\pmb{q}=\{是，高\}\)，即这是好瓜且甜度高的概率有多大。

由上图可知，吉布斯采样算法先随机产生一个与证据\(\pmb{E} = \pmb{e}\)一致的样本\(\pmb{q}^0\)作为初始点，然后每步从当前样本出发产生下一个样本。具体来说，在第\(t\)次采样中，算法先假设\(\pmb{q}^t = \pmb{q}^{t-1}\)，然后对非证据变量逐个进行采样改变其取值，采样概率根据贝叶斯网\(B\)和其他变量的当前取值（即\(\pmb{Z} = \pmb{z}\)）计算获得。假定经过\(T\)次采样得到的与\(\pmb{q}\)一致的样本共有\(n_q\)个，则可近似估算出后验概率 \[P(\pmb{Q} = \pmb{q}|\pmb{E} = \pmb{e}) \simeq \frac{n_q}{T}\] 实质上，吉布斯采样是在贝叶斯网所有变量的联合状态空间与证据\(\pmb{E} = \pmb{e}\)一致的子空间中进行“随机漫步”。每一步仅依赖于前一步的状态，这是一个“马尔科夫链”。在一定条件下，无论从什么状态开始，马尔科夫链第\(t\)步的状态分布在\(t \to \infty\)时必收敛于一个平稳分布；对于吉布斯采样来说，这个分布恰好是\(P(\pmb{Q} = \pmb{q}|\pmb{E} = \pmb{e})\)。因此，在\(T\)很大时，吉布斯采样相当于根据\(P(\pmb{Q}|\pmb{E}=\pmb{e})\)采样，从而保证公式收敛于\(P(\pmb{Q} = \pmb{q}|\pmb{E} = \pmb{e})\)。