3. 使用 EM 的半监督文本分类

数十年以来，统计学家提倡使用标记数据和未标记数据的组合，通过迭代期望最大化（EM）技术估计生成模型的参数来训练分类器。本章探讨了这种方法在应用于文本分类领域时的有效性。本文用一组词模型来表示文本文档，这导致了一个基于多项式混合的生成分类模型。这个模型非常简单地表示了书面文本的复杂性。本章阐述并说明了生成模型下文本分类半监督学习的三个要点。首先，尽管文本域的表示形式过于简单，但在生成模型概率和分类精度之间，有些文本域具有很高的正相关。在这些领域中，简单地将em应用于NaiveBayes文本模型效果很好。其次，一些文本域没有这种相关性。在这里，我们可以采用一个更具表现力和适当的生成模型，它确实具有正相关性。在这些领域中，半监督学习再次提高了分类的准确性。最后，EM还存在局部极大值问题，特别是在文本分类等高维领域。我们证明了确定性退火是EM的一个变种，它可以克服局部极大值问题，在生成模型适当的情况下进一步提高分类精度。

3.1 简介

从标记数据和未标记数据的组合中学习分类器是统计学界的一个老观点。至少早在1968年，就有人建议通过测试所有可能的类分配，将有标记和无标记的数据结合起来，以建立具有最大似然性的分类器（Hartley和Rao，1968年）。Day（1969）的开创性论文提出了一种迭代的EM-like方法，仅从未标记的数据中获得已知协方差的两个正态的混合参数。类似的迭代算法，用于从有标记和无标记的数据中构建最大似然分类器，随后使用显式生成模型，主要用于正态分布的混合分布（McLachlan，1975；Titterington，1976）。

Dempster等人（1977）提出了 EM 框架的理论，将先前提出的用于缺失数据的似然最大化的迭代技术的许多共性集合起来并形式化。它适用于根据标记和未标记数据（Murray和Titterington，1978年）估计混合模型的最大似然（或最大后验）参数，然后将其用于分类（Little，1977年），立即得到了承认。此后，继续使用和研究这种方法（McLachlan和Ganesaligam，1982年；Ganesaligam，1989年；Shahshahani和Landgrebe，1994年）。最近，利用混合模型的似然最大化将标记和未标记的数据组合起来进行分类，已经向机器学习社区发展了起来（Miller和Uyar，1996年；Nigam等人，1998年；Baluja，1999年）。

期望最大化的理论基础表明，当模型类生成足够多的未标记数据时，可以找到比仅使用标记数据更可能的模型。如果分类任务是预测生成模型的潜在变量，那么有足够的数据，一个更可能的模型也将导致更准确的分类器。

这种方法基于生成模型是正确的假设。当分类任务是对人类编写的文本进行分类时（我们在这里考虑），真正的生成模型是不可能参数化的，而实践者倾向于使用非常简单的表示。例如，常用的朴素贝叶斯分类器将每个编写的文档表示为一个单词包，丢弃所有单词排序信息。这个分类器的生成模型断言文档是通过从类条件多项式中抽取来创建的。由于这是对创作过程的一种极端简化，因此有必要问一下，这种生成式的半监督学习建模方法在文本分类领域是否合适或有益。

这一章论证了当选择的生成模型概率与分类精度有很好的相关性，并且可以避免次优局部极大值时，生成方法适用于半监督文本分类。在某些情况下，尽管朴素的贝叶斯生成模型很简单，但它还是足够的。我们发现模型概率与分类精度密切相关，期望最大化技术产生的分类器具有未标记的数据，比单独使用标记数据构建的分类器更精确。在其他情况下，朴素贝叶斯生成模型与分类准确度没有很好的相关性。通过采用更具表现力的生成模型，恢复了模型的准确性和概率相关性，再次得到了良好的结果。

EM的一个缺陷是它只保证在模型概率空间中发现局部极大值而不是全局极大值。在像文本分类这样的领域中，由于参数数量非常多，这种效果可能非常显著。研究表明，当模型概率和分类之间存在良好的相关性时，采用确定性退火（一种交替的模型估计过程）可以发现更可能的，从而更准确的分类器。

非生成方法也被用于半监督文本分类。Joachims（1999）使用转导支持向量机为多个文本分类任务构建识别分类器。Blum和Mitchell（1998）使用联合培训设置为网页构建Naive Bayes分类器，使用锚文本和页面本身作为有关实例的两个不同信息源。Zelikovitz和Hirsh（2000）使用未标记的数据作为背景知识来增强最近邻分类器。他们不直接将测试示例与其最近的标记示例进行匹配，而是通过测量与一组未标记示例的相似性，将测试示例与标记示例进行匹配。

本章内容如下。第3.2节介绍了用于文本分类的生成模型，并说明了如何使用em执行半监督学习。第3.3节给出了一个示例，说明了这种方法在何处工作良好。第3.4节提出了一个更具表现力的生成模型，该模型在朴素的贝叶斯假设不充分时有效，并从需要它的领域获得了实验结果。第3.5节给出了确定性退火，并表明这发现了比EM发现的模型参数化更为可能的模型参数化，尤其是当标记数据稀疏时。

3.2 文本生成式模型

本节介绍了一个描述文本文档的框架，并说明了如何使用该框架从标记和未标记的数据训练分类器。该框架定义了概率生成模型，并对生成过程进行了三个假设：（1）数据是由混合模型生成的；（2）混合成分与类之间存在一一对应关系；（3）混合成分是单个词的多项式分布。这些是朴素贝叶斯分类器使用的假设，这是标准监督文本分类的常用工具（Lewis，1998；McCallum和Nigam，1998）。

