「机器学习」《机器学习》笔记

本系列Blog是基于周志华老师的《机器学习》一书的学习笔记。

第1章 绪论

机器学习（Machine Learning）致力于研究如何通过计算的手段，利用经验来改善系统自身的性能。在计算机系统中，“经验”通常以“数据”形式存在，因此，机器学习所研究的主要内容，是关于在计算机上从数据中学得“模型”（model）的算法，即“学习算法”（learning algorithm）。

一般地，我们用“模型”指从数据中学得的全局性结果（例如一棵决策树），而用“模式”指局部性结构（例如一条规则）。

1.1 基本术语

数据样本

要进行机器学习，先要有数据。

假定我们收集了一批关于西瓜的数据，例如：（色泽=青绿；根蒂=蜷缩；敲声=浊响），（色泽=乌黑；根蒂= 稍蜷；敲声=沉闷），（色泽=浅白；根蒂=硬挺；敲声=清脆），……

每对括号内是一条记录，这组记录的集合称为一个”数据集”（data set），其中：

• 每条记录是关于一个事件或对象（这里是一个西瓜）的描述，称为一个**”示例”（instance）或”样本”（sample）**；

• 反映事件或对象在某方面的表现或性质的事项，例如”色泽””根蒂””敲声”，称为**”属性”（attribute）或”特征”（feature）**;

• 属性上的取值，例如”青绿””乌黑”，称为**”属性值”（attribute value）**；

• 属性张成的空间称为”属性空间”（attribute space）、**”样本空间”（sample space）或”输入空间”（input space）**。

  例如我们把”色泽””根蒂” “敲声”作为三个坐标轴，则它们张成一个用于描述西瓜的三维空间，每个西瓜都可在这个空间中找到自己的坐标位置。

• 由于空间中的每个点对应一个坐标向量，因此我们也把一个示例称为一个**”特征向量”feature vector）**。

一般地，令 $D = {x_1, x_2, \dots, x_m}$ 表示包含 $m$ 个样本的数据集，每个样本由 $d$ 个属性描述（例如上面的西瓜数据使用了3个属性），则每个样本 $x_i = (x_{i1}; x_{i2}; \dots; x_{id})$ 是 $d$ 维样本空间 $\chi$ 中的一个向量，其中 $x_{ij}$ 表示 $x_i$ 在第 $j$ 个属性上的取值。

数据标签

如果希望学得一个能帮助我们判断没剖开的西瓜是不是“好瓜”的模型，我们还需获得训练样本的“结果”信息，例如“（（色泽=青绿；根蒂=蜷缩；敲声=浊响），好瓜）”。

• 这里关于示例结果的信息，例如“好瓜”，称为“标记”（label）；
• 拥有了标记信息的示例，则称为“样例”（example）。

一般地，用 $(x_i, y_i)$ 表示第 $i$ 个样例，其中 $y_i \in \gamma$ 是示例 $x_i$ 的标记，$\gamma$ 是所有标记的集合，亦称“标记空间”（label space）或“输出空间”（output space）。

训练模型

从数据中学得模型的过程称为”学习”（learning）或**”训练”（training）**，这个过程通过执行某个学习算法来完成。

• 训练过程中使用的数据称为”训练数据”（training data），其中每个样本称为一个”训练样本”（training sample），训练样本组成的集合称为**”训练集”（training set）**。
• 学得模型对应了关于数据的某种潜在的规律，因此亦称**”假设”（hypothesis），这种潜在规律自身，则称为“真相”（ground-truth）**；
• 学习过程就是为了找出或逼近ground-truth，学得的模型可以看作学习算法在给定数据和参数空间上的实例化。

测试模型

学得模型后，使用其进行预测的过程称为“测试”（testing），被预测的样本称为“测试样本”（testing sample）。例如在学得 $f$ 后，对测试例 $x$ ，可得到其预测标记 $y = f(x)$ 。

• 若我们欲预测的是离散值，例如“好瓜”“坏瓜”，此类学习任务称为 “分类”（lassification）；

  对只涉及两个类别的“二分类”（binary classification）任务，通常称其中一个类为“正类”（positive class），另一个类为“反类”（negative class）；涉及多个类别时，则称为“多分类”（multi-class classification）任务。

• 若欲预测的是连续值，例如西瓜成熟度0.95、0.37，此类学习任务称为“回归”（regression）。

一般地，预测任务是希望通过对训练集 ${ (x_1, y_1), (x_2, y_2), \dots, (x_m, y_m) }$ 进行学习，建立一个从输入空间 $\chi$ 到输出空间 $\gamma$ 的映射 $f: \chi \rightarrow \gamma $ 。

• 对二分类任务，通常令 $\gamma = {-1, +1}$ 或 ${0, 1}$ ；
• 对多分类任务，$|\gamma| > 2$ ；
• 对于回归任务，$\gamma = \mathbb{R}$ 。

根据训练数据是否拥有标记信息，学习任务可大致划分为两大类：“监督学习”（supervised learning）和“无监督学习”（unsupervised learning），分类和回归是前者的代表，而聚类则是后者的代表。

• 比如我们还可以对西瓜做“聚类”（clustering），即将训练集中的西瓜分成若干组，每组称为一个“簇”（cluster）；这些自动形成的簇可能对应一些潜在的概念划分，例如“浅色瓜”“深色瓜”，甚至“本地瓜”“外地瓜”。这样的学习过程有助于我们了解数据内在的规律，能为更深入地分析数据建立基础。

泛化能力

需注意的是，机器学习的目标是使学得的模型能很好地适用于“新样本”，而不是仅仅在训练样本上工作得很好，学得模型适用于新样本的能力，称为“泛化”（generalization）能力。具有强泛化能力的模型能很好地适用于整个样本空间，于是，尽管训练集通常只是样本空间的一个很小的采样，我们仍希望它能很好地反映出样本空间的特性。

• 通常我们假设样本空间中全体样本服从一个未知“分布”（distribution）$\mathbb{D}$，我们获得的每个样本都是独立地从这个分布上采样获得的，即“独立同分布”（independent and identicallydistributed，简称i.i.d.）。

一般而言，训练样本越多，我们得到的关于 $\mathbb{D}$ 的信息越多，这样就越有可能通过学习获得具有强泛化能力的模型。

1.2 归纳学习

归纳（induction）与演绎（deduction）是科学推理的两大基本手段。

• 前者是从特殊倒一般的“泛化”（generalization）过程，即从具体的事实归纳出一般性规律；
• 后者是从一般到特殊的“特化”（specialization）过程，即从基础原理推演出具体状况。

例如，在数学公理系统中，基于一组公理和推理规则推导出与之相洽的定力，这是演绎；而“从样例中学习”显然是一个归纳的过程，因此亦成为“归纳学习”（inductive learning）。

假设空间

我们可以把学习过程看作一个在所有假设（hypothesis）组成的空间中进行搜索的过程，搜索目标是找到与训练集“匹配”（fit）的假设，即能够将训练集中的瓜进行正确判断的假设。

需注意的是，现实问题中我们常面临很大的假设空间，但学习过程是基于有限样本训练集进行的，因此，可能有多个假设与训练集一致，即存在着一个与训练集一致的“假设集合”，我们称之为“版本空间”（version space）。

归纳偏好

机器学习算法在学习过程中对某种类型假设的偏好，称为“归纳偏好”（inductive bias）。

任何一个有效的机器学习算法必有其归纳偏好，否则它将被假设空间中看似在训练集上“等效”的假设所迷惑，而无法产生确定的学习结果。

可以想象，如果没有偏好，我们的西瓜学习算法产生的模型每次在进行预测时随机抽选训练集上的等效假设，那么对这个新瓜“（色泽=青绿；根蒂=蜷缩；敲声=沉闷）”，学得模型时而告诉我们它是好的、时而告诉我们它是不好的，这样的学习结果显然没有意义。

归纳偏好的作用在下面这个回归学习图示中可能更为直观。

这里的每个训练样本是图中的一个点 $(x，y)$ ，要学得一个与训练集一致的模型，相当于找到一条穿过所有训练样本点的曲线。显然，对有限个样本点组成的训练集，存在着很多条曲线与其一致。

• 我们的学习算法必须有某种偏好，才能产出它认为“正确”的模型。

归纳偏好可看作学习算法自身在一个可能很庞大的假设空间中对假设进行启发式选择。那么，有没有一般性的原则来引导算法确立“正确的”偏好呢？“奥卡姆剃刀”（Occam’s razor）是一种常用的、自然科学研究中最基本的原则，即“若有多个假设与观察一致，则选最简单的那个”。

• 如果采用这个原则，并且假设我们认为“更平滑”意味着“更简单”（例如曲线A更易于描述，其方程式是 $y=-x^2+6x+1$，而曲线B则要复杂得多），则在上图1.3中我们会自然地偏好“平滑”的曲线A。

没有免费的午餐

让我们再回头看看图1.3。假设学习算法 $£_a$ 基于某种归纳偏好产生了对应于曲线A的模型，学习算法 $£_b$ 基于另一种归纳偏好产生了对应于曲线B的模型。

• 基于前面讨论的平滑曲线的某种“描述简单性”，我们满怀信心地期待算法 $£_a$ 比 $£_b$ 更好。确实，图1.4（a）显示出，与B相比，A的泛化能力更强。
• 但是，且慢！虽然我们希望并相信 $£_a$ 比 $£_b$ 更好，但会不会出现图1.4(b)的情况：与A相比，B与训练集外的样本更一致？
• 很遗憾，这种情况完全可能出现。换言之，对于一个学习算法 $£_a$，若它在某些问题上比学习算法 $£_b$ 好，则必然存在另一些问题，在那里比 $£_a$ 好。

有趣的是，这个结论对任何算法均成立：

$$\sum_f E_{ote}(£_a|X,f) = \sum_f E_{ote}(£_b|X,f)$$

也就是说，无论学习算法 $£_a$ 多聪明、学习算法 $£_b$ 多笨拙，它们的期望性能是相同的！

• 这就是“没有免费的午餐”定理（NoFree Lunch Theorem，简称NFL定理）【Wolpert，1996；Wolpert and Macready，1995】

但我们需注意到，NFL定理有一个重要前提：所有“问题”出现的机会相同、或所有问题同等重要。但实际情形并不是这样。很多时候，我们只关注自己正在试图解决的问题（例如某个具体应用任务），希望为它找到一个解决方案，至于这个解决方案在别的问题、甚至在相似的问题上是否为好方案，我们并不关心。

• 所以，NFL定理最重要的寓意，是让我们清楚地认识到，脱离具体问题，空泛地谈论“什么学习算法更好”毫无意义，因为若考虑所有潜在的问题，则所有学习算法都一样好。
• 要谈论算法的相对优劣，必须要针对具体的学习问题；在某些问题上表现好的学习算法，在另一些问题上却可能不尽如人意，而学习算法自身的归纳偏好与问题是否相配，往往会起到决定性的作用。

1.3 思考与归纳

注意下面这句话：

通常我们假设样本空间中全体样本服从一个未知“分布”（distribution）$\mathbb{D}$，我们获得的每个样本都是独立地从这个分布上采样获得的，即“独立同分布”（independent and identicallydistributed，简称i.i.d.）。

以及，注意对归纳偏好的理解。

另外，深刻理解NFL定理的意义。

第2章 模型评估与选择

暂略

第3章 线性模型

3.1 基本形式

给定由 $d$ 个属性描述的示例 $\mathbf{x} = (x_1;x_2;\dots;x_d)$ ，其中 $x_i$ 是 $\mathbf{x}$ 在第 $i$ 个属性上的取值，线性模型（linear model）试图学得一个通过属性的线性组合来进行预测的函数，即

$$\begin{align} f(\mathbf{x}) = w_1x_1 + w_2x_2 + \dots + w_dx_d + b \tag{3.1} \end{align}$$

一般向量形式写成

$$\begin{align} f(\mathbf{x}) = \mathbf{w^T} \mathbf{x} + b \tag{3.2} \end{align}$$

其中 $\mathbf{w} = (w_1;w_2;\dots;w_d)$ 。

线性模型形式简单、易于建模，但却蕴涵着机器学习中一些重要的基本思想。

• 许多功能更为强大的非线性模型（nonlinear model）可在线性模型的基础上通过引入层级结构或高维映射而得。

• 此外，由于 $\mathbf{w}$ 直观表达了各属性在预测中的重要性，因此线性模型有很好的可解释性（comprehensibility）。

  例如若在西瓜问题中学得 “$f_{好瓜}(a)=0.2 \cdot 色泽 + 0.5 \cdot 工根蒂 + 0.3 \cdot 敲声 + 1$”，则意味着可通过综合考虑色泽、根蒂和敲声来判断瓜好不好，其中根蒂最要紧，而敲声比色泽更重要。

本章介绍几种经典的线性模型，我们先从回归任务开始，然后讨论二分类和多分类任务。

3.2 线性回归

给定数据集 $D = {(\mathbf{x_1}, y_1), (\mathbf{x}_2, y_2), \dots, (\mathbf{x_m}, y_m) }$ ，“线性回归”（linear regression）试图学得一个线性模型以尽可能准确地预测实值输出标记。

我们先考虑一种最简单的情形：输入属性的数目只有一个，即 $d=1$ 。

• 对离散属性，若属性值间存在“序”（order）关系，可通过连续化将其转化为连续值。

  例如二值属性“身高”的取值“高”“矮”可转化为{1.0，0.0}，三值属性“高度”的取值“高”“中”“低”可转化为{1.0，0.5，0.0}；

• 若属性值间不存在序关系，假定有k个属性值，则通常转化为k维向量。

  例如属性“瓜类”的取值“西瓜”“南瓜”“黄瓜”可转化为（0，0，1），（0，1，0），（1，0，0）。

  若将无序属性连续化，则会不恰当地引入序关系，对后续处理如距离计算等造成误导，参见9.3节。

线性回归试图学得

$$\begin{align} f(x_i) = wx_i + b \mbox{ ，使得 } f(x_i) \cong y_i \tag{3.3} \end{align}$$

那如何确定 $w$ 和 $b$ 呢？

• 显然，关键在于如何衡量 $f(x)$ 与 $y$ 之间的差别。

前面介绍过，均方误差是回归任务中最常用的性能度量，因此我们的目标为最小化均方误差，即：

$$\begin{align} (w*, b*) &= \underset{(w, b)}{\arg\min} \sum_{i=1}^m (f(x_i) - y_i)^2 \ &= \underset{(w, b)}{\arg\min} \sum_{i=1}^m (y_i - wx_i - b)^2 \tag{3.4} \end{align} $$

基于均方误差最小化来进行模型求解的方法称为“最小二乘法”（least square method）。

最小二乘法

在线性回归中，最小二乘法就是**试图找到一条直线，使所有样本到直线上的欧氏距离之和最小**。

图3.0  最小二乘法示意图

求解 $w$ 和 $b$ 使 $E_{(w, b)} = \sum_{i=1}^m (y_i - wx_i - b)^2$ 最小化的过程， 称为线性回归模型的最小二乘“参数估计”（parameter estimation）。

这里 $E_{(w,b)}$ 是关于 $w$ 和 $b$ 的凸函数，当它关于 $w$ 和 $b$ 的导数均为零时，得到 $w$ 和 $b$ 的最优解。

我们可将 $E_{(w, b)} $ 分别对 $w$ 和 $b$ 求导，得到

$$\begin{align} \frac{\partial E_{(w,b)}}{\partial w} &= 2\left(w\sum_{i=1}^mx_i^2 - \sum_{i=1}^m(y_i-b)x_i \right) \tag{3.5} \ \frac{\partial E_{(w,b)}}{\partial b} &= 2\left(mb - \sum_{i=1}^m(y_i - wx_i)\right) \tag{3.6} \end{align} $$

然后令式 $(3.5)$ 和 $(3.6)$ 为零可得到 $w$ 和 $b$ 最优解的闭式（closed-form）解

$$\begin{align} w &= \frac{\sum_{i=1}^m y_i(x_i - \bar{x})}{\sum_{i=1}^m x_i^2 - \frac{1}{m}(\sum_{i=1}^m x_i)^2} \tag{3.7} \ b &= \frac{1}{m} \sum_{i=1}^m (y_i - wx_i) \tag{3.8} \end{align} $$

其中 $\bar{x} = \frac{1}{m} \sum_{i=1}^m x_i$ 为 $x$ 的均值。

多元线性回归

更一般的情形是每个样本由 $d$ 个属性描述，这称为“多元线性回归”（multivariate linear regression）或“多变量线性回归”。

类似的，可利用最小二乘法来对 $w$ 和 $b$ 进行估计。

• 为便于讨论，我们把 $w$ 和 $b$ 记为向量形式 $\mathbf{\hat{w}} = (\mathbf{w};b)$

• 相应的，把数据集 $D$ 表示为一个 $m \times (d + 1)$ 大小的矩阵 $\mathbf{X}$ ，其中每行对应于一个示例，该行前 $d$ 个元素对应于示例的 $d$ 个属性值，最后一个元素恒置为1，即

  $$\mathbf{X} = \left( \begin{matrix}
  x_{11} & x_{12} & \cdots & x_{1d} & 1 \
  x_{21} & x_{22} & \cdots & x_{2d} & 1 \
  \vdots & \vdots & \ddots & \vdots \
  x_{m1} & x_{m2} & \cdots & x_{md} & 1 \

                    \end{matrix} \right) = \left( \begin{matrix} 

  \mathbf{x_1^T} & 1 \
  \mathbf{x_2^T} & 1 \
  \vdots & \vdots\
  \mathbf{x_m^T} & 1 \

                    \end{matrix} \right)$$

• 再把标记也写成向量形式 $\mathbf{y} = (y_1;y_2;\dots;y_m)$

则类似于式 $(3.4)$ ，有

