chap 07 - 贝叶斯分类器 | Bayesian Classifier

7.1 贝叶斯决策论 Bayesian decision theory

定义： 贝叶斯决策论是概率框架下实施决策的基本方法。对分类任务来说，在所有相关概率都已知的理想情形下，贝叶斯决策论考虑如何基于这些概率和误判损失来选择最优类别标记。

举例：多分类任务

符号：

• $N$：类别数目，即$\cal{Y} = {c_1,c_2, \cdots, c_N}$；
• $λ_{ij}$：将真实标记为$c_j$的样本误分类为$c_i$所产生的损失；
• 样本$\boldsymbol{x}$上的“条件风险”(conditional risk)：基于后验概率$P(c_i|\boldsymbol{x})$可获得将样本分类为$c_i$所产生的期望损失(expected loss)

决策论中将“期望损失”称为“风险”(risk)。

学习目标：

寻找判定准则$h\, : \, \cal{X} \mapsto \cal{Y}$以最小化总体风险

贝叶斯判定准则Bayes decision rule：

为最小化总体风险，只需为每个样本选择能使条件风险$R(c|\boldsymbol{x})$最小的类别标记，即

符号：

• $h^\star$：贝叶斯最优分类器(Bayes optimal classifier)；
• $R(h^\star)$：与$h^\star$对应的总体风险，贝叶斯风险(Bayes risk)；
• $1-R(h^\star)$：分类器能达到的最好性能（模型精度的理论上限）。

具体来说，若目标是最小化分类错误率：

• 误判损失$λ_{ij}$：
• 条件风险：
• 最小化分类错误率的贝叶斯最优分类器： 即对每个样本$\boldsymbol{x}$，选择能使后验概率$P(c|\boldsymbol{x})$最大的类别标记。

使用贝叶斯判定准则的第一步：获得后验概率$P(c\, | \, \boldsymbol{x})$

1. 现实任务中常常难以直接获得；
2. 只能基于有限的训练样本集合尽可能准确估计后验概率。

估计后验概率的方法：

1. 判别式模型 discriminative models：给定$\boldsymbol{x}$，通过直接建模$P(c|\boldsymbol{x})$来预测$c$。如，决策树、BP神经网络、支持向量机。
2. 生成式模型 generative models：先对联合概率分布$P(\boldsymbol{x},c)$建模，再由此获得$P(c|\boldsymbol{x})$。考虑 基于贝叶斯定理，$P(c|\boldsymbol{x})$可写为

符号：

• $P( c )$：类别$c$的“先验”(prior)概率，样本空间中$c$类样本所占比例；
• $P(\boldsymbol{x}\, | \, c)$：样本$\boldsymbol{x}$相对于类标记c的类条件概率(class-conditional probability)，或称为“似然”(likelihood)；
• $P(\boldsymbol{x})$：用于归一化的“证据”(evidence)因子。

估计：

• $P( c )$：根据大数定律，可用频率估计；
• $P(\boldsymbol{x}\, | \, c)$：涉及关于$\boldsymbol{x}$所有属性的联合概率，不能直接用频率估计（样本集合的数目通常远小于现实应用中的数目，“未被观测到”与“出现概率为零”通常是不同的）。
• $P(\boldsymbol{x})$：与类别标记无关，对所有类标记均相同；

为了便于讨论，我们假设所有属性均为离散型。对连续属性，可将概率质量函数$P(·)$换成概率密度函数$p(·)$。

7.2 极大似然估计 Maximum Likelihood Estimation, MLE

估计类条件概率$P(\boldsymbol{x}\, | \, c)$的常用策略：

• 先假定其具有某种确定的概率分布，再基于训练样本对概率分布的参数进行估计。

数学语言说明：

• 记关于类别c的类条件概率为$P(\boldsymbol{x}\, | \, c)$【连续分布下为概率密度$p(\boldsymbol{x}\, | \, c)$】，假设$P(\boldsymbol{x}\, | \, c)$具有确定的形式并且被参数向量\thetac唯一确定，则我们的任务就是利用训练集D估计参数\thetac。为明确起见，将$P(\boldsymbol{x}\, | \, c)$记为$P(\boldsymbol{x}\, | \, \boldsymbol{\theta}_c)$。

