统计学习

统计学习的特点

统计学习(statistical learning)是关于计算机给予数据构建概率统计模型并运用模型对数据进行预测与分析的一门学科。统计学习也称为统计机器学习(statistical machine learning)。

哈尔伯特西蒙(Herbert A.Simon)曾对"学习"给出以下定义:

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

统计学习的对象

统计学习的对象时数据(data)。它从数据出发，提取数据的特征，抽象出数据的模型，发现数据中的知识，又回到对数据的分析与预测中去。

统计学习关于数据的基本假设是同类数据具有一定的统计规律性，这是统计学习的前提。

在统计学习过程中，以变量或变量组表示数据。数据分为由连续变量和离散变量表示的类型。

统计学习的目的

统计学习用于对数据进行预测与分析，特别是对未知数据进行预测与分析。统计学习总的目标就是考虑学习什么样的模型和如何学习模型，以使模型能够对数据进行准确的预测与分析，同时也要考虑尽可能地提高学习效率。

统计学习的方法

监督学习(supervised learning)
非监督学习(unsupervised learning)
半监督学习(semi-supervised learning)
强化学习(reinforcement learning)

监督学习

监督学习(supervised learning)的任务时学习一个模型，使模型能够对任意给定的输入，对其相应的输出做出一个好的预测(注意，这里的输入、输出是指某个系统的输入与输出，与学习的输入与输出不同)

基本概念

输入空间、特征空间与输出空间

在监督学习中，将输入与输出所有可能取值的集合分别称为输入空间(input space)与输出空间(output space)，输入与输出空间可以是有限元素的集合，也可以是整个欧式空间。输入空间与输出空间可以是同一个空间，也可以是不同的空间；但通常输出空间远远小于输入空间。

每个具体的输入是一个实例(instance)，通常是由特征向量(feature vector)表示，这时，所有特征向量存在的空间成为特征空间(feature space),特征空间的每一维对应于一个特征。有时假设输入空间与特征空间为相同的空间，对它们不予区分；有时假设输入空间与特征空间为不同的空间，将实例从输入空间映射到特征空间。模型实际上都是定义在特征空间上的。

回归问题:输入变量与输出变量均为连续变量。
分类问题:输出变量为有限个离散变量
标注问题:输入变量与输出变量均为变量序列的预测。

联合概率分布

监督学习假设输入与输出的随机变量X与Y遵循联合概率分布$P(X,Y)$。$P(X,Y)$表示分布函数，或分布密度函数。X和Y具有联合概率分布的假设就是监督学习关于数据的基本假设。

假设空间

监督学习的目的在于学习一个由输入到输出的映射，这一映射由模型来表示。模型属于由输入空间到输出空间的映射的集合，这个集合就是假设空间(hypothesis space).假设空间的确定意味着学习范围的确定。

问题的形式化

监督学习利用训练数据集学习一个模型，再用模型对测试样本集进行预测，由于在这个过程中需要训练数据集，而训练数据集往往是人工给出的，所以这个学习过程称为监督学习。监督学习分为学习和预测两个过程。

监督学习中，假设训练数据与观测数据是依联合概率分布$P(X,Y)$独立同分布产生的。

统计学习三要素

方法 = 模型 + 策略 + 算法

模型

在监督学习过程中，模型就是所要学习的条件概率分布或决策函数，也就是说，模型可以用概率条件分布或决策函数来表示。模型的假设空间(hypothesis space)包含了所有可能的条件概率分布或决策函数。假设空间中的模型一般有无穷多个。

决策函数

当假设空间用决策函数表示时，假设空间可以定义为决策函数的集合

$$ \begin{equation} \mathcal{F}=\{f|Y=f(X)\} \end{equation} $$

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

$$ \begin{equation} \mathcal{F}=\{f|Y=f_\theta(X),\theta\in R^n\} \end{equation} $$

参数向量$\theta$取值于$n$维欧式空间$R_n$，称为参数空间(parameter space)。

条件概率分布

