统计学习方法第一章统计学习方法概论

1.1 统计学习

1.1.1 特点

统计学习（statistical learning）是关于计算机基于数据构建概率统计模型并运用模型对数据进行预测与分析的一门学科。

赫尔伯特·西蒙（Herbert A.Simon）对“学习”给出如下定义：如果一个系统能够通过执行某个过程改变它的性能，这就是学习。

1.1.2 对象

统计学习的对象是数据。

统计学习关于数据的基本假设是同类数据具有一定的统计规律性，这是统计学习的前提。

1.1.3 目的

统计学习用于对数据进行预测和分析，特别是对未知新数据进行预测与分析。

1.1.4 方法

监督学习（supervised learning）
非监督学习（unsupervised learning）
半监督学习（semi-supervised learning）
强化学习（reinforcement learning）

1.1.5 统计学习方法三要素

模型（model）：即假设空间（hypothesis space），假设空间是一个集合，这个集合包含要学习的模型
策略（strategy）：模型选择的准则
算法（algorithm）：模型学习的算法

1.2 监督学习

监督学习（supervised learning）的任务是学习一个模型，使模型能够对任意给定的输入，对其相应的输出做出一个好的预测。

1.2.1 基本概念

输入空间（input space）：输入的所有可能取值的集合，表示为 ${\cal X}$
输出空间（output space）：输出的所有可能取值的集合，表示为 ${\cal Y}$
实例（instance）：每个具体的输入，通常由特征向量（feature vector）表示
特征空间（feature space）：所有特征向量存在的空间，每一维度对应一个特征
训练数据（training data）：由输入（或特征向量）与输出对组成
联合概率分布（joint probability distribution）：监督学习假设输入与输出的随机变量 $X$ 和 $Y$ 遵循联合概率分布 $P(X,Y)$
假设空间（hypothesis space）：模型属于由输入空间到输出空间的映射的集合，这个集合就是假设空间。假设空间的确定意味着学习范围的确定

注1：输入和输出空间可以使有限集也可以是整个欧式空间；输入与输出空间可以使用一个空间，也可以是不同的空间；通常输出空间远小于输入空间。

注2：有时假设输入空间与特征空间为相同的空间，对它们不予区分；有时假设输入空间与特征空间为不同的空间，将实例从输入空间映射到特征空间。模型实际上都是定义在特征空间上的。

注3：在学习过程中，假设联合概率分布存在，但对于学习系统来说，联合概率分布的具体定义是未知的。训练数据与测试数据被看作是依联合概率分布 $P(X,Y)$ 独立同分布（independent and identically distribution）产生的。统计学习假设数据存在一定的统计规律，$X$ 和 $Y$ 遵循联合概率分布 $P(X,Y)$ 就是监督学习关于数据的基本假设。

在监督学习过程中，将输入和输出看做是定义在输入（特征）空间与输出空间上的随机变量的取值。输入、输出变量用大写字母表示，输入、输出变量所取的值用小写字母表示。

输入实例 $x$ 的特征向量记作

$$x=\left(x^{(1)},x^{(2)},\dots,x^{(n)}\right)^\text{T}$$

$x^{(i)}$ 表示 $x$ 的第 $i$ 个特征。

多个输入变量的第 $i$ 个记作

$$x_i=\left(x_i^{(1)},x_i^{(2)},\dots,x_i^{(n)}\right)^\text{T}$$

训练集：$T=\{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)\}$

监督学习的模型可以是概率模型或非概率模型，由条件概率分布 $P(Y|X)$ 或决策函数（decision function）$Y=f(X)$ 表示。对具体的输入进行相应的输出预测时，写作 $P(y|x)$ 或 $y=f(x)$。

1.3 统计学习三要素

1.3.1 模型

统计学习首要考虑的问题是学习什么样的模型。模型的假设空间包含所有可能的条件概率分布或决策函数。假设空间中的模型一般有无穷多个。

假设空间用 $\cal{F}$ 表示。假设空间可以定义为决策函数或条件概率分布的集合

$${\cal F}=\{f|Y=f_\theta(X),\theta \in \mathbb R^n\}$$

或

$${\cal F}=\{P|P_\theta(Y|X),\theta \in \mathbb R^n\}$$

参数向量 $\theta$ 取值于 $n$ 维欧式空间 $\mathbb R^n$，称为参数空间（parameter space）。

1.3.2 策略

有了模型的假设空间，统计学习接着需要考虑的是按照什么样的准则学习或选择最优的模型。

损失函数和风险函数

损失函数（loss function）或代价函数（cost function）用来度量预测错误的程度。损失函数是 $f(X)$ 和 $Y$ 的非负实值函数，记作 $L(Y,f(X))$。

