贝叶斯分类器¶

贝叶斯决策论¶

假设有 \(N\) 种可能的类别标记，即 \(\mathcal{Y} = \{c_1, c_2, \ldots, c_N\}\), \(\lambda_{ij}\) 是将一个真实标记为 \(c_i\) 的样本误分类为 \(c_j\) 所产生的损失. 基于后验概率 \(P(c_i | \bm{x})\) 可获得将样本 \(\bm{x}\) 分类为 \(c_i\) 所产生的期望损失（expected loss）, 即在样本 \(x\) 上的条件风险（conditional risk）

\[ R(c_i | \bm{x}) = \sum_{j=1}^{N} \lambda_{ij} P(c_j | \bm{x}) \]

我们的任务是寻找一个判定准则 \(h: \mathcal{X} \mapsto \mathcal{Y}\), 以最小化总体风险

\[ R(h) = \mathbb{E}_{\bm{x}}[R(h(\bm{x}) | \bm{x})] \]

显然，对每个样本 \(\bm{x}\), 若 \(h\) 能最小化条件风险 \(R(h(\bm{x}) | \bm{x})\), 则总体风险 \(R(h)\) 也将被最小化. 这就产生了贝叶斯判定准则（Bayes decision rule）：为最小化总体风险，只需在每个样本上选择那个能使条件风险 \(R(c | \bm{x})\) 最小的类别标记，即

\[ h^*(\bm{x}) = \argmin_{c \in \mathcal{Y}} R(c | \bm{x}) \]

此时，\(h^*\) 称为贝叶斯最优分类器（Bayes optimal classifier）, 与之对应的总体风险 \(R(h^*)\) 称为贝叶斯风险（Bayes risk）. \(1 - R(h^*)\) 反映了分类器所能达到的最好性能，即通过机器学习所能产生的模型精度的理论上限.

具体来说，若目标是最小化分类错误率，则误判损失函数可写为

\[ \lambda_{ij} = \begin{cases} 0, & i = j \\ 1, & i \neq j \end{cases} \]

此时条件风险

\[ R(c | \bm{x}) = 1 - P(c | \bm{x}) \]

于是，最小化分类错误率的贝叶斯最优分类器为

\[ h^*(\bm{x}) = \argmax_{c \in \mathcal{Y}} P(c | \bm{x}) \]

即对每个样本应选择能使后验概率 \(P(c | \bm{x})\) 最大的类别标记.

不难看出，欲使用贝叶斯判定准则来最小化决策风险，首先要获得后验概率 \(P(c | \bm{x})\). 然而，在现实任务中这通常难以直接获得. 从这个角度来看，机器学习所要实现的是基于有限的训练样本集尽可能准确地估计出后验概率 \(P(c | \bm{x})\)。

大体来说，主要有两种策略：

通过直接建模 \(P(c | \bm{x})\) 来预测 \(c\), 这样得到的是判别式模型（discriminative models），代表是决策树、BP 神经网络、支持向量机等
先对联合概率分布 \(P(\bm{x}, c)\) 建模，然后再由此获得 \(P(c | \bm{x})\)，这样得到的是生成式模型（generative models），代表是贝叶斯分类器

对于生成式模型，必然考虑

\[ P(c | \bm{x}) = \frac{P(\bm{x}, c)}{P(\bm{x})} = \frac{P(c) P(\bm{x} | c)}{P(\bm{x})} \]

\(P(c)\) 是类先验（prior）概率，表达了样本空间中各类样本所占的比例，可通过各类样本出现的频率来进行估计（大数定律）
\(P(\bm{x} | c)\) 是样本 \(\bm{x}\) 相对于类标记 \(c\) 的类条件概率（class-conditional probability），或称为似然（likelihood）
\(P(\bm{x})\) 是用于归一化的证据（evidence）因子，与类别无关，可以不考虑

极大似然估计¶

估计类条件概率的一种常用策略是先假定其具有某种确定的概率分布形式，再基于训练样本对概率分布的参数进行估计。假设 \(P(\bm{x} | c)\) 具有确定的形式并且被参数向量 \(\bm{\theta}_c\) 唯一确定，则我们的任务就是利用训练集 \(D_c\) 估计参数 \(\bm{\theta}_c\)。为明确起见，我们将 \(P(\bm{x} | c)\) 记为 \(P(\bm{x} | \bm{\theta}_c)\)。

事实上，概率模型的训练过程就是参数估计（parameter estimation）过程。对于参数估计，统计学界的两个学派分别提供了不同的解决方案：

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

本节介绍源自频率主义学派的极大似然估计（Maximum Likelihood Estimation, 简称 MLE），这是根据数据采样来估计概率分布参数的经典方法。

令 \(D_c\) 表示训练集 \(D\) 中第 \(c\) 类样本组成的集合，假设这些样本是独立同分布的，则参数 \(\bm{\theta}_c\) 对于数据集 \(D_c\) 的似然是

\[ P(D_c | \bm{\theta}_c) = \prod_{\bm{x} \in D_c} P(\bm{x} | \bm{\theta}_c) \]