$$\begin{align} \mathbf{\hat{w}^*} &= \underset{\hat{w}}{\arg\min} \mathbf{(y - X\hat{w})^T (y - X\hat{w})} \tag{3.9} \end{align}$$

令 $E_{\hat{w}} = \mathbf{(y - X\hat{w})^T (y - X\hat{w})} $ ，对 $\hat{w}$ 求导得到

$$\begin{align} \frac{\partial E_{\hat{w}}}{\partial \hat{w}} &= 2 \ \mathbf{X^T(X\hat{w}-y)} \tag{3.10} \end{align}$$

令上式为零可得 $\hat{w}$ 最优解的闭式解，但由于涉及矩阵逆的计算，比单变量情形要复杂一些，这里我们做一个简单的讨论。

当 $\mathbf{X^T} \mathbf{X}$ 为满秩矩阵（full-rank matrix）或正定矩阵（positive definite ma-trix）时，令式（3.10）为零可得

$$\begin{align} \hat{w}^* &= \mathbf{(X^T X)^{-1} X^T y} \tag{3.11} \end{align}$$

令 $\mathbf{\hat{x}} = (\mathbf{x_i, 1})$ ，则最终学得的多元线性回归模型为

$$\begin{align} f(\mathbf{\hat{x}_i}) &= \mathbf{\hat{x}_i^T (X^T X)^{-1} X^T y} \tag{3.12} \end{align} $$

注意，对于多元线性回归，我们的优化目标可以看作：

$$\begin{align} f(\mathbf{\hat{x}}) = \mathbf{X} \mathbf{\hat{w}} \mbox{ ，使得 } f(\mathbf{\hat{x}}) \cong \mathbf{y} \end{align}$$

那么可直接利用广义逆解得：

$$\mathbf{\hat{w}} = \mathbf{X^{+}} \mathbf{y}$$

对于广义逆，如果 $\mathbf{X^T} \mathbf{X}$ 为满秩矩阵（full-rank matrix），那么我们就有补充公式（可利用正SVD分解证明）：

$$\mathbf{X^{+}} = \mathbf{(X^{T}X)^{-1}} \mathbf{X^T} $$

进而有：

$$\mathbf{\hat{w}} = \mathbf{(X^{T}X)^{-1}} \mathbf{X^T} \mathbf{y}$$

可见，这与利用最小二乘法得到的结论是一致的。（矩阵理论nb！）

然而，现实任务中 $\mathbf{X^T} \mathbf{X}$ 往往不是满秩矩阵。例如在许多任务中我们会遇到大量的变量，其数目甚至超过样例数，导致 $\mathbf{X}$ 的列数多于行数， $\mathbf{X^T} \mathbf{X}$ 显然不满秩。

• 此时可解出多个 $\hat{w}$ ，它们都能使均方误差最小化。

选择哪一个解作为输出，将由学习算法的归纳偏好决定，常见的做法是引入正则化（regularization）项。

广义线性回归

线性模型虽简单，却有丰富的变化。

例如对于样例 $(\mathbf{x}, y)$ ，$y \in \mathbb{R}$ ，当我们希望线性模型（3.2）的预测值逼近输出标记（ground-truth）时，就得到了线性回归模型。此时我们可以将线性回归模型简写为

$$\begin{align} y = \mathbf{w^T x} + b \tag{3.13} \end{align}$$

那么可否令模型预测值逼近 $y$ 的衍生物呢？譬如说，假设我们认为示例所对应的输出标记是在指数尺度上变化，那就可将输出标记的对数作为线性模型逼近的目标，即

$$\begin{align} \ln y = \mathbf{w^T x} + b \tag{3.14} \end{align}$$

这就是“对数线性回归”（log-linear regression），它实际上是在试图让 $e^{\mathbf{w^T x} + b}$ 逼近 $y$ 。

• 式（3.14）在形式上仍是线性回归，但实质上已是在求取输入空间到输出空间的非线性函数映射。

如图3.1所示，这里的对数函数起到了将线性回归模型的预测值与真实标记联系起来的作用。

更一般地，考虑单调可微函数 $g(\cdot)$ ，令

$$\begin{align} y = g^{-1} (\mathbf{w^T x} + b) \tag{3.15} \end{align}$$

这样得到的模型称为“广义线性模型”（generalized linear model），其中函数 $g(\cdot)$ 称为“联系函数”（link function）。显然，对数线性回归是广义线性模型在 $g(\cdot) = ln(\cdot)$ 时的特例。

3.3 逻辑回归

上一节讨论了如何使用线性模型进行回归学习，但若要做的是分类任务该怎么办？答案蕴涵在式（3.15）的广义线性模型中：

• 只需找一个单调可微函数将分类任务的真实标记 $y$ 与线性回归模型的预测值联系起来即可。

比如我们考虑二分类任务，其输出标记 $y \in {0, 1}$，而线性回归模型产生的预测值 $z = \mathbf{w^T x} + b$ 是实值，于是，我们需将实值 $z$ 转换为 $0/1$ 值。

最理想的是“单位阶跃函数”（unit-step function）：

$$\begin{align} y = \begin{cases} 0, \ \ \ \ \ z < 0; \ 0.5, \ \ z = 0; \ 1, \ \ \ \ \ z > 0; \end{cases} \tag{3.16} \end{align}$$

即若预测值 $z$ 大于零就判为正例，小于零则判为反例，预测值为临界值零则可任意判别，如图3.2所示：

但从图3.2可看出，单位阶跃函数不连续，因此不能直接用作式（3.15）中的 $g^{-1}(\cdot)$ 。于是我们希望找到能在一定程度上近似单位阶跃函数的“替代函数”（surrogate function），并希望它单调可微 —— 对数几率函数（logisticfunction）正是这样一个常用的替代函数：

$$\begin{align} y = \frac{1}{1 + e^{-z}} \tag{3.17} \end{align}$$

从图3.2可看出，对数几率函数是一种“Sigmoid函数”，它能够将 $z$ 值转化为一个接近0或1的 $y$ 值，并且其输出值在 $z=0$ 附近变化很陡。

Sigmoid函数即形似S的函数，对率函数是Sig-moid函数最重要的代表。

将对数几率函数作为 $g^{-1}(\cdot) $ 代入式（3.15），得到

$$\begin{align} y = \frac{1}{1 + e^{-( \mathbf{w^T x} + b )}} \tag{3.18} \end{align} $$

类似于式（3.14），式（3.18）可变化为

$$\begin{align} \ln \frac{y}{1-y} = \mathbf{w^T x} + b \tag{3.19} \end{align}$$

若将 $y$ 视为样本 $x$ 作为正例的可能性，则 $1-y$ 是其作为反例的可能性，两者的比值即为

$$\begin{align} \frac{y}{1-y} \tag{3.20} \end{align}$$

称为“几率”（odds），反映了 $x$ 作为正例的相对可能性。

对几率取对数则得到“对数几率”（log odds，亦称logit）

$$\begin{align} \ln \frac{y}{1-y} \tag{3.21} \end{align}$$

由此可看出，式（3.18）实际上是在用线性回归模型的预测结果去逼近真实标记的对数几率，因此，其对应的模型称为“对数几率回归”（logistic regression），亦称逻辑回归（logit regression）。

特别需注意到，虽然它的名字是“回归”，但实际却是一种分类学习方法。这种方法有很多优点，例如

• 它是直接对分类可能性进行建模，无需事先假设数据分布，这样就避免了假设分布不准确所带来的问题；
• 它不是仅预测出“类别”，而是可得到近似概率预测，这对许多需利用概率辅助决策的任务很有用；
• 此外，对率函数是任意阶可导的凸函数，有很好的数学性质，现有的许多数值优化算法都可直接用于求取最优解。

极大似然估计

那么如何确定式（3.18）中的 $w$ 和 $b$ 呢？前面提到，$y$ 和 $1-y$ 分别表示 $x$ 作为正例和反例的可能性大小，我们不妨将它们视为类后验概率估计 $p(y=1|x)$ 和 $p(y=0|x)$ ，显然有

$$\begin{align} p(y=1|x) = \frac{e^{\mathbf{w^T x} + b}}{1 + e^{\mathbf{w^T x} + b}} \tag{3.23} \end{align} $$

$$\begin{align} p(y=0|x) = \frac{1}{1 + e^{\mathbf{w^T x} + b}} \tag{3.24} \end{align} $$

于是，我们可通过“极大似然法”（maximum likelihood method）来估计，若给定数据集 $D = {(\mathbf{x_i}, y_i)}_{i=1}^m$ ，则

• 对率回归模型（逻辑回归模型）就是最大化“对数似然”（log-likelihood）函数

  $$\begin{align} L(\mathbf{w}, b) = \sum_{i=1}^m \ln p(y_i | \mathbf{x_i}; \mathbf{w}, b) \tag{3.25} \end{align}$$

  即令每个样本属于其真实标记的概率越大越好。

为便于讨论，我们

• 令 $\mathbf{\hat{w}} = (\mathbf{w}; b)$ ，$\mathbf{\hat{x}} = (\mathbf{x};1)$ ，则 $\mathbf{w^T x} + b$ 可以简写为 $\mathbf{\hat{w}^T \hat{x}}$ ；
• 再令 $p_1(\mathbf{\hat{x}; \hat{w}}) = p(y = 1 | \mathbf{\hat{x}; \hat{w}})$ ，$p_0(\mathbf{\hat{x}; \hat{w}}) = p(y = 0 | \mathbf{\hat{x}; \hat{w}}) = 1 - p_1(\mathbf{\hat{x}; \hat{w}}) $ 。

则式（3.25）中的似然项可重写为

$$\begin{align} p(y_i | \mathbf{x_i}; \mathbf{w}, b) = y_i p_1(\mathbf{\hat{x_i}; \hat{w}}) + (1 - y_i) p_0(\mathbf{\hat{x_i}; \hat{w}}) \tag{3.26} \end{align}$$

#? question

这里似然项的展开，并没有完全理解，这是信息熵演变而来的吗？

#! answer

不是，注意这里 $y_i$ 为0或1，因此上（3.26）实际只会有一项。

将式（3.26）代入（3.25），并根据式（3.23）和（3.24）可知，最大化式（3.25）等价于最小化

$$\begin{align} L(\mathbf{\hat{w}}) = \sum_{i=1}^m \left( -y_i \mathbf{\hat{w}^T \hat{x}} + \ln (1 + e^{\mathbf{\hat{w}^T \hat{x}}}) \right) \tag{3.27} \end{align}$$

注意到 $y_i$ 为0或1，因此可分别将两种情况代入并综合即可得到上式，具体证明见【南瓜书-P10】。

式（3.27）是关于 $\mathbf{\hat{w}}$ 的高阶可导连续凸函数，根据凸优化理论【Boyd and Vandenberghe，2004】，或经典的数值优化算法如梯度下降法（gradient descent method）、牛顿法（Newton method）等都可求得其最优解。

于是就得到

$$\begin{align} \mathbf{\hat{w}}^* = \underset{\mathbf{\hat{w}}}{\arg\min} \ L(\mathbf{\hat{w}}) \tag{3.28} \end{align}$$

3.4 线性判别分析

线性判别分析（Linear Discriminant Analysis，简称LDA）是一种经典的线性学习方法，在二分类问题上因为最早由【Fisher，1936】提出，亦称“Fisher判别分析”。

LDA的思想非常朴素：

• 给定训练样例集，设法将样例投影到一条直线上，使得同类样例的投影点尽可能接近、异类样例的投影点尽可能远离；
• 在对新样本进行分类时，将其投影到同样的这条直线上，再根据投影点的位置来确定新样本的类别

图3.3给出了一个二维示意图：

令 $X_i、\mu_i、\Sigma_i$ 分别表示第 $i \in {0, 1}$ 类示例的集合、均值向量、协方差矩阵。

• 若将数据投影到直线 $y = w^Tx$ 上，则两类样本的中心在直线上的投影分别为 $w^T \mu_0$ 和 $w^T \mu_1$ ；
• 若将所有样本点都投影到直线上，则两类样本的协方差分别为 $w^T \Sigma_0 w$ 和 $w^T \Sigma_1 w$ 。

由于直线是一维空间，因此 $w^T \mu_0$ 、 $w^T \mu_1$ 、 $w^T \Sigma_0 w$ 和 $w^T \Sigma_1 w$ 均为实数。

• 欲使同类样例的投影点尽可能接近，可以让同类样例投影点的协方差尽可能小，即 $w^T \Sigma_0 w + w^T \Sigma_1 w$ 尽可能小；
• 而欲使异类样例的投影点尽可能远离，可以让类中心之间的距离尽可能大，即 $ ||w^T \mu_0 - w^T \mu_1||^2$ 尽可能大。

同时考虑二者，则可得到欲最大化的目标

$$\begin{align} J &= \frac{||w^T \mu_0 - w^T \mu_1||^2}{w^T \Sigma_0 w + w^T \Sigma_1 w} \ &= \frac{w^T (\mu_0 - \mu_1)(\mu_0 - \mu_1)^T w}{w^T (\Sigma_0 + \Sigma_1) w} \tag{3.32} \end{align}$$

• 定义“类内散度矩阵”（within-class scatter matrix）

  $$\begin{align} S_w &= \Sigma_0 + \Sigma_1 \ &= \sum_{x \in X_0} (x - \mu_0)(x - \mu_0)^T + \sum_{x \in X_1} (x - \mu_1)(x - \mu_1)^T \tag{3.33} \end{align}$$

• 以及“类间散度矩阵”（between-class scatter matrix）

  $$\begin{align} S_b = (\mu_0 - \mu_1)(\mu_0 - \mu_1)^T \tag{3.34} \end{align}$$

则式（3.32）可重写为

$$\begin{align} J = \frac{w^T S_b w}{w^T S_w w} \tag{3.35} \end{align}$$

这就是LDA欲最大化的目标，即 $S_b$ 与 $S_w$ 的“广义瑞利商”（generalized Rayleigh quotient)。

拉格朗日乘子法

如何确定 $w$ 呢？注意到式（3.35）的分子和分母都是关于 $w$ 的二次项，因此式（3.35）的解与 $w$ 的长度无关，只与其方向有关。

因此令 $w^T S_w w= 1 $ 不失一般性 ，则式（3.35）等价于

$$\begin{align} \min_{w} \ \ -w^TS_bw \ s.t. \ \ w^TS_ww = 1 \tag{3.36} \end{align}$$

由拉格朗日乘子法，能够求得

$$\begin{align} w = S_w^{-1}(\mu_0 - \mu_1) \tag{3.39} \end{align}$$

详见【南瓜书- P11】

此外，书中还提到了“考虑到数值解的稳定性，在实践中通常是对S进行奇异值分解…”

LDA多分类任务

loading…

• 3.5 多分类学习

• 3.6 类别不平衡问题

3.7 思考与归纳

在前面介绍的线性模型中，实际上目标均为使 $\mathbf{w^T x} + b$ 尽可能地拟合 $y$ ，不同之处仅在于优化算法，或者说使用的准则函数不同，如：

• 最常见的最小二乘法，即最小平方误差准则（MSE），优化目标为最小化样本点到直线的距离。
• LDA法，或称Fisher准则，优化目标为使类内距离尽可能小，类间距离尽可能大，其考虑的是样本在直线上的投影点之间的距离。
• 还有一种感知机准则，亦即神经网络采用的优化函数，常使用梯度下降法进行优化。

第4章 决策树

4.1 基本流程

决策树（decision tree）是一类常见的机器学习方法。顾名思义，决策树是基于树结构来进行决策的，这恰是人类在面临决策问题时一种很自然的处理机制。

例如，我们要对“这是好瓜吗？”这样的问题进行决策时，通常会进行一系列的判断或“子决策”，如图4.1所示：

一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点：

• 叶结点对应于决策结果；
• 其他每个结点则对应于一个属性测试，每个结点包含的样本集合根据属性测试的结果被划分到子结点中；
• 根结点包含样本全集，从根结点到每个叶结点的路径对应了一个判定测试序列。

决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循简单且直观的“分而治之”（divide-and-conquer）策略，如图4.2所示。

显然，决策树的生成是一个递归过程。

在决策树基本算法中，有三种情形会导致递归返回：

1. 当前结点包含的样本全属于同一类别，无需划分；
2. 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分；
3. 当前结点包含的样本集合为空，不能划分.

• 在第（2）种情形下，我们把当前结点标记为叶结点，并将其类别设定为该结点所含样本最多的类别；

• 在第（3）种情形下，同样把当前结点标记为叶结点，但将其类别设定为其父结点所含样本最多的类别。

注意这两种情形的处理实质不同：

情形（2）是在利用当前结点的后验分布，而情形（3）则是把父结点的样本分布作为当前结点的先验分布。

4.2 划分选择

由算法4.2可看出，决策树学习的关键是第8行，即如何选择最优划分属性。

• 一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”（purity）越来越高。

4.2.1 信息增益

“信息熵”（information entropy）是度量样本集合纯度最常用的一种指标。

假定当前样本集合 $D$ 中第 $k$ 类样本所占的比例为 $p_k(k=1,2,\dots,|\gamma|)$ ，则样本集 $D$ 的信息熵定义为

$$\begin{align} \text{Ent}(D) = - \sum_{k=1}^{|\gamma|} p_k \log_2 p_k \tag{4.1} \end{align} $$

计算信息熵时约定：若 $p = 0$ ，则 $p \log_2 p = 0.$

$Ent(D)$ 的值越小，则 $D$ 的纯度越高。$Ent(D)$ 的最小值为0，最大值为 $\log_2 |\gamma|$ 。

假定离散属性 $a$ 有 $V$ 个可能的取值 ${ a^1, a^2, \dots, a^V }$ ，若使用 $a$ 来对样本集 $D$ 进行划分，则会产生 $V$ 个分支结点，其中第 $v$ 个分支结点包含了 $D$ 中所有在属性 $a$ 上取值为 $a^v$ 的样本，记为 $D^v$ 。那么我们便可根据式（4.1）计算出 $D^v$ 的信息熵。

