统计学习方法概论

Posted on

统计学习方法概论

1. 统计学习

1.1. 对象及方法

（1）统计学习的对象：数据
（2）关于数据的基本假设：同类数据具有一定的统计规律性
（3）统计学习的方法：基于数据构建统计模型从而对数据进行预测与分析
（4）组成：监督学习，非监督学习，半监督学习，强化学习
（5）统计学习方法三要素：模型，策略，算法

1.2. 步骤

统计学习方法的步骤：

  1. 得到一个有限的训练数据集合；
  2. 确定包含所有可能的模型的假设空间，即学习模型的集合；
  3. 确定模型选择的准则，即学习的策略；
  4. 实现求解最优模型的算法，即学习的算法；
  5. 通过学习方法选择最优的模型；
  6. 利用学习的最优模型对新数据进行预测和分析。

2. 监督学习

2.1. 基本概念

（1）输入空间、特征空间和输出空间 将输入与输出所有可能取值的集合分别称为输入空间（input space）和输出空间（output space）。 每个具体的输入是一个实例，通常由特征向量表示，所有特征向量存在的空间成为特征空间（feature space）。

（2）联合概率分布 监督学习假设输入与输出的随机变量X和Y遵循联合概率分布P(X,Y)，训练数据和测试数据被看作是依联合概率分布P(X,Y)独立同分布产生的。X和Y具有联合概率分布的建设就是监督学习关于数据的基本假设。

（3）假设空间（hypothesis space） 监督学习的目的在于学习一个由输入到输出的映射，这一映射由模型来表示。模型属于由输入空间到输出空间的映射的集合，这个集合就是假设空间。

（4）广泛使用的分类器 包括：人工神经网络、支持向量机、高斯混合模型、朴素贝叶斯、决策树和径向基函数分类。

3. 统计学习三要素

统计学习方法由三要素构成：方法 = 模型 + 策略 + 算法

3.1. 模型

在监督学习过程中，模型就是所要学习的条件概率分布或决策函数。模型的假设空间包含所有可能的条件概率分布或决策函数。

（1）决策函数 假设空间可以用F表示，假设空间可以定义为决策函数的集合： \[F=\{f|Y=f(X)\}\] X和Y是定义在输入空间X和输出空间Y上的变量，F通常是一个由参数向量决定的函数族： \[F=\{f|Y=f_\theta(X),\theta\in R^n\}\] 参数向量$\(取值于n维欧式空间\)R^n$，成为参数空间（parameter space）。

（2）条件概率分布 假设空间定义为条件概率的集合：
\[F=\{P|P(Y|X)\}\] X和Y是定义在输入空间X和输出空间Y上的随机变量，这时F通常是由一个参数向量决定的条件概率分布族：
\[F=\{P|P_\theta (Y|X),\theta \in R^n\}\] 参数向量$\(取值于n维欧式空间\)R^n$，也成为参数空间。
由决策函数表示的模型为非概率模型，有条件概率表示的模型为概率模型。

3.2. 策略

