【统计学习方法】第1章 统计学习方法概论

如果一个系统能够通过执行某个过程改进它的性能，这就是学习

— Herbert A. Simon

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

基本概念：

输入空间（input space）：输入所有可能取值的集合

输出空间（output space）：输出所有可能取值的集合

实例（instance）：具体的输入，通常由特征向量（feature vector）表示

特征空间（feature space）：所有特征向量存在的空间

监督学习从训练数据（training data）集合中学习模型，对测试数据（test data）进行预测。训练数据由输入（或特征向量）与输出对组成，训练集通常表示为

T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) } T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\} T={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)}

测试数据也由相应的输入与输出对组成。输入与输出对又称为样本（sample）或样本点

监督学习假设输入与输出的随机变量 X X X 和 Y Y Y 遵循联合分布概率 P ( X , Y ) P(X,Y) P(X,Y)。 P ( X , Y ) P(X,Y) P(X,Y) 表示分布函数，或分布密度函数

监督学习的目的在于学习一个由输入到输出的映射，这一映射由模型来表示。模型属于由输入空间到输出空间的映射的集合，这个集合就是假设空间（hypothesis space）

在监督学习过程中，模型就是所要学习的条件概率分布或决策函数。模型的假设空间（hypothesis space）包含所有可能的条件概率分布或决策函数。

假设空间用 F \mathcal{F} F 表示。假设空间可以定义为决策函数的集合

F = { f ∣ Y = f ( X ) } \mathcal{F}=\{f|Y=f(X)\} F={f∣Y=f(X)}

其中， X X X 和 Y Y Y 是定义在输入空间 X \mathcal{X} X 和输出空间 Y \mathcal{Y} Y 上的变量。这时 F \mathcal{F} F 通常时由一个参数向量决定的函数族：

F = { f ∣ Y = f θ ( X ) , θ ∈ R n } \mathcal{F}=\{f|Y=f_\theta(X),\theta\in\mathbb{R}^n\} F={f∣Y=fθ​(X),θ∈Rn}

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

假设空间也可以定义为条件概率的集合

F = { P ∣ P ( Y ∣ X ) } \mathcal{F}=\{P|P(Y|X)\} F={P∣P(Y∣X)}

其中， X X X 和 Y Y Y 是定义在输入空间 X \mathcal{X} X 和输出空间 Y \mathcal{Y} Y 上的随机变量。这时 F \mathcal{F} F 通常是由一个参数向量决定的条件概率分布族：

F = { P ∣ P θ ( Y ∣ X ) , θ ∈ R n } \mathcal{F}=\{P|P_\theta(Y|X),\theta\in\mathbb{R}^n\} F={P∣Pθ​(Y∣X),θ∈Rn}

参数向量 θ \theta θ 取值于 n n n 维欧式空间 R n \mathbb{R}^n Rn，也称为参数空间（parameter space）

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

损失函数值越小，模型就越好。由于模型的输入、输出 ( X , Y ) (X,Y) (X,Y) 是随机变量，遵循联合分布 P ( X , Y ) P(X,Y) P(X,Y)，所以损失函数的期望是

R exp ⁡ ( f ) = E P [ L ( Y , f ( X ) ) ] = ∫ x × y L ( y , f ( x ) ) P ( x , y ) d x d y R_{\exp}(f)=E_P[L(Y,f(X))]=\int_{x\times y}L(y,f(x))P(x,y)dxdy Rexp​(f)=EP​[L(Y,f(X))]=∫x×y​L(y,f(x))P(x,y)dxdy

这是理论上模型 f ( X ) f(X) f(X) 关于联合分布 P ( X , Y ) P(X,Y) P(X,Y) 的平均意义下的损失，称为风险函数（risk function）或期望损失（expected loss）

经验风险最小化（empirical risk minimization，ERM）的策略认为，经验风险最小化的模型是最优的模型。根据这一策略，按照经验风险最小化求最优模型就是求解最优化问题：

min ⁡ f ∈ F 1 N ∑ i = 1 N L ( y i , f ( x i ) ) \min_{f\in\mathcal{F}}\frac{1}{N}\sum_{i=1}^NL(y_i,f(x_i)) f∈Fmin​N1​i=1∑N​L(yi​,f(xi​))

其中， F \mathcal{F} F 是假设空间。当样本量足够大时，ERM 能保证有很好的学习效果，比如极大似然估计（maximum likelihood estimation）就是经验风险最小化的一个例子。但是，当样本容量很小时，ERM 的效果就未必很好，会产生“过拟合（over-fitting）”现象

结构风险最小化（structural risk minimization，SRM）就是为了防止过拟合而提出的策略。结构风险最小化等价于正则化（regularization）。结构风险在经验风险上加上表示模型复杂度的正则化项（regularizer）或罚项（penalty term）。在假设空间、损失函数以及训练数据集确定的情况下，结构风险的定义是