考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重 $|D^v|/|D|$ ，即样本数越多的分支结点的影响越大。

于是可计算出属性 $a$ 对样本集 $D$ 进行划分所获得的“信息增益”（information gain）：

$$\begin{align} \text{Gain}(D, a) = \text{Ent}(D) - \sum_{v=1}^V \frac{|D^v|}{|D|} \text{Ent}(D^v) \tag{4.2} \end{align} $$

• 一般而言，信息增益越大，则意味着使用属性 $a$ 来进行划分所获得的“纯度提升”越大。

因此，我们可用信息增益来进行决策树的划分属性选择，即在图4.2算法第8行选择属性：

$$\begin{align} a_* = \arg\max_{a \in A} Gain(D, a). \end{align}$$

• 著名的ID3决策树学习算法【Quinlan，1986】就是以信息增益为准则来选择划分属性。

ID3 名字中的 ID 是 Iterative Dichotomiser （迭代二分器）的简称.

4.2.2 增益率

实际上，信息增益准则对可取值数目较多的属性有所偏好。

比如若样本集 $D$ 大小为 17，如果把“编号”也作为一个候选划分属性，则根据式（4.2）可计算出它的信息增益为 0.998。

这很容易理解，因为“编号”将产生17个分支，且每个分支仅包含一个样本，这些分支样本的纯度已达最大。

然而，这样的决策树显然不具有泛化能力，无法对新样本进行有效预测。

为减少这种偏好可能带来的不利影响，著名的C4.5决策树算法【Quinlan，1993】不直接使用信息增益，而是使用“增益率”（gain ratio）来选择最优划分属性：

$$\begin{align} \text{Gain_ratio} \ (D, a) = \frac{\text{Gain}(D, a)}{\text{IV}(a)} \tag{4.3} \end{align} $$

其中

$$\begin{align} \text{IV}(a) = - \sum_{v=1}^V \frac{|D^v|}{|D|} \ \log_2 \frac{|D^v|}{|D|} \tag{4.4} \end{align} $$

称为属性 $a$ 的“固有值”（intrinsic value）。

• 属性 $a$ 的可能取值数目越多（即 $V$ 越大），则 $\text{IV}(a)$ 的值通常会越大。

需注意的是，增益率准则对可取值数目较少的属性有所偏好，因此，C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：

• 先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

4.2.3 基尼指数

CART决策树【Breiman et al.，1984】使用“基尼指数”（Gini index）来选择划分属性，样本集 $D$ 的纯度可用基尼值来度量：

$$\begin{align} \text{Gini}(D) &= \sum_{k=1}^{|\gamma|} \sum_{k’ \neq k} p_k p_{k’} \ &= 1 - \sum_{k=1}^{|\gamma|}p_k^2 \tag{4.5} \end{align}$$

CART是Classificationand Regression Tree的简称，这是一种著名的决策树学习算法，分类和回归任务都可用.

直观来说，$\text{Gini}(D)$ 反映了从数据集 $D$ 中随机抽取两个样本，其类别标记不一致的概率。因此，$\text{Gini}(D)$ 越小，则数据集D的纯度越高。

那么，属性 $a$ 的基尼指数定义为

$$\begin{align} \text{Gini_index}(D, a) = \sum_{v=1}^V \frac{|D^v|}{|D|} \text{Gini}(D^v) \tag{4.6} \end{align} $$

4.3 剪枝处理

剪枝（pruning）是决策树学习算法对付“过拟合”的主要手段。

在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，这时就可能因训练样本学得“太好”了，

• 以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合。

因此，可通过主动去掉一些分支来降低过拟合的风险。

决策树剪枝的基本策略有“预剪枝”（prepruning）和 “后剪枝”（post-pruning）。

4.3.1 预剪枝

预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。

泛化性能可以在验证集上进行评估。

预剪枝策略特点：

• 优势：“剪掉”很多没必要展开的分支，降低了过拟合风险，并且显著减少了决策树的训练时间开销和测试时间开销.
• 劣势：有些分支的当前划分有可能不能提高甚至降低泛化性能，但后续划分有可能提高泛化性能，预剪枝禁止这些后续分支的展开，可能会导致欠拟合.

4.3.2 后剪枝

后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。

后剪枝策略特点：

• 优势：测试了所有分支，比预剪枝决策树保留了更多分支，降低了欠拟合的风险，泛化性能一般优于预剪枝决策树.
• 劣势：后剪枝过程在生成完全决策树后再进行，且要自底向上对所有非叶节点逐一评估，因此，决策树的训练时间开销要高于未剪枝决策树和预剪枝决策树.

4.4 连续与缺失值

4.4.1 连续值处理

现实任务中常会遇到连续属性，此时可将连续属性进行离散化，最简单的策略是采用二分法（bi-partition），这也正是C4.5决策树算法中采用的机制。

给定样本集 $D$ 和连续属性 $a$ ， 假定 $a$ 在 $D$ 上出现了 $n$ 个不同的取值，将这些值从小到大进行排序，记为 ${ a^1, a^2, \dots, a^n }$ .

• 基于某个划分点 $t$ 可将 $D$ 分为子集 $D_t^-$ 和 $D_t^+$ ，其中 $D_t^-$ 包含那些在属性 $a$ 上取值不大于 $t$ 的样本，而 $D_t^+$ 则包含那些在属性 $a$ 上取值大于 $t$ 的样本。

显然，对相邻的属性取值 $a^i$ 与 $a^{i+1}$ 来说，$t$ 在区间 $[a^i, a^{i+1})$ 中取任意值所产生的划分结果相同。

因此，对连续属性 $a$ ，我们可考察包含 $n-1$ 个元素的候选划分点集合

$$\begin{align} T_a = { \frac{a^i + a^{i+1}}{2} \ \ | \ \ 1 \leq i \leq n-1 } \tag{4.7} \end{align}$$

即把区间 $[a^i, a^{i+1})$ 的中位点 $\frac{a^i + a^{i+1}}{2}$ 作为候选划分点 $t_i$ ，这样便能得到 $n-1$ 对划分。

• 然后，我们就可像离散属性值一样来考察这些划分，并选取最优的划分点进行样本集合的划分。

例如，可对式（4.2）稍加改造：

$$\begin{align} \text{Gain}(D, a) &= \max_{t \in T_a} \text{Gain}(D, a, t) \ &= \max_{t \in T_a} \ ( \text{Ent}(D) - \sum_{\lambda \in {-, +}} \frac{|D^{\lambda}_t|}{|D|} \text{Ent}(D^{\lambda}_t)) \tag{4.8} \end{align} $$

其中 $\text{Gain} (D, a, t)$ 是样本集 $D$ 基于划分点 $t$ 二分后的信息增益。

于是，我们就可选择使 $\text{Gain} (D, a, t)$ 最大化的划分点来作为连续属性 $a$ 的信息增益。

4.4.2 缺失值处理

现实任务中常会遇到不完整样本，即样本的某些属性值缺失。尤其是在属性数目较多的情况下，往往会有大量样本出现缺失值。

例如由于诊测成本、隐私保护等因素，患者的医疗数据在某些属性上的取值（如HIV测试结果）未知.

如果简单地放弃不完整样本，仅使用无缺失值的样本来进行学习，显然是对数据信息的极大浪费。因此，有必要考虑利用有缺失属性值的训练样例来进行学习。

那么我们便需要解决两个问题：

1. 如何在属性值缺失的情况下进行划分属性选择？
2. 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？

给定训练集 $D$ 和属性 $a$ ，令 $\tilde{D}$ 表示 $D$ 中在属性 $a$ 上没有缺失值的样本子集。

对问题（1）

显然我们可根据 $\tilde{D}$ 来判断属性 $a$ 的优劣，假定属性 $a$ 有 $V$ 个可取值 ${ a^1, a^2, \dots, a^V }$ ，

• 令 $\tilde{D}^v$ 表示 $\tilde{D}$ 中在属性 $a$ 上取值为 $a^v$ 的样本子集，
• $\tilde{D_k}$ 表示 $\tilde{D}$ 中属于第 $k$ 类（$k = 1, 2, \dots, |\gamma|$）的样本子集，

则显然有 $\tilde{D} = \cup_{k=1}^{|\gamma|} \tilde{D}k$ ， $\tilde{D} = \cup{v=1}^{V} \tilde{D}^v$ .

一个是按类别划分，一个是按属性取值划分.

假定我们为每个样本 $x$ 赋予一个权重 $w_x$ ，并定义

$$\begin{align} \rho = \frac{\sum_{x \in \tilde{D}} w_x}{\sum_{x \in D} w_x} \tag{4.9} \end{align}$$

$$\begin{align} \tilde{p}k = \frac{\sum{x \in \tilde{D}_k} w_x}{\sum_{x \in \tilde{D}} w_x} \ , \ (1 \leq k \leq |\gamma|) \tag{4.10} \end{align}$$

$$\begin{align} \tilde{r}v = \frac{\sum{x \in \tilde{D}^v} w_x}{\sum_{x \in \tilde{D}} w_x} \ , \ (1 \leq v \leq V) \tag{4.11} \end{align}$$

直观地看，对于属性 $a$ ，

• $\rho$ 表示无缺失值样本所占的比例
• $\tilde{p}_k$ 表示无缺失值样本中第 $k$ 类所占的比例
• $\tilde{r}_v$ 则表示无缺失值样本中在属性 $a$ 上取值 $a^v$ 的样本所占的比例

显然，$\sum_{k=1}^{|\gamma|} \tilde{p}k = 1$ ，$\sum{v=1}^V \tilde{r}^v = 1$ .

基于上述定义，我们可将信息增益的计算式（4.2）推广为

$$\begin{align} \text{Gain}(D, a) &= \rho \times \text{Gain}(\tilde{D}, a) \ &= \rho \times ( \text{Ent}(\tilde{D}) - \sum_{v=1}^V \tilde{r}_v \text{ Ent}(\tilde{D}^v) ) \tag{4.12} \end{align} $$

对问题（2）

• 若样本 $x$ 在划分属性 $a$ 上的取值已知，则将 $x$ 划入与其取值对应的子结点，且样本权值在子结点中保持为 $w_x$
• 若样本 $x$ 在划分属性 $a$ 上的取值未知，则将 $x$ 同时划入所有子结点，且样本权值在与属性值 $a^v$ 对应的子结点中调整为 $\tilde{r}_v · w_x $ .

直观地看，这就是让同一个样本以不同的概率划入到不同的子结点中去。

C4.5算法便使用了上述解决方案。

4.5 多变量决策树

若我们把每个属性视为坐标空间中的一个坐标轴，则由 $d$ 个属性描述的样本就对应 $d$ 维空间中的一个数据点。

• 对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界。

决策树所形成的分类边界有一个明显的特点：轴平行（axis-parallel），即它的分类边界由若干个与坐标轴平行的分段组成。

这样的分类边界使得学习结果有较好的可解释性，因为每一段划分都直接对应了某个属性取值。

但在学习任务的真实分类边界比较复杂时，必须使用很多段划分才能获得较好的近似，此时的决策树会相当复杂，由于要进行大量的属性测试，预测时间开销会很大。

如图4.12所示，若能使用斜的划分边界，则决策树模型将大为简化。

“多变量决策树”（multivariate decision tree）就是能实现这样的“斜划分”甚至更复杂划分的决策树，亦称“斜决策树”（oblique decision tree)。

• 在此类决策树中，非叶结点不再是仅对某个属性，而是对属性的线性组合进行测试；

• 换言之，每个非叶结点是一个形如 $\sum_{i=1}^d w_i a_i = t $ 的线性分类器.

  其中 $w_i$ 是属性 $a_i$ 的权重。

于是，与传统的“单变量决策树”（univariate decision tree）不同，在多变量决策树的学习过程中，不是为每个非叶结点寻找一个最优划分属性，而是试图建立一个合适的线性分类器。

4.6 思考与归纳

决策树的思想较为简单，理解算法4.2即可。

第5章 神经网络

5.1 神经元模型

神经网络中最基本的成分是神经元（neuron）模型。

• 在生物神经网络中，每个神经元与其他神经元相连，当它“兴奋”时，就会向相连的神经元发送化学物质，从而改变这些神经元内的电位；
• 如果某神经元的电位超过了一个“阈值”（threshold），那么它就会被激活，即“兴奋”起来，继续向其他神经元发送化学物质。

1943年，【McCulloch and Pitts，1943】将上述情形抽象为图5.1所示的简单模型，这就是一直沿用至今的“M-P神经元模型”。

• 在该模型中，神经元接收到来自n个其他神经元传递过来的输入信号，这些输入信号通过带权重的连接（connection）进行传递，神经元接收到的总输入值将与神经元的阈值进行比较，然后通过“激活函数”（activation function）处理以产生神经元的输出。

理想中的激活函数是图5.2（a）所示的阶跃函数，它将输入值映射为输出值“0”或“1”。

然而，阶跃函数具有不连续、不光滑等不太好的性质，因此实际常用Sigmoid函数作为激活函数，如图5.2（b）所示。

把许多个这样的神经元按一定的层次结构连接起来，就得到了神经网络。

5.2 感知机与多层网络

感知机（Perceptron）由两层神经元组成，如图5.3所示，输入层接收外界输入信号后传递给输出层，输出层是M-P神经元，亦称“阈值逻辑单元”（threshold logic unit），其数学形式为 $y = f(\sum_i w_i x_i - b)$。

给定训练数据集，权重 $w_i (i = 1, 2, \dots, n)$ 以及偏置 $b$ 可通过学习得到。

• 偏置 $b$ 可看作一个固定输入为 $-1.0$ 的“哑结点”（dummy node），其对应的权重为 $w_{n+1}$ ，这样权重和偏置的学习就可统一为权重的学习。

感知机学习规则非常简单，对训练样例 $(\vec{x}, y)$ ，若当前感知机的输出为 $\hat{y}$ ，则感知机权重将这样调整：

$$\begin{align} w_i \larr w_i + \Delta w_i \tag{5.1} \end{align}$$

$$\begin{align} \Delta w_i \larr \eta (y - \hat{y})x_i \tag{5.2} \end{align}$$

其中，$\eta \in (0, 1)$ 称为学习率（learning rate），$x_i$ 是 $\vec{x}$ 对英语第 $i$ 个输入神经元的分量。

从式（5.1）可看出，

• 若感知机对训练样例 $(\vec{x}, y)$ 预测正确，即 $y - \hat{y}$，则感知机不发生变化
• 否则将根据错误的程度进行权重调整.

需注意的是，感知机只有输出层神经元进行激活函数处理，即只拥有一层功能神经元（functional neuron），其学习能力非常有限，例如感知机甚至不能解决异或这样简单的非线性可分问题。

• 要解决非线性可分问题，需考虑使用多层功能神经元。

例如图5.5中这个简单的两层感知机就能解决异或问题。

• 在图5.5（a）中，输出层与输入层之间的一层神经元，被称为隐层或隐藏层（hidden layer），隐藏层和输出层神经元都是拥有激活函数的功能神经元。

更一般的，常见的神经网络是形如图5.6所示的层级结构，每层神经元与下一层神经元全互连，神经元之间不存在同层连接，也不存在跨层连接，这样的神经网络结构通常称为“多层前馈神经网络”（multi-layer feedforward neural networks）。

注意：

输入层神经元仅是接受输入，不进行函数处理，隐层与输出层则包含功能神经元。

5.3 误差反向传播算法

欲训练多层网络，式（5.1）的简单感知机学习规则显然不够了，需要更强大的学习算法——误差逆传播（errorBackPropagation，简称BP）算法。

数学推导

给定训练集 $D = { (x_1, y_1), (x_2, y_2), \dots, (x_m, y_m) } , x_i \in \mathbb{R}^d, y_i \in \mathbb{R}^l$ ，即输入样例由 $d$ 个属性描述，输出 $l$ 维向量。

图5.7给出了一个拥有 $d$ 个输入神经元、$l$ 个输出神经元，以及 $q$ 个隐层神经元的多层前馈网络结构。

其中，

• 输入层第 $i$ 个神经元与隐藏层第 $h$ 个神经元之间的连接权重为 $w^{(1)}_{ih}$ ；
• 隐藏层第 $h$ 个神经元的偏置用 $b^{(1)}h$ 表示，隐藏层第 $h$ 个神经元与输出层第 $j$ 个神经元的连接权重为 $w^{(2)}{hj}$ ；
• 输出层第 $j$ 个神经元的偏置用 $b^{(2)}_j$ 表示；

注意，这里的变量是按照自己的理解写的，与图5.7并不一一对应。

本节实际推导过程中的变量定义是按下表来的：

	输入层 i	隐藏层 h	输出层 j
input	$a^{(0)}_i = x_i $	$a^{(1)}h = \sum{i=1}^d w^{(1)}_{ih} x_i + b^{(1)}_h$	$a^{(2)}j = \sum{h=1}^q w^{(2)}_{hj} z_h + b^{(2)}_j$
output	$x_i $	$z_h = f(a^{(1)}_h)$	$y_j = f(a^{(2)}_j)$
weight	-	$w^{(1)}_{ih} $	$w^{(2)}_{hj}$
bias	-	$b^{(1)}_h$	$b^{(2)}_j$

但实际上，一般来说 $a$ 常作为激活值，$z$ 一般作为输入值，因此一个更容易扩写且让本强迫症比较满意的变量定义如下：

	输入层 i	隐藏层 h	输出层 j
input	$z^{(0)}_i = x_i$	$z^{(1)}h = \sum{i=1}^d w^{(1)}_{ih} a^{(0)}_i + b^{(1)}_h$	$z^{(2)}j = \sum{h=1}^q w^{(2)}_{hj} a^{(1)}_h + b^{(2)}_j$
output	$a^{(0)}_i = x_i$	$a^{(1)}_h = f(z^{(1)}_h)$	$a^{(2)}_j = f(z^{(2)}_j)$ ，即 $y_j$