（1）损失函数和风险函数（loss function） 损失函数度量模型一次预测的好坏，风险函数度量平均意义下模型预测的好坏。
损失函数是\(f(X)\)和\(Y\)的非负实值函数，记作\(L(Y,f(X))\)。
（i）0-1损失函数（0-1 loss function） \[L(Y,f(X))=\left\{ \begin{aligned} 1, \quad Y \neq f(X) \\ 0, \quad Y = f(X) \\ \end{aligned} \right.\]

（ii）平方损失函数（quadratic loss function） \[L(Y,f(x))=(Y-f(X))^2\]

（iii）绝对损失函数（absolute loss function） \[L(Y,f(X))=|Y-f(X)|\]

（iiii）对数损失函数（logarithmic loss function） \[L(Y,P(Y|X))=-logP(Y|X)\]

损失函数值越小，模型越好，模型输入、输出(X,Y)遵循联合分布P(X,Y)，损失的期望为：
\[R_{exp}(f)=E_p[L(Y,f(X))]=\int_{X\times Y} L(y,f(x))P(x,y)dxdy\] 这是理论上模型\(f(X)\)关于联合分布\(P(X,Y)\)的平均意义下的损失，称为风险函数（risk function）或期望损失（expected loss）。
学习的目标就是选择期望风险最小的模型。

模型\(f(X)\)关于训练数据集的平均损失称为经验风险（empirical risk）或经验损失（empirical loss），记作\(R_{exp}\)： \[R_{exp}(f) = \frac{1}{N} \sum_{i=1}^N L(y_i,f(x_i))\] 注意：期望风险\(R_{exp}(f)\)是模型关于联合分布的期望损失，经验风险\(R_{exp}(f)\)是模型关于训练样本集的平均损失。 当样本容量N趋于无穷时，经验风险趋于期望风险。

（2）经验风险最小化和结构风险最小化 （i）经验风险最小化（empirical risk minimization，ERM）
经验风险最小化的策略认为经验风险最小的模型就是最优的模型： \[\min_{f \in F} \frac{1}{N} \sum_{i=1}^N L(y_i,f(x_i))\] 其中\(F\)是假设空间。
当样本容量足够大时，经验风险最小化能保证有比较好的学习效果。
当模型是条件概率分布，损失函数是对数损失函数时，经验风险最小化等价于极大似然估计。
当样本容量较小时，经验风险最小化会产生过拟合现象。

（ii）结构风险最小化（structural risk minimization，SRM）
结构风险最小化是为了防止过拟合而提出的策略。
结构风险最小化等价于正则化，就是在经验风险上加入表示模型复杂度的正则化项（regularizer），定义为：
\[R_{srm}(f)=\frac{1}{N} \sum_{i=1}^N L(y_i,f(x_i))+\lambda J(f)\] 其中\(J(f)\)为模型的复杂度，\(\lambda \geq 0\)是系数，用以权衡经验风险和模型复杂度。
结构风险小的模型往往对训练数据和未知的测试数据都有较好的预测。
当模型是条件概率分布，损失函数是对数损失函数，模型复杂度由模型的先验概率表示时，结构风险最小化等 价于最大后验概率估计（maximum posterior probability estimation，MAP）。
结构风险最小化的策略认为结构风险最小的模型就是最优模型： \[\min_{f \in F} \frac{1}{N} \sum_{i=1}^N L(y_i,f(x_i)) + \lambda J(f)\]

此时，监督学习问题就变成了经验风险或结构风险函数的最优化问题，经验或结构风险函数就是最优化的目标函数。 ### 3.3. 算法 算法是指学习模型的具体计算方法。统计学习问题归结为最优化问题，统计学习的算法成为求解最优化问题的算法。如何保证找到全局最优解，并使求解的过程非常高效，就成为了一个重要的问题。

4. 模型评估与模型选择

4.1. 训练误差与测试误差

统计学习的目的是使学习到的模型不仅对已知数据而且对未知数据都能有很好的预测能力，不同的学习方法给出不同的模型，损失函数给定时，基于损失函数的模型的训练误差（training error）和模型的测试误差（test error）就成为学习方法评估的标准。
假设学习到的模型为\(Y=\hat{f}(X)\)，训练误差是模型\(Y=\hat{f}(X)\)关于训练数据集的平均损失： \[R_{emp}(\hat{f}) = \frac{1}{N} \sum_{i=1}^{N} L(y_i,\hat{f}(x_i))\] 其中\(N\)是训练样本容量。
测试误差是模型\(Y=\hat{f}(X)\)关于测试数据集的平均损失： \[e_{test}=\frac{1}{N'} \sum_{i=1}^{N'} L(y_i, \hat{f}(x_i))\] 其中\(N'\)是测试样本容量。
训练误差的大小对于判定给定的问题是不是一个容易学习的问题是有意义的，测试误差反映了学习方法对未知的测试数据集的预测能力，即泛化能力（generalization ability）。

4.2. 过拟合和模型选择

当假设空间含有不同的复杂度（如不同的参数个数）的模型时，就要面临模型选择（model selection）的问题。一味的追求提高对训练数据的预测能力，所选的模型的复杂度往往会比真模型更高，这种现象称为过拟合（overfitting）。
过拟合：学习时选择的模型包含的参数过多，导致模型对一直数据预测得很好，但对未知数据预测的很差的现象。

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

学习时需要防止过拟合，进行最优的模型选择，即选择复杂度适当的模型，以达到使测试误差最小的学习目的，两种常用的模型选择方法：正则化和交叉验证。

5. 正则化与交叉验证

5.1. 正则化

正则化是结构风险最小化策略的实现，在经验风险上加一个正则项（regularizer）或罚项（penalty term），正则化项一般是模型复杂度的单调递增函数，模型越复杂，正则化值越大。
一般形式：
\[\min_{f \in F} \frac{1}{N} \sum_{i=1}^{N} L(y_i,f(x_i)) + \lambda j(f)\] 第一项为经验风险，第二项为正则项。\(\lambda \geq 0\)为调整两者之间关系的系数。
正则化的作用是选择经验风险与模型复杂度同时较小的模型。
正则化符合奥卡姆剃刀原则（Occam's razor）原理：在所有可能选择的模型中，能够很好解释已知数据并十分简单的才是最好的模型。
从贝叶斯估计的角度考虑：正则化项对应于模型的先验概率，可以假设复杂的模型有较小的先验概率，简单的模型有较大的先验概率。

5.2. 交叉验证

交叉验证是一种常用的模型选择方法。
如果给定的样本数据充足，可以随机将数据集切分为三部分：训练集（training set）、验证集（validation set）和测试集（test set）。训练集用于训练模型，验证集用于模型的选择，测试集用于最终对学习方法的评估。学习不同复杂度的模型时，选择对验证集有较小预测误差的模型。
当数据样本不充足时，可以采用交叉验证的方法。其基本思想是重复地使用数据，把给定的数据进行切分，将切分的数据集合组合为训练集和测试集，在此基础上反复地进行训练、测试以及模型选择。 交叉验证形式：

  • 简单交叉验证：随机地将给定数据集分为两部分，一部分作为训练集，另一部分作为测试集；
  • S折交叉验证：随机地将给定数据切分为S个互不相交的大小相同的子集，利用S-1个子集的数据训练模型，利用余下的子集测试模型，对可能的S种选择重复进行，最后选出S次评测中平均测试误差最小的模型；
  • 留一交叉验证：S折交叉验证的特殊情形S=N。

6. 泛化能力

6.1. 泛化误差

学习方法的泛化能力（generalization ability）是指该方法学习到的模型对未知数据的预测能力。
如果学习到的模型是\(\hat{f}\)，那么用这个模型对未知数据预测的误差即为泛化误差（generalization error）： \[R_{exp}(\hat{f})=E_p[L(Y, \hat{f}(X))]=\int_{\chi \times \gamma} L(y,\hat{f}(x))P(x,y)dxdy \] 泛化误差反映了学习方法的泛化能力，就是学习到的模型的期望风险。

6.2. 泛化误差上界（generalization error bound）

一般通过比较两种学习方法的泛化误差上界的大小来比较它们的优劣。
性质：

  • 它是样本容量的函数，当样本容量增加时，泛化上界趋于0；
  • 他是假设空间容量（capacity）的函数，假设空间容量越大，模型就越难学，泛化上界就越大。

泛化误差上界：对于二分类问题，当假设空间时有限个函数的集合\(F=\{f_1,f_2,\dots,f_d\}\)时，对任意一个函数\(f \in F\)，至少以概率$1-$，以下列不等式成立： \[R(f) \leq \hat{R}(f) + \varepsilon (d,N,\delta )\] 其中 \[\begin{align} R(f) &= E[L(Y,f(X))] \nonumber \\ \hat{R}(f) &= \frac{1}{N} \sum_{i=1}^N L(y_i,f(x_i)) \nonumber \\ \varepsilon (d,N, \delta) &= \sqrt{\frac{1}{2N} (\log{d}+ \log{\frac{1}{\delta}})} \nonumber \end{align}\]

不等式左端的\(R(f)\)是泛化误差，右端即为泛化误差上界。在泛化误差上界中，第一项为训练误差，训练误差越小，泛化误差也越小；第二项\(\varepsilon (d,N,\delta )\)是\(N\)的单调递减函数，当\(N\)趋于无穷时趋于0；同时它也是\(\sqrt{\log{d}}\)阶的函数，假设空间\(F\)包含的函数越多，其值越大。

证明： Hoeffding不等式：设\(S_n = \sum_{i=1}^n X_i\)是独立随机变量\(X_1,X_2, \cdots, X_n\)之和，\(X_i \in [a_i,b_i]\)，则对任意\(t > 0\)，有以下不等式成立： \[\begin{align} P(S_n-ES_n \geq t) \leq exp(\frac{-2t^2}{\sum_{i=1}^n (b_i - a_i)^2}) \nonumber \\ P(ES_n-S_n \geq t) \leq exp(\frac{-2t^2}{\sum_{i=1}^n (b_i - a_i)^2}) \nonumber \end{align}\]

对任意函数\(f \in F\)，\(\hat{R}(f)\)是\(N\)个独立的随机变量\(L(Y,f(X))\)的样本均值，\(R(f)\)是随机变量\(L(Y,f(X))\)的期望值，如果损失函数取值于区间\([0,1]\)，即对所有i，\([a_i,b_i]=[0,1]\)，那么由Hoeffding不等式中的第二条可以得到，对\(\varepsilon = \frac{t}{N} > 0\)，有以下不等式成立： \[P(R(f) - \hat{R}(f) \geq \varepsilon ) \leq exp(-2N \varepsilon ^2)\]   由于\(F=\{f_1,f_2, \cdots ,f_d\}\)是一个有限集合，故 \[\begin{align} P(R(f) - \hat{R}(f)< \varepsilon) &\geq P(\bigcup_{f \in F}\{R(f) - \hat{R}(f) \geq \varepsilon \}) \nonumber \\ &\leq \sum_{f \in F}P(R(f) - \hat{R}(f) \geq \varepsilon ) \nonumber \\ &\leq d exp(-2N \varepsilon ^2) \nonumber \end{align}\]

或者等价的，对任意\(f \in F\)，有 \[P(R(f) - \hat{R}(f) < \varepsilon ) \geq 1 - d exp(-2N \varepsilon ^2)\] 令  \(\delta = d exp(-2N \varepsilon ^2)\)，那么有： \[P(R(f) < \hat{R}(f) + \varepsilon ) \geq 1 - \delta\] 即至少以概率\(1 - \delta\)有\(R(f) < \hat{R}(f) + \varepsilon\)。
以上讨论的只是假设空间包含有限个函数情况下的泛化误差上界，对于一般的假设空间要找到误差上界并没有这么简单。 ## 7. 生成模型与判别模型 监督学习方法可分为生成方法（generative approach）和判别方法（discriminative approach），所学到的模型分别称为生成模型（generative model）和判别模型（discriminative model）。
### 7.1. 生成方法 生成方法由数据学习联合概率分布\(P(X,Y)\)，然后求出条件概率分布\(P(Y|X)\)作为预测模型，即生成模型： \[P(Y|X) = \frac{P(X,Y)}{P(X)}\] 这种方法成为生成方法，因为模型表示了给定输入\(X\)产生输出\(Y\)的生成关系。
典型的生成模型：朴素贝叶斯法、隐马尔科夫模型。
特点：

  • 生成方法可以还原出联合概率分布\(P(X,Y)\)，而判别方法不能；
  • 生成方法的学习收敛速度更快，即当样本容量增加时，学到的模型可以更快的收敛到真实模型；
  • 当存在隐变量时，仍可以用生成方法学习，此时判别方法不能用。

7.2. 判别方法

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

  • 判别方法直接学习条件概率\(P(Y|X)\)或决策函数\(f(X)\)，直接预测，往往准确度更高；
  • 犹豫直接学习\(P(Y|X)\)或\(f(X)\)，可以对数据进行各种程度上的抽象、定义特征并使用特征，简化学习问题。

8. 分类问题

输入变量X可以是离散的，也可以是连续的，而输出变量是有限个离散的值，该预测问题为分类问题。
分类问题包括学习和分类两个过程：学习过程中，根据已知的训练数据集利用有效的学习方法学习一个分类器；分类过程中，利用学习的分类器对新的输入实例进行分类。

评价分类器性能的指标一般是分类准确率（accuracy）：对于给定的测试数据集，分类器正确分类的样本数与总样本数之比。
常用的指标是精确率（precision）与召回率（recall），通常关注一下4中情况：

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

精确率定义为： \[P = \frac{TP}{TP+FP} \] 召回率定义为： \[R = \frac{TP}{TP+FN} \] \(F_1\)值为精确率和召回率的调和均值，即 \[\begin{equation} \frac{2}{F_1} = \frac{1}{P} + \frac{1}{R} \nonumber \\ F_1 = \frac{2TP}{2TP+FP+FN} \end{equation}\]

用于分类的统计学习方法：k近邻法、感知机、朴素贝叶斯法、决策树、决策列表、logistic回归模型、支持向量机、提升方法、贝叶斯网络、神经网络、Winnow等。

9. 标注问题

标注问题是分类问题的推广，输入是一个观测序列，输出是一个标记序列或状态序列。
标注问题的目标在于学习一个模型，使它能够对观测序列给出标记序列作为预测。具体地，对于一个观测序列\(x_{N+1} = (x_{N+1}^{(1)}, x_{N+1}^{(2)}, \cdots, x_{N+1}^{(n)})^T\)找到是条件概率\(P((y_{N+1}^{(1)}, y_{N+1}^{(2)}, \cdots, y_{N+1}^{(n)})^T|(x_{N+1}^{(1)}, x_{N+1}^{(2)}, \cdots, x_{N+1}^{(n)})^T)\)最大的标记序列\(y_{N+1}=(y_{N+1}^{(1)}, y_{N+1}^{(2)}, \cdots, y_{N+1}^{(n)})^T\)。

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

10. 回归问题

回归用于预测输入变量（自变量）和输出变量（因变量）之间的关系，回归模型正是表示从输入变量到输出变量之间映射的函数，等价于函数拟合：选择一条函数曲线使其很好地拟合已知数据且很好地预测未知数据。

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