1. 统计学习方法概论
本文是统计学习方法（李航）第一章的学习总结。
1.1 统计学习
1.统计学习的特点
统计学习（statistical learning）是关于计算机基于数据构建概率统计模型并运用模型对数据进行预测和分析的一门学科。统计学习也称为统计机器学习（statistical machine learning）。现在人们提到的机器学习往往是指统计机器学习。
统计学习的特点：(1)以计算机和网络为平台；(2)以数据为研究对象，是数据驱动的学科；(3)目的是对数据进行分析和预测；(4)以方法为中心，构建模型并应用模型进行分析和预测；(5)是概率论、统计学、信息论、优化理论和计算机科学等多个领域的交叉学科。
2.统计学习的对象
统计学习的对象是数据（data）。它从数据出发，提取数据特征，抽象出数据模型，根据模型对数据进行分析和预测。统计学习的前提是假设同类数据（具有某种共同性质）具有一定的统计规律性。统计学习过程中，以变量或变量组表示数据，数据分为连续变量和离散变量表示的类型。
3.统计学习的目的
统计学习总的目标就是考虑学习什么的模型和如何学习模型，以使模型能够对数据进行准确的预测和分析，同时也要考虑学习效率。
4.统计学习的方法
统计学习分为监督学习（supervised learning）、非监督学习（unsupervised learning）、半监督学习(semi-supervised learning)和强化学习(reinforcement learning)等。统计学习方法包括模型的假设空间、模型选择的准则及模型选择的算法，称为统计学习方法的三要素，简称模型（model）、策略（strategy）和算法（algorithm）。
5.统计学习的研究
统计学习的研究包括统计学习方法（算法创新）、统计学习理论（算法效率及有效性）及统计学习应用（解决问题）三个方面。
6.统计学习的重要性
统计学习的重要性体现在三个方面：（1）统计学习是处理海量数据的有效方法。（2）统计学习是计算机智能化的有效手段。（3）统计学习是计算机发展的重要组成部分。
1.2 监督学习
监督学习的任务是学习一个模型，使模型能够对任意给定的输入，对其相应的输出做出一个好的预测。
1.2.1 基本概念
1.输入空间、特征空间与输出空间
在监督学习中，输入与输出的所有可能的取值集合分别称为输入空间（input space）和输出空间（output space）。通常输出空间远远小于输入空间。
每个具体的输入是一个实例（instance），通常由特征向量（feature vector）表示。所有特征向量存在的空间称为特征空间（feature space）。特征空间的每一维对应一个特征。当输入空间与特征空间不同时，需要将实例从输入空间映射到特征空间，模型实际上都是定义在特征空间上的。
监督学习过程中，将输入和输出看作是定义在输入空间和输出空间上的随机变量的取值。习惯上输入变量写作X，其取值写作x，输出变量写作Y，其取值写作y。输入实例的x的特征向量记作
x=(x(1),x(2),...,x(i),...,x(n))Tx = (x^{(1)}, x^{(2)},..., x^{(i)} ,...,x^{(n)})^Tx=(x(1),x(2),...,x(i),...,x(n))T
x(i)x^{(i)}x(i)表示向量x的第i个特征，而xix_ixi表示第i个输入变量。
xi=(xi(1),xi(2),...,xi(i),...,xi(n))Tx_i = (x_i^{(1)}, x_i^{(2)},..., x_i^{(i)} ,...,x_i^{(n)})^Txi=(xi(1),xi(2),...,xi(i),...,xi(n))T
监督学习从训练数据中学习模型，对测试数据进行预测。训练集通常表示为
T=(x1,y1),(x2,y2),...,(xN,yN)T = {(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}T=(x1,y1),(x2,y2),...,(xN,yN)
(xi,yi)(x_i,y_i)(xi,yi)表示样本或样本点。
输入变量和输出变量可以是离散型的，也可以是连续型的。输入变量和输出变量都是连续型变量的预测问题称为回归问题；输出变量为有限个离散型变量的预测问题称为分类问题；输入变量和输出变量均为变量序列的预测问题称为标注问题。
2.联合概率分布
监督学习假设输入与输出的随机变量X和Y遵循联合概率分布P(X,Y)，P(X,Y)表示分布函数或分布密度函数。训练数据和测试数据被看作是依联合概率分布P(X,Y)独立同分布产生的。统计学习假设数据存在一定的统计规律。
3.假设空间
监督学习的目的在于学习一个由输入到输出的映射，映射关系用模型表示。输入到输出的映射集合就是假设空间（hypothesis space）。简单学习的模型可以是概率模型或非概率模型。由条件概率分布P(Y|X)或决策函数Y=f(X)表示。对具体的输入进行输出预测时，写作P(y|x)或y=f(x)。
1.2.2 问题的形式化
监督学习利用训练数据学习模型，再用模型对测试数据进行预测。学习过程中的训练数据往往是人工给出的，因此称为监督学习。监督学习分为学习和预测两个过程，如下图：
首先给定数据集T=(x1,y1),(x3,y2),...,(xN,yN)T={(x_1,y_1),(x_3,y_2),...,(x_N,y_N)}T=(x1,y1),(x3,y2),...,(xN,yN)，其中(xi,yi)，i=1,2,...,N(x_i,y_i)，i=1,2,...,N(xi,yi)，i=1,2,...,N，称为样本或样本点，xi∈X⊆Rnx_i in X subseteq R^nxi∈X⊆Rn是输入的观测值，称为输入或实例，yi∈Yy_i in Yyi∈Y是输出的观测值，也称为输出。通过学习得到的模型表示为条件概率分布P(Y∣X)P(Y|X)P(Y∣X)和决策函数Y=f(X)Y=f(X)Y=f(X)，模型表示的是输入与输出之间的映射关系。
预测过程中，对于测试数据中的输入x_N 1x_{N 1}x_N 1,由模型y_N 1=argmaxP(y_N 1∣x_N 1)y_{N 1}=argmax P(y_{N 1}|x_{N 1})y_N 1=argmaxP(y_N 1∣x_N 1)或y_N 1=f(x_N 1)y_{N 1}=f(x_{N 1})y_N 1=f(x_N 1)给出对应的输出y_N 1y_{N 1}y_N 1。
1.3 统计学习三要素
统计学习方法的三要素为模型、策略和算法，它们关系为：统计学习方法 = 模型 策略 算法。
1.3.1 模型
在监督学习过程中，模型是要学习的条件概率分布或决策函数。模型的假设空间包含所有可能的条件概率分布或决策函数。假设空间用F表示： F={f∣Y=f(X)}F=lbrace f|Y=f(X)rbrace F={f∣Y=f(X)} X和Y是定义在输入输出空间上的变量，F通常是由一个参数向量决定的函数族： F={f∣Y=fθ(X),θ∈Rn}F=lbrace f|Y=f_theta (X),theta in R^n rbraceF={f∣Y=fθ(X),θ∈Rn} 参数向量θthetaθ取值于n维欧式空间RnR^nRn，称为参数空间（parameter space）。假设空间也可以定义为条件概率的集合：
F={P∣P(Y∣X)}F=lbrace P|P(Y|X)rbraceF={P∣P(Y∣X)} X和Y是定义在输入输出空间上的随机变量，F通常是一个由参数向量决定的条件概率分布族：
F={P∣Pθ(Y∣X)，θ∈Rn}F=lbrace P|P_theta (Y|X)，theta in R^n rbraceF={P∣Pθ(Y∣X)，θ∈Rn} 参数向量θthetaθ取值于n维欧式空间RnR^nRn，也称为参数空间。
1.3.2 策略
有了模型的假设空间，统计学习接着考虑的是按照什么样的准则学习或选择最优的模型，统计学习的目标在于从假设空间中选取最优的模型。损失函数度量模型一次预测的好坏，风险函数度量平均意义下模型预测的好坏。
1.损失函数和风险函数
监督学习问题是在假设空间F中选取f作为决策函数，对于给定的输入X，f(X)给出对应的输出Y，输出预测值f(X)与真实值Y可能一致也可能不一致，用一个损失函数（loss function）或代价函数（cost function）。损失函数是f(X)和Y的非负实值函数，记作L(Y,f(X))L(Y,f(X))L(Y,f(X))。统计学习常用的损失函数有以下几种：
- 0-1损失函数（0-1 loss function） L(Y,f(X))={1,Y≠f(X)0,Y=f(X) L(Y,f(X))= begin{cases} 1, Y neq f(X) \\ 0, Y=f(X) end{cases} L(Y,f(X))=⎩⎪⎨⎪⎧1,Y̸=f(X)0,Y=f(X)
- 平方损失函数（quadratic loss function） L(Y,f(X))=(Y−f(X))2L(Y,f(X))=(Y-f(X))^2L(Y,f(X))=(Y−f(X))2
- 绝对损失函数（absolute loss function） L(Y,f(X))=∣(Y−f(X))∣L(Y,f(X))=|(Y-f(X))|L(Y,f(X))=∣(Y−f(X))∣
- 对数损失函数（logarithmic loss function）或对数似然损失函数(log-likelihood loss function) L(Y,f(X))=−logP(Y∣X)L(Y,f(X))=-log P(Y|X)L(Y,f(X))=−logP(Y∣X)
损失函数越小，模型越好。由于模型输入、输出(X,Y)是随机变量，遵循联合分布P(X,Y)，所以损失函数的期望是
R_exp(f)=E_p[L(Y,f(X))]=∫x∗yL(y,f(x))P(x,y)dxdyR_{exp}(f)=E_p[L(Y,f(X))]=int_{x*y}L(y,f(x))P(x,y)dxdyR_exp(f)=E_p[L(Y,f(X))]=∫x∗yL(y,f(x))P(x,y)dxdy
这是理论上模型f(X)关于联合分布P(x,y)的平均意义下的损失，称为风险函数（risk function）或期望损失（expected loss）。学习的目标就是选择期望风险最小的模型。由于联合分布P(X,Y)是未知的，Rexp(f)R_{exp}(f)Rexp(f)不能直接计算。如果知道联合分布P(X,Y)，从联合分布可以直接求出条件概率分布P(Y|X)，也就不需要学习了。一方面根据期望风险最小学习模型需要用到联合分布，一方面联合分布又是未知的，因此监督学习就称为一个病态问题（ill-formed problem）。
给定一个训练数据集
T=(x1,y1),(x2,y2),...,(xN,yN)T = {(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}T=(x1,y1),(x2,y2),...,(xN,yN)
模型f(X)关于训练数据集的平均损失称为经验风险（empirical risk）或经验损失（empirical loss），记作RempR_{emp}Remp：
R_emp(f)=1N∑i=1NL(yi,f(xi))R_{emp}(f)=frac {1} {N} sum_{i=1}^N L(y_i,f(x_i))R_emp(f)=N1i=1∑NL(yi,f(xi))
期望风险R_exp(f)R_{exp}(f)R_exp(f)是模型关于联合分布的期望损失，经验风险R_emp(f)R_{emp}(f)R_emp(f)是模型关于训练样本集的平均损失。根据大数定律，当样本容量N趋于无穷时，经验风险R_emp(f)R_{emp}(f)R_emp(f)趋于期望风险R_exp(f)R_{exp}(f)R_exp(f)。因此很自然的一个想法就是用经验风险估计期望风险，但由于训练数据是有限的，因此要对经验风险进行一定的矫正。这关系到监督学习的两个基本策略：经验风险最小化和结构风险最小化。
2.经验风险最小化和结构风险最小化
在假设空间、损失函数以及训练数据集确定的情况下，经验风险函数就可以确定。经验风险最小化（empirical risk minimization，ERM）策略认为，经验风险最小的模型就是最优的模型。求解经验最小化最优模型就是求解最优化问题：
min_f∈F1N∑_i=1NL(y_i,f(x_i))^{min} _{f in F} frac {1} {N} sum_{i=1}^N L(y_i, f(x_i))min_f∈FN1∑_i=1NL(y_i,f(x_i))
当样本容量足够大时，经验风险最小化能保证有很好的学习效果，在现实中被广泛采用。极大似然估计（maximum likelihood estimation）就是经验风险最小化的一个例子。当模型是条件概率分布时，损失函数是对数损失函数时，经验风险最小化就等价于极大似然估计。但是，当样本容量很小时，经验风险最小化未必会很好，有可能产生“过拟合”现象。
结构风险最小化（structural risk minimization，SRM）是为了防止过拟合而提出来的策略，结构化风险最小化等价于正则化（regularization）。结构风险在经验风险的基础上加上了表示模型复杂度的正则项（regularizer）或惩罚项（penalty term）。在假设空间、损失函数和训练数据集确定的情况下，结构风险定义为：
R_srm(f)=1N∑i=1NL(yi,f(xi)) λJ(f)R_{srm}(f)=frac {1} {N} sum_{i=1}^N L(y_i,f(x_i)) lambda J(f) R_srm(f)=N1i=1∑NL(yi,f(xi)) λJ(f)
J(f)J(f)J(f)为模型的复杂度，模型f越复杂，J(f)越大。λ>=0lambda>=0λ>=0是权衡经验风险和模型复杂度的系数。
结构风险最小化策略认为，结构风险最小的模型就是最优的模型。求解最优模型就是求解最优化问题：
min_f∈F1N∑_i=1NL(y_i,f(x_i)) λJ(f)^{min} _{f in F} frac {1} {N} sum_{i=1}^N L(y_i, f(x_i)) lambda J(f) min_f∈FN1∑_i=1NL(y_i,f(x_i)) λJ(f)
这样，监督学习问题变成了经验风险或结构风险的最优化问题。
1.3.3算法
算法是指学习模型的具体计算方法。统计学习基于训练数据集，根据学习策略，从假设空间中选取最优模型，然后考虑用什么计算方法求解最有模型。统计学习问题变为了最优化问题，统计学习的算法变味求解最优化问题的算法。如何保证找到全局最优解，并使求解过程非常高效，就称为一个重要问题。
1.4 模型评估与模型选择
1.4.1 训练误差与测试误差
当损失函数给定时，基于损失函数的模型的训练误差和模型的测试误差就自然称为学习方法评估的标准。假设学习到的模型为$ Y=fhat (X)$，训练误差是模型关于训练数据集的平均损失：
R_emp(f)^=1N∑_i=1NL(y_i,f(^x_i))R_{emp}(f hat)=frac {1} {N} sum_{i=1}^N L(y_i,f hat(x_i)) R_emp(f)^=N1∑_i=1NL(y_i,f(^x_i))
测试误差是关于测试数据集的平均损失：
e_test(f)^=1N′∑_i=1N′L(y_i,f(^x_i))e_{test}(f hat)=frac {1} {N prime} sum_{i=1}^{Nprime} L(y_i,f hat(x_i)) e_test(f)^=N′1∑_i=1N′L(y_i,f(^x_i))
N和N′NprimeN′分别为训练数据集和测试数据集的样本容量。
通常将学习方法对未知数据的预测能力称为泛化能力（generalization ability）。
1.4.2 过拟合和模型选择
过拟合是指学习时选择的模型包含参数过多，以至于模型对已知数据预测很好，而对未知数据预测很差的现象。模型选择旨在避免过拟合并提供模型的预测能力。模型选择时，不仅要考虑对已知数据的预测能力，而且还要考虑对未知数据的预测能力。下图展示了训练误差、测试误差与模型复杂度之间的关系。当模型复杂度增大时，训练误差会逐渐减少并趋向于0；而测试误差会先减少，达到最小值后又增大。当选择的模型复杂度过大时，过拟合现象就会发生。学习时要防止过拟合，进行最优的模型选择，即选择模型复杂度适当的模型，以使测试误差达到最小。
1.5 正则化与交叉验证
1.5.1 正则化
模型选择的方法是正则化（regularization）。正则化是结构风险最小化策略的实现，是在经验风险上加上一个正则化项（regularizer）或惩罚项（penalty term）。正则化项一般是模型复杂度的单调递增函数，模型越复杂，正则化值就越大。正则化一般具有以下形式：
min_f∈F1N∑_i=1NL(y_i,f(x_i)) λJ(f)^{min}_{f in F } frac {1} {N} sum_{i=1}^{N} L(y_i,f(x_i)) lambda J(f)min_f∈FN1∑_i=1NL(y_i,f(x_i)) λJ(f)
其中，第一项是经验风险，第二项是正则化项，λ>=0lambda >= 0λ>=0为调整两者之间关系的系数。
正则化项可以取不同的形式，回归问题中，损失函数是平方损失，正则化项可以是参数向量的L_2L_2L_2范数：
L(w)=1N∑_i=1N(f(x_i;w)−y_i)2 λ2∣∣w∣∣2L(w)=frac {1} {N} sum_{i=1}^{N} (f(x_i;w) - y_i)^2 frac {lambda} {2} ||w||^2L(w)=N1∑_i=1N(f(x_i;w)−y_i)2 2λ∣∣w∣∣2
∣∣w∣∣||w||∣∣w∣∣表示参数向量w的L_2L_2L_2范数。正则化项也可以是参数向量的L_1L_1L_1范数：
L(w)=1N∑_i=1N(f(x_i;w)−y_i)2 λ2∣∣w∣∣_1L(w)=frac {1} {N} sum_{i=1}^{N} (f(x_i;w) - y_i)^2 frac {lambda} {2} ||w||_1L(w)=N1∑_i=1N(f(x_i;w)−y_i)2 2λ∣∣w∣∣_1
∣∣w∣_1||w|_1∣∣w∣_1表示参数向量w的L_1L_1L_1范数。
正则化的作用是选择经验风险和模型复杂度同时较小的模型。正则化符合奥卡姆剃刀原理：在所有可能选择的模型中，应该选择能够很好的解释已知数据并且十分简单的模型。从贝叶斯估计的角度来看，正则化项对应模型的先验概率，可以假设复杂的模型具有较小的先验概率，简单的模型具有较大的先验概率。
1.5.2 交叉验证
另一种常用的模型选择方法是交叉验证（cross validation）。如果给定的样本数据充足，进行模型选择的一种简单方法是随机的将数据分为训练集（training set）、测试集（test set）和验证集（validation set）。训练集用来训练模型，测试集用于模型的评估，验证集用于模型的选择。在学习到的模型中，选择对验证集有最小预测误差的模型。当数据集不充足时，可以采用交叉验证的方法。交叉验证的基本思想是重复的使用数据；吧核定的数据分为训练集和测试集，在此基础上进行反复的训练、测试和模型选择。
1.简单交叉验证
简单交叉验证方法是：首先随机地将数据分为两部分——训练集(70%)和测试集(30%)；然后用训练集在各种条件下训练得到不同的模型，在测试集上评价各个模型的测试误差，选择测试误差最小的模型。
2.S折交叉验证
应用最多的是S折交叉验证（S-fold cross validation），首先随机地将数据分为S个互不相交的大小相同的子集，然后利用S−1S-1S−1个子集的数据进行训练，用剩下的子集进行测试；重复上述过程，最后选出S次测试中平均测试误差最小的模型。
3.留一交叉验证
S折交叉验证特殊情况是S=NS=NS=N，称为留一交叉验证（leave-one cross validation），往往在数据缺乏的情况下使用。
1.6 泛化能力
1.6.1 泛化误差
学习方法的泛化能力（generalization ability）是指由该方法学习到的模型对未知数据的预测能力，是学习方法本质上最重要的性质。通常采用测试误差来评价学习方法的泛化能力，但这种方法依赖于测试数据，但数据较少时评价结果有可能不可靠。统计学试图从理论上对学习方法的泛化能力进行分析。
首先给出泛化误差的定义，如果学到的模型是f^hat ff^，那么用这个模型对未知数据预测的误差即为泛化误差（generalization error）
R_exp(f^)=E_p[L(Y,f^(X))]=∫x∗yL(y,f^(x))P(x,y)dxdyR_{exp}(hat f)=E_p[L(Y,hat f(X))] = int_{x*y}L(y,hat f(x))P(x,y)dxdyR_exp(f^)=E_p[L(Y,f^(X))]=∫x∗yL(y,f^(x))P(x,y)dxdy
泛化误差反映了学习方法的泛化能力，泛化误差就是所学习到的模型的期望风险。
1.6.2 泛化误差上界
学习方法的泛化能力分析往往是通过研究误差的概率上界进行的，简称为泛化误差上界（generalization error bound）。泛化误差上界通常具有以下性质：它是样本容量的函数，当样本容量增加时，泛化上界趋向于0；它是假设空间容量的函数，假设空间容量越大，模型就越难学，泛化误差上界就越大。
1.7 生成模型和判别模型
监督学习方法可分为生成方法（generative approach）和判别方法（discriminative approach）。所学到的模型分别称为生成模型（generative model）和判别模型（discriminative model）。生成方法由数据学习联合概率分布P(X,Y)，然后求出条件概率分布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产生输出Y的生成关系。典型的生成模型有：朴素贝叶斯法和隐马尔可夫模型。
判别方法由数据直接学习决策函数f(X)或者条件概率分布P(Y|X)作为预测的模型，即判别模型。判别方法关心的是对给定的输入X，应该预测什么样的输出Y。典型的判别模型包括：k近邻法、感知机、决策树、逻辑回归模型、最大熵模型、支持向量机、提升方法和条件随机场。
在监督学习中，生成方法和判别方法各有优缺点，适合于不同条件下的学习问题。生成方法的特点：生成方法可以还原出联合概率分布P(X,Y)，而判别方法则不能；生成方法的收敛速度更快，当存在隐变量时，仍可以使用生成方法，此时判别方法不可用。判别方法的特点：判别方法直接学习的是条件概率P(Y|X)或决策函数f(X)，直接面对预测，往往学习的准确率更高；由于直接学习P(Y|X)或f(X)，可以对数据进行各种程度上的抽象、定义特征并使用特征，因此可以简化学习问题。
1.8 分类问题
分类是监督学习的一个核心问题。在监督学习中，当输出变量Y取有限个离散值时，预测问题便称为分类问题。监督学习从数据中学习一个分类模型或分类决策函数，称为分类器（classifier）。分类器对新的输入进行输出的预测（prediction），称为分类（classification）。分类的类别为多个时，称为多分类问题。分类问题包括学习和分类两个过程。学习过程中，根据已知的训练数据集学习一个分类器，分类过程中，根据学习的分类器对新实例进行分类。分类问题如图所示：
精确率的定义为P=TPTP FPP=frac {TP} {TP FP}P=TP FPTP，召回率的定义为R=TPTP FNR=frac {TP} {TP FN}R=TP FNTP，F1值是精确率和召回率的调和均值，公式为F1=2PRP RF1=frac {2PR} {P R}F1=P R2PR。精确率和召回率都高时，F1值也会高。
1.9 标注问题
标注（tagging）也是一个监督学习问题，可以认为标注问题是分类问题的一个推广，标注问题的输入是一个观测序列，输出是一个标记序列或状态序列。标注问题的目标在于学习一个模型，使它能够对观测序列给出标记序列作为预测。标注问题分为学习和标记过程。学习系统基于训练数据集构建一个模型，表示为条件概率，标注系统按照学习到的条件概率分布模型，对新的输入观测序列找到相应的输出标记序列。标注问题如下图所示：
评价标注模型的指标与评价分类模型的指标一样，常用的有标注准确率、精确率和召回率。标注常用的统计学习方法有：隐马尔可夫模型、条件随机场。标注问题在信息抽取、自然语言处理等领域被广泛应用，是这些领域的基本问题。
1.10 回归问题
回归（regression）是监督学习的另一个重要问题。回归用于预测输入变量（自变量）和输出变量（因变量）之间的关系，特别是当输入变量的值发生变化时，输出变量的值随之发生变化。回归模型正是表示从输入变量到输出变量之间的映射的函数。回归问题等价于函数拟合，选择一条函数曲线使其很好地拟合已知数据且很好的预测未知数据。
回归问题分为学习和预测两个过程。学习系统基于训练数据构建一个模型，预测系统根据学习的模型确定相应的输出。回归问题如下图所示：
回归问题按照变量的个数分为一元回归和多元回归；按照输入变量和输出变量之间关系的类型即模型的类型，分为线性回归和非线性回归。回归学习最常用的损失函数是平方损失函数，此情况下回归问题可以用最小二乘法求解。