概率模型的训练过程就是参数估计(parameter estimation)的过程。

参数估计的两种不同解决方案：

• 频率主义学派 Frequentist：虽然参数未知，但它们是客观存在的固定值。因此，可通过优化函数等准则确定参数值。
• 贝叶斯学派Bayesian：参数是未观察到的随机变量，其本身也可有分布。因此，可假定参数服从一个先验分布，然后基于观测到的数据来计算参数的后验分布。

极大似然估计来源于频率主义学派，是根据数据采样来估计概率分布参数的经典方法。

极大似然法 MLE

符号：

• $D_c$：训练集$D$中第$c$类样本组成的集合，假设样本i.i.d.
• 参数$\boldsymbol{\theta}_c$对于数据集$D_c$的似然： 对$\boldsymbol{\theta}_c$进行极大似然估计，即寻找能最大化似然$P(D_c \, | \, \boldsymbol{\theta}_c)$的参数值$\boldsymbol{\hat{\theta}}_c$直观上看，MLE试图在$\boldsymbol{\theta}_c$所有可能的取值中，找到使数据出现“可能性”最大的值。

式(7.9)中的连乘操作易造成下溢（值太小，无法进行判别分类），通常使用对数似然(log-likelihood)

此时参数$\boldsymbol{\theta}_c$的极大似然估计$\boldsymbol{\hat{\theta}}_c$为

举一个例子🌰：

在连续属性情形下，假设概率密度函数$p(\boldsymbol{x} \, | \, c) \sim \cal{N}(\boldsymbol{\mu}_c, \boldsymbol{\sigma}_c^2)$【正态分布，参见附录C.1.7】，则参数$\boldsymbol{\mu}_c$和$\boldsymbol{\sigma}_c^2$的极大似然估计为

即，通过MLE得到的正态分布的均值就是样本均值，方差就是$(\boldsymbol{x}-\hat{\boldsymbol{\mu}}_c)(\boldsymbol{x}-\hat{\boldsymbol{\mu}}_c)^T$的均值。

离散情形下，用类似方法可估计条件概率。

注意：

• MLE估计结果的准确性严重依赖于对原始数据概率分布的假设的准确性。【所假设的概率分布形式是否符合潜在的真实数据分布。】即，若对原始概率分布的假设错误，MLE的估计结果就是不可靠的。
• 在现实应用中，常要结合任务本身的经验知识假设原始数据的概率分布，单凭猜测很容易产生误导性结果。

7.3 朴素贝叶斯分类器Naïve Bayes Classifier

用贝叶斯公式估计后验概率$P(c \, | \, \boldsymbol{x})$的主要困难：

• 类条件概率$P(\boldsymbol{x}\, | \, c)$是所有属性上的联合概率，难以从有限的训练样本直接估计而得。【基于有限训练样本直接估计联合概率，在计算上将会遭遇组合爆炸问题，在数据上将会遭遇样本稀疏问题；属性越多，问题越严重。】

解决方案：

朴素贝叶斯分类器采用“属性条件独立假设”(attribute conditional independence assumption)：对已知类别，假设所有属性相互独立。【假设每个属性独立地对分类结果发生影响。】

模型建立：

基于属性条件独立性假设，式(7.8)可重写为：

符号：

• $d$：属性数目
• $x_i$：$\boldsymbol{x}$在第$i$个属性上的取值

$x_i$实际上是一个“属性-值”对，例如“色泽=青绿”。为了便于泰伦，在上下文明确是，有时我们用$x_i$表示第$i$个属性对应的变量（如“色泽”），有时直接用其指代$\boldsymbol{x}$在第$i$个属性上的取值（如“青绿”）。

对所有类别来说，$P(\boldsymbol{x})$相同，因此基于式(7.6)的贝叶斯判定准则有朴素贝叶斯分类器的表达式：

训练过程

• 基于训练集$D$来估计先验概率$P( c )$，并为每个属性估计条件概率$P(x_i|c)$。

1. 估计类先验概率：令$D_c$表示$D$中第$c$类样本组成的集合，若有充足的i.i.d.样本，则可容易地估计出类先验概率$P( c )$

