[人工智能]ML (Chapter 7): 贝叶斯分类器

本文为《机器学习》(周志华) 的读书笔记

• 参考 南瓜书

贝叶斯决策论 (Bayesian decision theory)

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

• 下面我们以多分类任务为例来解释其基本原理。假设有 $N$ 种可能的类别标记，即 Y = { c 1 , c 2 , . . . , c N } \mathcal Y= \{c_1,c_2, ... ,c_N\} Y={c1?,c2?,...,cN?}，${\lambda }_{ij}$ 是将一个真实标记为 $c_j$ 的样本误分类为 $c_i$ 所产生的损失．基于后验概率 $P(c_i;\mathbf{x})$ 可获得将样本 $\mathbf{x}$ 分类为 $c_i$ 所产生的期望损失 (expected loss), 即在样本 $\mathbf{x}$ 上的 “条件风险” (conditional risk)
  我们的任务是寻找一个判定准则 $h$ 以最小化总体风险
  
• 显然，对每个样本 $\mathbf{x}$, 若 $h$ 能最小化条件风险 $R(h(\mathbf{x})|\mathbf{x})$, 则总体风险 $R(h)$ 也将被最小化. 这就产生了贝叶斯判定准则 (Bayes decision rule): 为最小化总体风险，只需在每个样本上选择那个能使条件风险 $R(c|\mathbf{x})$ 最小的类别标记，即
  此时，$h^{?}$ 称为贝叶斯最优分类器 (Bayes optimal classifier),与之对应的总体风险 $R(h^{?})$ 称为贝叶斯风险 (Bayes risk). $1?R(h^{?})$ 反映了分类器所能达到的最好性能，即通过机器学习所能产生的模型精度的理论上限

分类问题

• 若目标是最小化分类错误率，则误判损失 ${\lambda }_{ij}$ 可写为
  此时条件风险
  于是，最小化分类错误率的贝叶斯最优分类器即对每个样本 $\mathbf{x}$， 选择能使后验概率 $P(c|\mathbf{x})$ 最大的类别标记
  
• 为了基于有限的训练样本集尽可能准确地估计出后验概率 $P(c|\mathbf{x})$. 大体来说，主要有两种策略:
  • (1) 给定 $\mathbf{x}$，可通过直接建模 $P(c|\mathbf{x})$ 来预测 $c$，这样得到的是 “判别式模型” (discriminative models) (决策树、BP 神经网络、支持向量机…)
  • (2) 也可先对联合概率分布 $P(\mathbf{x},c)$ 建模，然后再利用贝叶斯公式获得 $P(c|\mathbf{x})$， 这样得到的是 “生成式模型” (generative models)
    其中，$P(c)$ 是类 “先验” (prior) 概率; $P(\mathbf{x}|c)$ 是样本 $\mathbf{x}$ 相对于类标记 $c$ 的类条件概率 (class-conditional probability)，或称为 “似然” (likelihood); $P(\mathbf{x})$ 是用于归一化的 “证据” (evidence) 因子. 可以看出，估计 $P(c|\mathbf{x})$ 的问题就转化为如何基于训练数据 $D$ 来估计先验 $P(c)$ 和似然 $P(\mathbf{x}|c)$
    • 根据大数定律，当训练集包含充足的独立同分布样本时，$P(c)$ 可通过各类样本出现的频率来进行估计
    • 对类条件概率 $P(\mathbf{x}|c)$ 来说, 由于它涉及关于 $\mathbf{x}$ 所有属性的联合概率，直接根据样本出现的频率来估计似然将会遇到严重的困难
      • e.g. 假设样本的 $d$ 个属性都是二值的, 则样本空间将有 $2^d$ 种可能的取值，在现实应用中，这个值往往远大于训练样本数, 也就是说，很多样本取值在训练集中根本没有出现，直接使用频率来估计 $P(\mathbf{x}|c)$ 显然不可行，因为 “未被观测到” 与 “出现概率为零” 通常是不同的