假设隐藏层和输出层神经元均使用图5.2（b）中的Sigmoid 函数（对率几率函数）作为激活函数，则记

• 输入层不进行任务处理，因此第 $i$ 个神经元的输入与输出均为 $x_i$ ；
• 隐藏层第 $h$ 个神经元接收到的输入为 $a^{(1)}{h} = \sum{i=1}^d w^{(1)}_{ih} x_i$ ，输出为 $z^{(1)}_h = f(a^{(1)}_h)$ ；
• 输出层第 $j$ 个神经元接收到的输入为 $a^{(2)}{j} = \sum{h=1}^q w^{(2)}_{hj} z^{(1)}_h$ ，输出为 $z^{(2)}_j = f(a^{(2)}_j) = \hat{y}_j$；

那么网络在样例 $(x_k, y_k)$ 上的均方误差即为

$$\begin{align} E_k = \frac{1}{2} \sum_{j=1}^l (\hat{y}^k_j - y^k_j)^2 \tag{5.4} \end{align} $$

BP算法采用式（5.1）来更新参数，并基于梯度下降（gradient descent）策略，以目标的负梯度方向对参数进行调整。

1）计算 $\Delta w^{(2)}_{hj}$

对式（5.4）的误差 $E_k$ ，给定学习率 $\eta$ ，有

$$\begin{align} \Delta w^{(2)}_{hj} = - \eta \frac{\part E_k}{\part w^{(2)}_{hj}} \tag{5.6} \end{align} $$

注意到 $w^{(2)}_{hj}$ 先影响到第 $j$ 个输出层神经元的输入值 $a^{(2)}_j$ ，再影响到其输出值 $\hat{y}^k_j$ ，然后才影响到 $E_k$ ，故又

$$\begin{align} \frac{\part E_k}{\part w^{(2)}_{hj}} = \frac{\part E_k}{\part \hat{y}^k_j} · \frac{\part \hat{y}^k_j}{\part a^{(2)}_j} · \frac{\part a^{(2)}j}{\part w^{(2)}{hj}} \tag{5.7} \end{align} $$

现在问题是化简式（5.7）。

我们知道Sigmoid函数有一个很好的性质：

$\begin{align} f’(x) = f(x)(1 - f(x)) \tag{5.8} \end{align}$

于是有根据式（5.4）有：

$$\begin{align} g^{(2)}_j &= \frac{\part E_k}{\part \hat{y}^k_j} · \frac{\part \hat{y}^k_j}{\part a^{(2)}_j} \ &= (\hat{y}^k_j - y^k_j) \hat{y}^k_j (1 - \hat{y}^k_j) \tag{5.9} \end{align}$$

又由前述 $a^{(2)}_j$ 的定义可知：

$\begin{align} \frac{\part a^{(2)}j}{\part w^{(2)}{hj}} = z^{(1)}_h \tag{5.10} \end{align} $

把式（5.9）和式（5.10）带入式（5.7）中，再代入式（5.6）中，可得第二层神经元 $w^{(2)}_{hj}$ 的更新公式

$$\begin{align} \Delta w_{hj} = - \eta g^{(2)}_j z^{(1)}_h \tag{5.11} \end{align} $$

2）计算 $\Delta w^{(1)}_{ih}$

由于隐藏层的第 $h$ 个神经元与输出层的 $l$ 个神经元均有连接，因此在反向传播时需要考虑所有的 $\sum_{j=1}^l w^{(2)}_{hj} z^{(1)}_h $ .

因此有

$$\begin{align} \frac{\part E_k}{\part w^{(1)}{ih}} &= \sum{j=1}^l \frac{\part E_k}{\part \hat{y}^k_j} · \frac{\part \hat{y}^k_j}{\part a^{(2)}j} · \frac{\part a^{(2)}j}{\part z^{(1)}{h}} · \frac{\part z^{(1)}h}{\part a^{(1)}{h}} · \frac{\part a^{(1)}h}{\part w{ih}} \ &= \sum{j=1}^l g^{(2)}j \cdot w{hj} \ \cdot z^{(1)}_h (1 - z^{(1)}_h) \ \cdot x_i \tag{5.12} \end{align} $$

令 $g^{(1)}h = z^{(1)}_h (1 - z^{(1)}_h) \ \cdot \sum{j=1}^l w_{hj} \cdot g^{(2)}_j$

则有

$$\begin{align} \Delta w^{(2)}_{hj} &= - \eta \frac{\part E_k}{\part w^{(2)}_{hj}} \ &= - \eta g^{(1)}_h x_i \tag{5.13} \end{align} $$

3）计算偏置 $\Delta b^{(1)}_h$ 与 $\Delta b^{(2)}_j$

正如5.2节提到的，「偏置 $b$ 可看作一个固定输入为 $-1.0$ 的哑结点」，因此可直接将 $-1.0$ 带入式（5.11）与式（5.12）即得

$$\begin{align} \Delta b^{(2)}_j = \eta g^{(2)}_j \tag{5.13} \end{align} $$

$$\begin{align} \Delta b^{(1)}_h = \eta g^{(1)}_h \tag{5.14} \end{align} $$

算法流程

BP算法的工作流程如下：

需注意的是，BP算法的目标是要最小化训练集 $D$ 上的累积误差：

$$\begin{align} E = \frac{1}{m} \sum_{k=1}^m E_k \tag{5.16} \end{align}$$

但我们上面介绍的“标准BP算法”每次仅针对一个训练样例更新连接权和偏置，参数更新得非常频繁，而且对不同样例进行更新的效果可能出现“抵消”现象。

因此，在实际训练中，我们常采用随机梯度下降的方法进行参数更新，详见「深度学习」神经网络中的优化算法。

残差网络中的BP

详见 残差网络解决了什么，为什么有效？ .

5.4 全局最小与局部极小

若用 $E$ 表示神经网络在训练集上的误差，则它显然是关于连接权 $w$ 和偏置 $b$ 的函数。

此时，神经网络的训练过程可看作一个参数寻优过程，

• 即在参数空间中，寻找一组最优参数使得E最小。

我们常会谈到两种“最优”：“局部极小”（local minimum）和“全局最小”（global minimum）。

显然，

• 参数空间内梯度为零的点，只要其误差函数值小于邻点的误差函数值，就是局部极小点；
• 可能存在多个局部极小值，但却只会有一个全局最小值；

如图5.10中有两个局部极小，但只有其中之一是全局最小，显然，我们在参数寻优过程中是希望找到全局最小。

基于梯度的搜索是使用最为广泛的参数寻优方法。

• 在此类方法中，我们从某些初始解出发，迭代寻找最优参数值；

• 每次迭代中，我们先计算误差函数在当前点的梯度，然后根据梯度确定搜索方向。

例如，由于负梯度方向是函数值下降最快的方向，因此梯度下降法就是沿着负梯度方向搜索最优解。

• 若误差函数在当前点的梯度为零，则已达到局部极小，更新量将为零，这意味着参数的迭代更新将在此停止。

显然，如果误差函数具有多个局部极小，则不能保证找到的解是全局最小。

在现实任务中，人们常采用以下策略来试图“跳出”局部极小，从而进一步接近全局最小：

• 以多组不同参数值初始化多个神经网络，按标准方法训练后，取其中误差最小的解作为最终参数。这相当于从多个不同的初始点开始搜索，这样就可能陷入不同的局部极小，从中进行选择有可能获得更接近全局最小的结果；

• 使用“模拟退火”（simulated annealing）技术。模拟退火在每一步都以一定的概率接受比当前解更差的结果，从而有助于“跳出”局部极小。在每步迭代过程中，接受“次优解”的概率要随着时间的推移而逐渐降低，从而保证算法稳定；

• 使用随机梯度下降，与标准梯度下降法精确计算梯度不同，随机梯度下降法在计算梯度时加入了随机因素。于是，即便陷入局部极小点，它计算出的梯度仍可能不为零，这样就有机会跳出局部极小继续搜索；

• 此外，遗传算法（genetic algorithms） 也常用来训练神经网络以更好地逼近全局最小。

需注意的是，上述用于跳出局部极小的技术大多是启发式，理论上尚缺乏保障。

5.5 深度学习

理论上来说，参数越多的模型复杂度越高、“容量”（capacity）越大，这意味着它能完成更复杂的学习任务。典型的深度学习模型就是很深层的神经网络，然而，深度神经网络难以直接用经典算法（例如标准BP算法）进行训练，因为误差在多隐层内逆传播时，往往会“发散”（diverge）而不能收敛到稳定状态。

1）“预训练+微调”

无监督逐层训练（unsupervised layer-wise training）是多隐层网络训练的有效手段，其基本思想是

• 每次训练一层隐结点，训练时将上一层隐结点的输出作为输入，而本层隐结点的输出作为下一层隐结点的输入，这称为“预训练”（pre-training）；
• 在预训练全部完成后，再对整个网络进行“微调”（fine-tuning）训练。

事实上，“预训练+微调”的做法可视为将大量参数分组，对每组先找到局部看来比较好的设置，然后再基于这些局部较优的结果联合起来进行全局寻优。这样就在利用了模型大量参数所提供的自由度的同时，有效地节省了训练开销。

2）“权共享”

另一种节省训练开销的策略是“权共享”（weight sharing），即让一组神经元使用相同的连接权，这个策略在卷积神经网络（Convolutional NeuralNetwork，简称CNN）【LeCun and Bengio，1995；LeCun et al.，1998】中发挥了重要作用。

关于CNN的详细内容可参考「深度学习」卷积网络架构的演进：从 LeNet5 到 DenseNet。

5.6 思考与归纳

务必注意并掌握反向传播算法的推导过程。

第6章 支持向量机

支持向量机（Support Vertor Machines，SVM）是一种常用的二分类模型，其基本思想是构建特征空间上类间间隔最大的超平面，并以此进行分类。

• 本章首先介绍SVM的分类间隔定义，并给出基础SVM的目标函数，以及其对应的凸二次规划问题。
• 通过使用拉格朗日乘子法，可导出其对偶问题，并给出SVM目标函数的求解方法。
• 其次，针对基础SVM只能处理线性可分数据的情况，引入软间隔（softmargin）及核方法（kernel method）的概念。
  • 对于近似线性可分数据，通过引入软间隔来允许SVM在少数样本下不满足约束条件，达到分类的目的。
  • 对于线性不可分数据，可使用核方法，将原始数据空间映射到高维特征空间中，并在高维特征空间下构造最优超平面，实现数据的分类。
• 最后，将介绍一种快速的启发式学习方法一序列最小优化算法（SMO），该方法是目前较为常用的SVM训练算法。

6.1 支持向量机的基本型

基本分类问题

给定训练样本集 $D = {(\mathbf{x_1}, y_1), (\mathbf{x_2}, y_2), \dots, (\mathbf{x_m}, y_m)}, \ y_i \in {-1, +1}$ ，分类学习最基本的想法就是：

• 基于训练集 $D$ 在样本空间中找到一个划分超平面，将不同类别的样本分开。

但正如图6.1所示，能将训练样本分开的划分超平面可能有很多，我们该如何确定最优分类面呢？

直观上看，应该去找位于两类样本“正中间”的划分超平面，即图6.1中加粗部分，因为该平面对样本局部扰动的“容忍性”最好。

• 换句话说，我们希望最优分类面不但能将两类样本正确分开，且能够使分类间隔最大。

间隔与支持向量

在样本空间中，划分超平面可通过如下线性方程来描述：

$$\begin{align} \mathbf{w^T x} + b = 0 \tag{6.1} \end{align}$$

其中， $\mathbf{w} = (w_1;w_2;\dots;w_d)$ 为法向量，决定了超平面的方向；$b$ 为位移项，决定了超平面与原点之间的距离。

显然，划分超平面可由法向量 $\mathbf{w}$ 和位移 $b$ 共同确定，我们不妨记为 $(\mathbf{w}, b)$ 。

假设超平面 $(\mathbf{w}, b)$ 能将训练样本正确分类，即对于某个样本点 $(\mathbf{x}_i, y_i) \in D$ ：

• 若 $y_i = +1$ ，则有 $\mathbf{w^T x}_i + b > 0$ ，即正类样本必在超平面上方；
• 若 $y_i = -1$ ，则有 $\mathbf{w^T x}_i + b < 0$ ，即负类样本必在超平面下方。

不妨令

$$\begin{align} \begin{cases} \mathbf{w^T x_i} + b \geq +1, \ \ y_i = +1; \ \mathbf{w^T x_i} + b \leq -1, \ \ y_i = -1. \end{cases} \tag{6.2} \end{align}$$

即若超平面 $(\mathbf{w}, b)$ 能将训练样本正确分类，需满足条件 $y_i (\mathbf{w^T x_i} + b) \geq 1$ 。

易知，若超平面 $(\mathbf{w’}, b’)$ 能将训练样本正确分类 ，则必定存在线性变换 $\tau \mathbf{w} \rightarrow \mathbf{w’}$ 和 $\tau b \rightarrow b’$ 使得（6.2）式成立。

这是因为对于任意超平面 $(\mathbf{w’}, b’)$ ，有

$$\begin{align} \begin{cases} \mathbf{w^T x_i} + b \geq +\tau, \ \ y_i = +1; \ \mathbf{w^T x_i} + b \leq -\tau, \ \ y_i = -1. \end{cases} \end{align}$$

其中 $\tau > 0$ ，进而有

$$\begin{align} \begin{cases} \frac{1}{\tau} \mathbf{w^T x_i} + \frac{1}{\tau} b \geq +1, \ \ y_i = +1; \ \frac{1}{\tau} \mathbf{w^T x_i} + \frac{1}{\tau} b \leq -1, \ \ y_i = -1. \end{cases} \end{align}$$

因此，不等号后面取1只是为了简化计算。

那么如何保证分类间隔最大呢？我们知道，样本空间中的任意点 $\mathbf{x}$ 到超平面 $(\mathbf{w}, b)$ 的距离可写为

$$\begin{align} r = \frac{|\mathbf{w^T x} + b|}{||\mathbf{w}||} \geq \frac{1}{||\mathbf{w}||} \tag{6.3} \end{align}$$

如图6.2所示，距离超平面最近（被圆圈起来）的这几个样本点使式（6.3）的等号成立，它们被称为“支持向量”（support vector）。

那么两个异类支持向量到超平面的距离之和为

$$\begin{align} \gamma = \frac{2}{||\mathbf{w}||} \tag{6.4} \end{align} $$

它被称为“间隔”（margin）。

欲找到具有“最大间隔”（maximum margin）的划分超平面，也就是要找到能满足式（6.2）中约束的参数 $\mathbf{w}$ 和 $b$ ，使得 $\gamma$ 最大，即

$$\begin{align} \max_{w,b} \ \ \frac{2}{||\mathbf{w}||} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ s.t. \ \ \ \ y_i(\mathbf{w^T x_i} + b) \geq 1, \ \ i=1,2,\dots,m \ . \tag{6.5} \end{align}$$

显然，为了最大化间隔，仅需最大化 $||\mathbf{w}||^{-1}$ ，这等价于最小化 $||\mathbf{w}||^2$ 。于是，式（6.5）可重写为：

$$\begin{align} \min_{w,b} \ \ \frac{1}{2} ||\mathbf{w}||^2 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ s.t. \ \ \ \ y_i(\mathbf{w^T x_i} + b) \geq 1, \ \ i=1,2,\dots,m \ . \tag{6.6} \end{align}$$

这就是支持向量机（Support Vector Machine，SVM）的基本型。

6.2 对偶问题

使用拉格朗日乘子法求对偶问题

我们希望求解式（6.6）来确定模型参数 $\mathbf{w}$ 和 $b$ ，以得到最优划分超平面：

$$\begin{align} f(\mathbf{x}) = \mathbf{w^T x} + b \tag{6.7} \end{align}$$

注意到式（6.6）本身是一个凸二次规划（convex quadratic programming）问题，我们可以使用拉格朗日乘子法得到其“对偶问题”（dual problem）。

具体来说，对式（6.6）的每条约束添加拉格朗日乘子 $\alpha_i \geq 0$ ，则该问题的拉格朗日函数可写为

$$\begin{align} L(\mathbf{w}, b, \mathbf{\alpha}) = \frac{1}{2}||\mathbf{w}||^2 + \sum_{i=1}^m \alpha_i (1 - y_i(\mathbf{w^T x} + b)) \tag{6.8} \end{align}$$

其中，$\mathbf{\alpha} = (\alpha_1; \alpha_2; \dots; \alpha_m).$

令 $L(\mathbf{w}, b, \mathbf{\alpha})$ 对 $\mathbf{w}$ 和 $b$ 的偏导数为零可得

$$\begin{align} \mathbf{w} = \sum_{i=1}^m \alpha_i y_i \mathbf{x_i} + b \tag{6.9} \end{align}$$

$$\begin{align} 0 = \sum_{i=1}^m \alpha_i y_i \tag{6.10} \end{align}$$

将式（6.9）代入（6.8），即可将 $L(\mathbf{w}, b, \mathbf{\alpha})$ 中的 $\mathbf{w}$ 和 $b$ 消去，再考虑式（6.10）的约束，就得到式（6.6）的对偶问题：

$$\begin{align} \max_{\alpha} \ \ \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i=1}^m\sum_{j=1}^m \alpha_i \alpha_j y_i y_j \mathbf{x^T_i} \mathbf{x_j} \ s.t. \ \ \sum_{i=1}^m \alpha_i y_i = 0 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \alpha_i \geq 0, \ \ i = 1,2,\dots,m \ . \ \ \ \ \ \ \ \ \ \ \ \ \ \tag{6.11} \end{align}$$

因此，只需求解出 $\alpha$ ，进而可以得到模型