2. 针对测试样本，为其每个属性估计条件概率：

对离散属性，令$D_{c,x_i}$表示$D_c$中在第$i$个属性上取值为$x_i$的样本组成的集合，则条件概率$P(x_i|c)$可估计为

对连续属性,可考虑密度函数$p(\boldsymbol{x}i \, | \, c) \sim \cal{N}(\boldsymbol{\mu}{c,i}, \boldsymbol{\sigma}{c,i}^2)$，假定，其中$\boldsymbol{\mu}{c,i}$和$\boldsymbol{\sigma}_{c,i}^2$分别是第$c$类样本在第$i$个属性上取值的均值和方差，则条件概率$p(x_i|c)$为

1. 根据贝叶斯全概率公式，分别计算出样本属于每个类别的概率$P(c_i)$。
2. 把样本标记为$P(c_i)$最大的一类，即标记为$\max{P(c_i)}$对应的类别$c_i$。

举一个例子🌰

用西瓜数据集3.0训练一个朴素贝叶斯分类器，对测试例“测1”进行分类：

首先，估计类先验概率$P©$，显然有

然后，针对测试样本，为其每个属性估计条件概率$P(x_i \, | \, c)$

于是，有

实践中常通过取对数的方式来将“连乘”转化为“连加”以避免数值下溢。

由于$0.063>6.80×10e(-5)$，因此朴素贝叶斯分类器将测试样本“测1”判别为“好瓜”。

Glitch：抹去问题

问题： 若某个属性值在训练集中没有与没某个类别同时出现过，则直接用上述方法【用式(7.17)进行概率估计，用式(7.15)进行类别判别】判别测试样本的类别时，该未出现类别将会被“抹去”。

举一个例子🌰：

在使用西瓜数据集3.0训练朴素贝叶斯分类器时，对一个“敲声=清脆”的测试例，有 由于式(7.15)的连乘式计算出的概率值为零，因此，无论该样本的其他属性是是什么，哪怕在其他属性上明显像好瓜，分类的结果都会是“好瓜=否”，显然不合理。

解决方案：

• 估计概率值时通常要进行“平滑”(smoothing)处理，常用“拉普拉斯修正”(Laplacian correction)。

具体操作：

令$N$表示训练集$D$中可能的类别数，$N_i$表示第$i$个属性可能的取值数，则式(7.16)和(7.17)分别修正为

举一个例子🌰:

在本节例子中，类先验概率可估计为

类似，$P{青绿|是}$和$P{青绿|否}$可估计为

拉普拉斯修正的作用：

• 避免了因训练集样本不充分而导致概率估计为零的问题；
• 训练集变大时，修正中所引入的先验(prior)的影响也会逐渐减小，使估计值逐渐趋近与实际概率值。
• 实质上假设了属性值与类别均匀分布，这是在朴素贝叶斯学习过程中额外引入的关于数据的先验。

现实任务中朴素贝叶斯分类器的使用方式：

• 先存后用：若任务对预测速度要求较高，则对给定训练集，可将朴素贝叶斯分类器设计的所有概率估值实现计算好存储起来，这样在进行预测时只需“查表”即可进行判别；
• 更替频繁，懒惰学习：若任务数据更替频繁，则可采用“懒惰学习”lazy learning方式，先不进行任何训练，待收到预测请求时再根据当前数据集进行概率估值；
• 数据增加，修正属性：若数据不断增加，则可在现有估值基础上，仅对新增样本的属性值所设计的概率估值进行计数修正即可实现增量学习。

7.4 半朴素贝叶斯分类器 Semi-Naïve Bayes Classifiers

问题：朴素贝叶斯的“属性条件独立性假设”在现实中往往难以成立。

基本思想：适当考虑一部分属性间相互依赖信息，从而既不需进行完全联合概率计算，又不会彻底忽略较强的属性依赖关系。

常用策略： 独依赖估计 (One-Dependent Estimator, ODE)

• 独依赖：假设每个属性在类别之外最多仅依赖于一个其他属性，即 其中，$pa_i$：属性$x_i$所依赖的属性，称为$x_i$的父属性。

