第一章 统计学习方法概论
1.1 统计学习
- 统计学习由监督学习（主要包括用于分类、标注与回归问题）、非监督学习、半监督学习、强化学习等组成
- 统计学习方法三要素：模型、策略、算法
- 统计学习方法步骤：1、得到一个有限的训练数据集合。2、确定包含所有可能的模型的假设空间，即学习模型的集合。3、确定模型选择的准则，即学习的策略。4、实现求解最优模型的算法，即学习的算法。5、通过学习方法选择最优模型。6、利用学习的最优模型对新数据进行预测或分析。
1.2 监督学习
监督学习的任务是学习一个模型，使模型能够对任意给定的输入，对其相应的输出做出一个好的预测。每一个具体的输入时一个实例，通常由特征向量表示。这时，所有特征向量存在的空间称为特征空间，特征空间的每一维对应于一个特征。
输入输出变量通常用大写字母表示，习惯上输入变量写作X，输出变量写作Y，输入、输出变量值用小写字母表示。
本书默认向量为列向量，
训练数据集通常表示为：
- 输入变量与输出变量均为连续变量的预测问题称回归问题
- 输出变量为有限个离散变量的预测问题称为分类问题
- 输入变量与输出变量均为变量序列的预测问题称为标注问题
监督学习假设输入与输出的随机变量X和Y遵循联合概率分布P(X,Y),P(X,Y)表示分布函数。对于学习系统来说，联合概率分布的具体定义是未知的。统计学习假设数据存在一定的同意规律，X和Y具有联合概率分布的假设就是监督学习关于数据的基本假设。
监督学习的目的在于学习一个又输入到输出的映射，这一映射由模型来表示。模型属于由输入空间到输出空间 映射的集合，这个集合就是假设空间。假设空间的确定意味着学习范围的确定。
监督学习的模型可以是概率模型或非概率模型，由条件概率分布P(Y|X)或决策函数Y=f(X)表示，随具体学习方法而定。
监督学习中，假设训练数据与测试数据是依联合概率分布P(X,Y)独立同分布产生的。
1.3 统计学习的三要素
方法=模型+策略+算法
1.3.1 模型
在监督学习过程中，模型就是所要学习的条件概率分布或决策函数。模型的假设空间包含所有可能的条件概率分布或决策函数。
在本书中，称由决策函数表示的模型为非概率模型，由条件概率模型表示的模型为概率模型。
假设空间可以定义为决策函数的集合：
其中，X和Y是定义在输入空间和输出空间上的变量。这时，F通常是由一个参数向量确定的函数族：
参数向量θ取值于n维欧式空间，称为参数空间。
假设空间也可定义为条件概率的集合：
其中，X和Y是定义在输入空间和输出空间上的变量。这时，F通常是由一个参数向量决定的条件概率分布族：
参数向量θ取值于n维欧式空间，称为参数空间。
1.3.2 策略
统计学习的目标在于从假设空间中选取最优模型。
首先引入损失函数与风险函数的概念。损失函数度量模型一次预测的好坏，风险函数度量平均意义下模型预测的好坏。
损失函数是f(X)和Y的非负实值函数，记作L(Y,f(X))，其中，f(X)为这个输出的预测值，Y为真实值。常见损失函数有以下几种：1-4，见笔记本
由于模型的输入输出(X,Y)是随机变量，遵循联合分布P(X,Y)，所以损失函数的期望是：
这是理论上模型f(X)关于联合分布P(X,Y)的平均意义下的损失，称为风险函数或期望损失。学习的目标就是选择期望风险最小的模型。由于联合分布是未知的，所以期望不能直接计算，所以才需要进行学习。这样一来，一方面根据期望风险最小学习模型要用到联合分布，另一方面联合分布又是未知的，所以监督学习就成为一个病态问题。
给定一个训练数据集：
模型f(X)关于训练数据集的平均损失称为经验风险或经验损失，记作
R e m p R_{emp} Remp
R e m p ( f ) = 1 N ∑ i = 1 N L ( y i , f ( x i ) ) R_{emp}\left ( f \right )=\frac{1}{N}\sum_{i=1}^{N}L\left ( y_{i},f\left ( x_{i} \right ) \right ) Remp(f)=N1i=1∑NL(yi,f(xi))
期望风险是模型关于联合分布的期望损失，经验风险是模型关于训练样本集的平均损失。根据大数定律，当样本容量趋于无穷时，经验风险趋于期望风险。所以可以用经验风险估计期望风险。但是，由于现实中训练样本数目有限，甚至很小，所以用经验风险估计期望风险常常不理想，要对经验风险进行一定矫正。这就关系到监督学习的两个基本策略：经验风险最小化和结构风险最小化。
经验风险最小化的策略认为，经验风险最小的模型是最优的模型。根据这一策略，按照经验风险最小化求最优模型就是求解最优化问题：
m i n 1 N ∑ i = 1 N L ( y i , f ( x i ) ) min \frac{1}{N}\sum_{i=1}^{N}L\left ( y_{i},f\left ( x_{i} \right ) \right ) minN1i=1∑NL(yi,f(xi))
当样本容量足够大时，经验风险最小化能够保证有很好的学习效果，在现实中被广泛采用。比如极大似然估计就是经验风险最小化的例子。当模型是条件概率分布，损失韩式是对数损失函数时，经验风险最小化就等价于极大似然估计。 但是当样本容量小时，经验风险最小化学习的效果就未必好，可能出现后面叙述的“过拟合”现象。
结构风险最小化是为了防止过拟合而提出的策略。结构风险最小化等价于正则化。结构风险在经验风险上加上表示模型复杂度的正则化项或罚项。 结构风险的定义是：
R s r m ( f ) = 1 N ∑ i = 1 N L ( y i , f ( x i ) ) + λ J ( f ) R_{srm}\left ( f \right )=\frac{1}{N}\sum_{i=1}^{N}L\left ( y_{i},f\left ( x_{i} \right ) \right )+\lambda J\left ( f \right ) Rsrm(f)=N1i=1∑NL(yi,f(xi))+λJ(f)
其中，J(f)为模型的复杂度，是定义在假设空间F上的泛函。模型f越复杂J(f)就越大。也就是说，复杂度表示了对复杂模型的惩罚。λ>=0是系数，用于权衡经验风险和模型复杂度。结构风险小需要经验风险与模型复杂度同时小。结构风险小的模型往往对训练数据以及未知的预测数据都有较好的预测。
比如贝叶斯估计中的最大后验概率估计（MAP）就是结构风险最小化的一个例子。当模型是条件概率分布，损失韩式是对数损失函数、模型复杂度由模型的先验概率表示时，结构风险最小化就等价于最大后延概率估计。
同理，结构风险最小化的策略认为结构风险最小的模型是最优的模型。这样，监督学习问题就变成了经验风险或结构风险函数的最优化问题和。这是经验或结构风险函数式最优化的目标函数。
1.3.3 算法
算法是指学习模型的具体计算方法。统计学习问题归结为最优化问题，统计学习的算法成为求解最优化问题的算法。如果最优化问题有显式的分析解，这个最优化问题就比较简答。但通常解析解不存在，这就需要用数值计算的方法求解。
1.4 模型评估与模型选择
选择模型时，该模型要对已知数据和未知数据都有很好的预测能力。那么该如何评估模型的好坏呢？下面给出两个基于损失函数的学习方法评估标准：模型的训练误差、模型的预测误差。
训练误差
假设学习到的模型为 Y = f 1 ( X ) Y=f^{1}\left ( X \right ) Y=f1(X)
训练误差是模型f1关于训练数据集的平均损失： R e m p ( f 1 ) = 1 N ∑ i = 1 N L ( y i , f 1 ( x i ) ) R_{emp}\left ( f^{1} \right )=\frac{1}{N}\sum_{i=1}^{N}L\left ( y_{i},f^{1}\left ( x_{i} \right ) \right ) Remp(f1)=N1i=1∑NL(yi,f1(xi))
其中，N是训练样本的容量。
测试误差
测试误差是模型 Y = f 1 ( X ) Y=f^{1}\left ( X \right ) Y=f1(X)关于测试数据集的平均损失：
e e m p = 1 N ′ ∑ i = 1 N ′ L ( y i , f 1 ( x i ) ) e_{emp}=\frac{1}{N^{'}}\sum_{i=1}^{N^{'}}L\left ( y_{i},f^{1}\left ( x_{i} \right ) \right ) eemp=N′1i=1∑N′L(yi,f1(xi))
其中N撇是测试样本容量。
例如，当损失函数是0-1损失（见1.3）时，测试误差就变成了常见的测试数据集上的误差率 e t e s t = 1 N ′ ∑ i = 1 N ′ I ( y i ≠ f ′ ( x i ) ) e_{test}=\frac{1}{N^{'}}\sum_{i=1}^{N^{'}}I\left ( y_{i}\neq f^{'}\left ( x_{i} \right ) \right ) etest=N′1i=1∑N′I(yi=f′(xi))
这里I为指示函数，当真实的测试数据不等于模型估计出的数据时，指示函数的值为1，否则为0。
相应地，常见的测试数据集上的准确率为： r t e s t = 1 N ′ ∑ i = 1 N ′ I ( y i = f ′ ( x i ) ) r_{test}=\frac{1}{N^{'}}\sum_{i=1}^{N^{'}}I\left ( y_{i}=f^{'}\left ( x_{i} \right ) \right ) rtest=N′1i=1∑N′I(yi=f′(xi))
显然， r t e s t + e t e s t = 1 r_{test}+e_{test}=1 rtest+etest=1
训练误差的大小，是判断给定的问题是不是一个容易学习的问题，不重要。测试误差反映了学习方法对未知的测试数据集的预测能力，重要。显然，当给定两种学习方法时，测试误差小的方法具有更好的预测能力，更有效。通常，将学习方法对未知数据的预测能力称为泛化能力（1.6中讲）。
过拟合与模型选择
模型复杂度。参数个数越多，模型的复杂程度越高。假设存在一个“真”模型，我们所选择的模型应该与真模型有相同个数的参数，所选择模型的向量与真模型的参数向量应相近。如果一味追求对数据的预测能力，所选模型复杂度往往会比真模型高，这种现象称为过拟合。过拟合是指学习时选择的模型所包含的参数过多，以至于这一模型对已知数据预测的很好，对未知数据预测的很差的现象。我们应该在给定模型复杂度的情况下，按照经验风险最小胡的策略求解模型中的参数。
模型选择时，不仅应该考虑对已知数据的预测能力，也应该考虑对未知数据的预测能力。随着模型复杂度的增加，训练误差会减小，直至趋向于0，但是测试误差会先减小后增大。应选择复杂度适当的模型，以达到使测试误差最小。
1.5 正交化与交叉验证（常用的模型选择的方法）
1.5.1 正则化
正则化是结构风险最小化策略的实现。正则化一般有如下形式： L ( y i , f ( x i ) ) + λ J ( f ) L\left ( y_{i},f\left ( x_{i} \right ) \right )+\lambda J\left ( f \right ) L(yi,f(xi))+λJ(f)其中，第一项为经验风险，第二项是正则化项或罚项，λ>=0为调整两者之间关系的系数。正则化项一般是模型复杂度的单调递增函数，一般模型越复杂，正则化值越大。比如，正则化项可以是模型参数的向量的范数。
正则化项在回归中，损失函数是平方损失，正则化项可以是参数向量L2范数： L ( w ) = 1 N ∑ i = 1 N ( f ( x i ; w ) − y i ) 2 + λ 2 ∥ w ∥ 2 L\left ( w \right )=\frac{1}{N}\sum_{i=1}^{N}\left ( f\left ( x_{i} ;w\right )-y_{i} \right )^{2}+\frac{\lambda }{2}\left \| w \right \|^{2} L(w)=N1i=1∑N(f(xi;w)−yi)2+2λ∥w∥2||w||表示参数向量w的L2范数。正则化项是参数向量的L1范数时： L ( w ) = 1 N ∑ i = 1 N ( f ( x i ; w ) − y i ) 2 + λ ∥ w ∥ 1 L\left ( w \right )=\frac{1}{N}\sum_{i=1}^{N}\left ( f\left ( x_{i} ;w\right )-y_{i} \right )^{2}+\lambda \left \| w \right \|_{1} L(w)=N1i=1∑N(f(xi;w)−yi)2+λ∥w∥1||w||1表示参数向量w的L1范数。
当第1项的经验风险较小时，模型可能较复杂（有多个非零参数），这时第二项的模型复杂度会较大。正则化的作用是同时选择经验风险与模型复杂度同时较小的模型。
奥卡姆剃刀原理：在所有可能选择的模型中，能够很好地解释已知数据并且此模型很简单，这样的模型是最好的模型。从贝叶斯估计角度看，正则化项对应于模型的先验概率。可以假设复杂的模型有较小的先验概率，简单的模型有较大的先验概率。
1.5.2 交叉验证
当数据充足时，可以将数据集切分为3部分，训练集（用于训练模型）、验证集（用于选择模型）、测试集（用于最终对学习方法的评估）。我们应选择对验证集有最小预测误差的模型。
但是在实际中，数据是不充足的，所以用到交叉验证方法，其思想是：重复地使用数据；把给定的数据进行切分，将切分的数据集组合为训练集与测试集，在此基础上反复地进行训练、测试及模型选择。交叉验证方法有三种：
- 简单交叉验证。首先随机地将已给数据分为两部分（训练集和测试集）。例如70%是训练集，30%为测试集。然后用训练集在各种条件下（例如，不同的参数个数）训练模型，从而得到不同模型。最后在测试集上评价各个模型的误差，选测试误差最小的那个模型。
- S折交叉验证。此方法应用最多。将数据集分成互不相交大小相同的S份，其中S-1个数据集的数据用于训练模型，剩下的一个数据集用于测试模型。将这一过程对可能的S种选择重复进行，最后选出S次评测中平均测试误差最小的模型。
- 留一交叉验证.这种情形是S=N，通常在数据缺乏情况下用。其中N是给定数据集的容量。
1.6 泛化能力
泛化能力是指由该方法学习到的模型对未知数据的预测能力。最常用的是通过测试误差来评价学习方法的泛化能力。但是由于数据的有限，所以有局限性。
泛化误差的定义：如果学到的模型是f尖，那么用这个模型对未知数据预测的误差即为泛化误差 R e x p ( f ^ ) = E p [ L ( Y , f ^ ( X ) ) ] = ∫ x ∗ y L ( y , f ^ ( x ) ) P ( x , y ) d x d y R_{exp}\left ( \widehat{f} \right )=E_{p}\left [ L\left ( Y,\widehat{f}\left ( X \right ) \right ) \right ]=\int _{x*y}L\left ( y,\widehat{f}\left ( x \right ) \right )P\left ( x ,y\right )dxdy Rexp(f
)=Ep[L(Y,f
(X))]=∫x∗yL(y,f
(x))P(x,y)dxdy
泛化误差反映了学习方法的泛化能力，泛化误差越小，模型越好。事实上，泛化误差就是所学到的模型的期望风险。
学习方法的泛化能力往往是通过研究泛化误差的概率上界进行的。即通过比较两种学习方法的泛化误差上界的大小来比较他们的优劣。泛化误差上界通常有以下性质：
- 是样本容量的函数，当样本容量增加时，泛化上界趋于0.
- 它是假设空间容量的函数，假设空间容量越大，泛化误差上界越大。
二分类问题的泛化误差上界
假设空间是函数的有限集合 £ = { f 1 , f 2 , ⋯ , f d } \pounds =\left \{ f_{1},f_{2},\cdots ,f_{d} \right \} £={f1,f2,⋯,fd}，d是函数个数。fn的泛化能力为： R ( f N ) = E [ L ( Y , f N ( X ) ) ] R\left ( f_{N} \right )=E\left [ L\left ( Y,f_{N}\left ( X \right ) \right ) \right ] R(fN)=E[L(Y,fN(X))]
对于二分类问题，当假设空间是有限个函数的集合，对任意一个函数f，至少以概率1-δ，以下不等式成立： R ( f ) ⩽ R ^ ( f ) + ε ( d , N , δ ) R\left (f \right )\leqslant \widehat{R}\left ( f \right )+\varepsilon \left ( d,N,\delta \right ) R(f)⩽R
(f)+ε(d,N,δ) ε ( d , N , δ ) = 1 2 N ( l o g d + l o g 1 δ ) \varepsilon \left ( d,N,\delta \right )=\sqrt{\frac{1}{2N}\left ( logd+log\frac{1}{\delta } \right )} ε(d,N,δ)=2N1(logd+logδ1)
不等式左端是泛化误差，右侧为泛化误差上界。在泛化误差上界中，第一项是训练误差，训练误差越小，泛化误差越小。第二项是N的单调递减函数，当N趋于无穷时趋于0.同时它也是sqrt（logd）阶的函数，假设空间包含的函数越多，其值越大。
1.7 生成模型与判别模型
监督学习的任务就是学习一个模型，应用这个模型，对给定的输入预测相应的输出。这个模型的一般形式为决策函数Y=f(X)，或者条件概率分布P(Y|X).
监督学习的方法可分为生成方法和判别方法。所学到的模型分别称为生成模型与判别模型。
生成方法由数据学习联合概率分布P(X,Y),生成模型为 P ( Y ∣ X ) = P ( X , Y ) P ( X ) P(Y|X)=\frac{P\left ( X,Y \right )}{P\left ( X \right )} P(Y∣X)=P(X)P(X,Y)典型的生成模型有朴素贝叶斯法和隐马尔科夫模型。
判别方法由数据直接学习决策函数f(X)或者条件概率分布P(Y|X)作为预测的模型，即判别模型。判别方法关心的问题是给定输入的X，应该预测出什么样的Y。典型的判别模型有：k近邻法，感知机，决策树，逻辑斯蒂回归模型，最大熵模型，支持向量机，提升方法和条件随机场等。
生成方法特点：能还原联合概率分布、学习收敛速度快（当样本容量增加时，学到的模型可以更快地收敛于真实模型）、当存在隐变量时，仍可以用生成学习方法（判别方法不能用）。
判别方法特点：直接学习决策函数f(X)或者条件概率分布P(Y|X)，直接面对预测，学习的准确率更高，可以对数据进行各种程度上的抽象、定义特征并使用特征，可以简化学习问题。
1.8 分类问题
当输出的Y取有限个离散值时，预测问题就变成分类问题。输入变量X可以离散可以连续。分类问题包括两个过程：
- 学习。通过训练数据集利用有效的学习方法学习一个分类器。
- 分类。通过分类器，对新的输入进行分类。
评价分类器性能的指标一般是分类准确率（分类器正确分类的样本数与总样本数之比）。对于二分类问题，常用的评价指标是精确率与召回率。通常关注的类为正类，其他类为负类。
TP(true positive)–将正类预测为正类数 FN(false negative)–将正类预测为负类数
FP–将负类预测为负类数 TN–将负类预测为负类数
精确率定义为： 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
F1值是精确率和召回率的调和均值，即： 2 F 1 = 1 P + 1 R \frac{2}{F1}=\frac{1}{P}+\frac{1}{R} F12=P1+R1 F 1 = 2 T P 2 T P + F P + F N F1=\frac{2TP}{2TP+FP+FN} F1=2TP+FP+FN2TP当精确率和召回率都高时，F1也会高。
1.9 标注问题
标准问题是分类问题的推广，也是更复杂的结构预测问题的简单形式。标注问题的输入是一个观测序列，输出是一个标记序列或状态序列。标注问题的目标在于学习一个模型，使它能够对观测序列给出标记序列作为预测。注意，可能的标记个数是有限的，但其组合缩成的标记序列的个数是依序列长度呈指数级增长的。
给定训练数据集： T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯ , ( x N , y N ) } T=\left \{ \left ( x_{1},y_{1} \right ), \left ( x_{2},y_{2} \right ), \cdots , \left ( x_{N},y_{N} \right ) \right \} T={(x1,y1),(x2,y2),⋯,(xN,yN)}输入观测序列（i=1，…，N）： x i = ( x i ( 1 ) , x i ( 2 ) , ⋯ , x i ( n ) ) T x_{i}=\left ( x_{i}^{\left ( 1 \right )} ,x_{i}^{\left ( 2 \right )},\cdots ,x_{i}^{\left ( n \right )} \right )^{T} xi=(xi(1),xi(2),⋯,xi(n))T相应的输出标记序列（n是序列的长度）： y i = ( y i ( 1 ) , y i ( 2 ) , ⋯ , y i ( n ) ) T y_{i}=\left ( y_{i}^{\left ( 1 \right )} ,y_{i}^{\left ( 2 \right )},\cdots ,y_{i}^{\left ( n \right )} \right )^{T} yi=(yi(1),yi(2),⋯,yi(n))T学习系统基于训练数据集构建一个模型，表示为条件概率分布: P ( Y ( 1 ) , Y ( 2 ) , ⋯ , Y ( n ) ∣ X ( 1 ) , X ( 2 ) , ⋯ , X ( n ) ) P\left ( Y^{\left ( 1 \right )} ,Y^{\left ( 2 \right )} ,\cdots ,Y^{\left ( n \right )}|X^{\left ( 1 \right )} ,X^{\left ( 2 \right )} ,\cdots ,X^{\left ( n \right )} \right ) P(Y(1),Y(2),⋯,Y(n)∣X(1),X(2),⋯,X(n))这里每个Xi取值为所有可能的观测，每个Yi取值为所有可能的标记，一般n远小于N。标注系统按照学习得到的条件概率分布模型，对新的输入观测序列找到相应的输出标记序列。对于每个 x N + 1 = ( x N + 1 ( 1 ) , x N + 1 ( 2 ) , ⋯ , x N + 1 ( n ) ) T x_{N+1}=\left ( x_{N+1}^{\left ( 1 \right )} ,x_{N+1}^{\left ( 2 \right )},\cdots ,x_{N+1}^{\left ( n \right )} \right )^{T} xN+1=(xN+1(1),xN+1(2),⋯,xN+1(n))T找到使条件概率P（N+1）最大的标记序列 y N + 1 = ( y N + 1 ( 1 ) , y N + 1 ( 2 ) , ⋯ , y N + 1 ( n ) ) T y_{N+1}=\left ( y_{N+1}^{\left ( 1 \right )} ,y_{N+1}^{\left ( 2 \right )},\cdots ,y_{N+1}^{\left ( n \right )} \right )^{T} yN+1=(yN+1(1),yN+1(2),⋯,yN+1(n))T评价标注模型的指标与评价分类模型的指标一样，常用的有标注准确率、精确率和召回率。
标注常用的统计学习方法有：隐马尔科夫模型、条件随机场。
1.10 回归问题
按照输入变量的个数，分为一元回归和多元回归。按照输入变量和输出变量之间的关系的类型，可分为线性回归和非线性回归。