我们假设文档是由多项式模型的混合生成的，其中每个混合分布组件对应一个类。设有 M 个类别和一个大小为 $|\chi|$ 的词汇表；每个文档 $x_i$ 含有 $|x_i|$ 个单词。如何使用此模型创建文档？第一，我们滚动有偏的M面骰子来确定文档的类。然后，选取与所选类对应的偏 $|\chi|$ 边骰子。我们将这个骰子滚动 $|x_i|$ 次，计算每个单词出现的次数。这些字数构成生成的文档。

形式上，每个文档都是根据由混合模型参数定义的概率分布生成的，称为θ。概率分布由一个由组件 $c_j\in[M]$ 混合分布组成。文档， $x_i$ ，首先根据混合权重选择一个混合组件—— $P(c_j|\theta)$ ，然后使用这个被选中的组件根据自身的参数依分布 $P(x_i|c_j;\theta)$ 生成一个文档。因此，看到文档 $x_i$ 的似然是所有混合分布成分的总概率之和：

$P(x_i|\theta)=\sum_{j\in [M]}P(c_j|\theta)P(x_i|c_j;\theta)$ (3.1)

每个文档有一个类标签。我们假设混合模型组件和类之间是一对一的对应关系，因此使用 $c_j$ 来表示 $jth$ 混合物组件以及 $jth$ 类。一个文档 $x_i$ 对应的类标签写为 $y_i$ 。如果文档 $x_i$ 是由混合组件 $c_j$ 生成的我们就说 $y_i=c_j$ 。

一个文档， $x_i$ ，是一个词汇数量的向量。我们将 $x_{it}$ 写为文档 $x_i$ 中出现的单词 $w_t$ 的次数。当一个文件由一个特定的混合成分生成时，文件长度， $|x_i|=\sum\nolimits_{t=1}^{|\chi|}x_{it}$ ，首先是独立于组件选择的。然后，利用所选混合组分的多项式分布，生成指定长度的文档。

由此我们可以展开（3.1）中的第二项，并根据文档的组成特征（文档长度和文档中的单词）表示给定混合成分的文档的概率。

$P(x_i|c_j;\theta)\propto P(|x_i|)\prod_{w_t=\chi} P(w_t|c_j;\theta)^{x_{it}}$ （3.2）

这个公式嵌入了标准朴素贝叶斯假设：文档中的词汇在给定类标签时是条件独立于同一文档中的其他词汇的。

因此，单个混合成分的参数定义了词的多项式分布，即词概率的集合，每一个写为 $\theta_{w_t|c_j}$ ，因此 $\theta_{w_t|c_j}\equiv P(w_t|c_j;\theta)$ ，这儿 $t\in[|\chi|]$ 且 $\sum\nolimits_t P(w_t|c_j:\theta)=1$ 。因为我们假设对于所有类，文档长度都是相同分布的，所以不需要为分类参数化文档长度。模型的其他参数只有混合权重（类概率）， $\theta_{cj}\equiv P(c_j|\theta)$ ，其指示了选择不同混合成分的概率。因此，模型参数θ的完整集合定义了一组多项式和类概率： $\theta = \{\theta_{w_t|c_j}:w_t\in [M];\theta_{c_j}:c_j\in [M] \}$ 。

总结下，通过结合方程 3.1 、3.2 给出的的全生成模型，赋值概率 $P(x_i|\theta)$ 生成文档 $x_i$ 如下:

$P(x_i|\theta)\propto P(|x_i|)\sum_{j\in[M]}P(c_j|\theta)\prod_{w_t=\chi} P(w_t|c_j;\theta)^{x_{it}}$ （3.3）这儿次数集 $x_{it}$ 是生成模型中参数向量 $\theta$ 的充分统计。

3.2.1 基于生成模型的监督文本分类

从一组标记文档中学习朴素贝叶斯文本分类器包括估计生成模型的参数。对参数 $\theta$ 的估计记为 $\hat \theta$ 。朴素贝叶斯使用最大后验（MAP）估计，即找到 $argmax_{\theta}P(\theta|X,Y)$ 。这是考虑到训练数据的证据和一个先验值的最可能的 $\theta$ 值。

我们的先验分布是由Dirichlet分布的乘积形成的，每类多项式一个，总类概率一个。Dirichlet是多项式分布中常用的共轭先验分布。Dirichlet 分布如下：

$P(\theta_{w_t|c_j}|\alpha) \propto \prod_{w_t\in \chi}P(w_t|c_j)^{\alpha_t -1}$ （3.4）

这儿 $\alpha_t$ 限制大于 0。我们设置所有 $\alpha_t = 2$ ，这对应一个偏好均匀分布的先验。这与拉普拉斯和 M-估计平滑相同。Stolcke和Omohundro对Dirichlet分布作了很好的介绍。由数据和先验值最大化得到的参数估计公式是我们熟悉的经验计数平滑比。词概率估计值 $\hat\theta_{w_t|c_j}$ 为：

$\hat\theta_{w_t|c_j}\equiv P(w_t|c_j;\hat\theta)=\frac{1+\sum\nolimits_{x_i\in \chi}\delta_{ij}x_{it }}{|\chi|+\sum\nolimits_{s=1}^{|\chi|}\sum\nolimits_{x_i\in \chi}\delta_{ij}x_{is} }$ （3.5）

这儿 $\delta_{ij}$ 由类标签给出：1 当 $y_i=c_j$ ，0 其他。类概率，即 $\theta_{c_j}$ ，以同样的方式估计，并且还涉及一个平滑计数比：

$\hat\theta_{c_j}\equiv P(c_j|\hat \theta)=\frac{1+\sum\nolimits_{i=1}^{|\chi|}\delta_{ij} }{M + |X|}$ （3.6）