对 \(\bm{\theta}_c\) 进行极大似然估计，就是去寻找能最大化似然 \(P(D_c | \bm{\theta}_c)\) 的参数值 \(\hat{\bm{\theta}}_c\)。直观上看，极大似然估计是试图在依所有可能的取值中，找到一个能使数据出现的“可能性”最大的值。

上式中的连乘操作易造成下溢，通常使用对数似然（log-likelihood）

\[ LL(\bm{\theta}_c) = \log P(D_c | \bm{\theta}_c) = \sum_{\bm{x} \in D_c} \log P(\bm{x} | \bm{\theta}_c) \]

此时参数 \(\hat{\bm{\theta}}_c\) 的极大似然估计为

\[ \hat{\bm{\theta}}_c = \argmax_{\bm{\theta}_c} LL(\bm{\theta}_c) \]

需要注意的是，这种参数化的方法虽能使类条件概率估计变得相对简单，但估计结果的准确性严重依赖于所假设的概率分布形式是否符合潜在的真实数据分布。

例如，假定数据 \(\bm{x}\) 条件于类别 \(c\) 下服从概率密度函数 \(p(\bm{x} | c) \sim \mathcal{N}(\bm{\mu}_c, B_c)\)，我们希望求出参数 \(\bm{\mu}_c\) 和 \(B_c\) 的极大似然估计。

首先得到对数似然函数：

\[ \begin{aligned} LL(\bm{\mu}_c, B_c) &= \log \prod_{i=1}^n \frac{1}{(2\pi)^{d/2} |B_c|^{1/2}} \exp\left( -\frac{1}{2} (\bm{x}_i - \bm{\mu}_c)^T B_c^{-1} (\bm{x}_i - \bm{\mu}_c) \right) \\ &= -\frac{n d}{2} \log(2\pi) - \frac{n}{2} \log |B_c| - \frac{1}{2} \sum_{i=1}^n (\bm{x}_i - \bm{\mu}_c)^T B_c^{-1} (\bm{x}_i - \bm{\mu}_c) \end{aligned} \]

对 \(\bm{\mu}_c\) 求偏导数：

\[ \frac{\partial LL(\bm{\mu}_c, B_c)}{\partial \bm{\mu}_c} = \sum_{i=1}^n B_c^{-1} (\bm{x}_i - \bm{\mu}_c) \]

令其为零，解得：

\[ \bm{\mu}_c = \frac{1}{n} \sum_{i=1}^n \bm{x}_i \]

对 \(B_c\) 求偏导数：

\[ \frac{\partial LL(\bm{\mu}_c, B_c)}{\partial B_c} = -\frac{n}{2} B_c^{-1} + \frac{1}{2} B_c^{-1} \left( \sum_{i=1}^n (\bm{x}_i - \bm{\mu}_c)(\bm{x}_i - \bm{\mu}_c)^T \right) B_c^{-1} \]

令其为零，解得：

\[ B_c = \frac{1}{n} \sum_{i=1}^n (\bm{x}_i - \bm{\mu}_c)(\bm{x}_i - \bm{\mu}_c)^T \]

即，\(\bm{\mu}_c\) 的极大似然估计是类别 \(c\) 下的样本均值，\(B_c\) 的极大似然估计是类别 \(c\) 下的样本协方差矩阵，这显然是一个符合直觉的结果。

朴素贝叶斯分类器¶

不难发现，基于贝叶斯公式来估计后验概率 \(P(c | \bm{x})\) 的主要困难在于：类条件概率 \(P(\bm{x} | c)\) 是所有属性上的联合概率，难以从有限的训练样本直接估计而得。为避开这个障碍，朴素贝叶斯分类器（naive Bayes classifier）采用了属性条件独立性假设（attribute conditional independence assumption）：对已知类别，假设所有属性相互独立。

基于属性条件独立性假设，贝叶斯公式可重写为

\[ P(c | \bm{x}) = \frac{P(c) P(\bm{x} | c)}{P(\bm{x})} = \frac{P(c)}{P(\bm{x})} \prod_{i=1}^d P(x_i | c) \]

由于对所有类别来说 \(P(\bm{x})\) 相同，因此基于贝叶斯判定准则有

\[ h_{nb}(\bm{x}) = \argmax_{c \in \mathcal{Y}} P(c) \prod_{i=1}^d P(x_i | c) \]

这就是朴素贝叶斯分类器的表达式。

显然，朴素贝叶斯分类器的训练过程就是基于训练集 \(D\) 来估计类先验概率 \(P(c)\)，并为每个属性估计条件概率 \(P(x_i | c)\)。

令 \(D_c\) 表示训练集 \(D\) 中第 \(c\) 类样本组成的集合，若有充足的独立同分布样本，则可容易地估计出类先验概率

\[ P(c) = \frac{|D_c|}{|D|} \tag{1} \]

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

\[ P(x_i | c) = \frac{|D_{c, x_i}|}{|D_c|} \tag{2} \]