$$\begin{align} f(\mathbf{x}) &= \mathbf{w^T x} + b \ &= \sum_{i=1}^m \alpha_i y_i \mathbf{x_i^T} \ \mathbf{x} + b \tag{6.12} \end{align}$$

KKT条件

从对偶问题（6.11）解出的 $\alpha_i$ 是式（6.8）中的拉格朗日乘子，它恰对应着训练样本 $(\mathbf{x_i}, y_i)$ 。

注意到式（6.6）中有不等式约束，因此上述过程需满足KKT（Karush-Kuhn-Tucker）条件，即要求

$$\begin{align} \begin{cases} \alpha_i \geq 0 \ ; \ y_if(\mathbf{x_i}) - 1 \geq 0 \ ; \ \alpha_i(y_if(\mathbf{x_i}) - 1) = 0 \ . \end{cases} \tag{6.13} \end{align}$$

式（6.13）中前两项均为拉格朗日乘子约束，第三项为松弛变量约束，只是松弛变量可以通过推导消掉而已。

关于KKT条件的详细推导，见「机器学习」拉格朗日乘子法。

因此，对任一样本点 $(\mathbf{x_i}, y_i)$ ，总有 $\alpha_i = 0$ 或 $y_if(\mathbf{x_i}) = 1$ ：

• 若 $\alpha_i = 0$ ，则该样本不会在式（6.12）中出现，也就不会对最终的模型 $f(\mathbf{x})$ 有任何影响；
• 若 $\alpha_i > 0$ ，则必有 $y_if(\mathbf{x_i}) = 1$ ，即所对应的样本点位于最大间隔边界上，是一个支持向量。

这显示出支持向量机的一个重要性质：

• 训练完成后，最终模型仅与支持向量有关，因而大部分的训练样本都无需保留。

6.3 核函数

核技巧：将低维数据映射到高维空间

在本章前面的讨论中，我们假设训练样本是线性可分的，然而在现实任务中，原始样本空间内可能并不存在一个能正确划分两类样本的超平面。

对这样的问题，可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分，如图6.3所示。

幸运的是，如果原始空间是有限维，即属性数有限，那么一定存在一个高维特征空间使样本可分。

令 $\phi(\mathbf{x})$ 表示将 $\mathbf{x}$ 映射后的特征向量，于是，在特征空间中划分超平面所对应的模型可表示为

$$\begin{align} f(\mathbf{x}) = \mathbf{w^T \phi(x)} + b \tag{6.19} \end{align}$$

那么类似SVM的基本型（6.6），有

$$\begin{align} \min_{w,b} \ \ \frac{1}{2} ||\mathbf{w}||^2 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ s.t. \ \ \ \ y_i(\mathbf{w^T \phi(x_i)} + b) \geq 1, \ \ i=1,2,\dots,m \ . \tag{6.20} \end{align}$$

其对偶问题是

$$\begin{align} \max_{\alpha} \ \ \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i=1}^m\sum_{j=1}^m \alpha_i \alpha_j y_i y_j \mathbf{\phi(x_i)^T} \mathbf{\phi(x_j)} \ s.t. \ \ \sum_{i=1}^m \alpha_i y_i = 0 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \alpha_i \geq 0, \ \ i = 1,2,\dots,m \ . \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \tag{6.21} \end{align}$$

求解式（6.21）涉及到计算 $\mathbf{\phi(x_i)^T} \mathbf{\phi(x_j)}$ ，这是样本 $\mathbf{x_i}$ 与 $\mathbf{x_j}$ 映射到高维特征空间之后的内积。

• 由于特征空间维数可能很高，甚至可能是无穷维，因此直接计算 $\mathbf{\phi(x_i)^T} \mathbf{\phi(x_j)}$ 通常是困难的。

为了避开这个障碍，可以设想这样一个函数：

$$\begin{align} \kappa(\mathbf{x_i}, \mathbf{x_j}) = \ < \mathbf{\phi(x_i)^T}, \mathbf{\phi(x_j)} > \ \approx \ \mathbf{\phi(x_i)^T} \mathbf{\phi(x_j)} \tag{6.22} \end{align}$$

即 $\mathbf{x_i}$ 与 $\mathbf {x_j}$ 在特征空间的内积等于它们在原始样本空间中通过函数 $\kappa(·, ·)$ 计算的结果。

• 这称为“核技巧”（kernel trick），有了这样的函数，我们就不必直接去计算高维甚至无穷维特征空间中的内积。

于是式（6.21）可重写为

$$\begin{align} \max_{\alpha} \ \ \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i=1}^m\sum_{j=1}^m \alpha_i \alpha_j y_i y_j \kappa(\mathbf{x^T_i}, \mathbf{x_j}) \ s.t. \ \ \sum_{i=1}^m \alpha_i y_i = 0 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \alpha_i \geq 0, \ \ i = 1,2,\dots,m \ . \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \tag{6.23} \end{align}$$

求解后即得到

$$\begin{align} f(\mathbf{x}) &= \mathbf{w^T \phi(x)} + b \ &= \sum_{i=1}^m \alpha_i y_i \mathbf{\phi(x_i)^T} \ \mathbf{\phi(x)} + b \ &= \sum_{i=1}^m \alpha_i y_i \kappa(\mathbf{x^T_i}, \mathbf{x_j}) + b \tag{6.24} \end{align}$$

核函数

定理6.1表明，只要一个对称函数所对应的核矩阵半正定，它就能作为核函数使用。

事实上，对于一个半正定核矩阵，总能找到一个与之对应的映射。换言之，任何一个核函数都隐式地定义了一个称为“再生核希尔伯特空间”（Reproducing Kernel Hilbert Space，简称RKHS）的特征空间。

通过前面的讨论可知，我们希望样本在特征空间内线性可分，因此核函数的好坏对支持向量机的性能至关重要。

表6.1列出了几种常用的核函数：

此外，还可通过函数组合得到，例如：

• 若 $\kappa_1$ 和 $\kappa_2$ 为核函数，则对于任意正数 $\gamma_1$ 、$\gamma_2$ ，其线性组合 $\gamma_1 \kappa_1 + \gamma_2 \kappa_2$ 也是核函数；
• 若 $\kappa_1$ 和 $\kappa_2$ 为核函数，则核函数的直积 $\kappa_1 \otimes \kappa_2 (x,z) = \kappa_1(x, z) \kappa_2(x, z)$ 也是核函数；
• 若 $\kappa_1$ 为核函数，则对于任意函数 $g(\mathbf{x})$ ，$\kappa(x,z) = g(x) \kappa_1(x,z) g(z)$ 也是核函数.

6.4 软间隔

软间隔支持向量机

在现实任务中往往很难找到一个超平面将不同类的样本完全划分开，退一步说，即便恰好找到了，也很难断定这不是由于过拟合所造成的。

因此，为了缓解该问题，我们要引入软间隔的概念，即允许支持向量机在一些样本上出错，如图6.4所示。

具体来说，

• “硬间隔”（hard margin）要求所有样本均满足约束 $y_i(\mathbf{w^T x_i} + b) \geq 1$ ，即所有样本都必须划分正确；
• “软间隔”（soft margin）则允许某些样本不满足约束 $y_i(\mathbf{w^T x_i} + b) \geq 1$ ，当然不满足约束的样本应尽可能地少。

于是，优化目标可改写为

$$\begin{align} \min_{\mathbf{w}, b} \ \ \frac{1}{2} ||\mathbf{w}||^2 \ + \ C \sum_{i=1}^{m} l_{0/1}(y_i(\mathbf{w^T x_i} + b) - 1) \tag{6.29} \end{align}$$

其中，$C > 0$ 是一个常数，$l_{0/1}$ 是“0/1损失函数”

$$\begin{align} l_{0/1}(z) = \begin{cases} 1, \text{ if } z < 0; \ 0, \text{ otherwise.} \end{cases} \tag{6.30} \end{align}$$

显然，

• 当 $C$ 无穷大时，式（6.29）就迫使 $l_{0/1}$ 损失函数的值为0，即每个样本点 $x_i$ 均需满足约束 $y_i(\mathbf{w^T x_i} + b) - 1 \geq 0$ ；

• 当 $C$ 取有限值时，式（6.29）允许一些样本不满足约束.

然而，$l_{0/1}$ 非凸、非连续，数学性质不太好，使得式（6.29）不易直接求解。

于是，人们通常用其他一些具有较好数学性质的函数来作为“替代损失”（surrogate loss），图6.5给出了三种常用的替代损失函数：

它们的数学表达形式如下：

$$\begin{align} \text{hinge 损失： } l_{hinge}(z) = \max(0, 1 - z) \tag{6.31} \end{align}$$

$$\begin{align} \text{指数损失（exponential loss）： } l_{exp}(z) = \exp(- z) \tag{6.32} \end{align}$$

$$\begin{align} \text{对率损失（logistic loss）： } l_{log}(z) = \log(1 + \exp(-z)) \tag{6.33} \end{align}$$

若采用 hinge 损失，则式（6.29）的优化目标就变成

$$\begin{align} \min_{\mathbf{w}, b} \ \ \frac{1}{2} ||\mathbf{w}||^2 \ + \ C \sum_{i=1}^{m} \max \ (0,\ 1 - y_i(\mathbf{w^T x_i} + b)) \tag{6.34} \end{align}$$

如果我们引入“松弛变量”（slack variables） $\xi_i \geq 0$ ，可将式（6.34）重写为

$$\begin{align} \min_{\mathbf{w}, b} \ \ \frac{1}{2} ||\mathbf{w}||^2 \ + \ C \sum_{i=1}^{m} \xi_i \ \ \ \ \ \ \ \ \ s.t. \ \ y_i(\mathbf{w^T x_i} + b) \geq 1 - \xi_i \ \ \ \ \xi_i \geq 0, \ \ i = 1,2,\dots,m \ . \tag{6.35} \end{align}$$

显然，式（6.35）中每个样本都有一个对应的松弛变量，用以表征该样本不满足约束的程度，这就是常用的“软间隔支持向量机”。。

软间隔支持向量机的对偶问题

式（6.35）仍是一个二次规划问题。于是，类似式（6.8），通过拉格朗日乘子法可得到式（6.35）的拉格朗日函数

$$\begin{align} L(\mathbf{w}, b, \mathbf{\alpha}, \mathbf{\xi}, \mathbf{\mu}) &= \ \ \frac{1}{2} ||\mathbf{w}||^2 \ + \ C \sum_{i=1}^{m} \xi_i \ &+ \sum_{i=1}^m \alpha_i (1 - \xi_i - y_i(\mathbf{w^T x_i} + b)) - \sum_{i=1}^m \mu_i \xi_i \tag{6.36} \end{align}$$

其中，$\alpha_i \geq 0$ ，$\mu_i \geq 0$ 是拉格朗日乘子。

我们令 $L(\mathbf{w}, b, \mathbf{\alpha}, \mathbf{\xi}, \mathbf{\mu})$ 对 $\mathbf{w}, b, \xi_i$ 的偏导数为零可得

$$\begin{align} \mathbf{w} = \sum_{i=1}^m \alpha_i y_i \mathbf{x_i} \tag{6.37} \end{align}$$

$$\begin{align} 0 = \sum_{i=1}^m \alpha_i y_i \tag{6.38} \end{align}$$

$$\begin{align} C = \alpha_i + \mu_i \tag{6.39} \end{align}$$

将式（6.37）-（6.39）代入式（6.36）即可得到式（6.35）的对偶问题

$$\begin{align} \max_{\alpha} \ \ \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i=1}^m\sum_{j=1}^m \alpha_i \alpha_j y_i y_j \mathbf{x^T_i} \mathbf{x_j} \ s.t. \ \ \sum_{i=1}^m \alpha_i y_i = 0 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0 \leq \alpha_i \leq C, \ \ i = 1,2,\dots,m \ . \ \ \ \ \ \tag{6.40} \end{align}$$

将软间隔下的对偶问题（6.40）与硬间隔下的对偶问题（6.11）对比可看出，

• 两者唯一的差别就在于对偶变量的约束不同：前者是 $0 \leq \alpha_i \leq C$，后者是 $0 \leq \alpha_i$

于是，同样可采用SMO算法求解式（6.40）。

类似式（6.13），对软间隔支持向量机，KKT条件要求

$$\begin{align} \begin{cases} \alpha_i \geq 0 \ , \mu_i \geq 0 \ ; \ y_if(\mathbf{x_i}) - 1 + \xi_i \geq 0 \ ; \ \alpha_i(y_if(\mathbf{x_i}) - 1 + \xi_i) = 0 \ ; \ \xi_i \geq 0, \ \mu_i \xi_i = 0 \ . \end{cases} \tag{6.41} \end{align}$$

因此，对任一样本点 $(\mathbf{x_i}, y_i)$ ，总有 $\alpha_i = 0$ 或 $y_if(\mathbf{x_i}) = 1 - \xi_i$ ：

• 若 $\alpha_i = 0$ ，则该样本不会对最终的模型 $f(\mathbf{x})$ 有任何影响；
• 若 $\alpha_i > 0$ ，则必有 $y_if(\mathbf{x_i}) = 1 -\xi_i$ ，即该样本是一个支持向量，此时由式（6.39） $C = \alpha_i + \mu_i$ 可知：
  • 若 $\alpha_i < C$ ，则 $\mu_i > 0$ ，进而有 $\xi_i = 0$ ，即该样本恰在最大间隔边界上；
  • 若 $\alpha_i = C$ ，则 $\mu_i = 0$ ，此时若 $\xi_i \leq 1$ 则该样本落在最大间隔内部，若 $\xi_i > 1$ 则该样本被错误分类。

由此可看出，软间隔支持向量机的最终模型仍仅与支持向量有关，即通过采用hinge损失函数仍保持了稀疏性。

6.5 序列最小优化算法

如前文所述，支持向量机的训练过程可表示为求解具有最优解的凸二次规划问题，许多通用算法均可求解此类问题。

然而，该问题的规模正比于训练样本数，当训练数据集样本量较大时会带来很大的开销，导致效率较低，甚至无法使用。

为了缓解这个问题，人们提出了很多高效算法，序列最小化优化方法（Sequential Minimal Optimization, SMO）是其中一个著名的代表。

基本思路

SMO算法是一种启发式学习算法，其主要思想是

• 将一个复杂的二次规划问题分解为多个只有两个变量的二次规划子问题，并通过求解子问题来解决原始问题。

算法将检查当前是否仍存在未满足KKT条件的变量，若有，则选取两个变量（至少有一个不满足KKT条件）作为当前问题的待优化目标，固定其他变量，在此基础上求得优化目标的解析解。当所有变量的KKT条件均得到满足，原问题的就得到了。

这样，在参数初始化后，SMO不断执行如下两个步骤直至收敛：

1. 使用启发式方法选取一对需要更新的变量 $\alpha_i$ 和 $\alpha_j$ ；
2. 固定 $\alpha_i$ 和 $\alpha_j$ 以外的参数，求解两个变量 $\alpha_i$ 和 $\alpha_j$ 二次规划的解析方法。

使用启发式方法选取待优化变量 $\alpha_i$ 和 $\alpha_j$

注意到只需选取的 $\alpha_i$ 和 $\alpha_j$ 中有一个不满足KKT条件（6.13），目标函数就会在迭代后减小【Osuna et al，1997】。直观来看，KKT条件违背的程度越大，则变量更新后可能导致的目标函数值减幅越大。于是，

• SMO先选取一个违背KKT条件程度最大的变量作为 $\alpha_i$ ；

第二个变量应选择一个使目标函数值减小最快的变量，但由于比较各变量所对应的目标函数值减幅的复杂度过高，因此SMO采用了一个启发式方法：

• 使选取的两个变量所对应样本之间的间隔最大，从而确定 $\alpha_j$ .

一种直观的解释是，这样的两个变量有很大的差别，与对两个相似的变量进行更新相比，对它们进行更新会带给目标函数值更大的变化。

使用解析法计算 $\alpha_i$ 和 $\alpha_j$ 的最优解并确定偏移项 $b$

当我们仅考虑 $\alpha_i$ 和 $\alpha_j$ 时，SVM的对偶问题（6.11）中的约束可重写为

$$\begin{align} \alpha_iy_i + \alpha_jy_j = c, \ \ \alpha_i \geq 0, \ \ \alpha_j \geq 0 \tag{6.42} \end{align}$$

其中，$c = - \sum_{k \ne i,j} \alpha_ky_k$ 是使得约束 $\sum_{i=1}^m \alpha_i y_i = 0$ 成立的常数。

我们可以用式（6.42）消去式（6.11）中的变量 $\alpha_j$，则得到一个关于 $\alpha_i$ 的单变量二次规划问题，仅有的约束是 $\alpha_i \geq 0$ .

不难发现，这样的二次规划问题具有闭式解，于是不必调用数值优化算法即可高效地计算出更新后的 $\alpha_i$ 和 $\alpha_j$ .

那么如何确定偏移项 $b$ 呢？注意到对任意支持向量 $(\mathbf{x_s}, y_s)$ 都有 $y_s f(\mathbf{x_s}) = 1$，即

$$\begin{align} y_s (\sum_{i \in S} \alpha_i y_i \mathbf{x_i^T x_s} + b) = 1 \tag{6.43} \end{align}$$

其中 $S$ 为所有支持向量的下标集。

理论上，可选取任意支持向量并通过求解式（6.43）获得 $b$ ，但现实任务中常采用一种更鲁棒的做法：

• 使用所有支持向量求解的平均值

$$\begin{align} b = \frac{1}{|S|} \sum_{s \in S} ( y_s - \sum_{i \in S} \alpha_i y_i \mathbf{x_i^T x_s}) \tag{6.44} \end{align}$$

关于SMO算法更加具体的证明与实现，可参考《数据挖掘导论》的课件《SVM-utf8》.

• 6.6 支持向量回归（SVR）

• 6.7 核方法

6.8 思考与归纳