• 对每个属性$x_i$，若其父属性$pa_i$已知，则可采用类似式(7.20)的方法来估计概率值$P(x_i \, | \, c, pa_i)$

确定每个属性的父属性的方法：

1️⃣ SPODE (Super-Parent ODE)

假设所有属性都依赖于同一个属性，称为“超父” (super-parent)。通过交叉验证等模型选择方法来确定超父属性，由此形成了SPODE方法。 举一个例子🌰: 在图7.1(b)中，$x_1$是超父属性。

2️⃣ TAN(Tree Augmented naïve Bayes) [Friedman et al., 1997]

在最大带权生成树(maximum weighted spanning tree)算法[Chow and Liu, 1968]的基础上，将属性间依赖关系约简为如图7.1( c )所示的属性结构。

具体步骤：

1. 计算任意两个属性之间的条件互信息(conditional mutual information)

2. 以属性为结点构建完全图，任意两个结点之间边的权重设为$I(x_i, x_j \, | \, y)$;

3. 构建此完全图的最大带全生成树，挑选根变量，将边置为有向；

4. 加入类别结点y，增加从$y$到每个属性的有向边。

易看出，条件互信息刻画了属性$x_i$和$x_j$在已知类别情况下的相关性，因此，通过最大生成树算法，TAN实际上仅保留了强相关属性之间的依赖性。

3️⃣ AODE (Averaged One-Dependent Estimator) [Webb et al., 2005]

• 基于集成学习机制、更为强大的独依赖分类器。

具体步骤：

将每个属性作为超父来构建SPODE，然后将具有足够训练数据支撑的SPODE集成起来作为最终结果。 1. 将每个属性作为超父来构建SPODE，估计$P(c,x_i)$和$P(x_j \, | \,c,x_i)$. 类似式(7.20)，有

符号：

• $N$：$D$中可能的类别数；
• $N_i$：第$i$个属性可能的取值数；
• $D_{c,x_i}$：类别为$c$且在第$i$个属性上取值为$x_i$的样本集合；
• $D_{c,x_i,x_j}$：类别为$c$且在第$i$和第$j$个属性上取值分别为$x_i$和$x_j$的样本集合。

1. 将具有足够训练数据支撑的SPODE集成起来作为最终结果，即

符号：

• $D_{x_i}$：在第$i$个属性上取值为$x_i$的样本的集合；
• $m’$：阈值常数【默认设为30 [Webb et al., 2005]】。

举一个例子🌰： 对西瓜数据集3.0有

与朴素贝叶斯分类器的相似点：

• AODE的训练过程也是“计数”，即在训练数据集上对符合条件的样本进行计数的过程；
• AODE也无需模型选择，即能通过预计算节省预测时间，也能采取懒惰学习方式在预测时再进行计数，且易于实现增量学习。

ODE拓展为kDE：

• 依据：将属性条件独立性假设放宽为独依赖性假设可获得泛化性能提升。
• 方法：将式(7.21)中的属性$pa_i$替换为包含有$k$个属性的集合$\boldsymbol{pa}_i$，从而将ODE拓展为kDE（高阶依赖，即对多个属性依赖）。
• 注意：
  • 随着k的增加，准确估计概率$P(x_i \, | \, y, \boldsymbol{pa}_i)$所需的训练样本数量将以指数级增加；
  • 若训练数据非常充分，泛化性能可能提升；
  • 在有限样本条件下，则会陷入估计高阶联合概率的大坑。

7.5 贝叶斯网 Bayesian network / 信念网 belief network

贝叶斯网是一种经典的概率图模型。概率图模型参见第14章。

简介：贝叶斯网借助有向无环图(Directed Acyclic Graph, DAG)来刻画属性之间的依赖关系，并使用条件概率表(Conditional Probability Table, CPT)来描述属性的联合概率分布。

为简化讨论，本节假定所有属性均为离散型。对于连续属性，条件概率表可推广为条件概率密度函数。

基本结构：

一个贝叶斯网$B$由结构$G$和参数$\Theta$两部分构成，即$B=\langle G,\Theta \rangle$.