统计学习常用的损失函数有以下几种：

0-1 损失函数（0-1 loss function）
$$L(Y,f(X))=\begin{cases} 1, & Y\neq f(X) \\ 0, & Y=f(X) \end{cases}$$
平方损失函数（quadratic loss function）
$$L(Y,f(X))=(Y-f(X))^2$$
绝对损失函数（absolute loss function）
$$L(Y,f(X))=|Y-f(X)|$$
对数损失函数（logarithmic loss function）或对数似然损失函数（log-likelihood loss function）
$$L(Y,P(Y|X))=-\log P(Y|X)$$

风险函数（risk function）或期望损失（expected loss）：理论上模型 $f(X)$ 关于联合分布 $P(X,Y)$ 平均意义下的损失，记作 $R_\text{exp}$。

$$R_\text{exp}(f)=\text{E}_P[L(Y,f(X))]=\int_{{\cal X}\times{\cal Y}}L(y,f(x))P(x,y)dxdy$$

经验风险（empirical risk）或经验损失（empirical loss）：模型 $f(X)$ 关于训数据集的平均损失，记作 $R_\text{emp}$。

$$R_\text{emp}(f)=\frac{1}{N}\sum_{i=1}^NL\left(y_i,f(x_i)\right)$$

经验风险最小化

经验风险最小化（empirical risk minimization，ERM）策略认为：经验风险最小的模型是最优的模型。即求解下面的最优化问题

$$ \min_{f\in {\cal F}} \frac{1}{N}\sum_{i=1}^NL\left(y_i,f(x_i)\right)$$

其中 ${\cal F}$ 是假设空间。

当样本容量足够大时，经验风险最小化能保证有很好的学习效果。例如，极大似然估计（maximum likelihood estimation）就是经验风险最小化的一个例子。当模型是条件概率分布，损失函数是对数损失函数时，经验风险最小化就等价于极大似然估计。

但是，当样本容量很小时，经验风险最小化学习的效果就未必很好，会产生“过拟合（over-fitting）现象”。

结构风险最小化

结构风险最小化（structural risk minimization，SRM）是为了防止过拟合而提出来的策略。结构风险最小化等价于正则化（regularization）。结构风险在经验风险上加上表示模型复杂度的正则化项（regularizer）或罚项（penalty term），定义如下

$$R_\text{srm}=\frac{1}{N}\sum_{i=1}^NL\left(y_i,f(x_i)\right)+\lambda J(f)$$

其中 $J(f)$ 为模型的复杂度，是定义在假设空间 ${\cal F}$ 上的泛函。模型 $f$ 越复杂，$J(f)$ 越大。也就是说，复杂度表示了对复杂模型的惩罚，$\lambda\geq 0$ 是系数，用以权衡经验风险和模型复杂度。

结构风险小需要经验风险与模型复杂度同时小，结构风险小的模型往往对训练数据以及未知的测试数据都有较好的预测。结构化风险最小化策略认为：结构风险最小的模型是最优的模型。即求解下面的最优化问题

$$ \min_{f\in {\cal F}} \frac{1}{N}\sum_{i=1}^NL\left(y_i,f(x_i)\right)+\lambda J(f)$$

贝叶斯估计中的最大后验概率估计（maximum posterior probability estimation，MAP）就是结构化风险最小化的一个例子。当模型是条件概率分布，损失函数是对数损失函数，模型复杂度由模型的先验概率表示时，结构风险最小化就等价于最大后验概率估计。

1.3.3 算法

算法是指学习模型的具体计算方法。统计学习基于训练数据集，根据学习策略，从假设空间中选择最优模型，最后需要考虑用什么样的计算方法求解最优模型。

如果最优化问题有显式的解析解，这个最优化问题就比较简单，但通常解析解不存在，这就需要用数值方法求解。如何保证找到全局最优解，并使求解的过程非常高效，就成为一个重要问题。

1.4 模型评估与模型选择

1.4.1 训练误差

假设学习到的模型是 $Y=\hat{f}(X)$，训练误差（training error）是模型 $Y=\hat{f}(X)$ 关于训练数据集的平均损失

$$R_\text{emp}(\hat{f})=\frac{1}{N}\sum_{i=1}^NL(y_i,\hat{f}(x_i))$$

其中 $N$ 是训练样本容量。

1.4.2 测试误差

测试误差是模型 $Y=\hat{f}(X)$ 关于测试数据集的平均损失

$$e_\text{test}(\hat{f})=\frac{1}{N'}\sum_{i=1}^{N'}L(y_i,\hat{f}(x_i))$$