• SVM考虑寻找一个满足分类要求的超平面，并且使训练集中的点距离分类面尽可能的远，也就是寻找一个分类面使它两侧的空白区域（Margin）最大。
• 核函数解决的是在原始空间线性不可分的情况，将数据映射到高维特征空间。
• 软间隔SVM是一种正则化操作。

第7章 贝叶斯分类器

7.1 贝叶斯决策论

贝叶斯决策论（Bayesian decision theory）是概率框架下实施决策的基本方法。

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

基本原理

下面我们以多分类任务为例来解释其基本原理。

• 假设输入空间 $\chi \subseteq R^n$ 为 $n$ 维向量的集合，输出空间 $\gamma = {c_1，c_2, \dots, c_N }$ 有 $N$ 种可能的类别标记；

• $X$ 和 $Y$ 分别是定义在输入空间 $\chi$ 和输出空间 $\gamma$ 上的随机变量；

• $\lambda_{ij}$ 是将一个真实类别为 $c_j$ 的样本误分类为 $c_i$ 所产生的损失；

• 后验概率 $P(Y = c_i | X = x )$ 表示样本 $\mathbf{x} = (x_1, \dots, x_n)$ 为 $c_i$ 的概率，即观察到 $X$ 的各项属性值为 $(X_1 = x_1, \dots, X_n = x_n)$ 时，随机变量 $Y = c_i$ 的概率。

  注：为方便书写公式，后面将省略随机变量。

那么我们基于后验概率 $P(c_i | x )$ 便可获得将样本 $x$ 分类为 $c_i$ 所产生的期望损失（expected loss），亦即在样本上的“条件风险”（conditional risk）

$$\begin{align} R(c_i | x) = \sum_{j=1}^N \lambda_{ij} P(c_j | x) \tag{7.1} \end{align} $$

上述公式表明了，$x$ 的类别为 $c_j$ 的概率，以及当 $x$ 为 $c_j$ 时，将其错判为 $c_i$ 时的损失，然后对所有可能结果求和。

注：决策论中将“期望损失”称为“风险”(risk).

我们的任务是寻找一个判定准则 $h : \chi \rarr \gamma$ 以最小化总体风险

$$\begin{align} R(h) = \mathbb{E}_x [R(h(x)|x)] \tag{7.2} \end{align} $$

显然，对每个样本 $x$ ，若 $h$ 能最小化条件风险 $R(h(x) | x)$ ，则总体风险 $R(h)$ 也将被最小化。

这就产生了贝叶斯判定准则（Bayes decision rule）：

• 为最小化总体风险，只需在每个样本上选择那个能使条件风险 $R(c|x)$ 最小的类别标记，即

$$\begin{align} h^*(x) = \arg \min_{c \in \gamma} R(c | x) \tag{7.3} \end{align} $$

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

具体来说，若目标是最小化分类错误率，则误判损失 $\lambda_{ij}$ 可写为

$$\begin{align} \lambda_{ij} = \begin{cases} 0, \text{ if $i = j$;} \ 1, \text{ otherwise} \end{cases} \tag{7.4} \end{align} $$

此时代入式（7.1）得到条件风险为

$$\begin{align} R(c | x) = 1 - P(c | x) \tag{7.5} \end{align} $$

即把样本 $x$ 分类为 $c$ 的期望损失，可由对应的后验概率描述。

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

$$\begin{align} h^*(x) = \arg \max_{c \in \gamma} P(c | x) \tag{7.6} \end{align} $$

即对每个样本 $x$ ，选择能使后验概率 $P(c|x)$ 最大的类别标记。

贝叶斯分类器

不难看出，欲使用贝叶斯判定准则来最小化决策风险，首先要获得后验概率 $P(c | x)$ 。

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

1. 给定 $\mathbf{x}$，通过直接建模 $P(c | \mathbf{x})$ 来预测类别 $c$，这样得到的是“判别式模型”（discriminative models），如决策树、BP神经网络、支持向量机等；
2. 也可先对联合概率分布 $P(\mathbf{x},c)$ 建模，然后再由此获得 $P(c | \mathbf{x})$ ，这样得到的是“生成式模型”（generative models）.

对于生成式模型来说，基于贝叶斯定理，有

$$\begin{align} P(c|\mathbf{x}) = \frac{P(\mathbf{x},c)}{P(\mathbf{x})} = \frac{P(c)P(\mathbf{x}|c)}{P(\mathbf{x})} = \frac{P(c)P(\mathbf{x}|c)}{\sum_{c \in \gamma} P(c)P(\mathbf{x}|c)} \tag{7.8} \end{align}$$

其中，

• $P(c)$ 是类“先验”（prior）概率；
• $P(\mathbf{x} | c)$ 是样本 $x$ 相对于类标记 $c$ 的类条件概率（class-conditional probability），或似然（likelihood）；
• $P(\mathbf{x})$ 是用于归一化的“证据”（evidence）因子，可使用全概率公式求得。

因此估计后验概率 $P(c | x)$ 的问题就转化为如何基于训练数据 $D$ 来估计先验 $P(c)$ 和类条件概率 $P(\mathbf{x} | c)$ 。

• 这里可能不太好理解，我们举个例子来说明：

  假设某人感染了新冠病毒，那么其核酸检测呈阳性的概率为 95%；如果未感染病毒，则阳性的概率为 1%（这也称为类条件概率）。

  此外如果我们有先验知识，整个人群中感染此病毒的人数为10%左右，即 $P(感染) = 0.1$ 。

  现在有一个人结果为阳性，问这个人感染病毒了吗？

• 在这个问题中，「核酸检测是否为阳性」是样本 $x$ 的属性，而「是否感染病毒」则是我们要预测的类别 $c$ 。

  那么按照贝叶斯决策理论，有：

  $$\begin{align} \displaystyle P(感染|核酸检测阳性) &= \frac{P(核酸检测为阳性且感染了新冠病毒)}{P(核酸检测阳性)} \ &= \frac{P(感染) P(阳性|感染)}{P(感染) P(阳性|感染) + P(未感染) P(阳性|未感染)} \ &= \frac{0.1 \times 0.95}{0.1 \times 0.95 + 0.9 \times 0.01} = 0.51 \end{align}$$

• 类先验概率 $P(c)$ 表达了样本空间中各类样本所占的比例，根据大数定律，当训练集包含充足的独立同分布样本时，$P(c)$ 可通过各类样本出现的频率来进行估计。
• 对类条件概率 $P(\mathbf{x} | c)$ 来说，由于它涉及关于 $\mathbf{x}$ 所有属性的联合概率，直接根据样本出现的频率来估计将会遇到严重的困难，下面介绍一种估计策略。

7.2 极大似然估计

估计类条件概率的一种常用策略是先假定其具有某种确定的概率分布形式，再基于训练样本对概率分布的参数进行估计。

具体地，假设类别 $c$ 的类条件概率 $P(\mathbf{x} | c)$ 具有确定的形式并且被参数向量 $\theta_c$ 唯一确定，则我们的任务就是利用训练集 $D$ 估计参数 $\theta_c$ 。

为明确起见，我们将 $P(\mathbf{x} | c)$ 记为 $P(\mathbf{x} | \theta_c)$ .

事实上，概率模型的训练过程就是参数估计（parameter estimation）过程。

对于参数估计，统计学界的两个学派分别提供了不同的解决方案：

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

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

基本原理

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

$$\begin{align} P(D_c | \theta_c) = \prod_{x \in D_c} P(x | \theta_c) \tag{7.9} \end{align}$$

对 $\theta_c$ 进行极大似然估计，就是去寻找能最大化似然 $P(D_c | \theta_c)$ 的参数值。

• 直观上看，极大似然估计是试图在 $\theta_c$ 所有可能的取值中，找到一组能使数据出现的“可能性”最大的参数值。

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

$$\begin{align} LL(\theta_c) &= \log P(D_c | \theta_c) \ &= \sum_{x \in D_c} \log P(x | \theta_c) \tag{7.10} \end{align}$$

此时，参数 $\theta_c$ 的极大似然估计 $\hat{\theta}_c$ 为

$$\begin{align} \hat{\theta}c = \arg \max{\theta_c} LL(\theta_c) \tag{7.11} \end{align}$$

例如，在连续属性情形下，假设概率密度函数服从正态分布 $p(\mathbf{x} | c) \ ～ \ N(\mathbf{\mu}_c, \mathbf{\sigma}_c^2)$ ，则参数 $\mu_c$ 和 $\sigma_c^2$ 的极大似然估计为

$$\begin{align} \mu_c = \frac{1}{|D_c|} \sum_{x \in D_c} \mathbf{x} \tag{7.12} \end{align}$$

$$\begin{align} \sigma_c^2 = \frac{1}{|D_c|} \sum_{x \in D_c} (\mathbf{x} - \hat{\mu}_c )(\mathbf{x} - \hat{\mu}_c)^T \tag{7.13} \end{align}$$

也就是说，通过极大似然法得到的正态分布均值就是样本均值，方差就是 $(\mathbf{x} - \hat{\mu}_c )(\mathbf{x} - \hat{\mu}_c)^T$ 的均值，这显然是一个符合直觉的结果。

在离散属性情形下，也可通过类似的方式估计类条件概率。

• 在上面的例子中，如果按照极大似然估计进行决策，则有：

  既然感染了病毒出现阳性的概率为95%（P(x|c)），没感染出现阳性的概率只有1%，本着谁大像谁的原则，那我们认为这个人已经感染了病毒。

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

在现实应用中，欲做出能较好地接近潜在真实分布的假设，往往需在一定程度上利用关于应用任务本身的经验知识，否则若仅凭“猜测”来假设概率分布形式，很可能产生误导性的结果。

7.3 朴素贝叶斯分类器

基本原理

不难发现，基于贝叶斯公式（7.8）来估计后验概率 $P(c|x)$ 的主要困难在于：

• 类条件概率 $P(x|c)$ 是所有属性上的联合概率，难以从有限的训练样本直接估计而得。

基于有限训练样本直接估计联合概率，在计算上将会遭遇组合爆炸问题，在数据上将会遭遇样本稀疏问题，属性数越多，问题越严重。

为避开这个障碍，朴素贝叶斯分类器（naive Bayes classifier）采用了“属性条件独立性假设”（attribute conditional independence assumption）：

• 对已知类别，假设所有属性相互独立，换言之，假设每个属性独立地对分类结果发生影响。

基于属性条件独立性假设，式（7.8）可重写为

$$\begin{align} P(c|x) = \frac{P(c)P(x|c)}{P(x)} = \frac{P(c)}{Px} \prod_{i=1}^n P(x_i | c) \tag{7.14} \end{align}$$

其中，$n$ 为属性数目，$x_i$ 为样本 $\mathbf{x}$ 在第 $i$ 个属性上的取值。

由于对所有类别来说 $P(x)$ 相同，因此基于式（7.6）的贝叶斯判定准则有

$$\begin{align} h_{nb}(x) = \arg \max_{c \in \gamma} \ P(c) \prod_{i=1}^n P(x_i | c) \tag{7.15} \end{align} $$

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

估计先验概率与类条件概率

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

$$\begin{align} P(c) = \frac{|D_c|}{| D |} \tag{7.16} \end{align} $$

对类条件概率而言，

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

​ $$\begin{align} P(x_i | c) = \frac{|D_{c, x_i}|}{| D_c|} \tag{7.17} \end{align} $$

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

  $$\begin{align} p(x_i|c) = \frac{1}{\sqrt{2 \pi} \sigma_{c,i}} \exp (- \frac{(x_i - \mu_{c,i})^2}{2 \sigma^2_{c,i}}) \tag{7.18} \end{align} $$

需注意，若某个属性值在训练集中没有与某个类同时出现过，则直接基于式（7.17）进行概率估计，再根据式（7.15）进行判别将出现问题：

• 由于式（7.15）的连乘式计算出的概率值为零，因此，无论该样本的其他属性是什么，哪怕在其他属性上明显像好瓜，分类的结果都将是“好瓜=否”，这显然不太合理。

为了避免其他属性携带的信息被训练集中未出现的属性值“抹去”，在估计概率值时通常要进行“平滑”（smoothing），常用“拉普拉斯修正”（Laplacian correction）。

具体来说，令 $N$ 表示训练集 $D$ 中可能的类别数，$N_i$ 表示第 $i$ 个属性可能的取值数，则式（7.16）和（7.17）分别修正为

$$\begin{align} \hat{P}(c) = \frac{|D_c| + 1}{| D | + N} \tag{7.19} \end{align} $$

$$\begin{align} \hat{P}(x_i | c) = \frac{|D_{c, x_i}| + 1}{| D_c|+N_i} \tag{7.20} \end{align} $$

半朴素贝叶斯分类器

为了降低贝叶斯公式（7.8）中估计后验概率 $P(c|x)$ 的困难，朴素贝叶斯分类器采用了属性条件独立性假设，但在现实任务中这个假设往往很难成立，于是，人们尝试对属性条件独立性假设进行一定程度的放松，由此产生了一类称为“半朴素贝叶斯分类器”（semi-naive Bayes classifiers）的学习方法。

具体不再详细介绍.

7.5 贝叶斯网

贝叶斯网（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)$.

举例来说，图7.2给出了西瓜问题的一种贝叶斯网结构和属性“根蒂”的条件概率表.

从图中网络结构可看出：

• “色泽”直接依赖于“好瓜”和“甜度”；
• 而“根蒂”则直接依赖于“甜度”；
• 进一步从条件概率表能得到“根蒂”对“甜度”量化依赖关系，如 $P(根蒂=硬挺|甜度=高)=0.1$ 等。

7.5.1 结构（重点掌握）

重点掌握：

1. 贝叶斯网中的三种依赖关系
2. 如何从道德图中找到所有条件独立关系

从上图可以看出，贝叶斯网结构有效地表达了属性间的条件独立性。

给定父结点集，贝叶斯网假设每个属性与它的非后裔属性独立，于是 $B = (G, \Theta)$ 将属性 $x_1, x_2, \dots, x_d$ 的联合概率分布定义为

$$\begin{align} P_B(x_1, x_2, \dots, x_d) = \prod_{i=1}^d P_B(x_i|\pi_i) = \prod_{i=1}^d \theta_{x_i|\pi_i} \tag{7.26} \end{align}$$

以图7.2为例，其联合概率分布为

$$\begin{align} P(x_1, x_2, x_3, x_4, x_5) = P(x_1) P(x_2) P(x_3|x_1) P(x_4|x_1,x_2) P(x_5|x_2) \end{align} $$

显然，$x_3$ 和 $x_4$ 在给定 $x_1$ 的取值时是独立的，而 $x_4$ 和 $x_5$ 在给定 $x_2$ 的取值时独立，我们分别简记为 $x_3 \perp x_4 \ |\ x_1$ 和 $x_4 \perp x_5 \ | \ x_2 $ 。

这称为同父结构，除此之外，贝叶斯网中三个变量之间的典型依赖关系还有V型结构和顺序结构，如图7.3，其中前两种在式（7.26）中已有所体现。

• “同父”（common parent）结构：给定父结点 $x_1$ 的取值，则 $x_3$ 与 $x_4$ 条件独立；

• “顺序”结构：给定 $x$ 的值，则 $y$ 与 $z$ 条件独立；

• “V型”结构（V-structure）亦称“冲撞”结构：

  • 给定子结点 $x_4$ 的取值，则 $x_1$ 与 $x_2$ 必不独立；

  • 奇妙的是，若 $x_4$ 的取值完全未知，则V型结构下 $x_1$ 与 $x_2$ 却是相互独立的，我们做一个简单的验证：

    $$\begin{align} P(x_1, x_2) &= \sum_{x_4} P(x_1, x_2, x_4) \ &= \sum_{x_4} P(x_4|x_1,x_2) P(x_1) P(x_2) \ &= P(x_1) P(x_2) \tag{7.27} \end{align}$$

    这样的独立性称为“边际独立性”（marginal independence），可以记为 $x_1 \perp x_2$ .

事实上，一个变量取值的确定与否，能对另两个变量间的独立性发生影响，这个现象并非V型结构所特有，例如：

• 在同父结构中，条件独立性 $x_3 \perp x_4 \ |\ x_1$ 成立，但若 $x_1$ 的取值未知，则 $x_3$ 和 $x_4$ 就不独立，即 $x_3 \perp x_4$ 不成立；
• 在顺序结构中，$y \perp z \ | \ x $ ，但 $y \perp z$ 并不成立。

为了分析有向图中所有变量间的条件独立性，可使用“有向分离”（D-separation）。

我们先把有向图转变为一个无向图：

1. 找出有向图中的所有V型结构，在V型结构的两个父结点之间加上一条无向边；
2. 将所有有向边改为无向边

由此产生的无向图称为“道德图”（moral graph），令父结点相连的过程称为“道德化”（moralization）.

“道德化”的蕴义：孩子的父母应建立牢靠的关系，否则是不道德的。

基于道德图能直观、迅速地找到变量间的条件独立性。

• 假定道德图中有变量 $x, y$ 和变量集合 $\mathbf{z} = {z_i}$ ，若变量 $x$ 和 $y$ 能在图上被 $\mathbf{z}$ 分开，即从道德图中将变量集合 $\mathbf{z}$ 去除后，$x$ 和 $y$ 分属两个连通分支，则称变量 $x$ 和 $y$ 被 $\mathbf{z}$ 有向分离，$x \perp y \ | \ \mathbf{z} $ 成立.

• 例如，图7.2所对应的道德图如图7.4所示，从图中能容易地找出所有的条件独立关系：$x_3 \perp x_4 \ | \ x_1$ ，$x_4 \perp x_5 \ | \ x_2$ ，$x_3 \perp x_2 \ | \ x_1$ ，$x_3 \perp x_4 \ | \ x_1$ ，$x_3 \perp x_5 \ | \ x_1$ ，$x_3 \perp x_5 \ | \ x_2$ 等。