• 网络结构$G$：一个有向无环图，其每一个结点对应于一个属性，若两个属性有直接依赖关系，则它们由一条 边连接起来。
• 参数$\Theta$：定量描述上述依赖关系。假设属性$x_i$在$G$中的父结点集为$\pii$，则$\Theta$包含了每个属性的条件概率表$\Theta{x_i | \pi_i} = P_B (x_i | \pi_i)$

举一个例子🌰：

图7.2给出了西瓜问题的一种贝叶斯网结构和属性“根蒂”的条件概率表。从图中网络结构可看出，“色泽直接依赖于“好瓜”和“甜度”，而“根蒂”则直接依赖于“甜度”；进一步，从条件概率表中可以得到“根蒂”对“甜度”的量化依赖关系，如P(根蒂=硬挺|甜度=高)=0.1等。

此处已经将西瓜数据集的连续属性“含糖率”转化为离散属性“甜度”。

7.5.1 结构

属性间的条件独立性

贝叶斯网络结构能有效表示出属性间的条件独立性。 给定父结点集，贝叶斯网假设每个属性与它的非后裔属性独立，于是$B=\langle G,\Theta \rangle$将属性$x_1,x_2, \cdots, x_D$的联合概率分布定义为

举一个例子🌰：

以图7.2为例，联合概率分布定义为

显然，$x_3$和$x_4$在给定$x_1$的取值时独立，$x_4$和$x_5$在给定$x_2$的取值时独立，分别简记为$x_3 ⊥ x_4 | x_1$和$x_4⊥x_5|x_2$.

三个变量之间的典型依赖关系

• 同父结构 common parent：
  • 给定父结点$x_1$的取值，则$x_3$与$x_4$条件独立；
  • 若$x_1$取值未知，则$x_3$和$x_4$就不独立，即$x_3⫫x_4$不成立。
• V型结构 V-structure /冲撞结构：
  • 给定子节点$x_4$的取值，$x_1$与$x_2$不必独立；
  • 若$x_4$的取值完全未知，$x_1$与$x_2$相互独立。 证明如下：

这样的独立性称为“边际独立性”(margin independence)，记做$x_1⫫x_2$。 * 顺序结构： * 给定$x$的值，则$y$与$z$条件独立【$y⊥z|x$，但$y⫫z$不成立】；

分析条件独立性的方法——有向分离 D-seperation

步骤：

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

由此，把有向图转换成了无向图，该无向图称为“道德图”(moral graph)。父结点相连的过程称为“道德化”(moralization) [Cowell et al., 1999]。

判定方法：

假定道德图中有变量$x$，$y$和变量集合$\boldsymbol{z}={z_i}$，若变量$x$和$y$能在图上被$\boldsymbol{z}$分开，即从道德图中将变量集合$\boldsymbol{z}$去除后，$x$和$y$分属两个连通分支，则称变量$x$和$y$被$\boldsymbol{z}$有向分离，$x⊥y|z$成立。 > 一般需先对图剪枝，仅保留有向图中x,y,z及它们的祖先结点。

举一个例子🌰：

图7.2所对应的道德图如图7.4所示，从图中能容易地找出所有条件独立关系：

7.5.2 学习

步骤：网络结构⇒属性间依赖关系⇒“计数”训练样本⇒估计每个结点的条件概率表

首要任务：确定最恰当“贝叶斯网”

方法：评分搜索

1. 定义评分函数score function，用于评估贝叶斯网与训练数据契合程度；
2. 基于评分函数寻找具有最优结构的贝叶斯网。 【不同的评分函数表现不同的归纳偏好。】

评分函数

依据：“最小描述长度”(Minimal Descriotion Length, MDL)准则：

常用的评分函数通常基于信息论准则，此类准则将学习问题看做一个数据压缩任务，学习目标是找到一个能以最短编码长度描述训练数据的模型。此时，

编码长度 = 描述模型自身所需的字节长度 + 使用该模型描述数据所需的字节长度

对贝叶斯网学习而言，模型即贝叶斯网，同时，每个贝叶斯网描述了一个在训练数据上的概率分布，自有一套编码机制能使哪些经常出现的样本有更短的编码。于是，我们选择综合编码长度最短的贝叶斯网，这就是MDL准则。