R s r m ( f ) = 1 N ∑ i = 1 N L ( y i , f ( x i ) ) + λ J ( f ) R_{srm}(f)=\frac{1}{N}\sum_{i=1}{N}L(y_i,f(x_i))+\lambda J(f) Rsrm​(f)=N1​i=1∑​NL(yi​,f(xi​))+λJ(f)

其中 J ( f ) J(f) J(f) 为模型的复杂度，是定义在假设空间 F \mathcal{F} F 上的泛函。结构风险小的模型往往对训练数据以及未知的测试数据都有较好的预测。比如，贝叶斯估计中的最大后验概率估计（maximum posterior probability estimation，MAP）就是结构风险最小化的一个例子

算法是指学习模型的具体计算方法

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

R e m p ( f ^ ) = 1 N ∑ i = 1 N L ( y i , f ^ ( x i ) ) R_{emp}(\hat{f})=\frac1N\sum_{i=1}^NL(y_i,\hat{f}(x_i)) Remp​(f^​)=N1​i=1∑N​L(yi​,f^​(xi​))

其中 N N N 是训练样本容量。测试误差是模型 Y = f ^ ( X ) Y=\hat{f}(X) Y=f^​(X) 关于测试数据集的平均损失：

e t e s t = 1 N ′ ∑ i = 1 N ′ L ( y i , f ^ ( x i ) ) e_{test}=\frac{1}{N'}\sum_{i=1}^{N'}L(y_i,\hat{f}(x_i)) etest​=N′1​i=1∑N′​L(yi​,f^​(xi​))

其中 N ′ N' N′ 是测试样本容量

如果一味追求提高对训练数据的预测能力，所选模型的复杂度往往会比真模型更高。这种现象称为过拟合（over-fitting）。过拟合是指学习时选择的模型所包含的参数过多，以致于出现这一模型对已知数据预测的很好，但对未知数据预测很差的现象。可以说模型选择旨在避免过拟合并提高模型的预测能力

模型选择的典型方法是正则化（regularization）。正则化是结构风险最小化策略的实现，是在经验风险上加一个正则化项（regularizer）或罚项（penalty term）。正则化项一般是模型复杂度的单调递增函数，模型越复杂，正则化值就越大。比如，正则化项可以是模型参数向量的范数。

正则化一般具有如下形式：

min ⁡ f ∈ F 1 N ∑ i = 1 N L ( y i , f ( x i ) ) + λ J ( f ) \min_{f\in\mathcal{F}}\frac{1}{N}\sum_{i=1}^NL(y_i,f(x_i))+\lambda J(f) f∈Fmin​N1​i=1∑N​L(yi​,f(xi​))+λJ(f)

其中，第1项是经验风险，第2项是正则化项， λ ≥ 0 \lambda\geq0 λ≥0为调整两者之间关系的系数

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

L ( w ) = 1 N ∑ i = 1 N ( f ( x i ; w ) , − y i ) 2 + λ 2 ∥ w ∥ 2 L(w)=\frac{1}{N}\sum_{i=1}^N(f(x_i;w),-y_i)^2+\frac{\lambda}{2}\lVert w\rVert^2 L(w)=N1​i=1∑N​(f(xi​;w),−yi​)2+2λ​∥w∥2

这里， ∥ w ∥ \lVert w\rVert ∥w∥表示参数向量 w w w 的 L 2 L_2 L2​ 范数。正则化项也可以是参数向量的 L 1 L_1 L1​ 范数：

L ( w ) = 1 N ∑ i = 1 N ( f ( x i ; w ) , − y i ) 2 + λ 2 ∣ w ∣ 2 L(w)=\frac{1}{N}\sum_{i=1}^N(f(x_i;w),-y_i)^2+\frac{\lambda}{2}\lvert w\rvert^2 L(w)=N1​i=1∑N​(f(xi​;w),−yi​)2+2λ​∣w∣2

如果给定的样本数据充足，进行模型选择的一种简单方法是随机地将数据集切分成三部分，分别为训练集（training set）、验证集（validation set）和测试集（test set）。训练集用来训练模型，验证集用于模型的选择，而测试集用于最终对学习方法的评估。在学习到的不同复杂度的模型中，选择对验证集有最小预测误差的模型。由于验证集有足够多的数据，用它对模型进行选择也是有效的。但是，在许多实际应用中数据是不充足的，为了选择好的模型，可以采用交叉验证方法

首先随机地将已给数据分为两部分，一部分作为训练集，另一部分作为测试集；然后用训练集在各种条件下训练模型，从而得到不同的模型；在测试集上评价各个模型的测试误差，选出测试误差最小的模型

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

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