其中 $N'$ 是测试样本容量。

例如，当损失函数是 0-1 损失时，测试误差就变成了常见的测试数据集上的误差率（error rate）

$$e_\text{test}=\frac{1}{N'}\sum_{i=1}^{N'}{\mathbb I}(y_i\neq \hat{f}(x_i))$$

这里 ${\mathbb I}$ 是指示函数，即 $y_i\neq \hat{f}(x_i)$ 时为 1，否则为 0。

相应的，常见的测试数据集上的准确率（accuracy）为

$$r_\text{test}=\frac{1}{N'}\sum_{i=1}^{N'}{\mathbb I}(y_i=\hat{f}(x_i))$$

训练误差的大小，对判断给定的问题是不是一个容易学习的问题是有意义的，但本质上不重要。

测试误差反应了学习方法对未知的测试数据集的预测能力，是学习中的重要概念。

1.4.3 过拟合

当假设空间含有不同复杂度（例如，不同的参数个数）的模型时，就要面临模型选择（model selection）的问题。我们希望选择或学习一个合适的模型。

如果一味追求提高对训练数据的预测能力，所选模型的复杂度则往往会比真模型更高，这种现象称为过拟合。

过拟合是指学习时选择的模型所包含的参数过多，以致于出现这一模型对已知数据预测得很好，但对未知数据预测很差的现象。

训练误差与测试误差和模型复杂度关系如下：

训练误差与测试误差和模型复杂度

1.5 正则化与交叉验证

正则化与交叉验证是两种常用的模型选择方法。

1.5.1 正则化

正则化是结构风险最小化策略的实现。正则化项一般是模型复杂度的单调递增函数，模型越复杂，正则化值就越大。

正则化一般形式形式

$$ \min_{f\in {\cal F}} \frac{1}{N}\sum_{i=1}^NL\left(y_i,f(x_i)\right)+\lambda J(f)$$

其中，第一项是经验风险，第二项是正则化项，$\lambda\geq 0$ 为调整两者关系之间的系数。

正则化项可以取不同的形式。例如：回归问题中，损失函数是平方损失，正则化项可以是参数向量的 $L_2$ 范数

$$L(w)=\frac{1}{N}\sum_{i=1}^N\left(f(x_i;w)-y_i\right)^2+\frac{\lambda}{2}||w||^2$$

这里，$||w||$ 表示参数向量 $w$ 的 $L_2$ 范数。

1.5.2 交叉验证

另一种常用的模型选择方法是交叉验证（cross validation）。

如果给定的样本数据充足，进行模型选择的一种简单方法是随机的将数据集切成三部分：训练集、验证集和测试集。训练集用来训练模型，验证集用于模型选择，测试集用于最终对学习方法的评估。

但是，在许多实际应用中数据是不充足的。为了选择好的模型，可以采用交叉验证的方法。

交叉验证的基本思想是重复的使用数据：把给定的数据进行切分，将切分的数据集组合为训练集与测试集，在此基础上反复进行训练、测试以及模型选择。

简单交叉验证

首先随机的将已给数据分成两部分：训练集、测试集。然后用训练集在各种条件下（例如，不同的参数个数）训练模型，从而得到不同的模型。然后，在测试集上评价各个模型的测试误差，选出测试误差最小的模型。

$S$ 折交叉验证

应用最多的是 $S$ 折交叉验证（S-fold cross validation），方法如下：首先随机的将已给数据切分为 $S$ 个互不相交的大小相同的子集；然后利用 $S-1$ 个子集的数据训练模型，利用余下的子集测试模型；将这一过程对可能的 $S$ 种选择重复进行；最后选出 $S$ 次评估中平均测试误差最小的模型。

留一交叉验证

$S$ 折交叉验证的特殊情形是 $S=N$，称为留一交叉验证（leave-one-out cross validation），往往在数据缺乏的情况下使用。这里 $N$ 是给定数据集的容量。

1.6 泛化能力

1.6.1 泛化误差

学习方法的泛化能力（generalization ability）是指由该学习方法学到的模型对未知数据的预测能力。

泛化误差（generalization error）：如果学到的模型是 $\hat{f}$，那么用这个模型对未知数据预测的误差即为泛化误差。

$$R_\text{exp}(\hat{f})=\text{E}_P[L(Y,f(X))]=\int_{{\cal X}\times{\cal Y}}L(y,\hat{f}(x))P(x,y)dxdy$$

实际上，泛化误差就是所学习到的模型的期望风险。

1.6.2 泛化误差上界