7.5.2 学习

若网络结构已知，即属性间的依赖关系已知，则贝叶斯网的学习过程相对简单，只需通过对训练样本“计数”，估计出每个结点的条件概率表即可。

但在现实应用中我们往往并不知晓网络结构，于是，贝叶斯网学习的首要任务就是根据训练数据集来找出结构最“恰当”的贝叶斯网。

“评分搜索”是求解这一问题的常用办法，具体来说：

1. 我们先定义一个评分函数（score function），以此来评估贝叶斯网与训练数据的契合程度
2. 然后基于这个评分函数来寻找结构最优的贝叶斯网

显然，评分函数引入了关于我们希望获得什么样的贝叶斯网的归纳偏好。

7.5.3 推断

贝叶斯网训练好之后就能用来回答“查询”（query），即通过一些属性变量的观测值来推测其他属性变量的取值。

例如在西瓜问题中，若我们观测到西瓜色泽青绿、敲声浊响、根蒂蜷缩，想知道它是否成熟、甜度如何。这样通过已知变量观测值来推测待查询变量的过程称为“推断”（inference），已知变量观测值称为“证据”（evidence）。

• 最理想的是直接根据贝叶斯网定义的联合概率分布来精确计算后验概率，不幸的是，这样的“精确推断”已被证明是NP难的。

换言之，当网络结点较多、连接稠密时，难以进行精确推断，此时需借助“近似推断”，即通过降低精度要求，在有限时间内求得近似解。

在现实应用中，贝叶斯网的近似推断常使用吉布斯采样（Gibbs sampling）来完成，这是一种随机采样方法，具体如何工作可参考西瓜书7.5章。

7.6 EM算法

7.6.1 动机：隐变量

在前面的讨论中，我们一直假设训练样本所有属性变量的值都已被观测到即训练样本是“完整”的。但在现实应用中往往会遇到“不完整”的训练样本，例如由于西瓜的根蒂已脱落，无法看出是“蜷缩”还是“硬挺”，则训练样本的“根蒂”属性变量值未知。

在这种存在“未观测”变量的情形下，是否仍能对模型参数进行估计呢？

未观测变量的学名是“隐变量”（ latent variable）：

• 令 $\mathbf{X}$ 表示已观测变量集， $\mathbf{Z}$ 表示隐变量集， $\mathbf{\Theta}$ 表示模型参数

若欲对 $\mathbf{\Theta}$ 做极大似然估计，则应最大化对数似然

$$\begin{align} LL(\mathbf{\Theta} \ | \ \mathbf{X}, \mathbf{Z}) = \ln P(\mathbf{X}, \mathbf{Z} \ | \ \mathbf{\Theta}) \tag{7.34} \end{align}$$

然而，由于 $\mathbf{Z}$ 是隐变量，上式无法直接求解。

此时我们可通过对 $\mathbf{Z}$ 计算期望，来最大化已观测数据的对数“边际似然”（ marginal likelihood）

$$\begin{align} LL(\mathbf{\Theta} \ | \ \mathbf{X}) = \ln P(\mathbf{X} \ | \ \mathbf{\Theta}) = \ln \sum_{\mathbf{Z}} P(\mathbf{X}, \mathbf{Z} \ | \ \mathbf{\Theta}) \tag{7.35} \end{align}$$

7.6.1 EM算法

EM（ Expectation- Maximization）算法，直译为“期望最大化算法”，是常用的估计参数隐变量的利器。

EM算法是一种迭代式的方法，其基本想法是：

• 若参数 $\mathbf{\Theta}$ 已知，可根据训练数据推断出最优隐变量 $\mathbf{Z}$ 的值（E步）；
• 反之，若 $\mathbf{Z}$ 的值已知，则可方便地对参数 $\mathbf{\Theta}$ 做极大似然估计（M步）.

于是，以初始值 $\mathbf{\Theta}^0$ 为起点，对式（7.35），可迭代执行以下步骤直至收敛：

• 基于 $\mathbf{\Theta}^t$ 推断隐变量 $\mathbf{Z}$ 的期望，记为 $\mathbf{Z}^t$ ；
• 基于已观测变量 $\mathbf{X}$ 和 $\mathbf{Z}^t$ 对参数 $\mathbf{\Theta}$ 做极大似然估计，记为 $\mathbf{\Theta}^{t+1}$ .

这就是EM算法的原型。

事实上，隐变量估计问题也可通过梯度下降等优化算法求解，但由于求和的项数将随着隐变量的数目以指数级上升，会给梯度计算带来麻烦；

而EM算法则可看作一种非梯度优化方法，可看作用坐标下降（ coordinate descent）法来最大化对数似然下界的过程。

7.7 思考与归纳

• 贝叶斯决策可以描述为最小化期望损失，进而能表示为最大化后验概率。

• 最小错误率贝叶斯决策就是在0-1损失函数条件下的最小风险贝叶斯决策。

• 朴素贝叶斯法是基于贝叶斯定理与特征条件独立假设的分类法。

  • 对于给定的训练数据集，首先基于特征条件独立假设学习输入输出的联合概率分布；
  • 然后给予此模型，对给定的输入 $x$ ，利用贝叶斯定理求出后验概率最大的输出 $y$ 。

• 贝叶斯网是经典的概率图模型，详细参见第14章。

• EM算法是最常见的隐变量估计方法，在机器学习中有极为广泛的用途，例如常被用来学习高斯混合模型（GMM）的参数，9.4节将介绍的 $k$ 均值聚类算法就是一个典型的EM算法。

• 简要来说，EM算法使用两个步骤交替计算：

  • 第一步是期望（E）步，利用当前估计的参数值来计算对数似然的期望值；

  • 第二步是最大化（M）步，寻找能使E步产生的似然期望最大化的参数值；

    然后，新得到的参数值重新被用于E步，直至收敛到局部最优解…

第8章 集成学习

8.1 个体与集成

集成学习（ensemble learning）通过构建并结合多个学习器来完成学习任务，有时也被称为多分类器系统（multi-classifier system）、基于委员会的学习（committee-based learning）等。

图8.1显示出集成学习的一般结构：

• 先产生一组“个体学习器”（individual learner），再用某种策略将它们结合起来。

其中个体学习器通常由一个现有的学习算法从训练数据产生，例如C4.5决策树算法、BP神经网络算法等。

• 如果集成中只包含同种类型的个体学习器（例如“决策树集成”中全是决策树，“神经网络集成”中全是神经网络），这样的集成是“同质”的（homogeneous）。

  同质集成中的个体学习器亦称“基学习器”（base learner），相应的学习算法称为“基学习算法”（base learning algorithm）。

• 如果集成包含不同类型的个体学习器，例如同时包含决策树和神经网络，这样的集成是“异质”的（heterogenous）。

  异质集成中的个体学习器由不同的学习算法生成，这时就不再有基学习算法；相应的，个体学习器一般不称为基学习器，常称为“组件学习器”（component learner）或直接称为个体学习器.

集成学习通过将多个学习器进行结合，常可获得比单一学习器显著优越的泛化性能，这对“弱学习器”（weak learner）尤为明显。

弱学习器常指泛化性能略优于随机猜测的学习器，例如在二分类问题上精度略高于50%的分类器。

根据个体学习器的生成方式，目前的集成学习方法大致可分为两大类，即

1. 个体学习器间存在强依赖关系、必须串行生成的序列化方法，代表是Boosting；
2. 个体学习器间不存在强依赖关系、可同时生成的并行化方法，代表是Bagging和“随机森林”（Random Forest）。

8.2 Boosting

Boosting是一族可将弱学习器提升为强学习器的算法，这族算法的工作机制类似：

1. 先从初始训练集训练出一个基学习器；
2. 再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注；
3. 然后基于调整后的样本分布来训练下一个基学习器；
4. 如此重复进行，直至基学习器数目达到事先指定的值 $T$ ，最终将这 $T$ 个基学习器进行加权结合。

Boosting族算法最著名的代表是AdaBoost 【Freund and Schapire，1997】，其描述如图8.3所示：

其中 $y_i \in {-1, +1} $ ，$f$ 是真实函数。

AdaBoost算法有多种推导方式，比较容易理解的是基于“加性模型”（additive model），即基学习器的线性组合

$$\begin{align} H(x) = \sum_{t=1}^T \alpha_t h_t (x) \tag{8.4} \end{align}$$

来最小化指数损失函数（exponential loss function） 【Friedman et al，2000】

$$loss_{exp}(H | D) = E_{x \in D}[e^{-f(x)H(x)}] $$

8.3 Bagging与随机森林

由8.1节可知，欲得到泛化性能强的集成，集成中的个体学习器应尽可能具有较大的差异。

一种可能的做法是对训练样本进行采样，产生出若干个不同的子集，再从每个数据子集中训练出一个基学习器。

8.3.1 Bagging

Bagging 【Breiman，1996a】是并行式集成学习方法最著名的代表，从名字即可看出，它直接基于我们在2.2.3节介绍过的自助采样法（bootstrap sampling）

• 从给定数据集中随机采样出 $T$ 个含 $m$ 个训练样本的采样集，然后基于每个采样集训练出一个基学习器，再将这些基学习器进行结合。

• 在对预测输出进行结合时，Bagging通常对分类任务使用简单投票法，对回归任务使用简单平均法。

这就是Bagging的基本流程，其算法描述如图8.5所示.

值得一提的是，自助采样过程还给Bagging带来了另一个优点：

• 由于训练只使用了初始训练集中的部分样本，剩下的样本可用作验证集来对泛化性能进行“包外估计”（out-of-bag estimate）。

事实上，包外样本还有许多其他用途：

• 例如当基学习器是决策树时，可使用包外样本来辅助剪枝，或用于估计决策树中各结点的后验概率以辅助对零训练样本结点的处理；
• 当基学习器是神经网络时，可使用包外样本来辅助早期停止以减小过拟合风险。

8.3.2 随机森林

随机森林（Random Forest，简称RF）【Breiman，2001a】是Bagging的一个扩展变体。

RF在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。

具体来说，

• 传统决策树在选择划分属性时是在当前结点的属性集合（假定有d个属性）中选择一个最优属性；

• 而在RF中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含 $k$ 个属性的子集，然后再从这个子集中选择一个最优属性用于划分。

  这里的参数 $k$ 控制了随机性的引入程度：

  若令 $k=d$ ，则基决策树的构建与传统决策树相同；

  若令 $k=1$ ，则是随机选择一个属性用于划分；

  一般情况下，推荐值 $k = \log_2 d$ .

随机森林简单、容易实现、计算开销小，令人惊奇的是，它在很多现实任务中展现出强大的性能，被誉为“代表集成学习技术水平的方法”。

可以看出，随机森林对Bagging只做了小改动，随机森林中基学习器的多样性不仅来自样本扰动（通过对初始训练集采样），还来自属性扰动，这就使得最终集成的泛化性能可通过个体学习器之间差异度的增加而进一步提升。

8.3.3 性能分析

随机森林的收敛性与Bagging相似，如图8.7所示：

• 随机森林的起始性能往往相对较差，特别是在集成中只包含一个基学习器时。这很容易理解，因为通过引入属性扰动，随机森林中个体学习器的性能往往有所降低。
• 然而，随着个体学习器数目的增加，随机森林通常会收敛到更低的泛化误差。

值得一提的是，随机森林的训练效率常优于Bagging，因为在个体决策树的构建过程中，Bagging使用的是“确定型”决策树，在选择划分属性时要对结点的所有属性进行考察，而随机森林使用的“随机型”决策树则只需考察一个属性子集。

8.4 结合策略

学习器结合可能会从三个方面带来好处：

1. 首先，从统计的方面来看，由于学习任务的假设空间往往很大，可能有多个假设在训练集上达到同等性能，此时若使用单学习器可能因误选而导致泛化性能不佳，结合多个学习器则会减小这一风险；
2. 第二，从计算的方面来看，学习算法往往会陷入局部极小，有的局部极小点所对应的泛化性能可能很糟糕，而通过多次运行之后进行结合，可降低陷入糟糕局部极小点的风险；
3. 第三，从表示的方面来看，某些学习任务的真实假设可能不在当前学习算法所考虑的假设空间中，此时若使用单学习器则肯定无效，而通过结合多个学习器，由于相应的假设空间有所扩大，有可能学得更好的近似。

图8.8给出了一个直观示意图：

假定集成包含 $T$ 个基学习器 ${h_1, h_2, \dots, h_r}$ ，其中 $h_i$ 在示例 $x$ 上的输出为 $h_i(x)$ ，下面介绍几种对 $h_i$ 进行结合的常见策略：

1. 平均法：简单平均法和加权平均法；
2. 投票法：绝对多数投票法与相对多数投票法；
3. 学习法：代表是Stacking算法，先从初始数据集训练出初级学习器，然后“生成”一个新数据集用于训练次级学习器，在这个新数据集中，初级学习器的输出被当作样例输入特征，而初始样本的标记仍被当作样例标记。

第9章 聚类

9.1 聚类任务

在“无监督学习”（unsupervised learning）中，训练样本的标记信息是未知的，目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律，为进一步的数据分析提供基础。此类学习任务中研究最多、应用最广的是“聚类”（clustering）。

• 聚类试图将数据集中的样本划分为若千个通常是不相交的子集，每个子集称为一个“簇”（cluster）。

通过这样的划分，每个簇可能对应于一些潜在的概念（类别），如“浅色瓜”“深色瓜”，“有籽瓜”“无籽瓜”，甚至“本地瓜”“外地瓜”等。

需说明的是，这些概念对聚类算法而言事先是未知的，聚类过程仅能自动形成簇结构，簇所对应的概念语义需由使用者来把握和命名。

形式化地说，

• 假定样本集 $D = { x_1, x_2, \dots, x_m }$ 包含 $m$ 个无标记样本，每个样本 $x_i = (x_{i1}; x_{i2}; \dots; x_{in})$ 是一个 $n$ 维特征向量；
• 聚类算法将样本集 $D$ 划分为 $k$ 个不相交的簇 ${ C_l | l = 1, 2, \dots, k }$ ，其中 $\displaystyle C_{l1} \cap_{l1 \neq l2} C_{l2} = \emptyset$ ；
• 相应地，我们用 $\lambda_j \in { 1, 2, \dots, k }$ 表示样本 $x_j$ 的“簇标记”（cluster label），即 $x_j \in C_{\lambda_j}$ ；
• 于是，聚类的结果可用包含 $m$ 个元素的簇标记向量 $\mathbf{\lambda} = (\lambda_1; \lambda_2; \dots; \lambda_m)$ 表示.

聚类既能作为一个单独过程，用于找寻数据内在的分布结构，也可作为分类等其他学习任务的前驱过程。

例如，在一些商业应用中需对新用户的类型进行判别，但定义“用户类型”对商家来说却可能不太容易，此时往往可先对用户数据进行聚类，根据聚类结果将每个簇定义为一个类，然后再基于这些类训练分类模型，用于判别新用户的类型，

基于不同的学习策略，人们设计出多种类型的聚类算法，本章后半部分将对不同类型的代表性算法进行介绍，但在此之前，我们先讨论聚类算法涉及的两个基本问题一性能度量和距离计算。

• 9.2 性能度量

• 9.3 距离计算

9.4 原型聚类

原型聚类亦称“基于原型的聚类”（prototype-based clustering），此类算法假设聚类结构能通过一组原型刻画，在现实聚类任务中极为常用。

“原型”是指样本空间中具有代表性的点.

通常情形下，算法先对原型进行初始化，然后对原型进行迭代更新求解。

采用不同的原型表示、不同的求解方式，将产生不同的算法，下面介绍几种著名的原型聚类算法。

9.4.1 $k$ 均值算法

基本原理

给定样本集样本集 $D = { x_1, x_2, \dots, x_m }$ ，“k均值”（k-means）算法针对聚类所得簇划分 $C={C_1, C_2, \dots , C_k}$ 最小化平方误差：

$$\begin{align} E = \sum_{i=1}^k \sum_{x \in C_i} |x - \mu_i|^2 \tag{9.24} \end{align}$$

其中 $\mu_i = \frac{1}{C_i} \sum_{x \in C_i} x $ 是簇 $C_i$ 的均值向量。

可知，$k$ 均值算法认为簇的原型就是均值向量。

直观来看，式（9.24）在一定程度上刻画了簇内样本围绕簇均值向量的紧密程度，**$E$ 值越小表示簇内样本相似度越高**。

算法流程

最小化式（9.24）并不容易，找到它的最优解需考察样本集 $D$ 所有可能的簇划分，这是一个NP难问题【Aloise et al，2009】。

因此，$k$ 均值算法采用了贪心策略，通过迭代优化来近似求解式（9.24），算法流程如图9.2所示，其中：

• 第1行对均值向量进行初始化；
• 在第4-8行与第9-16行依次对当前簇划分及均值向量迭代更新；
• 若迭代更新后聚类结果保持不变，则在第18行将当前簇划分结果返回。

9.4.2 学习向量量化

基本原理

与 $k$ 均值算法类似，“学习向量量化”（Learning Vector Quantization，简称LVQ）也是试图找到一组原型向量来刻画聚类结构，但与一般聚类算法不同的是：

• LVQ假设数据样本带有类别标记，学习过程利用样本的这些监督信息来辅助聚类。

给定样本集 $D = { (x_1, y_1), (x_2, y_2), \dots, (x_m, y_m) }$ ，每个样本 $x_j$ 是由 $n$ 个属性描述的特征向量 $(x_{j1}; x_{j2}; \dots; x_{jn})$ ，$y_j \in \gamma$ 是样本 $x_j$ 的类别标记。

LVQ的目标是：

• 学得一组 $n$ 维原型向量 ${ p_1, p_2, \dots, p_q }$ ，每个原型向量代表一个聚类簇，其簇标记为 $t_i \in \gamma $ ，共 $q$ 个簇。

算法流程