极大似然估计 (Maximum Likelihood Estimation, MLE)

参数估计 (parameter estimation)

• 估计类条件概率的一种常用策略是先假定其具有某种确定的概率分布形式，再基于训练样本对概率分布的参数进行估计. 具体地，记关于类别 $c$ 的类条件概率为 $P(\mathbf{x}|c)$， 假设 $P(\mathbf{x}|c)$ 具有确定的形式并且被参数向量 ${\mathbf{\theta }}_c$ 唯一确定，则我们的任务就是利用训练集 $D$ 估计参数 ${\mathbf{\theta }}_c$. 为明确起见, 我们将 $P(\mathbf{x}|c)$ 记为 $P(\mathbf{x}|{\mathbf{\theta }}_c)$
  • 与频率主义学派 (Frequentist) 不同，贝叶斯学派 (Bayesian) 认为参数是未观察到的随机变量，其本身也可有分布

极大似然估计 (Maximum Likelihood Estimation, MLE)

• 令 $D_c$ 表示训练集 $D$ 中第 $c$ 类样本组成的集合，假设这些样本是独立同分布的，则参数 ${\mathbf{\theta }}_c$ 对于数据集 $D_c$ 的似然是
  对 ${\mathbf{\theta }}_c$ 进行极大似然估计, 就是去寻找能最大化似然 $P(D_c|{\mathbf{\theta }}_c$) 的参数值 ${\hat{\mathbf{\theta }}}_c$
• 式 (7.9) 中的连乘操作易造成下溢, 通常使用对数似然 (log-likelihood)
  

需注意的是，这种参数化的方法虽能使类条件概率估计变得相对简单，但估计结果的准确性严重依赖于所假设的概率分布形式是否符合潜在的真实数据分布. 在现实应用中，欲做出能较好地接近潜在真实分布的假设往往需在一定程度上利用关于应用任务本身的经验知识，否则若仅凭 “猜测” 来假设概率分布形式，很可能产生误导性的结果

朴素贝叶斯分类器

"属性条件独立性假设" (attribute conditional independence assumption)

• 对已知类别，假设所有属性相互独立 (条件独立)
  其中 $d$ 为属性数目，$x_i$ 为 $\mathbf{x}$ 在第 $i$ 个属性上的取值
• 该假设能避免之前提到的 “组合爆炸问题”

朴素贝叶斯分类器

• 由于对所有类别来说 $P(\mathbf{x})$ 相同，因此基于式 (7.6) 的贝叶斯判定准则有
  其中
  
  • 对连续属性可考虑概率密度函数 (正态分布)，假定 $P(x_i|c)～\mathcal{N}({\mu }_{c,i},{\sigma }_{c,i}^2)$, 其中 ${\mu }_{c,i}$ 和 ${\sigma }_{c,i}^2$ 分别是第 $c$ 类样本在第 $i$ 个属性上取值的均值和方差，则有
    

拉普拉斯修正 (Laplacian correction)

• 需注意，若某个属性值在训练集中没有与某个类 $c_i$ 同时出现过，则连乘式中计算出的概率值为 0，因此，无论该样本的其他属性是什么，哪怕在其他属性上明显像类 $c_i$，分类的结果都将不为 $c_i$，这显然不合理
• 为了避免其他属性携带的信息被训练集中未出现的属性值 “抹去” ，在估计概率值时通常要进行 “平滑” (smoothing)，常用 “拉普拉斯修正”. 具体来说，令 $N$ 表示训练集 $D$ 中可能的类别数，$N_i$ 表示第 $i$ 个属性可能的取值数，则式 (7.16) 和 (7.17) 分别修正为
  
  • 拉普拉斯修正实质上假设了属性值与类别均匀分布，这是在朴素贝叶斯学习过程中额外引入的关于数据的先验. 在训练集变大时，修正过程所引入的先验 (prior) 的影响也会逐渐变得可忽略，使得估值渐趋向于实际概率值

