《机器学习》笔记（第三部分：Bayes 分类器、集成学习）

7 Bayes 分类器

7.1 Bayes 决策论

  假设标签集合 $\mathcal Y = \{c_i\}_{i=1}^N$. 设 $\lambda _{ij}$ 是将真实标签 $c_j$ 误分类为 $c_i$ 的损失 (风险). 假设样本 $\boldsymbol x$ 真是类别为 $c_j$ 的后验概率为 $P(c_j \mid \boldsymbol x)$, 则定义将 $\boldsymbol x$ 分类为 $c_i$ 的期望损失 (条件风险) 为

$$R(c_i, \boldsymbol x) = \sum _j \lambda _{ij} P(c_j \mid \boldsymbol x)$$

特殊地, 在 0-1 损失 $\lambda _{ij} = 1 - \delta _{ij}$ 下,

$$R(c_i, \boldsymbol x) = 1 - P(c_i \mid \boldsymbol x)$$

Bayes 决策的目标是寻找一个判定准则 $h: \mathcal X \to \mathcal Y$ 来最小化总风险

$$\min \quad R(h) = \mathrm E_{\boldsymbol x} R(h(\boldsymbol x), \boldsymbol x)$$

Bayes 最优分类器 假设有一个最好的分类器, 它对于样本 $\boldsymbol x$ 总能选择最优类别. 即

$$h^*(\boldsymbol x) = \argmin _i R(c_i, \boldsymbol x)$$

此时的 Bayes 风险是 $R(h^*)$, 它是 Bayes 决策所能达到的理论风险下限.

  Bayes 决策的目标是获得后验概率 $P(c \mid \boldsymbol x)$. 有两种策略:

• 判别式模型: 直接对 $P(c \mid \boldsymbol x)$ 建模, 例如决策树、BP 神经网络、支持向量机等;
• 生成式模型: 对联合分布 $P(\boldsymbol x, c)$ 建模, 然后获得 $P(c \mid \boldsymbol x)$.

对于生成式模型使用 Bayes 公式

$$P(c \mid \boldsymbol x) = \frac{P(\boldsymbol x, c)}{P(\boldsymbol x)} = \frac{P(c) P(\boldsymbol x \mid c)}{P(\boldsymbol x)}$$

其中 $P(c)$ 是先验概率, 可通过各类样本出现频率估计. $P(c \mid \boldsymbol x)$ 是后验概率. $P(\boldsymbol x \mid c)$ 是样本 $\boldsymbol x$ 对于类别 $c$ 的条件似然. $P(\boldsymbol x)$ 是用于归一化的证据因子.

极大似然估计 假设条件似然 $P(\boldsymbol x \mid c)$ 的分布族已知, 仅剩一个待估参数 $\theta _c$. 对于训练集 $D$ 中第 $c$ 类样本组成的集合 (记为 $D_c$), 似然函数的最大值即为参数的极大似然估计.

$$\theta _c^* = \argmax _{\theta _c} \mathcal L_c = \argmax _{\theta _c} \prod _{\boldsymbol x \in D_c} P(\boldsymbol x \mid \theta _c)$$

但是条件似然 $P(x_1, \dots, x_d \mid \theta _c)$ 是难以估计的: 它一共有 $\prod _i |\mathcal X^{(i)}|$ 中取值的概率需要估计.

7.3 朴素 Bayes 分类器

  朴素 Bayes 分类器有一个很强的假设: 在给定类别 $c$ 下, 样本 $\boldsymbol x$ 的各维度属性是相互独立的. 该假设大大降低了估计难度: 在该假设下只有 $\sum _i |\mathcal X_i|$ 个取值概率要估计了. 朴素 Bayes 分类器为

$$h_{\mathrm{nb}}(\boldsymbol x) = \argmax _{c \in \mathcal Y} P(c) \prod _i P(x_i \mid c)$$

其中取 $P(c) = |D_c|/|D|$. 令 $D_{c, x_i}$ 为标签为 $c$ 且属性 $i$ 取值为 $x_i$ 的样本集合, 对离散属性, 取 $P(x_i^* \mid c) = |D_{c, x_i}| / |D_c|$; 对连续属性, 取 $P(x_i^* \mid c)$ 为正态密度, 均值和方差分别是 $D_{c, x_i}$ 的样本均值和样本方差.

