监督学习--统计三要素

根据《统计学习方法》中的描述，统计学习方法都是由模型、策略和算法构成的，即“方法=模型+策略+算法”。当然非监督学习、强化学习也同样拥有这三要素，但是目前只总结监督学习。

模型、策略和算法

模型

在监督学习中，模型就是所要学习的决策函数或条件概率分布。模型的假设空间中包含所有可能的决策函数或者条件概率分布，例如假设决策函数是输入变量的线性函数，那么模型的假设空间就是所有这些线性函数构成的函数集合。假设空间中的模型一般有无数个。

决策函数的假设空间表示为

其中X,Y分别是输入和输出，决策函数的假设空间通常是由一个参数向量决定的函数族。

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

监督学习的主要目的是确定假设空间中的决策函数f或条件概率P以及它们所依赖的参数θ。假如线性回归中，决策函数是数据集中特征的线性函数，那么决策函数的假设空间为F={f|Y=Xθ,θ∈Rn}。确定了参数θ，回归问题的模型就确定了。又如在logistics回归中，概率分布的假设空间为F={P|P(Y|X)=11+exp(−Xθ)}。在确定了参数θ之后，logistics回归的模型就确定了。

策略

有了模型的假设空间，监督学习的问题就变成从假设空间中选取最优的模型f或P。对于给定的输入X，可以得到预测值f(X)，预测值和真实值Y可能一致也可能不一致，需要用一个损失函数或代价函数来度量不一致的程度。损失函数是f(X)和Y的非负实值函数，用来度量模型一次预测的好坏，记作L(Y,f(X))。

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

这只是理论上风险函数或期望风险，我们学习的目标就是选择期望风险最小的模型。但是由于计算上式需要先知道联合分布P(X,Y)。实际上知道了联合分布，就可以直接求出条件分布P(Y|X)，也就不需要学习了。正是由于不知道联合分布才需要学习，这就成为了一个病态问题了。所以定义f(X)关于训练数据集的平均损失称为经验风险或者经验损失，如下：

其中n是样本个数。

期望风险是模型关于联合分布的期望损失，经验风险是模型关于训练样本集的平均损失。根据大数定律，当样本容量n趋于无穷，经验风险趋于期望风险。所以很自然的用经验风险估计期望风险。但是，现实中训练样本有限，所以用经验风险估计期望风险常常不理想，要对经验风险进行一定的矫正。这就关系到了监督学习的两个基本策略：经验风险最小化和结构风险最小化。

策略	最优化问题	说明	特例
经验风险最小化	经验风险最小的模型是最优的模型	minf∈F1n∑ni=1L(yi,f(xi))	当样本足够大，能达到很好的学习效果，当样本容量很小时，经验风险会产生过拟合的现象。
结构风险最小化	在经验风险的基础上，为防止过拟合提出的策略，等价于正则化	minf∈F1n∑ni=1L(yi,f(xi))+λJ(f)	J(f)表示模型复杂度，称为正则化项。模型越复杂，J(f)越大。λ≥0是系数，权衡经验风险和复杂度。

给定了假设空间和损失函数，监督学习就变成了经验风险或结构风险的最优化问题。

上文中有两个地方值得关注：1、常用的损失函数有哪些？2、结构风险最小化中的模型复杂度J(f)如何度量

常用的损失函数有：

1. 平方损失函数
2. log损失函数
3. 指数损失函数
4. Hinge损失函数
5. 感知损失
6. 其他损失函数

正则化常用的有l0范数，l1范数，l2范数，F范数和核范数。

平方损失函数（最小二乘）

平方损失函数的表达式为:

样本个数为n时，经验风险可以表示为

这和最小二乘法的目标函数一致。在最小二乘中，f(xi)=wTxi表示线性模型。所以最小二乘点的模型为线性模型，损失函数为平方损失，是经验风险最优化问题。

log损失函数（logistics回归）

对数损失函数针对的模型是条件概率分布。log损失函数也称作对数损失函数会对数似然损失函数。表达式为：

logistics的模型假设为