学习方法的泛化能力（generalization ability）是指由该方法学习到的模型对未知数据的预测能力，是学习方法本质上重要的性质。如果学到的模型是 f ^ \hat{f} f^​，那么用这个模型对未知数据预测的误差即为泛化误差（generalization error）

R exp ⁡ ( f ^ ) = E P [ L ( Y , f ^ ( X ) ) ] = ∫ x × y L ( y , f ^ ( x ) ) P ( x , y ) d x d y R_{\exp}(\hat{f})=E_{P}[L(Y,\hat{f}(X))]=\int_{x\times y}L(y,\hat{f}(x))P(x,y)dxdy Rexp​(f^​)=EP​[L(Y,f^​(X))]=∫x×y​L(y,f^​(x))P(x,y)dxdy

泛化误差反映了学习方法的泛化能力，如果一种方法学习的模型比另一种方法学习的模型具有更小的泛化误差，那么这种方法就更有效。事实上，泛化误差就是所学习到的模型的期望风险。

学习方法的泛化能力分析往往是通过研究泛化误差的概率上界进行的，简称为泛化误差上界（generalization error bound）。具体来说，就是通过比较两种学习方法的泛化误差上界的大小来比较它们的优劣。泛化误差上界通常具有以下性质：它是样本容量的函数，当样本容量增加时，泛化上界趋于0；它是假设空间容量（capacity）的函数，假设空间容量越大，模型就越难学，泛化误差上界就越大。

监督学习的任务就是学习一个模型，应用这一模型，对给定 输入预测相应的输出。这个模型的一般形式为决策函数： Y = f ( X ) Y=f(X) Y=f(X)或条件概率分布 P ( Y ∣ X ) P(Y|X) P(Y∣X)

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

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

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

这样的方法之所以称为生成方法，是因为模型表示了给定输入 X X X 产生输出 Y Y Y 的生成关系。典型的生成模型有：朴素贝叶斯法和隐马尔可夫模型。

判别方法由数据直接学习决策函数 f ( X ) f(X) f(X) 或者条件概率分布 P ( Y ∣ X ) P(Y|X) P(Y∣X) 作为预测的模型，即判别模型。判别方法关心的是对给定的输入 X X X，应该预测什么样的输出 Y Y Y。典型的判别模型包括：k邻近法、感知机、决策树、Logist回归模型、最大熵模型、支持向量机、提升方法和条件随机场等。

生成方法的特点：生成方法可以还原出联合概率分布 P ( X , Y ) P(X,Y) P(X,Y)，而判别方法则不能；生成方法的学习收敛更快，即当样本容量增加的时候，学习的模型可以更快地收敛于真实模型；当存在隐变量时，仍可以用生成方法学习，此时判断方法就不能用。

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

在监督学习中，当输出变量 Y Y Y 取有限个离散值时，预测问题就称为分类问题。这时，输入变量 X X X 可以是离散的，也可以是连续的。监督学习从数据中学习一个分类模型或分类决策函数，称为分类器（classifier）。分类器对新的输入进行输出的预测（prediction），称为分类（classification）。可能的输出称为类（class）。分类的类别为多个时，称为多分类问题。

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

对于二分类问题常用的评价指标是精确率（precision）与召回率（recall）。通常以关注的类为正类，其他类为负类，分类器在测试数据集上的预测或正确或不正确，四种情况出现的总数分别记作：

精确率定义为

P = T P T P + F P P=\frac{TP}{TP+FP} P=TP+FPTP​

召回率定义为

R = T P T P + F N R=\frac{TP}{TP+FN} R=TP+FNTP​

此外，还有 F 1 F_1 F1​ 值，是精确率和召回率的调和均值，即

2 F 1 = 1 P + 1 R \frac{2}{F_1}=\frac1P+\frac1R F1​2​=P1​+R1​

F 1 = 2 T P 2 T P + F P + F N F_1=\frac{2TP}{2TP+FP+FN} F1​=2TP+FP+FN2TP​

精确率和召回率都高时， F 1 F_1 F1​ 值也会高。

标注（tagging）也是一个监督学习问题，可以认为标注问题时分类问题的一个推广，标注问题又是更复杂的结构预测（structure prediction）问题的简单形式。标注问题的输入是一个观测序列，输出是一个标记序列或状态序列。标注问题的目标在于学习一个模型，使它能够对观测序列给出标记序列作为预测。注意，可能的标记个数是有限的，但其组合所成的标记序列的个数是依序列长度呈指数级增长的。

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

回归（regression）用于预测输入变量（自变量）和输出变量（因变量）之间的关系，特别是当输入变量的值发生变化时，输出变量的值随之发生的变化。回归模型正是表示从输入变量到输出变量之间映射的函数。回归问题分为学习和预测两个过程。回归问题按照输入变量的个数，分为一元回归和多元回归；按照输入变量和输出变量之前的关系的类型即模型的类型，分类线性回归和非线性回归。

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