当假设空间用条件概率分布时，假设空间也可以定义为条件概率的集合

$$ \begin{equation} \mathcal{F}=\{P|P(Y|X)\} \end{equation} $$

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

$$ \begin{equation} \mathcal{F}=\{f|Y=f_\theta(Y|X),\theta\in R^n\} \end{equation} $$

参数向量$\theta$取值于$n$维欧式空间$R_n$，也称为参数空间(parameter space)。

决策函数表示的模型为非概率模型，由条件概率表示的模型为概率模型。

策略

有了模型的假设空间，统计学习接着需要考虑的是按照什么样的准则学习或选择最优的模型。统计学习的目的在于从假设空间选取最优模型。

首先要了解损失函数与风险函数的概念。

损失函数:度量模型一次预测的好坏
风险函数:度量平均意义下模型预测的好坏

损失函数和风险函数

监督学习是从假设空间$\mathcal{F}$中选取一个最优的模型$f$，使得对于给定的输入$X$，由$f$给出相应的输出$f(X)$，这个输出的预测值$f(X)$与真实值$Y$可能一致也可能不一致，我们必须用一个函数来度量它们之间的差异程度。这就引出了损失函数(loss function)或代价函数(cost function)的概念。损失函数应该是$f(X)$和$Y$的非负实值函数，记作$L(Y,f(X))$。

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

0-1损失函数(0-1 loss function)

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

平方损失函数(quadratic loss function)

$$ \begin{equation} L(Y,f(X))=(Y-f(X))^2 \end{equation} $$

绝对损失函数(absolute loss function)
$$ \begin{equation} L(Y,f(X))=\left\vert Y-f(X)\right\vert \end{equation} $$
对数损失函数(logarithmic loss function)或对数似然损失函数(loglikeihood loss function)
$$ \begin{equation} L(Y,f(Y|X)=-\log P(Y|X) \end{equation} $$

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

$$ \begin{equation} R_{exp}(f)=E_p[L(Y,f(X))]=\int_\mathcal{X \times Y} L(y,f(x))P(x,y) dxdy \end{equation} $$

这是理论上模型$f(X)$关于联合分布$P(X,Y)$的平均意义下的损失，称为风险函数(risk function)或期望损失(expected loss)。我们学习的目标就是选择期望风险最小的模型。但是由于联合分布$P(X,Y)$是未知的，所以$R_{exp}(f)$不能直接计算。

给定一个训练数据集

$$ \begin{equation} T=\{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)\} \end{equation} $$

模型$f(X)$关于训练数据集的平均损失称为经验风险(empirical risk)或经验损失(empirical loss),记作$R_{emp}$:

$$ \begin{equation} R_{emp}(f)=\frac{1}{N}\sum_{i=1}^N L(y_i,f(x_i)) \end{equation} $$

期望风险$R\_{exp}(f)$是模型关于联合分布的期望损失，经验风险$R\_{emp}(f)$是模型关于训练样本集的平均损失。根据大数定律，当样本容量$N$趋于无穷时，经验风险$R\_{emp}(f)$趋于期望风险$R\_{exp}(f)$。所以很自然的想法是，用经验风险估计期望风险，但是现实中的训练样本数目有限，甚至很小，所以这样的估计并不理想，需要对经验风险进行一定的矫正。

经验风险最小化与结构风险最小化

在假设空间、损失函数以及训练数据集确定的情况下，经验风险函数就可以确定。经验风险最小化(empirical risk minimization,ERM)的策略认为，经验风险最小的模型是最优的模型。根据这一策略，按照经验风险最小化求最优模型就是求解最优化问题:

$$ \begin{equation} \min_{f \in\cal_{F} } \frac{1}{N}\sum_{i=1}^N L(y_i,f(x_i)) \label{ERM} \end{equation} $$

其中，$\cal{F}$是假设空间。

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

但是，当样本容量很小时，经验风险最小化学习的效果未必很好，会产生"过拟合(over-fitting)"现象。

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

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