学习方法的泛化能力分析往往使用过研究泛化误差的概率上界进行的，简称为泛化误差上界（generalization error bound）。也就是说，可以通过比较两种学习方法的泛化误差上界的大小来比较它们的优劣。

泛化误差上界具有如下性质：

它是样本容量的函数，当样本容量增加时，泛化误差上界趋于 0
它是假设空间容量（capacity）的函数，假设空间容量越大，模型就越难学，泛化误差上界就越大

1.6.3 二分类问题的泛化误差上界

考虑二分类问题。已知训练数据集 $T=\{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)\}$，它是从联合概率分布 $P(X,Y)$ 独立同分布产生的，$X\in \mathbb R^n$，$Y\in \{-1,1\}$。假设空间是函数的有限集合 ${\cal F}=\{f_1.f_2.\dots,f_d\}$，$d$ 是函数个数。设 $f$ 是从 ${\cal F}$ 中选取的函数。损失函数是 0-1 损失。关于 $f$ 的期望风险和经验风险分别是

$$\begin{eqnarray} R_\text{exp}(f)&=&\text{E}_P[L(Y,f(X))]\\ R_\text{emp}(f)&=&\frac{1}{N}\sum_{i=1}^NL(y_i,f(x_i)) \end{eqnarray}$$

经验风险最小化函数是

$$f_N=\arg \min_{f\in{\cal F}}R_\text{emp}(f)$$

人们更关心的是 $f_N$ 的泛化能力

$$R(f_N)=\text{E}_P[L(Y,f_N(X))]$$

定理 1.1（泛化误差上界）对二分类问题，当假设空间是有限个函数的集合 ${\cal F}=\{f_1.f_2.\dots,f_d\}$ 时，对任意一个函数 $f\in{\cal F}$，至少以概率 $1-\delta$，以下不等式成立

$$R(f)\leq R_\text{emp}(f)+\epsilon(d,N,\delta)$$

其中，
$$\epsilon(d,N,\delta)=\sqrt{\frac{1}{2N}\left(\log d+\log \frac{1}{\delta}\right)}$$

上述定理表明：训练误差越小，泛化误差也越小；当 $N$ 趋于无穷时，第二项为 0；假设空间包含的函数越多，泛化误差越大。

证明：在证明过程中要用到 Hoeffding 不等式，先叙述如下：

Hoeffding 不等式适用于有界的随机变量。设有两两独立的一系列随机变量 $X_{1},\dots ,X_{n}$。假设对所有的 $1\leq i\leq n$，$X_{i}$ 都是几乎有界的变量，即满足

$$\mathbb {P} (X_{i}\in [a_{i},b_{i}])=1$$

那么这 $n$ 个随机变量的经验期望

$$\overline {X}={\frac {X_{1}+\cdots +X_{n}}{n}}$$

满足以下的不等式

$$\begin{eqnarray} \mathbb {P}({\overline {X}}-\mathbb {E} [{\overline {X}}]\geq t) &\leq& \exp \left(-{\frac {2t^{2}n^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}}\right)\\ \mathbb {P} (|{\overline {X}}-\mathbb {E} [{\overline {X}}]|\geq t)&\leq& 2\exp \left(-{\frac {2t^{2}n^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}}\right) \end{eqnarray}$$

对任意函数 $f\in{\cal F}$，$R_\text{emp}(f)$ 是 $N$ 个随机变量 $L(Y,f(X))$ 的样本均值，$R(f)$ 是随机变量 $L(Y,f(X))$ 的期望值。如果损失函数取值于区间 [0,1]，则由 Hoeffding 不等式得到，对 $\epsilon>0$，以下不等式成立

$$P(R(f)-R_\text{emp}(f)\geq\epsilon)\leq\exp (-2N\epsilon^2)$$

由于 ${\cal F}=\{f_1;f_2,\dots,f_d\}$ 是一个有限集合，故

$$\begin{eqnarray} P\left(\exists f\in{\cal F}:R(f)-R_\text{emp}(f\right)\geq\epsilon)&=&P\left(\bigcup_{f\in{\cal F}}\{R(f)-R_\text{emp}(f)\geq\epsilon\}\right)\\ &\leq&\sum_{f\in{\cal F}}P(R(f)-R_\text{emp}(f)\geq\epsilon)\\ &\leq& d\exp(-2N\epsilon^2) \end{eqnarray}$$

或者等价的，对任意的 $f\in{\cal F}$，有

$$P(R(f)-R_\text{emp}(f)\geq\epsilon))\geq1-d\exp(-2N\epsilon^2)$$

令

$$\delta=d \exp(-2N\epsilon^2)$$

则