数学表达式：

给定训练集 贝叶斯网B=在D上的评分函数可写为

• 第一项：计算编码贝叶斯网$B$所需的字节数（结构风险）；
• 第二项：计算$B$所对应的概率分布$P_B$对$D$描述得有多好（经验风险）。

符号：

• $|B|$：贝叶斯网的参数个数；
• $f(\theta)$：描述每个参数$\theta$所需的字节数；
• $LL(B|D)$：贝叶斯网$B$的对数似然

模型建立：优化问题，寻找贝叶斯网$B$使评分函数$s(B|D)$最小。

常用评分函数：

• 若$f(\theta)=1$, 即每个参数用1字节描述：
  • AIC(Akaike Information Criterion)评分函数

• 若$f(\theta)=\frac{1}{2} \log m$, 即每个参数用$\frac{1}{2} \log m$字节描述：

  • BIC(Bayesian Information Criterion)评分函数

• 若$f(\theta)=0$, 即不计算对网络进行编码的长度：

  • 评分函数退化为负对数似然；
  • 学习任务退化为极大似然估计。

模型求解：

若贝叶斯网$B=\langle G,Θ \rangle$的网络结构$G$固定，则评分函数$s(B|D)$的第一项为常数。此时，最小化$s(B|D)$等价于对参数$\theta$的极大似然估计。

由式(7.29)和(7.26)可知，参数$\theta_{x_i | \pi_i}$能直接在训练数据$D$上通过经验估计获得，即

其中，$\hat{P}_D(\cdot)$是$D$上的经验分布。因此，为了最小化评分函数$s(B|D)$，只需对网络结构进行搜索，而候选结构的最优参数可直接在训练集上计算得到。

不幸的是，从所有可能的网络结构空间搜索最优贝叶斯网结构是一个NP难问题，难以快速求解。有两种常用的策略能在有限时间内求得近似解：

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

7.5.3 推断

查询query：用训练好的贝叶斯网络，通过一些属性变量的观测值来推测其他属性变量的取值。【类别也可看做一个属性变量。】

• 举一个例子：若我们观测到西瓜色泽青绿、敲声浊响、根蒂蜷缩，想知道它是否成熟、甜度如何。
• 推断 inference：通过已知变量观测值来推测待查询变量的过程。
• 证据 evidence：已知变量的观测值。

困难：

• 最理想的方法是直接根据贝叶斯网定义的联合概率分布来精确计算后验概率，但是这种“精确推断”的方法是NP难的[Cooper, 1990]；【更多关于推断的内容见第14章】
• 需要借助“近似推断”，降低精度要求，在有限时间内求得近似解。

方法：吉布斯采样 Gibbs sampling

【变分推断也很常用，参见14.5节】

符号说明：

• $\boldsymbol{Q}={Q_1,Q_2,\cdots, Q_n}$：待查询变量；
• $\boldsymbol{E}={E_1,E_2,\cdots, E_n}$：证据变量，其已知取值为$\boldsymbol{e}={e_1,e_2,\cdots, e_n}$；
• $P(\boldsymbol{Q}=\boldsymbol{q} \, | \, \boldsymbol{E}=\boldsymbol{e})$：目标，需要计算的后验概率，$\boldsymbol{q}={q_1,q_2,\cdots,q_n}$为待查询变量的一组取值。

举一个例子🌰：

以西瓜问题为例，待查询变量为$Q={好瓜，甜度}$，证据变量为$E={色泽，敲声，根蒂}$且已知其取值为$e={青绿，浊响，蜷缩}$，查询的目标值是$q={是，高}$，即查询这个西瓜是好瓜且甜度高的可能性有多大。

步骤说明：

• 首先，随机产生一个与证据$\boldsymbol{E}=\boldsymbol{e}$一致的样本$\boldsymbol{q}^0$作为初始点；
• 然后，每一步从当前样本出发产生下一个样本。具体来说，在第$t$次采样中，算法先假设$\boldsymbol{q}^t=\boldsymbol{q}^{t-1}$，对非证据变量逐个进行采样改变其取值，采样概率根据贝叶斯网$B$和其他变量的当前取值（即$\boldsymbol{Z}=\boldsymbol{z}$）计算获得。假定经过T次采样得到的与$\boldsymbol{q}$一致的样本共有$n_q$个，则可近似估算出后验概率

