统计学习方法概述

统计学习的主要特点:
(1)统计学习以计算机及网络为平台,是建立在计算机及网络之上的
(2)统计学习以数据为研究对象,是数据驱动的科学
(3)统计学习的目的是对数据进行预测和分析
(4)统计学习以方法为中心
(5)统计学习是概率论、统计学、信息论、计算理论、最优化理论及计算机科学等多个领域的交叉学科

统计学习的对象是数据(data),数据分为由连续变量和离散变量表示的类型.本书以讨论离散变量的方法为主.本书只涉及利用数据构建模型及利用模型对数据进行分析与预测,对数据的观测和收集等问题不作讨论.

统计学习的目的:用于对数据进行预测和分析,特别是对未知数据进行预测与分析.对数据的预测可以使计算机更加智能化.

统计学习的方法:监督学习、非监督学习、半监督学习和强化学习等.
统计学习方法包括模型的假设空间、模型的选择的准则以及模型学习的算法，称为统计学习方法的三要素,简称为模型(model)、策略(strategy)和算法(algorithm).

事先统计学习方法的步骤如下:
(1)得到一个有限的训练数据集合
(2)确定包含所有可能的模型的假设空间,即学习模型的集合
(3)确定模型选择的准则,即学习的策略
(4)事先求解最优模型的算法,即学习的算法
(5)通过学习方法选择最优模型
(6)利用学习的最优模型对新数据进行预测或分析

统计学习三要素

$方法=模型+策略+算法$

模型

模型的假设空间包括所有可能的条件概率分布或决策函数.例如,假设决策函数是输入变量的线性函数,那么模型的假设空间就是所有这些线性函数构成的函数集合.假设空间中的模型一般有无穷多个.
假设空间用F表示.假设空间可以定义为决策函数的集合：

$F=\{f|Y=f(X)\}$

其中X和Y是定义在输入空间和输出空间上的变量.F通常是由一个参数向量决定的函数族

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

参数向量$\theta$取值于n维欧氏空间$R^n$,称为参数空间

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

$F=\{P|P(Y|X)\}$

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

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

参数向量$\theta$取值于n维欧氏空间R^n,也成为参数空间

策略

有了模型的假设空间,统计学习接着需要考虑的是按照什么样的准则学习或选择最优的模型.统计学习的目标在于从假设空间中选取最优模型.
这就需要引入损失函数与风险函数的概念.损失函数度量模型一次预测的好坏,风险函数度量平均意义下模型预测的好坏

统计学习常用的损失函数有以下几种：
(1)0-1损失函数(0-1 loss function)

$L(Y,f(X))= \begin{cases} 1, \ \ \ \ \ \ \ Y≠f(X)\\ 0, \ \ \ \ \ \ \ Y=f(X)\\ \end{cases}$

(2)平方损失函数

$L(Y,f(X))=(Y-f(X))^2$

(3)绝对损失函数

$L(Y,f(X))=|Y-f(X)|$

(4)对数损失函数或对数似然损失函数

$L(Y,P(Y|X))=-logP(Y|X)$

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

$R_{exp}=E_P[L(Y,f(X))]=\int L(y,f(x))P(x,y)dxdy$

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

学习的目标就是选择期望风险最小的模型.由于联合分布P(X,Y)是位置的,$R_{exp}(f)$不能直接计算

而往往我们会这么做:
给定一个训练数据集$T=\{(x_1,y_1),(x_2,y_2),…(x_N,y_N)\}$
模型f(X)关于训练数据集的平均损失称为经验风险或经验损失,记作$R_{emp}$

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

期望风险$R_{exp}(f)$是模型关于联合分布的期望损失,经验风险$R_{emp}(f)$是模型关于训练样本集的平均损失