经验损失函数为

和logistics回归由极大似然估计得到的损失函数一致。

另外损失函数也可以表示为

以上假设的是二分类问题，且类别标签是0,1。如果类标签为-1,1，上式也可以表示为

如果令模型假设为f(X)，则log(1+exp(−Yf(X)))也可以称为log损失函数。

综上，logistics回归的模型为hθ(x)，损失函数为log损失，是经验风险最小化问题。

如果模型是条件概率模型，log损失函数是−logP(Y|X)

如果模型是非条件概率模型，即决策函数，log损失函数是log(1+exp(−Yf(X)))

指数损失函数（adaboost）

指数损失函数的表达式为：

在学习adaboost中提到过，Adaboost算法是模型为加法模型，目标损失函数是指数函数，学习算法为前向分步算法时的二分类学习方法。优化策略是经验风险最小化。具体推导见adaboost

Hinge损失函数（SVM）

Hinge损失函数的标准形式为

也可以写作

其中[z]+=max{0,z}

Hinge损失函数主要用于SVM。在学习SVM时，得到SVM的目标函数为

上式的前部分就是hinge损失函数的形式，其中f(x)=wTx+b表示线性模型，后面部分是正则化项。所以SVM的模型是线性模型，损失函数是hinge函数，优化策略是结构风险最小化。

感知损失（感知机）

感知损失是hinge损失的弱化形式，表达式为

也可以写作

感知损失主要用于感知机。感知机只记录分类错误的样本。假设所有错误分类的点的集合为M，则损失函数为

其中模型f(x)=wTx

下面正面两者等价。将感知机的模型函数带入感知损失得到

分类标签为-1,1，上式可以写作：

且L(y,f(x))≥0

所以经验风险为

所以感知机的模型为线性模型，损失函数为感知损失，优化策略是经验风险最小化。

0-1损失函数