Laplace 修正  若预测样本的属性 $i$ 在类别 $c$ 的测试样本中未出现 (即 $|D_{c, x_i}| = 0$) 的情况下, 朴素 Bayes 分类器会直接认为其属于类别 $c$ 的概率为 $0$. 为避免该情况, 可以作 Laplace 修正

$$P(c) = \frac{|D_c| + 1}{|D| + N}, \qquad P(x_i \mid c) = \frac{|D_{c, x_i}| + 1}{|D_c| + N_i}$$

其中 $N = |\{y^{(k)}\}_k|$ 和 $N_i = |\{x^{(k)}_i\}_k|$ 分别是样本中的类别数和样本第 $i$ 维的可能取值种类数. 这就避免了因训练样本不充分导致概率估值为 $0$ 的问题.

7.4 半朴素 Bayes 分类器

  朴素 Bayes 分类器的条件独立假设过强. 对该假设进行一定程度的放松, 得到的分类器称为半朴素 Bayes 分类器.

独依赖估计 (ODE, One-Dependent Estimator) 假设每个属性 $x_i$ 在 $c$ 以外最多还可依赖一个其它属性 $x_{a(i)}$, 此时的后验概率

$$P(c \mid x) \propto P(c) \prod _i P(x_i \mid x_{a(i)}, c)$$

其中属性 $a(i)$ 称为属性 $i$ 的父属性, 后验概率可使用与朴素 Bayes 分类器相同的方法估计.

超父独依赖估计 (SPODE, Super-Parent ODE) 特殊地, SPODE 假设所有属性都依赖于同一个属性 (称为超父属性). 令属性 $a$ 为超父属性, 则后验概率

$$P(c \mid x) \propto P(c) \prod _i P(x_i \mid x_a, c)$$

超父属性可以通过交叉验证等方法选取.

AODE (Averaged One-Dependent Estimator) AODE 同时考虑每一个属性作为超父属性, 除非该属性的样本量不足. 即

$$P(c \mid x) \propto \sum _{a: |D_{x_a}| \geq m_0} P(c, x_a) \prod _i P(x_i \mid x_a, c)$$

一般取样本量阈值 $m_0 = 30$. 此时样本之间的依赖关系是一张完全图, 但是去掉样本量不足的那些节点. 上面的概率可以估计为

$$P(c， x_a) = \frac{|D_{c, x_a}| + 1}{|D| + N_a}, \qquad P(x_i \mid x_a, c) = \frac{|D_{c, x_a, x_i}| + 1}{|D_{c, x_a}| + N_i}$$

其中 $D_{c, x_a, x_i}$ 为标签为 $c$ 且属性 $a$ 取值为 $x_a$ 且属性 $i$ 取值为 $x_i$ 的样本集合.

TAN (Tree Augmented Naïve Bayes) TAN 将所有属性总结为一棵树. 它先依据条件互信息 (conditional mutual information) 为权值构建一个完全图

$$I_{ij} = \sum _{x_i} \sum _{x_j} \sum _c P(x_i, x_j \mid c) \ln \frac{P(x_i, x_j \mid c)}{P(x_i \mid c) P(x_j \mid c)}$$

然后计算该图的最大带权生成树, 获得一个半朴素 Bayes 分类器. TAN 算法实际上保留了强相关属性之间的依赖性.

7.5 Bayes 网

  Bayes 网是一个二元组 $B = (G, \Theta)$, 它有两个元素:

• 在各属性之间有一个有向无环图 $G$;
• 图的边权值服从一个带参数 $\Theta$ 的分布族.

假设属性 $x_i$ 的父节点集合为 $A_i$, 则其条件概率为 $P_B(x_i \mid A_i)$.

7.5.1 结构

  在一个 Bayes 网 $B$ 中, 一个样本 $\boldsymbol x$ 的联合概率分布定义为

$$P_B(\boldsymbol x) = \prod _i P_B(x_i \mid A_i)$$

  三个属性之间有三种典型依赖关系: 同父、同子 (V 型)、顺序.