吉布斯采样的实质：

吉布斯采样是在贝叶斯网所有变量的联合状态空间与证据$\boldsymbol{E}=\boldsymbol{e}$一致的子空间中进行“随机漫步”(random walk)。每一步仅依赖于前一步的状态，是一个“马尔可夫链”(Markov chain)。在一定条件下，无论从什么初始状态开始，马尔可夫链第$t$步的状态分布在$t→∞$时必收敛于一个平稳分布(statioinary distribution)；对于吉布斯采样而言，这个分布恰好是$P(\boldsymbol{Q}|\boldsymbol{E}=\boldsymbol{e})$。因此，在$T$很大时，吉布斯采样相当于根据$P(\boldsymbol{Q}|\boldsymbol{E}=\boldsymbol{e})$采样，从而保证了式(7.33)收敛于$P(\boldsymbol{Q}=\boldsymbol{q}|\boldsymbol{E}=\boldsymbol{e})$。

更多关于马尔可夫链和吉布斯采样的内容参见14.5节。

算法： (5)除去变量Qi外的其他变量。

注意：

• 马尔可夫链通常需很长时间才能趋于平稳分布，因此吉布斯采样算法的收敛速度较慢。
• 若贝叶斯网中存在极端概率“0”或“1”，则不能保证马尔可夫链存在平稳分布，此时吉布斯采用会给出错误的估计结果。

7.6 EM算法

与前面算法的区别：

• 前面的算法都假设样本是完整的，没有缺失值；
• 现实中常常会遇到“不完整”的训练样本，EM算法可以估计“未观测”变量。

新定义：

• 隐变量 latent variable：未观测变量。

新最大似然函数（目标函数）：

• 符号：
  • $\boldsymbol{X}$：已观测变量集；
  • $\boldsymbol{Z}$：隐变量集；
  • $\Theta$：模型参数。 若欲对$\Theta$做极大似然估计，则应最大化式(7.34)的对数似然函数。

求解方法： * $\boldsymbol{Z}$是隐变量，无法直接求解式(7.34)。 * 通过对$\boldsymbol{Z}$计算期望，来最大化已观测数据的对数“边际似然”(marginal likelihood)

EM(Expectation-Maximization)算法[Dempster et al., 1977]

归属类别：

• 迭代
• 非梯度优化方法
• 类似“坐标下降法”

基本思想：

• E步, Expectation：若参数\theta已知，则可根据训练数据推断出最优隐变量Z的值；
• M步, Maximization：反之，若Z的值已知，则可方便地对参数\theta做极大似然估计。

原型：以初始值$\Theta$为起点，对式(7.35)，可迭代执行以下步骤直至收敛：

• 基于$\Theta^t$推断隐变量$\boldsymbol{Z}$的期望，记为$\boldsymbol{Z}^t$；
• 基于已观测变量$\boldsymbol{X}$和$\boldsymbol{Z}^t$对参数$\Theta$做极大似然估计，记为$\Theta^{t+1}$。

改进：若不取$\boldsymbol{Z}$的期望，而是基于$\Theta^t$计算隐变量$\boldsymbol{Z}$的概率分布$P(\boldsymbol{Z} \, | \, \boldsymbol{X}, \Theta^t)$：

• E步：以当前参数$\Theta^t$推断隐变量分布$P(\boldsymbol{Z} \, | \, \boldsymbol{X}, \Theta^t)$，并计算对数似然$LL(\Theta \, | \, \boldsymbol{X},\boldsymbol{Z})$关于$\boldsymbol{Z}$的期望

• M步：寻找参数最大化期望似然，即

简单来说，EM算法使用两个步骤交替计算：第一步是期望(E)步，利用当前估计的参数值来计算对数似然的期望值；第二部是最大化(M)步，寻找能使E步产生的似然期望最大化的参数值。然后，新得到的参数值重新被用于E步，……直至收敛到局部最优解。

EM算法的收敛性分析参见[Wu, 1983]