其中$J(f)$为模型的复杂度，是定义在假设空间$\cal{F}$上的泛函。模型$f$越复杂，复杂度$J(f)$越大。$\lambda\ge0$是系数，用以权衡经验风险和模型复杂度。结构风险需要经验风险与模型复杂度同时小。结构风险小的模型往往对训练数据以及未知的测试数据都有较好的预测。

比如，贝叶斯估计中的最大后验概率估计(maximum posterior probability estimate,MAP)就是结构风险最小化的一个例子。当模型是条件概率分布、损失函数是对数损失函数、模型复杂度由模型的先验概率表示时，结构风险最小化等价于最大后验概率估计。

结构风险最小化的策略认为结构风险最小的模型是最优模型，所以寻找最优模型，就是求解最优化问题:

$$ \begin{equation} \min_{f\in\cal{F}}\frac{1}{N}\sum_{i=1}^N L(y_i,f(x_i)) + \lambda J(f) \label{SRM} \end{equation} $$

这样，监督学习的问题就变成了经验风险(公式$\ref{ERM}$)或结构风险函数(公式$\ref{SRM}$)的最优化问题，这时经验结构风险函数是最优化的目标函数。

算法

算法是指学习模型的具体计算方法。统计学习基于训练数据集，根据学习策略，从假设空间中选择最优模型，最后需要考虑用什么样的计算方法求解最有模型。

模型评估与模型选择

训练误差与测试误差

统计学习的目的是使学到的模型不仅对已知的数据而且对未知数据都能有很好的预测能力。不同的学习方法会给出不同的模型，当损失函数给定时，基于损失函数的训练误差(training error)和模型的测试误差(test error)就成为学习方法评估的标准。需要注意的是，统计学习方法具体采用的损失函数未必是评估时所使用的损失函数，当然，两者一致是比较理想的。

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

$$ \begin{equation} R_{emp}(\hat{f})=\frac{1}{N}\sum_{i=1}^N L(y_i,\hat{f}(x_i)) \end{equation} $$

其中$N$是训练样本容量。

测试误差是模型$Y=\hat{f}(X)$关于测试数据集的平均损失:

$$ \begin{equation} R_{emp}(\hat{f})=\frac{1}{N'}\sum_{i=1}^N' L(y_i,\hat{f}(x_i)) \end{equation} $$

其中$N'$是测试样本容量。

训练误差的大小，对判定给定的问题是不是一个容易学习的问题是有意义的，但本质上不重要。测试误差反映了学习方法对未知的测试数据集的预测能力，是学习中的重要概念。通常将学习方法对未知数据的预测能力称为泛化能力(generalization ability)

过拟合与模型选择

当假设空间含有不同复杂度(例如，不同的参数个数)的模型时，就要面临模型选择(model selection)的问题，我们希望选择或学习一个合适的模型，如果在假设空间中存在"真"模型，那么所选择的模型应该逼近真模型。

但是，如果一味追求提高对训练数据的预测能力，所选模型的复杂度则往往会比真模型更高。这种现象称为过拟合(over-fitting)。过拟合是指学习时选择的模型所包含的参数过多，以至于出现这一模型对已知数据预测得很好，但对未知数据预测得很差的现象。在上文说到的两个监督学习的策略中，结构风险就是把模型的复杂度考虑进去了，而经验风险就没有考虑模型的复杂度，因此结构风险对于未知数据会有更好的预测。可以说模型选择旨在避免过拟合并提高模型的预测能力。

下图描述了训练误差和测试误差与模型的复杂度之间的关系。当模型的复杂度增大时，训练误差会逐渐减小并趋向于0；而测试误差会先减小，达到最小值后又增大。当选择的模型复杂度过大时，过拟合现象就会发生。

训练误差和测试误差与模型复杂度的关系

下面介绍两种常用的模型选择方法:正则化与交叉验证。

正则化与交叉验证

正则化

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

正则化一般具有如下的形式:

$$ \begin{equation} \min_{f\in\cal{F}}\frac{1}{N}\sum_{i=1}^N L(y_i,f(x_i)) + \lambda J(f) \end{equation} $$

其中第一项是经验风险，第二项是正则化项，$\lambda\ge0$为调整两者之间关系的系数。

正则化的作用是选择经验风险与模型复杂度同时较小的模型。正则化符合奥卡姆剃刀原理(Occam's razor)，奥卡姆剃刀原理应用于模型选择时变为以下的想法:在所有可能选择的模型中，能够很好地解释已知数据并且十分简单才是最好的模型。

交叉验证

另一种常见的模型选择方法是交叉验证(cross validation)。

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

但是，在许多实际应用中数据是不充足的。为了选择好的模型，可以采用交叉验证的方式。交叉验证的基本思想是重复地使用数据；把给定的数据进行切分，将切分的数据集组合为训练集与测试集，在此基础上反复地进行训练、测试以及模型选择。

简单交叉验证

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

S折交叉验证

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

泛化能力

泛化误差

学习方法的泛化能力(generalization ability)是指由该方法学习到的模型对未知数据的预测能力，是学习方法本质上重要的性质。

泛化误差的定义:如果学到的模型是$\hat{f}$，那么用这个模型对未知数据预测的误差即为泛化误差(generalization error)

$$ \begin{equation} R_{exp}(\hat{f})=E_p[L(Y,\hat{f}(X))]=\int_{\cal_{X \times Y}}L(Y,\hat{f}(X))P(x,y)dxdy \end{equation} $$

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

泛化误差上界

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

生成模型与判别模型

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

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

$$ \begin{equation} P(Y|X)=\frac{P(X,Y)}{P(X)} \end{equation} $$

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

判别方法由数据直接学习决策函数$f(X)$或者条件概率分布$P(X\|Y)$作为预测的模型，即判别模型。典型的判别模型包括:k近邻法、感知机、决策树、逻辑斯蒂回归模型、最大熵模型、支持向量机、提升方法和条件随机场等。

分类问题

分类是监督学习的一个核心问题。在监督学习中，当输出变量Y取有限个离散值时，预测问题便成为分类问题。这是，输入变量X可以是离散的，也可以是连续的。监督学习从数据中学习一个分类模型或分类决策函数，称为分类器(classifier)。

对于二类分类问题常用的评价指标是精确率(precision)与召回率(recall)。分类器在测试数据集上的预测或正确或不正确，4种情况出现的总数分别记作:

TP——将正类预测为正类数；
FN——将正类预测为负类数；
FP——将负类预测为正类数；
TN——将负类预测为负类数；

精确率定义为:

$$ \begin{equation} P=\frac{TP}{TP+FP} \end{equation} $$

召回率定义为

$$ \begin{equation} R=\frac{TP}{TP+FN} \end{equation} $$

此外，还有$F$值，是精确率和召回率的调和均值，即

$$ \begin{gather} \frac{2}{F}=\frac{1}{P}+\frac{1}{R} \\ F=\frac{2TP}{2TP+FP+FN} \end{gather} $$

精确率和召回率都高时，$F$值也会高。

标注问题

标注问题的输入是一个预测序列，输出是一个标记序列或状态序列。标注问题的目标在于学习一个模型，是它能够对观测序列给出标记序列作为预测。注意，可能的标记个数是有限的，但其组合所城的标记序列的个数是依序列长度呈指数级增长的。

评价标注模型的指标与评价分类模型的指标一样，常用的标注精确率和召回率。其定义与分类模型相同。

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

回归问题

回归用于预测输入变量(自变量)和输出变量(因变量)之间的关系，特别是当输入变量的值发生变化时，输出变量的值随之发生的变化。回归模型正是表示从输入变量到输出变量之间映射的函数。回归问题的学习等价于函数拟合:选择一条函数曲线使其很好地拟合已知数据且很好地预测未知数据。

回归问题按照输入变量的个数，分为一元回归和多元回归；按照输入变量和输出变量之间关系的类型即模型的类型，分为线性回归和非线性回归。

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

Flyaway is the owner of this blog.

统计学习方法概论