• 同父结构 ($x \to y, y'$) 下, 一般 $y \not \perp y'$, 但 $y \perp y' \mid x$.
• 顺序结构 ($x \to y \to z$) 下, 一般 $x \not \perp z$, 但 $x \perp z \mid y$.
• 但在同子结构 ($x, x' \to y$) 下, 一般 $x \not \perp x' \mid y$, 相反子节点取值未知时 $x \perp x'$.

有向分离 (directed separation) 找到有向图中所有同子结构, 在两个父节点之间加上一条无向边. 然后将所有有向边改为无向边. 由此道德化 (moralization) 得到的无向图称为道德图 (moral graph). 在道德图中, 若一个节点集合 $Z$ 能将图分为不连通的两部分 $X$ 和 $Y$, 则

$$x \perp y \mid Z, \quad \forall x \in X, y \in Y$$

7.5.2 学习

  需要构建一个评分函数 (score function) 来评估 Bayes 网与训练数据的契合程度, 从而选出结构最恰当的 Bayes 网. 从信息论的角度, 学习目标是找到一个能以最短编码长度描述训练数据的模型. 即

$$s(B \mid D) = f(\theta) \cdot |B| - \ell(B \mid D) = \min$$

其中第一项 $|B|$ 是 Bayes 网的参数个数, $f(\theta)$ 是描述每个参数 $\theta$ 所需字节数, 该项计算了编码 Bayes 网所需的字节数; 第二项 $\ell = \sum _i \ln P_B(x_i)$ 是对数似然, 该项计算了 $B$ 对应的概率分布 $P_B$ 需要多少字节来描述 $D$.

• 若取 $f(\theta) = 0$, 则学习任务退化为极大似然估计;
• 若取 $f(\theta) = 1$, 则学习任务即以 AIC 为准则;
• 若取 $f(\theta) = 1/2 \cdot \ln m$, 则学习任务即以 BIC 为准则.

  不幸的是, Bayes 网的结构搜索是一个 NP 难问题. 一般使用一些贪心算法 (如步进地添加或删除一条边) 或者添加约束条件 (如限定为树状结构) 等来降低问题复杂度.

7.5.3 推断

  根据已知 Bayes 网的初始状态 (称为证据, evidence) 来计算 Bayes 网的最终状态 (称为查询, query) 的过程称为推断 (inference). 推断是一个 NP 难问题, 但可以使用 Gibbs 采样求得数值解: 考虑一个 Bayes 网作为 Markov 链并随机赋初值, 然后重复若干步随机游走. 记录每步随机游走的结果向量作为查询结果的分布.

7.6 EM 算法

  假设参数估计问题中有观测数据 $X_{\mathrm{OBS}}$ 和一些缺失或无法被观测的中间变量 $X_{\mathrm{MIS}}$, 现在要对参数 $\boldsymbol \theta$ 作估计. 此时可以使用 EM (Expectation-Maximization) 算法.

• 初始化: 给 $\boldsymbol \theta$ 随机赋初值. 定义完全数据 $X_{\mathrm{COM}} = X_{\mathrm{OBS}} \cup X_{\mathrm{MIS}}$.
• E-步: 计算缺失数据的数学期望. $X_{\mathrm{MIS}} \gets \mathrm E(X_{\mathrm{MIS}} \mid \theta, X_{\mathrm{OBS}})$.
• M-步:
  • 计算基于完全数据的极大似然估计. $\theta \gets \argmax _{\boldsymbol \theta} \ell(\theta \mid X_{\mathrm{COM}})$.
  • 或计算基于观测数据的极大似然估计. $\theta \gets \argmax _{\boldsymbol \theta} \ell(\theta \mid X_{\mathrm{OBS}})$.

重复迭代 E-步和 M-步直到收敛, 即得 $\boldsymbol \theta$ 的 EM 算法估计值.

8 集成学习

8.1 个体与集成

  集成学习 (ensamble learning) 通过构建并结合多个个体学习器 (individual learner) 来完成学习任务. 同质集成 (homogeneous ensamble) 中的个体学习器 (称为基学习器, base learner) 仅包含同种算法; 异质集成 (heterogenous ensamble) 中的个体学习器 (称为组件学习器, component learner) 可以包含不同算法. 弱学习器 (weak learner) 是指那些精度仅略高于随机猜测的学习器. 常将弱学习器进行集成来提高其精确度.

  考虑一个二分类问题 $y \in \{\pm 1\}$ 包含 $2T$ 个基分类器. 假设每个基分类器 $h_i$ 错误率均为 $\varepsilon$, 则总正确数量服从二项分布

$$\sum h_i =: H \sim B(2T, 1 - \varepsilon)$$

集成分类器结果依靠所有基分类器投票产生. 即最终的错误率 (不正确率)

$$\Pr(H \leq T) = \sum _{k=0} ^T \binom{2T}{k} (1-\varepsilon)^k \varepsilon^{2T-k} \leq e^{-T(1-2\varepsilon)^2}$$

后一个不等号是 Hoeffding 不等式. 上式显示出总错误率将会随分类器数目上升而指数下降.

  上面分析有一个假设: 基学习器“好而不同”. 即个体学习器要有一定准确性 (偏差低), 但是预测结果包含多样性 (方差高). 然而这一对矛盾总不会同时成立. 故生成“好而不同”的个体学习器是集成学习的研究核心.

  个体学习器的生成方法分为两大类:

• 串行方法: 基学习器之间强依赖, 必须顺序生成. 例如 Boosting.
• 并行方法: 基学习器之间无依赖, 可以同时生成. 例如 Bagging 和随机森林.

8.2 Boosting

  Boosting 主要关注降低偏差. Boosting 算法有两个要点:

• 对于预测正确的样本, 在下一个基学习器的训练权重降低; 反之预测错误则训练权重上升.
• 最终的集成分类器是基分类器的线性组合.

  AdaBoost 算法是 Boosting 算法族的代表. 假设有 $T$ 个基学习器 $\{h_i\}_{i=1}^T$. 令第 $t$ 轮中, 样本 $i$ 被抽到的概率 (训练时的权重) 为 $p_t^{(i)}$. AdaBoost 算法描述为

• 输入:

  • 训练集 $D = \{\boldsymbol x^{(i)}, y^{(i)}\}_{i=1}^m$
  • 训练轮数 $T$

• 过程:

  1. 初始化 $p_i^{(1)} \gets 1/m, \forall i$.
  2. for $t \in \{1, \dots, T\}$ do
  3.   在给定样本集 $D$ 和训练权重 $\{p_t^{(i)}\}_{i=1}^m$ 下, 训练基学习器 $h_t$. 若学习器无法指定训练权重, 则以权重为比例重采样一组样本进行训练.
  4.   定义错误率 $\varepsilon _t \gets \sum _i p_t^{(i)} \mathit 1_{h_t(\boldsymbol x^{(i)}) \neq y^{(i)}}$
  5.   if $\varepsilon _t > 0.5$ then break. 若当前基学习器性能不佳, 则抛弃.
  6.   定义权重 $\alpha _t = \frac 12 \ln \left(\frac{1-\varepsilon _t}{\varepsilon _t}\right)$
  7.   更新下一轮的样本训练权重
  $$p_{t+1}^{(i)} \gets A \cdot p_t^{(i)} \cdot \begin{cases} e^{-\alpha}, \quad & \text{样本 $i$ 预测正确}\\ e^{\alpha}, \quad & \text{样本 $i$ 预测错误} \end{cases}$$

  其中 $A$ 是待定系数以确保概率和为 $1$.

  8. end for

• 输出: 集成分类器 $H = \mathop{\mathrm{sgn}}\left(\sum _t \alpha _t h_t\right)$

  AdaBoost 算法本质上是在最小化指数损失函数, 即

$$H^\star = \argmin _{H} L := \argmin _{H} \sum _i p^{(i)} e^{-f(\boldsymbol x^{(i)})H(\boldsymbol x^{(i)})}$$

若考虑其偏导数并令其为零, 可以得到

$$\mathop{\mathrm{sgn}}H(\boldsymbol x) = \argmax _{y \in \{\pm 1\}} \Pr(f(\boldsymbol x) = y)$$

即指数损失与 0/1 损失是一致的, 但是指数损失的数学性质更好. 算法中 $\alpha _t$ 和 $p_{t+1}^{(i)}$ 都在使指数损失最小化. 它们的数学推导过程略.

8.3 Bagging 与随机森林

Bagging Bagging 主要关注降低方差. 在自助采样法中, 我们通过有放回抽样选取了一个测试集使得其包含全体数据的 $63\%$. Bagging 独立地重复抽选测试集, 然后独立地重复进行学习和预测输出. 所有预测输出使用投票法或者平均法获得最终结果.

  对于样本 $\boldsymbol x$, 现在只考虑那些未将其纳入训练集的基学习器. 不失一般性, 假设只有前 $T_0$ 个基学习器将其作为测试样本. 则包外估计 (out-of-bag estimate) 为

$$H_{\text{oob}} = \frac{1}{T_0} \sum _{i=1}^{T_0} h_t(\boldsymbol x)$$

包外估计的误差为

$$\varepsilon_{\text{oob}} = \frac 1D \sum _{i=1}^T \mathit 1_{H_{\text{oob}}(\boldsymbol x^{(i)}) = y^{(i)}}$$

随机森林 随机森林是将决策树作为 Bagging 基学习器的基础上加入随机属性选择. 传统决策树在当前步骤所有剩余属性 $A$ 中选择一个最优属性 $a^*$, 而随机森林在 $A$ 中随机选择一个包含至多 $k$ 个元素的子集 $A'$, 然后在 $A'$ 中选择最优属性 $a^*$. 一般取 $k = \mathop{\mathrm{lb}} d$.

8.4 结合策略

  学习器结合带来好处的原因有三种:

• 统计的原因: 有时最优假设可能不止一个, 而是形成一个区域 $\mathcal H^*$. 个体学习器有时同在该区域内, 但均在其边缘地带. 此时可以结合出一个靠近 $\mathcal H^*$ 中心的集成学习器, 以提高泛化性能.
• 计算的原因: 有时各个体学习器都落入了局部最小值. 有的局部最小值对应的泛化性能可能很糟糕. 集成学习可以降低陷入糟糕局部最小值的风险.
• 表示的原因: 有时假设空间 $\mathcal H$ 是一个凹集, 但真实假设 $f \notin \mathcal H$. 学习器的集合相当于将最终的假设空间扩展为 $\mathcal H$ 的凸包, 从而有几率包含 $f$.

平均法 适用于连续值预测. 即所有基学习器的平均值. 这个平均值也可以加权.

投票法 适用于离散值预测. 即所有基学习器投票决定结果. 这个投票也可以加权. 投票法可以按类标记投票, 即每个学习器给其中一个离散值投 $1$ 票; 也可以按类概率投票, 即可以给多个值投票, 但总和为 $1$.

• 在绝对多数投票法 (majority voting) 中, 集成学习器选择基学习器预测结果的众数. 若众数不唯一, 则拒绝预测.
• 在相对多数投票法 (plurality voting) 中, 集成学习器随机选取一个众数作为结果.

学习法 用个体学习器 (称为初级学习器) 提供对样本的预测, 用另一个学习器 (称为次级学习器或元学习器 meta-learner) 来集成所有初级学习器. Stacking 是学习法的典型代表:

• 每一个初级学习器的输入均是 $\{(\boldsymbol x^{(i)}, y^{(i)})\}_{i=1}^m$, 输出是学习器 $\{h_t: \mathcal X \to \mathcal Y\}_{t=1}^T$. 令初级学习器构成向量 $\boldsymbol h: \mathcal X \to \mathcal Y^T$.
• 次级学习器的输入是 $\{(\boldsymbol h(\boldsymbol x^{(i)}), \boldsymbol y^{(i)})\}_{i=1}^m$. 输出是学习器 $h': \mathcal Y^T \to \mathcal Y$.
• 最终的学习器是 $H := h' \circ \boldsymbol h: \mathcal X \to \mathcal Y$.

学习法的初级学习器训练集应使用交叉验证或留一法等方式, 用初级学习器的测试集来产生次级学习器的训练样本.

8.5 多样性

8.5.1 误差—分歧分解

  假设有个体学习器 $\{h_i\}_{i=1}^T$ 通过加权平均产生了集成学习器 $H$. 对于示例 $\boldsymbol x$, 集成学习器 $H$ 和个体学习器 $h_i$ 的泛化误差分别为

$$E = \mathrm E (f(\boldsymbol x) - H(\boldsymbol x)) ^2$$

和

$$E_i = \mathrm E (f(\boldsymbol x) - h_i(\boldsymbol x)) ^2$$

其中 $\boldsymbol x$ 取遍样本空间 $\mathcal X$ 中可能的样本点. 然后定义 $\bar E = \sum w_i E_i$ 是平均泛化误差. 定义个体学习器 $h_i$ 的分歧 (ambiguity) 为

$$A_i = \mathrm E (h_i(\boldsymbol x) - H(\boldsymbol x)) ^2$$

它刻画了 $h_i$ 与 $H$ 输出的不一致性. 然后定义 $\bar A = \sum w_i A_i$ 是平均分歧. 然后集成学习器的泛化误差可以作误差—分歧分解:

$$E = \bar E - \bar A$$

即“集成泛化误差”比“个体平均泛化误差”要低一个“分歧值”.

8.5.2 多样性度量

  多样性度量 (diversity measure) 用于度量个体分类器的多样化程度. 典型做法是两两考虑其相似性. 考虑两个分类器 $h_i$ 和 $h_j$ 的预测结果列联表

	$h_i = +1$	$h_i = -1$
$h_j = +1$	$a$	$c$
$h_j = -1$	$b$	$d$

定义 $m = a + b + c + d$, 常见的多样性度量包括

• 不合度量 (disagreement measure)

$$\mathrm{dis}_{ij} = \frac{b + c}{m} \in [0, 1]$$

不合度量越大, 多样性越大.

• 相关系数 (correlation coefficient)

$$\rho _{ij} = \frac{ad - bc}{\sqrt{(a + b)(a + c)(c + d)(b + d)}} \in [-1, 1]$$

相关系数越接近 $-1$, 负相关程度越大; 越接近 $0$, 越不相关; 越接近 $1$, 正相关程度越大.

• $Q$-统计量 ($Q$-statistic)

$$Q_{ij} = \frac{ad - bc}{ad + bc}$$

总有 $\mathop{\mathrm{sgn}} Q_{ij} = \mathop{\mathrm{sgn}} \rho _{ij}$, 但 $|Q_{ij}| \leq |\rho _{ij}|$.

• $\kappa$-统计量 ($\kappa$-statistic)

$$\kappa = \frac{p_1 - p_2}{1 - p_2}$$

其中 $p_1$ 是两个分类器一致的概率, $p_2$ 是两个分类器偶然达成一致的概率:

$$p_1 = \frac{a + d}{m}, \quad p_2 = \frac{(a + b)(a + c) + (c + d)(b + d)}{m^2}$$

$\kappa$-统计量越接近 $1$, 说明两分类器越一致; 越接近 $0$, 说明他们越可能仅是偶然达成一致; 若为负值, 则说明它们达成一致的概率甚至低于偶然性.

8.5.3 多样性增强

  常通过引入随机扰动增强多样性.

• 数据样本扰动: 对于不稳定基学习器 (unstable base learner) 例如决策树和神经网络, 可以考虑在初始数据集采样出不同子集构成个体学习器. 但对于稳定基学习器 (stable base learner) 例如线性回归、支持向量机、朴素 Bayes、$k$-近邻学习器等无效.
• 输入属性扰动: 将输入空间换为样本空间的子空间. 随机子空间 (random subspace) 算法将每一个个体学习器的输入更换为样本空间中的随机 $d'$ 维, 从而减少冗余属性.
• 输出表示扰动: 操纵输出表示以增强多样性. 翻转法 (Flipping Output) 随机改变一些样本的标记; 输出调制法 (Output Smearing) 将个体学习器的分类输出转化为回归输出; ECOC 法利用纠错输出码将多分类任务拆解一系列二分类任务来训练个体学习器.
• 算法参数扰动: 对模型超参数进行扰动来生成个体学习器.