根据大数定理,当样本数量N趋于无穷时,经验风险$R_{emp}(f)$趋于期望风险$R_{exp}(f)$.但是现实中训练样本数量有限,甚至很小,用经验风险估计期望风险常常并不理想,要对经验风险进行一定的矫正.这就关系到监督学习的两个基本策略:经验风险最小化和结构风险最小化

经验风险最小化:

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

其中F是假设空间
当样本容量足够大时,经验风险最小化能保证有很好的学习效果,在现实中被广泛采用,比如 极大似然估计就是经验风险最小化的一个例子。当模型是条件概率分布,损失函数是对数损失函数时,经验风险最小化等价于极大似然估计

但当样本容量很小时,经验风险最小化学习的效果未必很好,会产生过拟合现象.

结构风险最小化(SRM):

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

其中J(f)为模型的复杂度,是定义在假设空间F上的泛函.模型f越复杂,复杂度J(f)就越大;反之,模型f越简单,复杂度J(f)就越小。也就是说,结构风险最小需要经验风险与模型复杂度同时小.

比如贝叶斯估计中的最小后验概率估计(MAP),就是结构风险最小化的一个例子.

算法

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

模型评估与模型选择

过拟合与模型选择

当假设空间含有不同复杂度的模型时,就面临模型选择的问题.如果一味追求提高对训练数据的预测能力,所选模型的复杂度往往会比真模型更高,这种现象称为过拟合.

正则化与交叉验证

正则化

正则化是结构风险最小化策略的实现,是在经验风险上加一个正则化或罚项.正则化项一般是模型复杂度的单调递增函数,模型越复杂,正则化值就越大.
正则化一般具有如下形式:

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

正则化符合奥卡姆剃刀原理.从贝叶斯估计的角度俩看,正则化对应于模型的先验概率,可以假设复杂的模型有较小的先验概率,简单的模型具有较大的先验概率.

交叉验证

另一种常用的模型选择方法是交叉验证
如果给定样本数据充足,进行模型选择的一种简单方法是随机地将数据集切分成三部分,分别为训练集、测试集、验证集.
训练集用来训练模型,验证集用于模型的选择,而测试集用于最终对学习方法的评估.在学习到的不同复杂度的模型中,选择对验证集有最小预测误差的模型.

简单交叉验证
首先随机地将已给数据分为两部分:一部分作为训练集,另一部分作为测试集(70%训练集，30%测试集);然后用训练集在各种条件下训练模型,从而得到不同的模型;在测试集上评价哥哥模型的测试误差,选出测试误差最小的模型
S折交叉验证
应用最多的是S折交叉验证:首先随机地将已给数据切分成S个互不相交的大小相同地子集;然后利用S-1个子集的数据训练模型,利用余下的子集测试模型;将这一过程对可能的S种选择重复进行,最后选出S次评测种平均测试误差最小的模型.
留一交叉验证
S折交叉验证的特殊情形是S=N,称为留一交叉验证,往往在数据缺乏的情况下使用,这里N是给定数据集的容量

泛化能力

泛化能力是指由该方法学习到的模型对未知数据的预测能力,是学习方法本质上重要的性质.现实中采用最多的办法是通过测试误差来评价学习方法的泛化能力.

给出泛化误差地定义：

$R_{exp}(\hat{f})=E_P[L(Y,\hat{f}(X))]=\int L(y,\hat{f}(x))P(x,y)dxdy$

泛化误差反映了学习方法的泛化能力,如果一个方法学习的模型比另一种方法学习的模型具有更小的泛化误差,那么这种方法就更有效

生成模型和判别模型

监督学习方法又可以分为生成方法和判别方法，所学到的模型分别称为生成模型和判别模型

生成方法由数据学习联合概率分布P(X,Y),然后求出条件概率分布作为预测的模型
判别方法由数据直接学习决策函数f(X)或者条件概率分布P(Y|X)作为预测模型

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

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

感知机