对连续属性可考虑概率密度函数，假定 \(p(x_i | c) \sim \mathcal{N}(\mu_{c, i}, \sigma_{c, i}^2)\)，其中 \(\mu_{c, i}\) 和 \(\sigma_{c, i}\) 分别是第 \(c\) 类样本在第 \(i\) 个属性上取值的均值和方差，则有

\[ P(x_i | c) = \frac{1}{\sqrt{2\pi} \sigma_{c, i}} \exp\left( -\frac{(x_i - \mu_{c, i})^2}{2\sigma_{c, i}^2} \right) \]

需注意，若某个属性值在训练集中没有与某个类同时出现过，则直接基于式(2)进行概率估计，将出现问题。为避免其它属性携带的信息被训练集中未出现的属性值“抹去”，在估计概率值时通常要进行平滑，常用拉普拉斯修正（Laplacian correction）。具体来说，令 \(N\) 表示训练集 \(D\) 中可能的类别数，\(N_i\) 表示第 \(i\) 个属性可能的取值数，则式(1)和(2)分别修正为

\[ P(c) = \frac{|D_c| + 1}{|D| + N} \]

\[ P(x_i | c) = \frac{|D_{c, x_i}| + 1}{|D_c| + N_i} \]

拉普拉斯修正实质上假设了属性值与类别均匀分布，这是在朴素贝叶斯学习过程中额外引入的关于数据的先验。显然，拉普拉斯修正避免了因训练集样本不充分而导致概率估值为零的问题，并且在训练集变大时，修正过程所引入的先验的影响也会逐渐变得可忽略，使得估值渐趋向于实际概率值。

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

半朴素贝叶斯分类器¶

在现实生活中，属性条件独立性假设往往很难成立，于是人们尝试对属性条件独立性假设进行一定程度的放松，由此产生了一类称为半朴素贝叶斯分类器（semi-naive Bayes classifiers）的学习方法。

独依赖估计（One-Dependent Estimator, 简称 ODE）是半朴素贝叶斯分类器最常用的一种策略。顾名思议，所谓“独依赖”就是假设每个属性在类别之外最多仅依赖于一个其他属性，即

\[ P(c | \bm{x}) \propto P(c) \prod_{i=1}^d P(x_i | c, pa(i)) \tag{3} \]

其中 \(pa(i)\) 为属性 \(x_i\) 所依赖的属性，称为 \(x_i\) 的父属性。此时，对每个属性 \(x_i\) 若其父属性 \(pa(i)\) 已知，则可采用类似式(2)的办法来估计概率值 \(P(x_i | c, pa(i))\)。于是，问题的关键就转化为如何确定每个属性的父属性，不同的做法产生不同的独依赖分类器。

SPODE（Super-Parent ODE）方法假设所有属性都依赖于同一个属性，然后通过交叉验证等模型选择方法来确定超父属性
TAN（Tree Augmented naive Bayes）则是通过计算任意两个属性之间的条件互信息，构建最大带权生成树，从而将属性间依赖关系约简为树形结构，仅保留强相关属性之间的依赖性，条件互信息的公式为

\[ I(x_i, x_j | y) = \sum_{x_i, x_j; c \in \mathcal{Y}} P(x_i, x_j | c) \log \frac{P(x_i, x_j | c)}{P(x_i | c) P(x_j | c)} \]

AOED（Averaged One-Dependent Estimator）是一种集成学习机制的独依赖分类器，尝试将每个属性作为超父来构建 SPODE，然后将那些具有足够训练数据支撑的 SPODE 集成起来作为最终结果，即

\[ P(c | \bm{x}) \propto \underset{|D_{x_i}| \ge m'}{\sum_{i=1}^d} P(c, x_i) \prod_{j=1}^d P(x_j | c, x_i) \]

不难看出，与朴素贝叶斯分类器类似，AOED 无需模型选择，既能通过预计算节省预测时间，也能采取懒惰学习方式在预测时再进行计数，并且易于实现增量学习。

可以将式(3)中的属性 \(pa(i)\) 替换为包含 \(k\) 个属性的集合 \(\bm{pa}(i)\)，从而将 ODE 拓展为 \(k\)DE。需注意的是，随着 \(k\) 的增加，准确估计概率 \(P(x_i | c, \bm{pa}(i))\) 所需的训练样本数量将以指数级增加。因此，若训练数据非常充分，泛化性能有可能提升；但在有限样本条件下，则又陷入估计高阶联合概率的泥沼。

贝叶斯网络¶

贝叶斯网络（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)\)。

结构¶

贝叶斯网络结构有效地表达了属性间的条件独立性。给定父节点集，贝叶斯网络假设每个属性与它的非后裔属性独立，于是 \(B = (G, \Theta)\) 将属性的 \(x_1, x_2, \ldots, x_d\) 的联合概率分布定义为

\[ P(x_1, x_2, \ldots, x_d) = \prod_{i=1}^d P(x_i | \pi_i) = \prod_{i=1}^d \theta_{x_i | \pi_i} \]