推断

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

半朴素贝叶斯分类器 (semi-naive Bayes classifiers)

• 在现实任务中，“属性条件独立性假设” 往往很难成立. 于是，人们尝试对属性条件独立性假设进行一定程度的放松，由此产生了一类称为 “半朴素贝叶斯分类器” 的学习方法

半朴素贝叶斯分类器 (独依赖估计)

• 半朴素贝叶斯分类器的基本想法是适当考虑一部分属性间的相互依赖信息，从而既不需进行完全联合概率计算，又不至于彻底忽略了比较强的属性依赖关系
• “独依赖估计” (One-Dependent Estimator，ODE) 是半朴素贝叶斯分类器最常用的一种策略. 顾名思议，所谓 “独依赖” 就是假设每个属性在类别之外最多仅依赖于一个其他属性，即
  其中 $p{a}_i$ 为属性 $x_i$ 所依赖的属性，称为 $x_i$ 的父属性 ($\propto$ 表示正比于). 此时，对每个属性 $x_i$，若其父属性 $p{a}_i$ 已知，则可采用类似式 (7.20) 的办法来估计概率值 $P(x_i|c,p{a}_i)$. 于是, 问题的关键就转化为如何确定每个属性的父属性，不同的做法产生不同的独依赖分类器
  • SPODE (Super-Parent ODE) 方法: 最直接的做法是假设所有属性都依赖于同一个属性，称为 “超父” (super-parent)，然后通过交叉验证等模型选择方法来确定超父属性. 例如，在图 7.1 (b) 中，$x_1$ 是超父属性
  • TAN (Tree Augmented naive Bayes) 则是在最大带权生成树 (maximum weighted spanning tree) 算法的基础上，通过以下步骤将属性间依赖关系约简为如图 7.1 ($c$) 所示的树形结构:
    • (1) 计算任意两个属性之间的条件互信息 (conditional mutual information)
      
    • (2) 以属性为结点构建完全图，任意两个结点之间边的权重设为 $I(x_i,x_j|y)$
    • (3) 构建此完全图的最大带权生成树，挑选根变量，将边置为有向. 条件互信息 $I(x_i,x_j|y)$ 刻画了属性 $x_i$ 和 $x_j$ 在己知类别情况下的相关性，因此，通过最大生成树算法，TAN 实际上仅保留了强相关属性之间的依赖性
    • (4) 加入类别结点 $y$， 增加从 $y$ 到每个属性的有向边
      
  • AODE (Averaged One-Dependent Estimator) 是一种基于集成学习机制、更为强大的独依赖分类器. 与 SPODE 通过模型选择确定超父属性不同， AODE 尝试将每个属性作为超父来构建 SPODE，然后将那些具有足够训练数据支撑的 SPODE 集成起来作为最终结果，即
    其中 $D_{x_i}$ 是在第 $i$ 个属性上取值为 $x_i$ 的样本的集合，$m^{\prime }$ 为阈值常数 (默认设为 30). 同样也需要在估计时进行拉普拉斯修正：
    

“高阶依赖” (对多个属性依赖)

• 既然将属性条件独立性假设放松为独依赖假设可能获得泛化性能的提升，那么，能否通过考虑属性间的高阶依赖来进一步提升泛化性能呢? 也就是说，将式 (7.23) 中的属性 $p{a}_i$ 替换为包含 $k$ 个属性的集合 ${\text{pa}}_{\text{i}}$，从而将 ODE 拓展为 kDE
• 需注意的是，随着 $k$ 的增加，准确估计概率 $P(x_i|y,{\text{pa}}_{\text{i}})$ 所需的训练样本数量将以指数级增加. 因此，若训练数据非常充分，泛化性能有可能提升; 但在有限样本条件下，则又陷入估计高阶联合概率的泥沼