0-1损失：L(Y,f(X))={1,y=f(X)0,y≠f(X)。0-1损失是一个非凸的函数，在求解的过程中，存在很多的不足，通常在实际的使用中将0-1损失函数作为一个标准，选择0-1损失函数的代理函数作为损失函数。

损失函数总结

假设前面的损失函数的模型都是线性模型f(x)=wTx，则各损失函数的图像如下：

1. 平方损失函数是一条抛物线，用于回归
2. 0-1损失函数是最本质的损失函数，当分类正确时损失为0，分类错误是损失为1
3. log损失函数可以作为0-1损失的近似
4. Hinge损失当yf(x)>1时为0，对应分类正确，和感知机相比，不仅要求样本在超平面正确的一侧，而且要求有一定的距离。当yf(x)<1时，损失和yf(x)成正比
5. 感知损失和hinge损失平行，当yf(x)>0即认为分类正确，损失为0
6. 指数损失相比其他损失惩罚力度更大
7. hinge损失，log损失，指数损失和感知损失的左侧都是凸函数，方便求导，而且都是0-1损失的上界，可以通过减小损失函数实现分类(0-1)问题的求解。

正则化

正则化是在结构风险最小化中出现的，是为了防止模型过拟合对模型所做的约束，表征的是模型的复杂度。只有模型的优化策略是结构风险最小化时才会有正则化项的出现，也就是优化以下目标函数：

前面一项是经验风险最小化，越小，函数拟合数据越好，经验误差越小。但是经验误差小可能会造成过拟合(方差大)，泛化能力差。后面一项是表示的是模型的复杂度，J(f)越小，模型越简单，也不可能过拟合。所以两者的结合，用正则化参数λ调整两者之间的关系，使得模型的经验误差小，而且泛化能力好。

正则化项J(f)有很多种选择，一般是模型复杂度的单调递增函数，模型越复杂，值就越大。比如，正则化项可以是模型参数向量的范数。然而，不同的选择对参数的约束不同，取得的效果也不同，但我们在论文中常见的都聚集在：0范数、1范数、2范数、迹范数、Frobenius范数和核范数等等。

下面以向量w=[w1,w2,...,wm]为例，看一下各个范数有什么异同

0范数：||w||0，表示向量w中非零元素的个数

1范数：||w||1=∑mi=1|wi|，表示各个分量的绝对值之和

2范数：||w||2=∑mi=1w2i−−−−−−−√，表示各个分量的平方和在开方

首先有一个问题，为什么正则化项能够防止过拟合呢？

根据知乎上的一个回答https://www.zhihu.com/question/20700829/answer/21066719

首先解释了什么是过拟合。过拟合是一种现象，当模型在训练数据集上表现很好时，在测试数据集上反而表现很差。过拟合发生的本质原因是训练数据远远少于模型假设空间中的函数的个数，而函数的个数一般是由参数决定的，所以过拟合的本质是训练数据远远小于可选参数个数。过拟合的发生，可以分解成以下三点：

1. 有限的训练数据不能完全反应一个模型的好坏，然而却不得不在这个数据集上挑选模型，由于经验风险的原因，完全有可能挑选到在训练集上表现很好却在测试集上表现很坏的模型，因为我们完全无法知道模型在测试数据集上的表现。
2. 如果模型空间很大，也就是说有很多模型可供选择，那么挑选到最合适的那个模型的概率就很小
3. 如果要是模型在训练集上表现很好，最为直接的方法就是要在足够大的模型空间中挑选模型，否则，如果模型空间很小，可能不存在最好的模型。

所以，要拟合好数据，就要有足够大的模型空间，有了足够大的模型空间，选到好的模型的概率就下降了。因此就会出现训练数据拟合的很好，泛化能力却很差的过拟合现象。

另外，前文的“模型复杂度”不是指的模型本身长的很复杂，比如5次多项式比2次多项式复杂。复杂指的是模型假设空间中可供选择的模型很多。

正则化是对参数的约束，而模型假设空间的函数正是由参数所决定，所以正则化可以控制模型空间的大小，这样，数据量和模型空间中函数的个数对等，就会防止过拟合的发生。

具体来讲，2范数是对参数加上高斯先验分布，1范数是加上laplace先验分布，0范数更是限制了参数非零的个数，这样就减小了模型假设空间中函数的个数，从而防止过拟合。

下面具体看看这三种范数的特点

L2范数

L2范数在回归中被称为Ridge回归，重要的作用还是防止过拟合。2范数是对模型参数加上高斯先验分布，通过对模型空间的控制，在一定程度上避免了过拟合。

L2范数有什么优点呢？

1. 防止过拟合，提高模型的泛化能力
2. L2范数是凸函数，且处处可导，在数值计算上有很大的优势
3. 在线性回归中，如果特征维数大于样本个数，解不唯一，2范数可以在给定条件下使解唯一；另一方面，2范数可以解决condition number不好的情况下矩阵求逆很困难的问题

什么是cindition number呢？下面具体学习一下。

优化有两大难题，一是：局部最小值，二是：ill-condition病态问题。condition number不好就是指ill-condition。ill-condition对应的是well-condition。假设方程组AX=b，需要求解X。如果A或者b稍微的改变，会使得X的解发生很大的改变，那么这个方程组系统就是ill-condition的，反之就是well-condition的。具体例子如下：

左边的是ill-condition的情况，稍微改变b或者A，解的改变很大，这个系统的解对系数矩阵A或者b太敏感了。右边的是well-condition，稍微改变A或b，解的值变动的幅度和A或b改变的幅度一致。一般我们的系数矩阵A和b是从实验数据里面估计得到的，所以它是存在误差的，如果我们的系统对这个误差是可以容忍的就还好，但系统对这个误差太敏感了，以至于我们的解的误差更大，那这个解就太不靠谱了。所以这个方程组系统就是ill-conditioned病态的，不正常的，不稳定的，

ill-condition的程度需要用condition number来衡量。矩阵A的condition number表示为：如果A非奇异

如果A奇异，condition number无穷大。也就是矩阵A的norm乘以它的逆的norm。具体的值是多少，就要看选择的norm是什么了。condition number衡量的是输入发生微小变化的时候，输出会发生多大的变化。也就是系统对微小变化的敏感度。condition number值小的就是well-conditioned的，大的就是ill-conditioned的。如果一个矩阵的condition number在1附近，那么它就是well-conditioned的，如果远大于1，那么它就是ill-conditioned的，如果一个系统是ill-conditioned的，它的输出结果就不要太相信了。

在最小二乘中有解析解

如果XTX的condition number很大的话，解不稳定，容易产生过拟合。如果加上2范数正则项的话，得到的解析解为

加入正则项的作用就是减小XTX的condition number，增加解的稳定性，从而避免过拟合

另一方面，如果使用迭代算法的话，condition number 太大仍然会导致问题：它会拖慢迭代的收敛速度，而正则项从优化的角度来看，实际上是将目标函数变成λ-strongly convex（λ强凸）的了。具体见http://blog.****.net/zouxy09/article/details/24971995/

综上，2范数正则项不仅可以防止过拟合，而且可以使优化求解变得稳定和快速。

L1范数和L0范数

L0范数是指向量中非零元素的个数。如果用L0范数约束参数向量的话，就是稀疏的概念了。但是在稀疏表示中，经常看到的是L1范数。L1范数是指向量中各元素绝对值之和，也可以称作“稀疏化算子”，也就是说L0范数也可以实现稀疏。这里有两个问题，1、为什么要用L1代替L0范数；2、为什么L1范数可以实现稀疏。

1. L0范数虽然可以实现稀疏，但是是一个NP难问题，在求解问题时很困难。而且L1是L0的最优凸近似(?)，它们在一定的条件下等价。L1比较容易求解，而且可以实现稀疏。

2. 为什么L1可以实现稀疏，可以从三个方面解释这个问题，优化，概率和图示。只要和L2范数比较，因为L2范数不能实现稀疏。

   • 从优化角度

   1	L2范数	L1范数
   目标函数	C=C0+λ∑mi=1w2i	C=C0+λ∑mi=1∥wi∥
   对第i个参数分量求导	∂C∂wi=∂C0∂wi+2λwi	∂C∂wi=∂C0∂wi+λsign(wi)
   左导数	∂C∂wi∥0+=∂C0∂wi∥0+	∂C∂wi∥0+=∂C0∂wi∥0++λ
   右导数	∂C∂wi∥0−=∂C0∂wi∥0−	∂C∂wi∥0+=∂C0∂wi∥0+−λ
   说明	如果当∂C∂wi=0时，wi=0，说明L2范数可以达到稀疏的目标。即∂C∂wi在0处的左右导数符号相反。从左右导数的表示式看，只有当∂C0∂wi∥wi=0=0时，才能实现。	和L2范数一样，要使得∂C∂wi在0处的左右导数符号相反，只需要∥∂C0∂wi∥wi=0∥<λ即可。也就是说，L1范数叜很宽松的条件下就能使得系数稀疏。

   • 从概率角度

     我们知道，L2正则化是在目标函数中加入对参数的高斯先验分布，L1范数是加上了laplace先验分布，对参数加上了限制条件，一方面限制了模型空间的大小，同时限制了参数取值的概率。

     先看一下高斯分布和laplace分布

   1	高斯分布	laplace分布
   概率密度函数	f(x;μ,σ)=12π√σexp(−(x−μ)22σ2)	f(x;μ,b)=12bexp(−∥x−μ∥b)
   图像
   和稀疏的关系	如果参数呈N(0,σ)分布，则参数在0附近的概率很大，L2正则化得到的参数大多接近于0	如果参数呈Laplace(0,b)，和L2正则化一样，参数在0附近的概率很大。但是和高斯分布相比，参数等于0的概率更大
   参数和图形的关系	σ越小，图像越陡，参数取得0附近值的概率更大	b越小，图像越陡，参数取得0的概率越大
   参数和正则化参数的关系	σ和正则化参数呈反比，σ越小，正则化约束越强，表示C越大	b和正则化参数呈反比，b越小，正则化约束越强，表示C越大

   • 从图示角度

     这里有一个很经典的图像

实际上，以线性回归为例，Ridge和Lasso可以写成下面的形式：

Ridge：

Lasso：

分别对应上图的右左两图。为了便于可视化，考虑2维的情况。在平面上可以画出目标函数的等高线，而约束则成为平面上半径为C的球。与等高线首次相交的地方就是最优解。可以看出，L1-ball和L2-ball的不同之处就在于，L1-ball在和坐标轴相交的地方都是凸出的。而目标函数除非在特殊位置，和L1-ball相交的地方总是在坐标轴上，由此便达到的稀疏的要求。而L2-ball边没有这样的性质，除非目标函数在特殊位置，和L2-ball相加的的方不在坐标轴上，便不能轻易达到稀疏。

以上从三个角度看待了L1和L2正则化，也说明了L1正则化可以产生稀疏解的原因。个人觉得第一个解释最具有说服力。

L1正则化可以产生稀疏的解，而且由于L1比L0更容易优化，所以常用L1代替L0。那么L1正则化有什么好处呢？

1. 和L2正则化一样，可以限制模型空间，故可以防止过拟合
2. 可以进行特征选择(featrue selection).大家对稀疏规则化趋之若鹜的一个关键原因在于它能实现特征的自动选择。一般来说，样本的大部分特征都是和最终的输出没有关系或者不提供任何信息的，在最小化目标函数的时候考虑这些额外的特征，虽然可以获得更小的训练误差，但在预测新的样本时，这些没用的信息反而会被考虑，从而干扰了正确的预测。稀疏规则化算子的引入就是为了完成特征自动选择的光荣使命，它会学习地去掉这些没有信息的特征，也就是把这些特征对应的权重置为0。
3. 可解释性强。另一个青睐于稀疏的理由是，模型更容易解释。例如患某种病的概率是y，然后我们收集到的数据x是1000维的，也就是我们需要寻找这1000种因素到底是怎么影响患上这种病的概率的。通过学习，如果最后学习到的参数就只有很少的非零元素，例如只有5个非零，那么我们就有理由相信，这些对应的特征在患病分析上面提供的信息是巨大的，决策性的。也就是说，患不患这种病只和这5个因素有关，那医生就好分析多了。但如果1000个参数都非0，医生面对这1000种因素，累觉不爱。

总结

到此，介绍了L0,L1,L2范数的定义，作用及优点。解决的问题如下：

1. 正则化为什么能够防止过拟合？因为这些范数限制了参数的分布，从而限制了模型空间的大小，从而使得参数个数和模型空间中的模型个数对等，防止过拟合。
2. L0,L1,L2范数的定义
3. L2范数的优点。除了能防止过拟合之外，由于L2范数是处处可微的凸函数，在数值优化上有很大优势。另外在线性回归中，L2正则化对应的是Ridge回归，一方面在样本个数小于特征数，解无穷多个的时候能够给定限制条件，产生唯一解；另一方面，能够解决ill-condition的问题。
4. L1范数为什么能够代替L0范数？L1范数和L0范数都可以实现稀疏，L1范数在一定条件下和L0范数等价，并且L1因具有比L0更好的优化求解特性而被广泛应用。
5. L1范数的优点？能够产生稀疏解，由此可以进行特征选择。
6. L1范数为什么能产生稀疏解？从三个角度解释
7. L0,L1,L2的异同？
   
   • 相同点，都是正则化的一种表现形式，都能都防止过拟合。
   • L2不能产生稀疏解，但也有自己的优点(3)。L0和L1能够产生稀疏解，并且L1比L0更容易优化，有自己的优点(5).

算法

给定了假设空间和损失函数，监督学习的问题就转化为最优化的问题了，统计学习的算法就称为求解最优化问题的算法。如果有解析解，最优化问题比较简单，但是大多数问题没有解析解，就需要用数值计算的方法求解。如何保证找到全局最优解，并使得求解过程非常高效，就称为一个重要的问题。统计学习可以利用已有的算法，或者开发特殊的算法。