感知机是二分类的线性分类模型,其输入为一个实例的特征向量输出为实例的类别,取+1和-1二值.感知机对应于输入空间(特征空间)中将实例划分为正负两类的分类超平面属于判别模型.感知机旨在求出将训练数据进行线性划分的分离超平面.

感知机算法具有简单而易于实现的优点,分为原始形式和对偶形式,感知机预测是用学习得到的感知机模型对新的输入实例进行分类.

感知机模型

输入空间到输出空间的如下函数:

$f(x)=sign(w·x+b)$

称为感知机,一种线性分类模型,属于判别模型.

$sign(x)= \begin{cases} +1, \ \ \ \ \ \ \ x≥0\\ -1, \ \ \ \ \ \ \ x<0\\ \end{cases}$

感知机模型

数据集的线性可分性:
给定数据集$T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}$
其中$x_i∈R^n$,$y_i∈{+1,-1}$,i=1,2,….N如果存在某个超平面S,wx+b=0能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧,即对所有的$y_i$=+1的实例i,$有wx_i+b>0$,对所有$y_i=-1$的实例i,有$wx_i+b<0$,则称数据集T为线性可分数据集.否则称数据集T为线性不可分.
感知机学习策略
感知机的损失函数定义为: $L(w,b)=-\sum_{x_i∈M}y_i(wx_i+b)$ 其中M为误分类点的集合,这个损失函数就是感知机学习的经验风险函数.
损失函数L(w,b)是连续可导函数

感知机学习的策略是在假设空间中选取使损失函数最小的模型参数w,b即感知机模型。

感知机学习算法

感知机学习算法的原始形式

损失函数极小化问题的解

$min_{w,b}L(w,b)=-\sum_{x_i∈M}y_i(wx_i+b)$

感知机学习算法使误分类驱动的,具体采用随机梯度下降法.首先任意选取一个超平面$w_0,b_0$,然后用梯度下降法不断地极小化目标函数(上式).极小化过程中不是一次使M中所有误分类点的梯度下降,而是一次随机选取一个误分类点使其梯度下降.

损失函数L(w,b)的梯度:

$▽_ wL(w,b)=-\sum_{x_i∈M}y_ix_i$ $▽_ bL(w,b)=-\sum_{x_i∈M}y_i$

随机选取一个误分类点,对w,b进行更新:

$w\leftarrow w+\eta y_ix_i$ $b\leftarrow b+\eta y_i$

其中$\eta$是步长,又称学习率.

感知机学习算法的对偶形式

对偶形式的基本想法是,将w和b表示为实例$x_i$和标记$y_i$的线性组合的形式,通过求解其系数而求得w和b.不失一般性,考虑w,b的初始值为0.对误分类点$(x_i,y_i)$通过

$w\leftarrow w+\eta y_ix_i$ $b\leftarrow b+\eta y_i$

逐步修改w,b设修改n次,则w,b关于$(x_i,y_i)$的增量分别是$α_iy_ix_i和α_iy_i$这里$α_i=n_i\eta$。不难发现,最后学习到的w,b可以分别表示为:

$w=\sum_{i=1}^Nα_iy_ix_i$ $b=\sum_{i=1}^Nα_iy_i$

感知机学习算法的对偶形式：
输入：线性可分数据集$T=\{(x_1,y_1),(x_2,y_2),…(x_N,y_N)\}$,其中$x_i∈R^n$,$y_i∈\{-1,+1\}$,i=1,2,…,N,学习率$\eta(0＜\eta≤1)$
输出:α,b;感知机模型$f(x)=sign(\sum_{j=1}^Nα_jy_jx_j·x+b)$其中α=(α_1,α_2,….,α_N)^T

$α\leftarrow 0,b\leftarrow 0$
训练集中选取数据$(x_i,y_i)$
如果$y_i(\sum_{j=1}^Nα_jy_jx_j·x_i+b)≤0$ $α_i\leftarrow α_i+\eta$ $b\leftarrow b+\eta y_i$
转至(2)直到没有误分类数据