$$P(R(f)<R_\text{emp}(f)+\epsilon)\geq1-\delta$$

证毕。

1.7 生成模型与判别模型

监督学习方法也可以分为生成方法（generative approach）和判别方法（discriminative approach）。所学到的模型分别称为生成模型（generative model）和判别模型（discriminative model）。

1.7.1 生成方法

生成方法由数据学习联合概率分布 $P(X,Y)$，然后求出条件概率分布 $P(Y|X)$ 作为预测的模型，即生成模型

$$P(Y|X)=\frac{P(X,Y)}{P(X)}$$

这样的方法之所以称为生成方法，是因为模型表示了给定输入 $X$ 产生输出 $Y$ 的生成关系。

典型的生成模型有：朴素贝叶斯法和隐马尔科夫模型。

1.7.2 判别方法

判别方法由数据直接学习策略函数 $f(X)$ 或者条件概率分布 $P(Y|X)$ 作为预测的模型。判别方法关心的是对给定的输入 $X$，应该预测什么样的输出 $Y$。

典型的判别模型有：$k$ 近邻法，感知机，决策树，logistic 回归模型，最大熵模型，支持向量机，提升方法和条件随机场等。

1.7.3 不同方法的特点

生成方法：

生成方法可以还原出联合概率分布 $P(X,Y)$，而判别方法则不能
生成方法的学习收敛速度更快，即当样本容量增加时，学到的模型可以更快的收敛到真实模型
当存在隐变量时，仍可以使用生成方法，此时判别方法就不能用了

判别方法：

判别方法直接学习的是条件概率 $P(Y|X)$ 或决策函数 $f(X)$，直接面对预测，往往学习的准确率更高
由于直接学习 $P(Y|X)$ 或 $f(X)$，可以对数据进行各种程度上的抽象、定义特征并使用特征，因此可以简化学习问题

1.8 分类问题

在监督学习中，当输出变量 $Y$ 取有限个离散值时，预测问题便成为分类问题。

分类器（classifier）：从数据中学习到的一个分类模型或分类决策函数。

评价分类器性能的指标一般是分类准确率（accuracy）：对于给定的测试数据集，分类器正确分类的样本数与总样本数之比。

对于二分类问题常用的评价指标是精确率（precision）和召回率（recall）。

通常以关注的类为正类，其他类为负类，分类器在测试数据集上的预测或正确或不正确，4 种情况出现的总数分别记为：

TP：将正类预测为正类的数目
FN：将正类预测为负类的数目
FP：将负类预测为正类的数目
TN：将负类预测为负类的数目

精确率定义

$$P=\frac{TP}{TP+FP}$$

召回率定义

$$R=\frac{TP}{TP+FN}$$

$F_1$ 值

$$\frac{2}{F_1}=\frac{1}{P}+\frac{1}{R}\longrightarrow F_1=\frac{2TP}{2TP+FP+FN}$$

许多统计学习方法可以用于分类，包括 $k$ 近邻法，感知机，朴素贝叶斯法，决策树，决策列表，logistic 回归模型，支持向量机，提升方法，贝叶斯网络，神经网络，Winnow 等。

一个分类应用的例子：垃圾邮件、非垃圾邮件分类。

1.9 标注问题

标注（tagging）也是一个监督学习问题，可以认为标注问题是分类问题的一个推广，标注问题又是更复杂的结构预测（structure prediction）问题的简单形式。

标注问题的输入是一个观测序列，输出是一个标记序列或状态序列。标注问题的目标在于学习一个模型，使它能够对观测序列给出标记序列作为预测。注意，可能的标记个数是有限的，但其组合所成的标记序列的个数是依序列长度呈指数级增长的。

评价标注模型的指标和分类模型一样，常用的有标注准确率、精确率和召回率。

标注常用的统计学习方法有：隐马尔科夫模型，条件随机场。

一个标注的例子：对英文文章进行标注，英文单词是一个观察，英文句子是一个观察序列，标记表示名词短语的“开始”、“结束”和“其他”。

1.10 回归问题

回归（regression）是监督学习的另一个重要问题。回归用于预测输入变量（自变量）和输出变量（因变量）之间的关系，特别是当输入变量的值发生变化时，输出变量的值随之发生的变化。回归问题等价于函数拟合：选择一条函数曲线使其很好的拟合已知数据且很好的预测未知数据。

回归问题按照输入变量的个数，分为一元回归和多元回归；按照输入变量和输出变量之间的关系分为线性回归和非线性回归。

回归学习中最常用的损失函数是平方损失函数，在此情况下，回归问题可以用最小二乘法（least squares）求解。

一个回归的例子：市场趋势预测。