这些计数比公式的推导直接来自于最大后验参数估计。求 $P(\theta|X,Y)$ 最大化的θ是通过首先用贝叶斯规则将这个表达式分成两个项来完成的： $P(\theta|X,Y) \propto P(X,Y|\theta)P(\theta)$ 。第一个术语是根据所有文档类型的乘积计算的（从等式 3.1）。第二项，参数上的先验分布，为 Dirichlets 分布的乘积。通过求解 $log(P(\theta|X,Y)$ 的偏导数系统，使用拉格朗日乘数来满足一个类中的词概率必须和为1的约束，从而使整个表达式最大化。这个最大化产生上面看到的计数比率。

根据标注的训练文档计算出的这些参数的估计值，可以将生成模型反转，并计算特定混合成分生成给定文档以执行分类的概率。这源于贝叶斯规则的应用：

$P(y_i=c_j|x_i;\hat\theta)=\frac{P(c_j|\hat\theta)P(x_i|c_j;\hat\theta)}{P(x_i|\hat\theta)} =\frac{P(c_j|\hat\theta)\prod_{w_t\in \chi}P(w_t|cj;\hat\theta)^{x_{it}}}{\sum\nolimits_{k=1}^M P(c_k|\hat\theta)\prod_{w_t\in \chi}P(w_t|c_k;\hat\theta)^{x_{it}}}$ (3.7)

如果任务是将一个测试文档分为单个类，然后是后验概率最高的类， $argmax_jP(y_i=c_j|x_i;\hat\theta)$ ，被选中。

3.2.2 基于 EM 的半监督文本分类

在带有标记和未标记数据的半监督设置中，我们仍然希望找到最大后验参数估计，如上面的监督设置中所示。因为没有标签的数据没有标签，所以前一节中的闭式公式不适用。然而，利用EM 技术，我们可以找到生成模型的局部最大后验参数估计。

将EM技术应用于带有朴素贝叶斯的标记和未标记数据的情况，可以得到一个简单而吸引人的算法。首先，一个朴素的贝叶斯分类器是以标准的监督方式从有限的标记训练数据中构建的。然后，我们用朴素贝叶斯模型对未标记的数据进行分类，注意到不是最可能的类，而是与每个类相关的概率。这意味着，根据这些估计的类概率，未标记的文档被视为几个部分文档。我们迭代这个过程，对未标记的数据进行分类，并重建朴素的贝叶斯模型，直到它收敛到一个稳定的分类器和数据的标签集。这在算法3.1中进行了总结：

算法 3.1 文本分类器半监督学习的基本EM算法

$\cdot$ 输入：标记文档集 $X_l$ 和未标记文档集 $X_u$

$\cdot$ 仅从标记文档集， $X_l$ ，构造一个初始化朴素贝叶斯分类器， $\hat\theta$ 。使用最大后验参数估计去找到 $\hat\theta = argmax_{\theta}P(X_l|\theta)P(\theta)$ （见等式 3.5 和 3.6）

$\cdot$ 通过 $l(\theta|X,Y)$ 的变化测量（标记和未标记数据的对数概率，以及先验），在分类器参数改善时循环（见等式 3.8）：

$\cdot$ （E 步）使用当前分类器， $\hat \theta$ ，估计每个未标记文档的组件成员身份，即，每个混合组分（和类）生成每个文档的概率， $P(c_j|x_i;\hat\theta)$ （见等式 3.7）

$\cdot$ （M 步）根据每个文档的估计组件成员关系，重新估计分类器， $\hat\theta$ 。使用最大后验（MAP）参数估计找到 $\hat\theta=argmax_{\theta}P(X,Y|\theta)P(\theta)$ （见等式 3.5 及 3.6）

$\cdot$ 输出：分类器， $\hat\theta$ ，其输入未标记的文档并预测类标签。

更正式地说，学习分类器的方法是计算 $\theta$ 的最大后验估计，即 $argmax_{\theta}P(\theta)P(X,Y|\theta)$ ，这相当于最大化相同函数的对数。考虑最大化的第二项，所有可观测数据的概率。单个未标记文档的概率是所有类的总概率之和，如等式 3.1 中所示。对于标记的数据，生成组件已经由标签 $y_i$ 给出，我们不需要引用与类对应的所有混合组件——只需要引用与类对应的。使用 $X_u$ 表示未标记的示例， $X_l$ 表示给出标签的示例，完整数据的预期对数概率为

$l(\theta|X,Y)=log(P(\theta)) + \sum_{x_i \in X_u} log\sum_{j\in [M]} P(c_j|\theta)P(x_i|c_j;\theta) + \sum_{x_i \in X_l} log(P(y_i=c_j|\theta)P(x_i|y_i=c_j;\theta))$ （3.8）

（为了方便我们删除了常数项）注意，这个方程包含了未标记数据的和的对数，这使得偏导数的最大化难以计算。EM 的形式化（Dempster 等人，1977）提供了一种迭代爬山方法，用于在参数空间中找到模型概率的局部最大值。算法的E步估计了给定模型参数最新迭代的缺失值（即未标记类信息）的期望值。M步骤使用先前计算的缺失值的期望值最大化模型参数的可能性，就好像它们是真实值一样。

实际上，E 步骤对应于使用等式3.7对每个未标记文档进行分类。M步对应于使用公式 3.5 、3.6与 $P(c_j|x_i;\hat\theta)$ 的当前估计值计算参数， $\hat\theta$ ，的新的最大后验（ $MAP$ ）估计。

本质上，所有参数的初始化都会导致一些局部极大值与 EM。许多 EM 的实例化都是从随机选择一个起始模型参数化开始的。在我们的例子中，由于我们不仅有未标记的数据，而且还有一些标记的数据，所以我们可以对起点进行更为选择性的选择。我们的迭代过程是用一个启动的 M 步骤初始化的，在这个步骤中，只使用标记的文档来估计分类器参数 $\hat\theta$ ，如等式3.5、3.6中所示。然后，循环从一个E步骤开始，该步骤使用这个分类器首次概率地标记未标记的文档。

该算法迭代，直到收敛到一个点，其中 $\hat\theta$ 不会随迭代改变。从算法上讲，我们通过观察参数的对数概率（公式3.8）低于阈值的变化来确定收敛性，该变化是 EM 爬坡的表面高度。

3.2.3 讨论

这种方法的理由取决于第3.2节中所述的假设，即数据由混合模型生成，并且混合物成分和类别之间存在一一对应关系。如果生成建模假设是正确的，那么最大化模型概率将是训练分类器的一个很好的标准。在这种情况下，当训练实例数接近无穷大时，贝叶斯最优分类器对应于模型的最大后验参数估计。当这些假设不能像真实文本数据中那样确定时，未标记数据的收益就不那么清楚了。仅使用标记数据，朴素贝叶斯分类器就可以很好地对文本文档进行分类（Lewis和Ringuette，1994；Craven等人，2000；Yang和Pedersen，1997；Joachims，1997；McCallum等人，1998）。这一观察部分解释为分类估计仅仅是函数估计的符号（二进制分类）的函数（Domingos和Pazzani，1997；Friedman，1997）。错误的单词独立性假设加剧了朴素贝叶斯产生极端（几乎为0或1）类概率估计的倾向。然而，即使这些估计是不适当的极端，分类精度也可能相当高。

半监督学习比监督学习更依赖于模型假设的正确性。下一节将从经验上说明，这种方法确实可以显著提高文档分类器的准确性，特别是在只有几个标记的文档的情况下。

图片3.1 20个新闻组数据集的分类准确度，包括10000个未标记文档和10000个未标记文档。使用少量的训练数据，使用 EM 可以生成更精确的分类器。随着训练数据的大量标记，无需使用未标记的数据就可以得到准确的参数估计，两种方法的分类精度开始收敛。

3.3 基于基础 EM 算法的实验结果

在本节中，我们证明了具有标记和未标记数据的半监督学习提供的文本分类器比仅使用标记数据的监督学习提供的文本分类器更准确。这是一个有趣的结果，因为多项式生成模型的混合是真实创作过程的巨大简化。然而，我们证明，对于某些领域，模型概率的优化准则与分类精度密切相关。

本节中的实验使用了著名的20个新闻组文本分类数据集（Mitchell，1997），它由大约20000篇均匀分布在20个新闻组中的 $Usenet$ 文章组成。任务是将文章分类到发布它的新闻组中。对于预处理，将删除停止词，并对每个文档的字数进行缩放，以使每个文档具有恒定的长度，并可能具有分数字数。由于数据具有时间戳，因此从每个新闻组的最后20%的文章中形成一个测试集。通过从剩余的样本中随机选择10000件样本，形成一个未标记的集合。标记的训练集是通过将剩余的文档划分为不重叠的集而形成的。我们根据集合的大小创建最多10个训练集，因为数据是可用的。当后验模型概率被报告并显示在图上时，一些加性和乘性常数被丢弃，但相对值保持不变。

图3.1显示了将 EM 与未标记数据一起使用对该数据集的影响。纵轴表示测试集上分类器的平均准确率，横轴表示对数刻度上标记的训练数据量。我们改变标记的训练数据的数量，并将传统的朴素贝叶斯（无未标记文档）的分类准确度与一个能够访问10000个未标记文档的em学习者进行比较。

图3.2 散点图显示了后验模型概率与用标记和未标记数据训练的模型精度之间的相关性。强相关性意味着模型概率是20个新闻组数据集的一个很好的优化标准。

EM 的表现明显优于传统的朴素贝叶斯。例如，有300个标记的文档（每类15个文档），朴素贝叶斯的精确度达到52%，而 EM 的精确度达到66%。这意味着分类误差减少了 30%。注意，即使只有很少的标记文档，EM 也有很好的表现；只有20个文档（每个类只有一个标记文档），朴素贝叶斯获得20%，EM 35%。正如所料，当有大量的标记数据，而朴素的贝叶斯学习曲线接近平稳时，拥有未标记的数据几乎没有帮助，因为已经有足够的标记数据来准确估计分类器参数。使用5500份标记文档（每类275份），分类精度从76%提高到78%。这些结果均具有统计学意义（P<0.05）。

EM 如何找到更准确的分类器？它是通过优化后验模型概率来实现的，而不是直接对分类精度进行优化。如果我们的生成模型是完美的，那么我们期望模型的概率和准确性是相关的，并且 EM 是有用的。但我们知道，我们的简单生成模型并不能捕获文本中包含的许多属性。我们的20个新闻组的结果表明，我们不需要一个完美的模型来帮助 EM 进行文本分类。如果模型的概率和准确性是相关的，生成模型就足以代表文本分类的目的，从而使 EM 能够间接地优化准确性。

为了更明确地说明这一点，让我们再次看看20个新闻组的实验，并根据经验测量这种相关性。图3.2显示了散点图中每个点的相关性，它们是图3.1中标记的和未标记的分割之一。此处标记的数据仅用于设置 $EM$ 初始化，在迭代期间不使用。我们将分类性能作为测试数据的准确度，并给出后验模型概率。

对于该数据集，分类精度和模型概率具有较好的对应性。准确度与模型概率的相关系数为0.9798，确实是一个很强的相关性，我们可以将其作为事后验证，证明该数据集可以通过生成模型方法使用未标记的数据。模型概率的优化准则是适用于此的，因为它与精度是一致的。

3.4 使用更具表现力的生成模型

第3.2节中生成模型的第二个假设指出，混合模型中的类和组件之间存在一对一的对应关系。在某些文本领域，很明显这样的假设是危险的。考虑文本过滤的任务，我们希望从很大的文档池或文档流中识别一个定义良好的小类文档。一个例子可能是一个系统，它监视网络管理员收到的电子邮件，以识别罕见的紧急情况，这种情况需要在休假时给她打电话。将非紧急邮件建模为仅具有一个多项式分布的负类将导致无表达力模型。否定类包含各种副标题的电子邮件：个人电子邮件、非紧急请求、垃圾邮件等。

更具表达力的模型是什么？与其用一个单一的混合成分来模拟大量的负面例子，不如用多个成分来建模。这样，在最大化之后，每一个负成分都可以捕获大量的例子。本节对文本数据采用了本例所建议的方法，并放宽了混合组件和类之间一对一对应的假设。我们将其替换为限制性较小的假设：混合组件和类之间的多对一对应。这使我们能够模拟类的副标题结构。

3.4.1 每类多个混合成分

新的生成模型必须考虑混合成分和类之间的多对一对应关系。和旧模型一样，我们首先选择一个带有偏压模具辊的类。每个类都有几个副标题；接下来我们将选择其中一个副标题，同样使用有偏差的骰子。既然确定了副标题，就生成了文档中的单词。我们首先选择一个长度（独立于副标题和类），然后从副标题的多项式分布中提取单词。

与以前不同的是，现在每个未标记的文档都缺少两个值——类和副标题。即使对于标记的数据，也缺少值；尽管类是已知的，但其副标题不是。由于我们无法访问这些丢失的类和副标题标签，因此必须使用诸如 $EM$ 之类的技术来估计局部最大后验（MAP）生成参数。如第3.2.2节所述，EM 被例示为迭代算法，该算法在估计缺失类和副标题标签的值和使用估计标签计算最大后验（MAP）参数之间交替进行。当 EM 收敛到高概率参数估计后，生成模型可以通过使用贝叶斯规则来进行文本分类。

新的生成模型指定了混合组件和类之间的分离。现在， $c_j\in [N]$ 只表示第j个混合物成分（副标题），而不是用 $c_j$ 来表示这两个成分。我们为将第 $a$ 类写成 $t_a \in [M]$ ，当组件 $c_j$ 属于 $t_a$ 类时， $q_{aj}=1$ ，否则为0。这表示混合组件和类之间预定的、确定性的、多对一的映射。我们分别用 $y_i$ 和 $z_i$ 表示文档的类标签和副标题标签。因此，如果文献 $x_i$ 是由混合成分 $c_j$ 生成的，我们说 $z_i=c_j$ ，如果文档属于 $t_a$ 类，那么我们称 $y_i=t_a$ 。

如果我们的数据集知道所有的类和副标题标签，那么为生成参数找到最大后验（MAP）估计将是类似于第3.2.1节中的朴素贝叶斯的闭式方程的一个简单应用。单词概率参数的公式与朴素贝叶斯的公式3.5相同。

$\hat \theta_{w_t|c_j}\equiv P(w_t|c_j;\hat\theta) = \frac{1+\sum\nolimits_{x_i\in \chi}\delta_{ij}x_{it}}{|\chi|+\sum\nolimits_{s=1}^{|\chi|}\sum\nolimits_{x_i\in \chi}\delta_{ij}x_{is} }$ （3.9）

类概率类似于等式3.6，但使用类的新符号而不是组件：

$\hat\theta_{t_a}\equiv P(t_a|\hat\theta) = \frac{1 + \sum\nolimits_{i=1}^{|\chi|}\delta_{ia} }{M +|\chi|}$ （3.10）

副标题的概率是相似的，除非它们是根据组件类中的其他文档进行估计的：

$\hat\theta_{c_j|t_a}\equiv P(c_j|t_a;\hat\theta) = \frac{1+\sum\nolimits_{i=1}^{|\chi|} \delta_{ij}\delta_{ia}}{\sum\nolimits_{j=1}^{N}q_{aj}+\sum\nolimits_{i=1}^{|\chi|}\delta_{ia}}$ （3.11）

在分类时，我们必须估计未标记文档的类成员概率。这是通过首先计算副标题的成员资格，然后求和副标题以获得总体类概率来完成的。副标题成员的计算类似于幼稚贝叶斯的混合成分成员，只需对两个先验（类和副主题）而不是一个先验进行小调整即可。

$P(z_i=c_j|x_i;\theta)=\frac{\sum\nolimits_{a\in [M]}q_{aj}P(t_a|\hat\theta)P(c_j|t_a;\hat\theta)\prod_{w_t\in \chi}P(w_t|c_j;\hat\theta)^{x_it}}{\sum\nolimits_{r\in [N]}\sum\nolimits_{b\in [M]}q_{br}P(t_b|\hat\theta)P(c_r|t_b;\hat\theta)\prod_{w_t\in \chi}P(w_t|c_r;\hat\theta)^{x_{it}}}$ （3.12）

整个类的成员关系是用类所有副标题的概率和计算的：

$P(y_i=t_a|x_i;\hat\theta)=\sum\nolimits_{j\in [N]}q_{aj}P(z_i=c_j|x_i;\hat\theta)$ （3.13）

只有当所有培训文件都有课堂和副标题标签时，这些监督学习方程才适用。没有这些，我们使用EM。M 步，和基本em一样，为多项式和先验建立最大的后验参数估计。这是用等式3.9、3.10和3.11完成的。使用前一个E步骤中估计的概率类和次主题成员身份。在E步骤中，对于未标记的文档，我们计算概率加权的副标题和类成员身份（等式 3.12和3.13）。对于带标签的文档，我们必须估计副标题成员身份。但是我们从它给出的类标签中知道，许多子主题成员必须是零——那些属于其他类的子主题。因此，我们计算未标记数据的子主题成员身份，但将适当的成员身份设置为零，并仅在属于其类的主题上规范化非零的成员身份。

如果我们得到一组类标记的数据和一组未标记的数据，我们现在可以应用 EM，如果每个类都有一些指定的副标题数。但是，这些信息通常不可用。因此，我们必须借助一些技术来选择模型。常用的模型选择方法有交叉验证法、阿卡克信息准则（AIC）、贝叶斯信息准则（BIC）等。由于我们确实有有限数量的标记文档可用，因此我们使用交叉验证来选择分类性能的副标题数量。

表 3.1 使用传统朴素贝叶斯（NB1）的Reuters二元分类器的分类精度，使用标记和未标记数据的基本 EM（EM1），使用刚标记数据的多个混合成分（NB*），以及使用标记和未标记数据的多个混合成分EM （EM*）。对于NB*和EM*，每个试验的组分数量是最佳选择的，括号中显示了负类试验的组分中间数。请注意，对于路透社来说，多成分模型更自然，因为它的否定类包含许多主题。每个类同时使用未标记的数据和多个混合组件可以提高性能，而不是单独使用或使用朴素的贝叶斯。

表 3.1

3.4.2 实验结果

这里，我们提供了经验证据，证明在生成建模方法中使用未标记的数据，有时需要更具表现力的生成模型。与原始生成模型相比，分类精度与模型概率呈负相关，在使用未标记数据时分类精度较低。使用更具表达力的生成模型，可以获得中等的正相关，从而提高分类精度。

路透社21578发行版1.0的数据集包括大约13000篇来自路透社通讯社的新闻文章，这些文章被标记为90个主题类别。此数据集中的文档具有多个类标签，并且传统上使用二进制分类器评估每个类别。在其他几项研究（Joachims，1998；Liere和Tadepalli，1997）之后，我们为十个人口最多的类中的每一个构建了二进制分类器，以确定主题。我们使用了一个非索引字表，但不停止。每项 Reuters 试验的词汇大小都是通过优化准确度来选择的，这是通过在标记的训练集上留出一个交叉验证来测量的。使用标准的Modapte列车/测试分割，这是时间敏感的。可供培训的9603份文件中有七千份未贴标签。从其余部分中，我们随机选择最多10个不重叠的训练集，其中只有10个正标记文档和40个负标记文档。

表3.1中结果的前两列重复了第3.3节中关于路透社数据集的基本em的实验。在这里我们看到，对于大多数类别，分类精度随着引入未标记的数据而降低。考虑到标记和未标记数据的证据，对于每个路透社类别，em都发现了一个更为可能的模型。但是，这个更可能的模型常常对应一个低精度的分类器，而不是我们所希望的。

图3.3 显示了Reuters ACQ 任务的模型概率和分类精度之间的关系的散点图。在左边，只有一个负类的混合成分，概率和准确度成反比，这正是我们不想要的。在右侧，10个混合成分为负，模型概率与分类精度之间存在中等正相关

图3.3中的第一个图提供了对未标记数据为什么会受到损伤的理解。每类有一个混合成分，分类精度和模型概率之间的相关性非常强（r=-0.9906），但方向不对！概率较高的模型分类精度明显较低。通过对EM发现的解决方案的分析，我们发现最可能的数据聚类有一个部分包含了大多数负面文档，第二个部分包含了大部分正面文档，但负面文档明显更多。因此，类与高概率模型不分离。

此数据集中的文档通常具有多个类标签。在基本的生成模型中，负类覆盖了多达89个不同的类别。因此，期望用单一的混合成分捕获如此广泛的文本基础是不合理的。为此，我们放松了生成模型，用一个混合成分对正类进行建模，用一个到四十个混合成分对负类进行建模，无论是否有未标记的数据。

表3.1的后半部分显示了使用每类多个混合物生成模型的结果。注意两个不同的结果。首先，对于单独标记的数据（nb*），分类精度比每个类的单个组件（nb1）高。第二，对于未标记的数据，新的生成模型结果（em*）通常优于其他结果。在路透社的所有试验中，未标记数据的增加具有统计学意义（p<0.05）。

表3.2 当通过交叉验证（EM*CV）选择组分数量时，与最佳选择（EM*）和简单朴素贝叶斯（NB1）相比，使用多个混合物组分的性能。注意交叉验证通常选择的组件太少。

表 3.2

对于十个混合组分，精度和模型概率之间的相关性是非常不同的。右图3.3显示了使用十个混合组分对负类进行建模时，精度与模型概率之间的相关性。在这里，模型概率与正确方向的分类精度之间存在中等相关性（r=0.5474）。对于这些解决方案，一个组件几乎涵盖了所有的正面文档和一些（但不是很多）负面文档。其他十个部分通过剩余的负面文档分发。由于分类精度和模型概率是相关的，因此该模型更能代表我们的分类任务的数据。这使得通过生成模型方法可以有效地使用未标记的数据。

一个显而易见的问题是，如何在不访问测试集标签的情况下自动选择最佳数量的混合组分。我们使用“留一法交叉验证”。与朴素贝叶斯（NB1）和最佳EM （EM*）相比，该技术（EM*CV）的结果如表3.2所示。请注意，交叉验证并不能完美地选择测试集上性能最佳的组件数量。结果一致地表明，通过交叉验证选择的组件数量比最佳组件数量少。

3.4.3 讨论

模型的复杂性与数据的稀疏性之间存在着模型选择过程中的张力，只要有大量的副标题和文档，就可以很好地对训练数据进行建模，每个副标题包含一个训练文档。由于仍然存在大量的副标题，我们可以对现有数据进行精确的建模，但泛化性能较差。这是因为每一个多项式将有它的许多参数估计从少数文件，并将遭受稀疏的数据。副标题很少，就会出现相反的问题。我们将非常准确地估计多项式，但模型将受到过度限制，不能代表真实的文档分布。交叉验证应该有助于在这些紧张关系之间选择一个很好的折衷方案，特别是在分类性能方面。

注意，我们对每个类使用多个混合组件允许我们捕获类级别上单词之间的一些依赖关系。例如，考虑一个体育课，它包含关于曲棍球和棒球的文档。在这些文档中，单词 ice 和 puck 可能同时出现，单词 bat 和 base 可能同时出现。然而，在体育课上，这些依赖性不能通过对单词的一个多项式分布来捕获。每个班级有多个混合成分，一个多项式可以覆盖曲棍球副标题，另一个则覆盖棒球副标题。在曲棍球的副标题中，“冰和冰球”这个词的概率比全部类别的概率要高得多。这使得它们在曲棍球文件中的共存比在单一多项式假设下更为可能。

3.5 克服局部最大值的挑战

在参数空间的似然性与分类精度密切相关的情况下，我们的优化得到了很好的分类器。然而，当地的格言明显阻碍了我们的进步。例如，我们在第3.3节中仅用几个带标签的示例发现的局部最大值比标记数据充足时提供的分类精度低40多个百分点。因此，考虑其他有助于弥合这一差距的方法是很重要的，尤其是在标记数据稀疏的情况下。

通常情况下，为了加快收敛速度，创建了EM的变体或替代品（McLachlan和Krishnan，1997）。然而，在文本分类领域，我们已经看到收敛速度非常快。因此，我们可以很容易地考虑以较慢收敛为代价来改进局部极大值情况的EM替代方案。确定性退火正是这种权衡。

3.5.1 确定性退火

确定性退火背后的直觉是，它开始于一个非常光滑的凸曲面上的最大化，而这个曲面只与我们真正感兴趣的概率曲面有着极远的联系。最初我们可以找到这个简单曲面的全局最大值。慢慢地，我们改变表面，使之变得更粗糙，更接近真实的概率表面。如果我们在曲面变得更复杂时遵循原始最大值，那么当给定原始曲面时，我们仍然有一个很可能的最大值。通过这种方式，它避免了许多当地的格言，否则他们会被抓住。

我们在前几节中应用 EM 可以认为是一个优化问题，其中损失函数是似然函数的否定（等式3.8）。EM 的迭代是参数空间中的爬山算法，局部地将损失最小化。

考虑一组密切相关的损失函数： $l(\theta|X,Y)=\sum_{x_i\in X_u}log\sum_{c_j\in [M]}[P(c_j|\theta)P(x_i|c_j;\theta)]^{\beta}$ $+ \sum_{x_i\in X_l}log([P(y_i=c_j|\theta)P(x_i|y_i=c_j;\theta)]^{\beta})$ （3.14）

其中β在0和1之间变化。当β=1时，我们熟悉前面章节的概率曲面，与分类精度有很好的相关性，但具有许多有害的局部最大值。当β接近于零时，参数空间中损失函数的表面值变成凸的，只有一个全局最大值。但在这种极端情况下，所提供的数据对损失函数没有影响，与分类精度的相关性较差。零和一之间的值表示参数空间平滑度与数据提供的良好相关概率曲面相似性之间权衡的不同点。

这种见解是驱动所谓确定性退火方法的原因之一。（Rose等人，1992年），首次用作在无监督集群期间构建层次结构的方法。它还用于从未标记的数据（Ueda和Nakano，1995）估计高斯混合体的参数，并从未标记的数据构建文本层次（Hofmann和Puzicha，1998）。

对于β的固定值，我们可以通过迭代以下步骤找到给定损失函数的局部最大值：

$\cdot$ E 步：计算类分派的预期值， $\hat z_{ij}^{(k+1)}=E[y_i=c_j|x_i;\hat\theta ^k]=\frac{[P(c_j|\hat\theta ^k)P(x_i|c_j;\hat\theta ^k)]^{\beta}}{\sum_{c_r \in [M]}[P(c_r|\hat\theta ^k)P(x_i|c_r;\hat\theta ^k)]^{\beta}}$ （3.15）

$\cdot$ M 步：使用预期的类分派找到最可能的模型，

$\hat\theta^{k+1}=argmax_{\theta}P(\theta|X;Y;\hat z^{k+1})$ （3.16）

M 步与3.2.2 节的是一样的，而E步骤包括通过 $\beta$ 的损失约束。

在形式上，β是一个拉格朗日乘子，当根据最大熵（或先验分布的最小相对熵）的优化准则求解似然空间中的固定损失时。一个 $\beta$ 接近于零对应于为一个允许损失非常大的模型找到最大熵参数化。

考虑不同目标损失对模型可能性（等式3.14）的影响。当目标损失非常大时， $\beta$ 将非常接近于零；每个模型的概率将非常接近于其先验概率，因为数据的影响可以忽略不计。在 $\beta$ 变为零的极限条件下，概率曲面将是凸的，具有一个全局最大值。对于较小的损失目标， $\beta$ 将很小，但不能忽略。在这里，数据的概率会有更大的影响，不再有单一的全局最大值，而是几个。当β=1时，我们有前面章节中我们熟悉的概率曲面，有许多局部极大值。

这些观察结果表明了寻找低损耗模型的退火过程。如果我们将 $\beta$ 初始化为非常小的，我们可以很容易地找到具有 EM 的全局最大后验解，因为曲面是凸的。当我们提高β值时，概率曲面会变得更加粗糙和复杂，因为数据的可能性会对模型的概率产生更大的影响。虽然更复杂，但如果我们稍微降低温度（ $1/\beta$ ），新的最大值将非常接近旧的最大值。因此，当用em搜索最大值时，我们可以用旧的最大值对其进行初始化，并为新的概率曲面收敛到一个好的最大值。这样，我们可以逐步提高 $\beta$ ，同时跟踪一个很可能的解。最终，当 $\beta$ 变为1时，我们将有一个很好的生成模型假设的局部最大值。因此，我们将从标记和未标记的数据中找到一个高概率的局部最大值，然后我们可以使用它进行分类。

请注意，确定性退火的计算成本明显高于 EM。虽然每次迭代都采用相同的计算，但由于温度降低非常缓慢，确定性退火的迭代次数更多。例如，在我们的实验中，我们对确定性退火进行了390次迭代，对 $EM$ 只进行了7次迭代。当能够提供额外的计算时，这样做的好处可能是分类器更加精确。

3.5.2 实验结果

在这一节中，我们从经验上看到，当标记的训练数据稀疏时，确定性退火比EM找到更可能的参数和更准确的分类器。

对于实验结果，我们使用 News5 数据集，它是20个新闻组的一个子集，其中包含五个容易混淆的comp.*类。我们为所有的实验确定了一个单一的词汇表，作为在整个标记数据集上通过相互信息测量的前4000个单词。为了运行这个确定性退火算法，我们初始化 $\beta$ 为 0.02，我通过乘以一个因子 1.01 增加 $\beta$ 的值直到 $\beta = 1$ 。我们几乎没有努力调整这些参数。因为每次我们增加 $\beta$ 的概率表面变化很小，我们在每个温度设置下只运行一次 EM 迭代。每类600份随机文件（共3000份）视为未贴标签。每个类固定数量的标记示例也随机选择。其余文档用作测试集。

图 3.4 与 EM 相比，确定性退火的性能。如果完全完成了类到组件的分配，那么确定性退火将比标记数据稀疏时的 EM 更精确。虽然默认的对应关系很差，但是可以用少量的领域知识来纠正。

图3.4比较了确定性退火与常规EM的分类精度。最初的结果表明，当标记数据丰富时，这两种方法的性能基本相同，但当标记数据为稀疏。例如，每个类有两个标记的例子（总共十个），EM 给出58%的准确度，而确定性退火只给出51%。对混淆矩阵的深入研究表明，当标记数据稀疏时，与确定性退火的类对组件不正确对应存在显著的不利影响。这是因为，当温度非常高时，全局最大值将使每个多项式混合分量非常接近其先验值，并且标记数据的影响最小。由于先验是相同的，所以每个混合成分基本上是相同的。随着温度的降低，混合成分变得更加明显，当没有足够的标记数据将簇拉向正确的类时，一个组件可以轻松地跟踪与错误类关联的聚类。

为了解决这个问题，我们在完成确定性退火之后，根据每个标记示例的分类，将类更改为集群对应关系。图3.4显示了通过经验选择的对应关系获得的精度，以及通过完全对应关系获得的最佳精度。我们发现，通过经验设置对应关系，确定性退火只会略微提高精度，在得到51%之前，通过改变对应关系，我们将其提高到55%，在58%时仍不优于 EM。然而，如果我们能够执行完美的类对应，确定性退火的精度将是67%，远远高于 EM。

图3.5 比较EM和确定性退火模型概率和精度的散点图。结果表明，确定性退火是成功的，因为它找到了概率显著较高的模型。

为了验证确定性退火的更高精度来自于寻找更可能的模型，图3.5显示了确定性退火（具有最优类分配）和 EM 的模型概率与精度的散点图。两个值得注意的结果非常突出。第一个问题是，确实确定性退火发现了更可能的模型，即使有少量的标记数据。这说明了确定性退火的额外准确性。第二个值得注意的是，通过确定性退火发现的模型仍然沿着相同的概率精度相关线。这进一步证明了模型的概率和准确性与此数据集有很强的相关性，并且相关性不仅仅是电磁干扰的产物。

3.5.3 讨论

实验结果表明，如果解决了类与组件之间的对应关系，确定性退火确实可以帮助分类。确定性退火成功地避免了陷入局部极大值的不足，而是找到了更可能的模型。由于这些高概率模型与高精度分类器相关，因此确定性退火可以很好地利用未标记的数据进行文本分类。

当只有有限的标记数据时，类对应问题最为严重。这是因为在标签较少的例子中，小的干扰更可能导致通信误入歧途。然而，只要有一点人类的知识，班级通信问题通常可以解决琐碎。在除最大和最令人困惑的分类任务外的所有分类任务中，根据最具指示性的单词（如加权对数似然比）等度量标准来衡量），可以很容易地识别一个类。例如，表3.3 中显示了按此度量设置的每类数据的前十个词。仅从这十个词来看，任何一个拥有一点点领域知识的人都可以很好地为组件分配类。因此，在确定性退火完成之后，需要少量的人力来纠正类对应关系并不是不合理的。这项工作可以定位在主动学习框架内。因此，当标记的训练数据最稀疏，并且培训师可以适当投资将类标签映射到集群组件时，确定性退火将成功地找到比传统 EM 更可能和更准确的模型。

即使这个有限的领域知识或人力资源不可用，也应该可以自动估计类的对应关系。可以对数据执行 EM 和确定性退火。