统计学习方法概论

统计学习

统计学习包括监督学习、非监督学习、半监督学习和强化学习（《统计学习方法》中主要讨论监督学习）。

监督学习

根据有限的训练数据，假设数据是独立同分布且假设模型属于某假设空间，采用某一种评价标准，从这个假设空间中选择出最优模型，以便使其对训练数据和为知测试数据在其评价标准下都有最佳的表现（准确的预测）。

概念

空间

• 输入空间
• 特征空间：特征向量
• 输出空间

在具体操作中，有时假设输入空间与特征空间相同，有时则根据需要假定两者不同，并存在映射关系可以将实例从输入空间映射到特征空间

联合概率分布

监督学习中假设输入与输出的随机变量X与Y遵循联合概率分布P(X,Y)，这是监督学习关于数据的基本假设。在实际操作中，其具体的联合概率分布定义通常未知，但是训练数据和测试数据被看做是依照该联合概率分布P(X,Y)独立同分布产生。

假设空间

监督学习中各种表达从输入空间到输出空间的模型共同构成的集合被称为假设空间，确定假设空间的过程也就是确定学习范围的过程。

假设空间用$F$表示，参数向量用$\theta$表示

• 概率模型： 条件概率分布P(Y|X)
  $F=\{P|P_\theta(Y|X), \theta\in{R^n}\}$
• 非概率模型：决策函数Y=f(X)
  $F=\{f|Y=f_{\theta}(X), \theta\in{R^n}\}$

其具体模型由具体学习方法而定。

问题的形式化

给定训练数据集

$$T=\{(x_1, y_1), (x_2, y_2), ..., (x_N, y_N)\}$$

其中$(x_i, y_i), i=1,2,…,N$是样本点， $x_i\in{x}\subset{R^n}$是输入的观测值，
$y_i\in{y}$是输出的观测值。

通过学习得到的模型通常被表示为条件概率分布 $\hat{P}(Y|X)$ 或决策函数 $Y=\hat{f}(X)$。
预测过程即是指由样本集的 $x_k,k=N+1$ 通过

$$y_k=\mathop{argmax}_{y_k}{\hat{P}(y_k|X_k)}$$

或

$$y_k=\hat{f}(x_k)$$

得到对应的输出 $y_k$。

统计学习三要素

方法=模型+策略+算法

• 模型
• 策略：选择最优模型的准则
• 算法

策略

损失函数和风险函数

损失函数

常用的损失函数：

• 0-1损失函数 $$L(Y,f(X)) = \begin{cases} 0, & \text{Y = f(X)} \\ 1, & \text{Y $\neq$ f(X)} \end{cases}$$
• 平方损失函数 $$L(Y,f(X)) = {(Y-f(X))}^2$$
• 绝对损失函数 $$L(Y,f(X)) = |(Y-f(X))|$$
• 对数损失函数 $$L(Y,P(Y|X) = -logP(Y|X)$$

风险函数（期望损失）

损失函数的期望就是风险函数：

$$R_{exp}(f) = E_{p}[L(Y, f(X))] = \int_{x\times y} L(y, f(x))P(x,y)dxdy$$

由于联合分布P(X,Y)是未知的，因此，引入经验风险，也就是训练数据集的平均损失

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

由于只有当样本量N无穷大的时候，经验风险$R{emp}(f)$才能趋近于期望风险$R{exp}(f)$，因此在现实中，经验风险并不能直接估计期望风险，需要进行校正：

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

经验风险的矫正

经验风险最小化

经验风险最小的模型就是最优模型

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

极大似然估计就是经验风险最小化。

结构风险最小化

提出目的是为了防止过拟合，因此等价于正则化，需要在经验风险上加上表示模型复杂度的正则化项。

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

其中， J(f)表示模型复杂度， 模型f越复杂，J(f)越大，$\lambda \ge 0$是系数。

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

最大后验概率估计就是结构风险最小化。

模型评估与模型选择

训练误差与测试误差

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

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

测试误差是测试数据集的平均损失：

$$e_{test} = \frac{1}{N'} \sum_{N'}^{i=1} L(y_i,\hat{f}(x_i))$$

泛化能力： 学习方法对未知数据的预测能力

过拟合与模型选择

过拟合：模型复杂度比真模型更高的现象

正则化与交叉验证

正则化与交叉验证是两种模型选择的方法

正则化

如前述，正则化是一种结构风险最小化的策略，通过给经验风险加上正则项来实现。一般而言，模型越复杂， 正则化值就越大。

$L_1$范数：

$$L(w) = \frac{1}{N} \sum_{i=1}^{N} (f(x_i;w) - y_i)^2 + \lambda {\left\| w \right\|}_1$$

${\left| w \right|}_1$表示参数向量w的范数

$L_2$范数：

$$L(w) = \frac{1}{N} \sum_{i=1}^{N} (f(x_i;w) - y_i)^2 + \frac{\lambda}{2} {\left\| w \right\|}^2$$

${\left| w \right|}$表示参数向量w的范数

交叉验证

简单交叉验证

S折交叉验证

留一交叉验证

泛化能力

泛化误差

模型对未知数据 的误差即为泛化误差（对未知数据的期望损失）。

泛化误差上界

泛化误差上界通常是用来衡量模型泛化能力的基本准则。

定理 泛化误差上界
对二类分类问题，当假设空间是有限个函数的集合$F = {f_1, f_2, …, f_d}$时， 对任意一个函数$f\in{F}$，至少以概率$1-\delta$， 以下不等式成立：

$$R(f) \le \hat{R}(f) + \epsilon{(d, N, \delta)}$$

其中，

$$\epsilon{(d, N, \delta)} = \sqrt{\frac{1}{2N}(logd + log\frac{1}{\delta})}$$

不等式左端$R(f)$是泛化误差，右端即为泛化误差上界，右端第一项是训练误差，第二项是N的单调递减函数。

生成模型与判别模型

生成模型

根据数据学习联合概率分布P(X, Y)，然后求出条件概率分布P(Y|X)作为预测模型

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

朴素贝叶斯法、隐性马尔科夫模型

判别模型

根据数据直接学习决策函数f(X)或者条件概率分布P(Y|X)作为预测模型

k近邻法、感知机、决策树、逻辑斯蒂回归模型、最大熵模型、支持向量机、提升方法、条件随机场