3.5 朴素贝叶斯分类器
评论
在本节中，我们将讨论如何对离散值特征的向量进行分类， \(\boldsymbol{x} \in {1,\dots,K}^D\) ，其中 \(K\) 是每个特征的值域数， \(D\) 是特征的数量。我们将使用生成方法。这要求我们指定类条件分布 \(p(\boldsymbol{x} | y=c)\) 。最简单的方法是假设特征是条件独立的, 对给定类标签。这使我们可以将类条件密度写成一维密度的乘积:
\[ p(\boldsymbol{x} | y=c, \boldsymbol{\theta}) = \prod_{j=1}^D {p(\boldsymbol{x}_j | y=c, \theta_{jc}) } \tag{3.54} \]此模型被称为 朴素贝叶斯分类器 （NBC）。
该模型被称为“朴素”，因为我们不希望这些特征是独立的，即使是以类标签为条件。然而，即使朴素贝叶斯假设不正确，它也常常导致分类法运作良好（Domingos and Pazzani 1997）。其中一个原因是该模型非常简单（它只有 O（CD） 参数，对于 C个类 和 D个特征），因此它相对不受过拟合的影响。
类条件密度的形式依赖于每个特征的类型。我们给出一些可能性：
- 实值特征的情况下，我们可以使用高斯分布： \(p(\boldsymbol{x} | y=c, \boldsymbol{\theta}) = \prod_{j=1}^D {\mathcal{N}(x_j | \mu_{jc}, \sigma_{jc}^2)}\) ，其中 \(\mu_{jc}\) 是c类对象的特征 \(j\) 的均值，而 \(\sigma_{jc}^2\) 是对应的方差。
- 二值特征的情况下， \(x_j \in \{0,1\}\) ，我们可以使用贝努利分布 ： \(p(\boldsymbol{x} | y=c, \boldsymbol{\theta}) = \prod_{j=1}^D {{\rm Ber}(x_j | \mu_{jc})}\) ，其中 \(\mu_{jc}\) 是c类对象的特征 \(j\) 发生的概率。有时称之为 多变量伯努利朴素贝叶斯模型。我们将在下面看到它的一个应用。
- 在多值分类特征的情况下， \(x_j \in \{1,\dots,K\}\) ，我们可以使用多项分布建模： \(p(\boldsymbol{x} | y=c, \boldsymbol{\theta}) = \prod_{j=1}^D {{\rm Cat}(x_j | \boldsymbol{\mu}_{jc})}\) ，其中 \(\boldsymbol{\mu}_{jc}\) 是c类中 \(x_j\) 的 \(K\) 个可能值的直方图。
显然，我们可以处理其他类型的特征，或使用不同的分布假设。此外，它很容易混合和匹配不同类型的特征。
3.5.1 模型拟合
我们现在讨论如何“训练”一个朴素的贝叶斯分类器。这通常意味着计算带参数的MLE或MAP估计。但是，我们还将讨论如何计算完整的后验: \(p(\boldsymbol{\theta} | \mathcal{D})\) 。
3.5.1.1 NBC的MLE
单个数据情况的概率表示如下(译者注: 这里进行了参数的重新编排) :
\[ p(\boldsymbol{x}_i, y_j | \boldsymbol{\theta})=p(y_i | \boldsymbol{\pi}) \prod_j {p(x_{ij} | \boldsymbol{\theta}_j)}=\prod_c {\pi_c^{\mathbb{I}(y_i=c)}} \prod_j {\prod_c {p(x_{ij} | \boldsymbol{\theta}_{jc})^{\mathbb{I}(y_i=c)}}} \tag{3.55} \]因此，对数似然由下式给出:
\[ {\rm log} \ p(\mathcal{D} | \boldsymbol{\theta})= \sum_{c=1}^C {N_c {\rm log} \ \pi_c} + \sum_{j=1}^D {\sum_{c=1}^C { \sum_{i:y_i=c} {{\rm log} \ p(x_{ij} | \boldsymbol{\theta}_{jc})}}} \tag{3.56} \]我们看到，这个表达式分解成一系列的项，第一项是关于参数 \(\boldsymbol{\pi}\) 的，而DC项是关于参数 \(\boldsymbol{\theta}_{jc}\) 的。因此，我们可以分别优化所有这些参数。
依据公式3.48，关于类先验的MLE可表示如下:
\[ \hat{\pi}_c = \dfrac{N_c}{N} \tag{3.57} \]其中 \(N_c \overset{\Delta}{=} \sum_i {\mathbb{I}(y_i=c)}\) 是c类的样本数。
对这个拟然的的MLE依赖于我们为每个特征选择分布类型。为简单起见，我们假设所有特征是二项的，于是 \(\boldsymbol{x}_j | y=c \propto {\rm Ber}(\theta_{jc})\) 。在这种情况下，MLE变为:
\[ \hat{\theta}_{jc} = \dfrac{N_{jc}}{N} \tag{3.58} \]可以非常简单地实现该模型拟合程序：见算法8提供的伪代码（及 Matlab代码_naiveBayesFit_ ）。该算法显然需要 \(O(N D)\) 时间。该方法易于推广以处理混合类型的特征。这种简单性是该方法有如此广泛使用的一个原因。
图3.8给出了一个2个类和600个二项特征的示例，用于表示在词袋模型中是否存在单词。绘制了关于2个类的 \(\boldsymbol{\theta}_c\) 向量的可视化。索引107处的大峰值对应于单词“subject”，它t同时以概率为1出现在两个类别中。（在第3.5.4节中，我们讨论如何“过滤”这样的无信息特征。）
图3.8 类条件密度 \(p(\boldsymbol{x}_j=1 | y=c)\) 的两个文档类，对应于“X视窗”和“MS视窗”。由_naiveBayesBowDemo_生成的图。
3.5.1.2 朴素贝叶斯的贝叶斯算法(Bayesian naive Bayes)
最大拟然的麻烦是它可能过拟合。例如，考虑在图3.8的例子：“subject"这个单词对应的特征(记作特征 \(j\) )总是同时出现在两个类，所以, 我们的估计总是 \(\hat{\theta}_{jc}=1\) 。如果我们遇到一封没有这个词的新电子邮件，会发生什么？我们的算法会出错，因为我们发现对两个类都有 \(p(y=c | \boldsymbol{x}, \hat{\boldsymbol{\theta}})=0\) ！这是第3.3.4.1节讨论的黑天鹅悖论的另一种表现形式。
过拟合的简单解决方案是贝叶斯算法(Bayesian)。为简单起见，我们使用一个先验因式分解 (译者注: 重新编排了参数):
\[ p(\boldsymbol{\theta})=p(\boldsymbol{\pi}) \prod_{j=1}^D {\prod_{c=1}^C{p(\theta_{jc})}} \tag{3.59} \]对 \(\boldsymbol{\pi}\) 我们使用 \({\rm Bir}(\boldsymbol{\alpha})\) 先验, 对每个 \(\theta_{jc}\) 使用 \({\rm Beta}(\beta_0,\beta_1)\) 先验。如果我们只取 \(\boldsymbol{\alpha}=1\) 和 \(\boldsymbol{\beta}=1\) ，对应于加1或拉普拉斯平滑。
结合公式3.56中的拟然因式分解和上面先验的因式分解, 可以得到下面的后验因式分解：
\[ \begin{aligned} p(\boldsymbol{\theta} | \mathcal{D}) =& p(\boldsymbol{\pi} | \mathcal{D}) \prod_{j=1}^D {\prod_{c=1}^C{p(\theta_{jc} | \mathcal{D})}} \\ p(\boldsymbol{\pi} | \mathcal{D}) =& {\rm Dir}(N_1+\alpha_1,\dots,N_C+\alpha_C) \\ p(\theta_{jc} | \mathcal{D}) =& {\rm Beta}((N_c - N_{jc})+\beta_0,N_{jc}+\beta_1) \end{aligned} \tag{3.60-62} \]换句话说，为了计算后验，我们只是把似然的经验计数加上先验计数即可。通过修改算法8来处理此版本的模型“拟合”是很简单的。
2.5.2 使用这个模型来预测
测试时，目标是计算:
\[ p(y=c | \boldsymbol{x}, \mathcal{D}) \propto p(y=c | \mathcal{D}) \prod_{j=1}^D {p(x_j | y=c,\mathcal{D})} \tag{3.63} \]正确的贝叶斯程序是要对未知参数积分(译者注: 原文公式有误, 此处我做了修正):
\[ \begin{aligned} p(y=c | \boldsymbol{x}, \mathcal{D}) \propto & \left[ \int {{\rm Cat}(y=c | \boldsymbol{\pi}) p(\boldsymbol{\pi} | \mathcal{D})} d \boldsymbol{\pi} \right] \\ \quad & \prod_{j=1}^D { \left[ \int {{\rm Ber}(x_j | y=c, \theta_{jc}) p(\theta_{jc} | \mathcal{D})}d \theta_{jc} \right]} \end{aligned} \tag{3.64-65} \]幸运的是，这是很容易做到，至少如果后验是狄利克雷分布。特别是，根据公式3.51，我们知道可以通过简单地插入后验平均参数 \(\bar{\boldsymbol{\theta}}\) 来获得后验预测密度 θ。因此
\[ \begin{aligned} p(y=c | \boldsymbol{x}, \mathcal{D}) & \propto \bar{\pi} _c \prod_{j=1}^D {\left(\bar{{\theta}}_{jc}\right)^{\mathbb{I}(x_j=1)} \left(1-\bar{{\theta}}_{jc}\right)^{\mathbb{I}(x_j=0)}} \\ \bar{{\theta}}_{jc} & = \dfrac{N_{jc}+\beta_1}{N_c+\beta_0+\beta_1} \\ \bar{{\pi}}_c & = \dfrac{N_c+\alpha_c}{N+\alpha_0} \end{aligned} \tag{3.66-68} \]其中 ， \(\alpha_0=\sum_c{\alpha_c}\) 。
如果我们有一个单点的后验近似， \(p(\boldsymbol{\theta} | \mathcal{D}) \approx \delta_{\hat{\boldsymbol{\theta}}}(\boldsymbol{\theta})\) ，其中 \(\hat{\boldsymbol{\theta}}\) 可以是MLE或MAP估计，那么 后验预测密度可通过简单地插入参数而获得，进而获得一个几乎一样的规则:
\[ p(y=c | \boldsymbol{x}, \mathcal{D}) \propto \hat{\pi} _c \prod_{j=1}^D {\left(\hat{{\theta}}_{jc}\right)^{\mathbb{I}(x_j=1)} \left(1-\hat{{\theta}}_{jc}\right)^{\mathbb{I}(x_j=0)}} \tag{3.69} \]唯一的区别是, 我们用后验众数或MLE \(\hat{\boldsymbol{\theta}}\) 来取代后验均值 \(\bar{\boldsymbol{\theta}}\) 。然而，这种微小差异在实践中很重要，因为后验均值将导致较少的过拟合（参见第3.4.4.1节）。
3.5.3 log-sum-exp技巧
无论使用任何类型的生成式分类器, 我们要讨论一个重要的实际细节 。尽管我们能够按公式2.13计算后验类标签， 并且使用适当的类条件密度（和近似插入）。但遗憾的是，由于数值下溢，公式2.13的简单实现可能会失败。问题出在 \(p(\boldsymbol{x} | y=c)\) 通常是一个非常小的数字，特别是如果 \(\boldsymbol{x}\) 是一个高维向量。这是因为我们要求 \(\sum_{\boldsymbol{x}}{p(\boldsymbol{x} | y)}=1\) ，因此观察任何特定高维向量的概率很小。一个明显的解决方案是在应用贝叶斯规则时进行log，如下所示：
\[ \begin{aligned} {\rm log} \ p(y=c | \boldsymbol{x}) = & b_c - {\rm log} \left[\sum_{c^{'}=1}^C {e^{b_{c^{'}}}} \right] \\ b_c \overset{\Delta}{=} & {\rm log} \ p(\boldsymbol{x}|y=c) + {\rm log} \ p(y=c) \end{aligned} \tag{3.70-71} \]然而，这需要计算以下这个表达式:
\[ {\rm log} \left[\sum_{c^{'}} {e^{b_{c^{'}}}} \right] = {\rm log} \sum_{c^{'}} {p(y=c^{'} | \boldsymbol{x})}={\rm log} \ p(\boldsymbol{x}) \tag{3.72} \]我们不能在 \({\rm log}\) 域中加减。幸运的是，我们可以将最大公因项分解出来，比如，
\[ {\rm log} (e^{-120}+e^{-121})={\rm log} (e^{-120}(1+e^{-1}))={\rm log} (1+e^{-1}) - 120 \tag{3.73} \]在一般情况下，我们有:
\[ {\rm log} \sum_c{e^{b_c}}={\rm log} \left[(\sum_c{e^{(b_c-B)}})e^B \right]= \left[{\rm log} (\sum_c{e^{(b_c-B)}}) \right] + B \tag{3.74} \]其中 \(B= \underset{c}{\rm max} \ b_c\) 。这被称为 log-sum-exp 技巧，并被广泛使用。（有关请参阅函数_logsumexp_的实现。）
此技巧在算法1中，使用NBC来计算 \(p(y_i | \boldsymbol{x}_i,\hat{\boldsymbol{\theta}})\) 。参阅Matlab代码 naiveBayesPredict。注意，如果我们只希望计算 \(\hat{y}_i\) , 那么我们不需要log-sum-exp技巧，因为我们只要最大化非标准量 \({\rm log} \ p(y_i=c) + {\rm log} \ p(\boldsymbol{x}_i | y_i=c)\) 。
3.5.4 用互信息进行特征选择
由于NBC是拟合潜在很多特征的联合分布，因此可能会受过拟合的影响。此外，运行时开销是 \(O(D)\) ，对于某些应用来说可能太高。
解决这两个问题的一种常见方法是进行特征选择，以消除对分类问题没有多大帮助的“无关”特征。最简单的特征选择方法是分别评估每个特征的相关性，然后取最高 \(K\) ，其中 \(K\) 的选择是基于准确性和复杂性之间的一些权衡。这种方法称为变量排序， 过滤或筛选。
衡量相关性的一种方法是使用在特征 \(X_j\) 和标签 \(Y\) 之间的互信息（第2.8.3节）:
\[ I(X,Y)=\sum_{x_j} {\sum_y{p(x_j,y) \log\dfrac{p(x_j,y)}{p(x_j)p(y)}}} \tag{3.75} \]互信息可以被认为是: 一旦我们观察到特征 \(j\) 的值，那么标签分布上的熵就减少。如果特征是二项的，那这点很容易证明（练习3.21），这个MI可被如下计算:
\[ I_j=\sum_c{\left[\theta_{jc}\pi_c \log\dfrac{\theta_{jc}}{\theta_j} +(1-\theta_{jc}) \pi_c \log \dfrac{1-\theta_{jc}}{1-\theta_j} \right]} \tag{3.76} \]其中 \(\pi_c=p(y=c),\theta_{jc}=p(x_j=1|y=c), \theta_j=p(x_j=1)=\sum_c{\pi_c \theta_{jc}}\) 。（所有这些能被计算的量都是朴素贝叶斯分类器的副产品。）
图3.1说明了如果我们将其应用于图3.8中使用的二项词袋数据集中会发生什么。我们看到具有最高互信息的词比最有可能的词更具有辨别力。例如，两个类中最可能的单词是“subject”，它总是出现，因为这是新闻组的数据，它总是有一个主题(subject)行。但显然这不是很有辨别力的。带有类别标签的MI最高的单词是（按降序排列）“windows”，“microsoft”，“DOS”和“motif”，这是有道理的，因为这些类对应于Microsoft Windows和X Windows。
3.5.5 使用词袋的文档分类器
文档分类器 是将文本文档分类为不同类别的问题。一种简单的方法是将每个文档表示为二项的向量，其记录每个单词是否存在与否, 于是 \(x_{ij}=1 \quad {\rm iff} \quad\) 单词 \(j\) 出现在文档 \(i\) 中, 否则 \(x_{ij}=0\) 。然后我们可以使用如下的类条件密度：
\[ p(\boldsymbol{x}_i | y_i, \boldsymbol{\theta})=\prod_{j=1}^D {{\rm Ber}(x_{ij} | \theta_{jc})} = \prod_{j=1}^D{\theta_{jc}^{\mathbb{I}(x_{ij})} (1-\theta_{jc})^{\mathbb{I}(1-x_{ij})}} \tag{3.77} \]这称为 伯努利乘积模型(the Bernoulli product model,)，或 二项独立模型(the binary independence model)。
然而，忽略文档中每个单词出现的次数会丢失一些信息（McCallum和Nigam 1998）。更准确的表示计算每个单词的出现次数。具体来说，让 \(\boldsymbol{x}_i\) 表示文档 \(i\) 的计数向量，于是 \(x_{ij} \in \{0,1,\dots,N_i\}\) ，其中 \(N_i\) 是在文件 \(i\) 的所有单词数（即, \(\sum_{j=1}^D{x_{ij}}=N_j\) ）。对于类条件密度，我们可以使用多项分布：
\[ p(\boldsymbol{x}_i | y_i=c,\boldsymbol{\theta})={\rm Mu}(\boldsymbol{x}_i | N_i,\boldsymbol{\theta}_c) = \dfrac{N_i!}{\prod_{j=1}^D{x_{ij}!}}\prod_{j=c}^D{\theta_{jc}^{x_{ij}}} \tag{3.78} \]我们隐含地假设文件长度为 \(N_i\) 独立于分类。这里 \(\theta_{jc}\) 是 \(c\) 类文档中生成单词 \(j\) 的概率; 这些参数满足约束 \(\sum_{j=1}^D{\theta_{jc}}=1, \forall \ c\) 。
尽管多项分类器在测试时易于训练且易于使用，但它并不是对文档分类特别有效。其中一个原因是它没有考虑到的突发性单词使用。这指的是大多数单词从未出现在任何给定文档中的现象，但如果它们确实出现一次，则它们可能不止一次出现，即单词以突发形式出现。
多项模型无法捕捉突发现象。要知道为什么，注意公式3.78有形如 \(\theta_{jc}^{x_{ij}}\) 的项， 由于对于罕见词 \(\theta_{jc} \ll 1\) ，越来越不可能产生许多词。对于更频繁的单词，衰减率不是那么快。为了直观地理解原因，请注意最常用的单词是不具体类的功能单词，例如“and”，“the”和“but”; “and”这个词出现的几率基本上是相同的，无论它先前发生了多少时间（模数长度），因此对于常用词而言，独立性假设更合理。然而，由于罕见词是最适合分类目的的词，因此我们想要最仔细地建模。
已经提出了各种富有启发式方法来改进文档分多项类器的性能（Rennie等人，2003）。我们现在提出了一种替代类条件密度，它与这些特殊方法一样，但概率上是合理的（Madsen等人，2005）。
假设我们简单地用狄利克雷混合多项(Dirichlet Compound Multinomial)密度 或 DCM 密度来代替多项类条件密度 ， 定义如下
\[ p(\boldsymbol{x}_i | y_i=c,\boldsymbol{\theta}) = \int {{\rm Mu}(\boldsymbol{x}_i|N_i,\boldsymbol{\theta}_c){\rm Dir}(\boldsymbol{\theta}_c | \boldsymbol{\alpha}_c) d \boldsymbol{\theta}_c}=\dfrac{N_i!}{\prod_{j=1}^D{x_{ij}!}}\dfrac{{\rm B}(\boldsymbol{x}_i+\boldsymbol{\alpha}_i)}{{\rm B}(\boldsymbol{\alpha}_i)} \tag{3.79} \]（这个等式推导自公式5.24。）令人惊讶的是，这个简单的变化就是捕获突发现象所需的全部。直观的原因如下：看到一个单词的一个发生后， 比如单词 \(j\) ，那么在 \(\theta_j\) 上的后验计数得到更新，于是单词 \(j\) 再次出现有更大可能。相反，如果 \(\theta_j\) 固定，那么每个单词的出现是独立的。多项模型对应于从有K中颜色球的坛子中取出一个球，记录其颜色，然后放回。相比之下，DCM模型对应于取出一个球，记录其颜色，然后将取出的球连同一个同色额外球一起放回; 这被称为 波利亚坛子。
使用DCM模型作为类条件密度比使用多项模型具有更好的结果，并且具有与现有技术方法相当的性能，正如（Madsen et al. 2005）中所述。唯一的缺点是配置DCM模型更复杂; 详见了（Minka 2000e; Elkan 2006）。