LVQ算法描述如图9.4所示，其中：

• 第1行先对原型向量进行初始化。

  例如对第 $q$ 个簇可从类别标记为 $t_q$ 的样本中随机选取一个作为原型向量；

• 第2~12行对原型向量进行迭代优化。

  在每一轮迭代中，算法随机选取一个有标记训练样本，找出与其距离最近的原型向量，并根据两者的类别标记是否一致来对原型向量进行相应的更新；

  第5行是竞争学习的“胜者为王”策略.

• 在第12行中，若算法的停止条件已满足（例如已达到最大迭代轮数，或原型向量更新很小甚至不再更新），则将当前原型向量作为最终结果返回。

显然，LVQ的关键是第6-10行，即如何更新原型向量。

直观上看，对样本 $x_j$，若最近的原型向量 $p_{i^*}$ 与 $x_j$ 的类别标记相同，则令 $p_{i^*}$ 向 $x_j$ 的方向靠拢，如第7行所示，此时新原型向量为

$$\begin{align} p^‘ = p_{i^*} + \eta \ \cdot \ (x_j - p_{i^*}) \tag{9.25} \end{align}$$

那么新的原型向量 $p^‘$ 与 $x_j$ 之间的距离将减小为

$$\begin{align} ||p^‘ - x_j||2 &= ||p{i^*} + \eta \ \cdot \ (x_j - p_{i^*}) - x_j||2 \ &= (1 - \eta) \cdot ||p{i^*} - x_j||_2 \tag{9.26} \end{align}$$

相应地，若 $p_{i^*}$ 与 $x_j$ 的类别标记不同，则更新后的原型向量 $p^‘$ 与 $x_j$ 之间的距离将增大为 $(1 + \eta) \cdot ||p_{i^*} - x_j||_2 $ ，从而更远离 $x_j$ 。

在学得一组原型向量 ${ p_1, p_2, \dots, p_q }$ 后，即可实现对样本空间 $\chi$ 的簇划分。

• 对任意样本 $x$ ，它将被划入与其距离最近的原型向量所代表的簇中；

换言之，每个原型向量 $p_i$ 定义了与之相关的一个区域 $R_i$ ，该区域中每个样本与 $p_i$ 的距离不大于它与其他原型向量 $p_{j} \ \ (j \neq i)$ 的距离，即

$$\begin{align} R_i = { x \in \chi \ \ | \ \ ||x - p_i||_2 \ \leq \ ||x - p_j||_2 \ , \ j \neq i } \tag{9.27} \end{align}$$

由此形成了对样本空间 $\chi$ 的簇划分 ${R_1, R_2, \dots, R_q}$ ，该划分通常称为 **“Voronoi剖分” (Voronoi tessellation)**。

若将 $R_i$ 中样本全用原型向量 $p_i$ 表示，则可实现数据的“有损压缩”（lossy compression），这称为“向量量化”（vector quantization），LVQ亦由此而得名.

9.4.3 高斯混合聚类

与 $k$ 均值、LVQ用原型向量来刻画聚类结构不同，高斯混合（Mixture-of-Gaussian）聚类采用概率模型来表达聚类原型。

基本原理

我们先简单回顾一下（多元）高斯分布的定义：

$$\begin{align} p(x) = \frac{1}{\sqrt{2\pi} \sigma} \exp (- \frac{(x - \mu)^2}{2 \sigma^2}) \end{align}$$

更一般地，对 $n$ 维样本空间 $\chi$ 中的随机向量 $\mathbf{x}$ ，若 $\mathbf{x}$ 服从高斯分布，其概率密度函数为

$$\begin{align} p(\mathbf{x}) &= \frac{1}{(2\pi)^{\frac{n}{2}} |\Sigma|^{\frac{1}{2}} } \exp (- \frac{(\mathbf{x} - \mathbf{\mu})^T(\mathbf{x} - \mathbf{\mu})}{2 \ \Sigma}) \ &= \frac{1}{(2\pi)^{\frac{n}{2}} |\Sigma|^{\frac{1}{2}} } \exp {(- \frac{1}{2} ( \mathbf{x} - \mathbf{\mu} )^T \Sigma^{-1} (\mathbf{x} - \mathbf{\mu}) )} \tag{9.28} \end{align}$$

其中，$\mu$ 是 $n$ 维均值向量， $\Sigma$ 是 $n \times n$ 的协方差矩阵。

可以看出，高斯分布完全由这两个参数确定。为了明确显示高斯分布与相应参数的依赖关系，将概率密度函数记为 $p(\mathbf{x} \ | \ \mu, \Sigma)$ .

那么我们可定义高斯混合分布

$$\begin{align} p_{M}(\mathbf{x}) = \sum_{i=1}^k \alpha_i \ \cdot \ p(\mathbf{x} \ | \ \mu_i, \Sigma_i) \tag{9.29} \end{align}$$

该分布共由 $k$ 个混合成分组成，每个混合成分对应一个高斯分布。其中，$\alpha_i > 0$ 为相应的“混合系数”（mixture coefficient），且 $\sum_{i=1}^k \alpha_i = 1$ .

高斯混合聚类的基本思想是：

• 对于训练集 $D = { \mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_m }$ 中的某个样本 $\mathbf{x}_j$ ，确定其属于这 $k$ 个高斯分布中的哪一个，并以此将所有样本划分为 $k$ 个簇。

那么如何确定样本属于哪个高斯分布呢？

• 我们考虑贝叶斯定理，如果样本 $\mathbf{x}_j$ 属于高斯分布 $i$ 的后验概率更大，那么我们就将 $\mathbf{x}_j$ 划分到第 $i$ 个簇中。

具体来说，令随机变量 $z_j \in {1, 2, \dots, k}$ 表示生成样本 $\mathbf{x}_j$ 的高斯分布。

显然，$z_j$ 的先验概率对应于 $\alpha_i$ 。

那么根据贝叶斯定理，$z_j$ 的后验概率则对应于

$$\begin{align} p_M(z_j=i \ | \ \mathbf{x}_j) &= \frac{P(z_j = i) \ \cdot \ p_M(\mathbf{x}j | z_j = i)}{p_M(\mathbf{x}_j)} \ &= \frac{\alpha_i \ \cdot \ p_M(\mathbf{x}_j \ | \ \mu_i, \Sigma_i)}{\sum{l=1}^k \alpha_l \ \cdot \ p_M(\mathbf{x}_j \ | \ \mu_l, \Sigma_l)} \tag{9.30} \end{align}$$

换言之，$p_M(z_j=i \ | \ \mathbf{x}_j)$ 给出了样本 $\mathbf{x}_j$ 由第 $i$ 个高斯分布生成的后验概率。

为方便叙述，将其简记为 $\gamma_{ji} \ \ (i = 1, 2, \dots, k)$ .

当高斯混合分布（9.29）已知时，高斯混合聚类将把样本集 $D$ 划分为 $k$ 个簇 $\mathbf{C} = { C_1, C_2, \dots ,C_k}$ ，每个样本 $x_j$ 的簇标记 $\lambda_j$ 如下确定：

$$\begin{align} \lambda_j = \arg \max_{i \in { 1,2,\dots,k }} \gamma_{ji} \tag{9.31} \end{align}$$

因此，从原型聚类的角度来看，高斯混合聚类是釆用概率模型（高斯分布）对原型进行刻画，簇划分则由原型对应后验概率确定。

划分过程——EM算法

那么，对于式（9.29），模型参数 ${ (\alpha_i, \mu_i, \Sigma_i) \ | \ 1 \leq i \leq k }$ 如何求解呢？

显然，给定样本集 $D$，可采用极大似然估计，即最大化（对数）似然

$$\begin{align} LL(D) &= \ln {(\prod_{j=1}^m p_M(\mathbf{x}j))} \ &= \sum{j=1}^m \ln {(\sum_{i=1}^k \alpha_i \ \cdot \ p(\mathbf{x}_j \ | \ \mu_i, \Sigma_i))} \tag{9.32} \end{align}$$

考虑约束条件 $\sum_{i=1}^k \alpha_i = 1$ ，使用拉格朗日乘子法，分别对 $\mu_i, \Sigma_i, \alpha_i$ 求导，并令一阶导数为零得到新的 $\mu_i, \Sigma_i, \alpha_i$ 表达式。

然后采用EM算法进行迭代优化求解：

• E步（Expectation）：使用当前的 $\mu_i, \Sigma_i, \alpha_i$ 和样本数据 $\mathbf{x}j$ 计算 $\gamma{ji}$ ，表示 $\mathbf{x}_j$ 属于第 $i$ 个高斯的概率；

• M步（Maximization）：将 $\gamma_{ji}$ 代入前面利用极大似然估计求得的 $\mu_i, \Sigma_i, \alpha_i$ 表达式，更新 $\mu_i, \Sigma_i, \alpha_i$ 的值。

  不断循环迭代E、M步，直至收敛。

• 9.x 密度聚类

• 9.x 层次聚类

9.6 思考与归纳

• $k$ 均值算法认为一个簇的原型就是该集合中的均值向量，而LVQ则是借助监督信息，通过迭代学习得到的原型向量，这个原型是可能不存在于样本集中的。

第10章 降维

10.1 k近邻学习

k近邻（k-Nearest Neighbor，简称kNN）学习是一种常用的监督学习方法，其工作机制非常简单：

给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个“邻居”的信息来进行预测。

• 通常，在分类任务中可使用“投票法”，即选择这k个样本中出现最多的类别标记作为预测结果；
• 在回归任务中可使用“平均法”，即将这k个样本的实值输出标记的平均值作为预测结果；
• 还可基于距离远近进行加权平均或加权投票，距离越近的样本权重越大，

与前面介绍的学习方法相比，k近邻学习有一个明显的不同之处：它似乎没有显式的训练过程！

• 事实上，它是“懒惰学习”（lazy learning）的著名代表，此类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理；
• 相应的，那些在训练阶段就对样本进行学习处理的方法，称为“急切学习”（eager learning）.

图10.1给出了k近邻分类器的一个示意图。

• 显然，k是一个重要参数，当k取不同值时，分类结果会有显著不同；
• 另一方面，若采用不同的距离计算方式，则找出的“近邻”可能有显著差别，从而也会导致分类结果有显著不同。

10.2 低维嵌入

诸如kNN等许多学习方法都涉及距离计算，而高维空间会给距离计算带来很大的麻烦，例如当维数很高时甚至连计算内积都不再容易。

事实上，在高维情形下出现的数据样本稀疏、距离计算困难等问题是所有机器学习方法共同面临的严重障碍，被称为“维数灾难”（curse ofdimensionality).

• 缓解维数灾难的一个重要途径是降维（dimension reduction），亦称“维数约简”，即

  通过某种数学变换将原始高维属性空间转变为一个低维“子空间”（subspace），在这个子空间中样本密度大幅提高，距离计算也变得更为容易。

为什么能进行降维？这是因为在很多时候，人们观测或收集到的数据样本虽是高维的，但与学习任务密切相关的也许仅是某个低维分布，即高维空间中的一个低维“嵌入”（embedding）.

图10.2给出了一个直观的例子，原始高维空间中的样本点，在这个低维嵌入子空间中更容易进行学习。

一般来说，欲获得低维子空间，最简单的是对原始高维空间进行线性变换。

给定 $n$ 维空间中的样本 $\mathbf{X} = (\mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_m) \in \mathbb{R}^{n \times m}$ ，变换之后得到 $d \ll n$ 维空间中的样本

$$\begin{align} \mathbf{Z} = \mathbf{W}^T \mathbf{X} \tag{10.13} \end{align}$$

其中，$\mathbf{W} = (\mathbf{w}_1, \mathbf{w}_2, \dots, \mathbf{w}_d) \in \mathbb{R}^{n \times d}$ 是变换矩阵，$\mathbf{Z} = (\mathbf{z}_1, \mathbf{z}_2, \dots, \mathbf{z}_m) \in \mathbb{R}^{d \times m}$ 是样本在新空间中的表达。

• 变换矩阵 $\mathbf{W}$ 可视为 $d$ 个 $n$ 维基向量；
• $\mathbf{z}_i = \mathbf{W}^T \mathbf{x}_i$ 是第 $i$ 个样本与这 $d$ 个基向量分别做内积而得到的 $d$ 维属性向量。换言之，$\mathbf{z}_i$ 是原样本向量 $\mathbf{x}_i$ 在新坐标系 ${ \mathbf{w}_1, \mathbf{w}_2, \dots, \mathbf{w}_d }$ 中的坐标向量。

基于线性变换来进行降维的方法称为线性降维方法，它们都符合式（10.13）的基本形式，不同之处是对低维子空间的性质有不同的要求，相当于对 $\mathbf{W}$ 施加了不同的约束。

在下一节我们将会看到，若要求低维子空间对样本具有最大可分性，则将得到一种极为常用的线性降维方法。

10.3 主成分分析

主成分分析（Principal Component Analysis，简称PCA）是最常用的一种降维方法。

在介绍PCA之前，不妨先考虑这样一个问题：

• 对于正交属性空间中的样本点，如何用一个超平面（直线的高维推广）对所有样本进行恰当的表达？

容易想到，若存在这样的超平面，那么它大概应具有这样的性质：

1. 最近重构性：样本点到这个超平面的距离都足够近；
2. 最大可分性：样本点在这个超平面上的投影能尽可能分开.

有趣的是，基于最近重构性和最大可分性，能分别得到主成分分析的两种等价推导。

10.3.1 最近重构性

最近重构性实际上就是最小均方误差，我们首先：

• 假定数据样本进行了中心化，即令 $\mathbf{x}_i = \mathbf{x}_i - \bar{\mathbf{x}} $ ，最终满足 $\sum_i \mathbf{x}_i = \mathbf{0}$ ；
• 再假定投影变换后得到的新坐标系为 ${\mathbf{w}_1, \mathbf{w}_2, \dots, \mathbf{w}_n }$ ，其中 $\mathbf{w}_i$ 是标准正交基向量，$||\mathbf{w}_i||_2 = 1$ 且 $\mathbf{w}_i^T \mathbf{w}_j = 0 \ \ (i \neq j)$ ；
• 若丢弃新坐标系中的部分坐标，即将维度降低到 $d \ll n$ ，则得到变换矩阵 $\mathbf{W} = (\mathbf{w}_1, \mathbf{w}_2, \dots, \mathbf{w}_d)$ 。

那么样本点 $\mathbf{x}_i$ 在低维坐标系中的投影是 $\mathbf{z}_i = \mathbf{W}^T \mathbf{x}_i$ 。

为了衡量样本在投影前后，即 $\mathbf{x}_i$ 与 $\mathbf{z}_i$ 之间的距离，需要将其放在同一个坐标系下。

不妨令 $\hat{\mathbf{x}}_i$ 表示投影点 $\mathbf{z}_i$ 在原坐标系下的向量，则有 $\hat{\mathbf{x}}_i = \mathbf{W} \mathbf{z}_i = \mathbf{W} \mathbf{W}^T \mathbf{x}_i$ .

那么原样本点 $\mathbf{x}_i$ 与基于投影重构的样本点 $\hat{\mathbf{x}}_i$ 之间的距离为

$$\begin{align} (\hat{\mathbf{x}}_i - \mathbf{x}_i)^2 &= (\mathbf{W} \mathbf{W}^T \mathbf{x}_i - \mathbf{x}_i)^T (\mathbf{W} \mathbf{W}^T \mathbf{x}_i - \mathbf{x}_i) \ &= ( \mathbf{x}_i^T \mathbf{W} \mathbf{W}^T - \mathbf{x}_i^T) (\mathbf{W} \mathbf{W}^T \mathbf{x}_i - \mathbf{x}_i) \ &= \mathbf{x}_i^T \mathbf{W} \mathbf{W}^T \mathbf{W} \mathbf{W}^T \mathbf{x}_i - 2 \mathbf{x}_i^T \mathbf{W} \mathbf{W}^T \mathbf{x}_i + \mathbf{x}_i^T \mathbf{x}_i \ &= - \mathbf{x}_i^T \mathbf{W} \mathbf{W}^T \mathbf{x}_i + \mathbf{x}_i^T \mathbf{x}_i \ &= - \mathbf{z}_i^T \mathbf{z}_i + C \tag{10.14} \end{align}$$

其中，$\mathbf{x}_i^T \mathbf{x}_i$ 为已知，可直接记为常数 $C$ .

因此考虑整个训练集，得到下面的优化目标

$$\begin{align} \min_{\mathbf{W}} \ \ \frac{1}{m} \sum_{i=1}^m - \mathbf{z}_i^T \mathbf{z}_i \ s.t. \ \mathbf{W}^T \mathbf{W} = \mathbf{I} \tag{10.15} \end{align}$$

这就是主成分分析的优化目标。

10.3.2 最大可分性

从最大可分性出发，能得到主成分分析的另一种解释。

我们知道，样本点 $\mathbf{x}_i$ 在新空间中超平面上的投影是 $\mathbf{W}^T \mathbf{x}_i$ ，若所有样本点尽可能分开，则应该使投影后样本点的方差最大化。

由于投影后的协方差矩阵为 $\frac{1}{m} \sum_{i=1}^{m} \mathbf{z}_i^T \mathbf{z}_i$ ，而样本方差为协方差矩阵的迹，即

$$\begin{align} \max_{\mathbf{W}} \ \ & tr(\frac{1}{m} \sum_{i=1}^m \mathbf{z}i \mathbf{z}i^T) \ &= \frac{1}{m} \sum{i=1}^m tr(\mathbf{z}_i \mathbf{z}_i^T) \ &= \frac{1}{m} \sum{i=1}^m \mathbf{z}_i^T \mathbf{z}_i \ & s.t. \ \mathbf{W}^T \mathbf{W} = \mathbf{I} \tag{10.16} \end{align}$$

显然，式（10.16）与（10.15）等价。

10.3.4 PCA的算法过程