DanielLaah

《统计学习方法》笔记 (二) - 统计学习方法概论(下)


本篇博客为《统计学习方法》笔记系列第2篇, 对应《统计学习方法》中第1章下半部分的内容. 主要介绍 正则化与交叉验证, 泛化能力, 生成模型与判别模型.
说明: 目前来讲, 本系列博客内容基本完全摘抄自李航博士的《统计学习方法》, 所以阅读本系列博客极有可能造成您的不适, 如发生, 请尽快关闭浏览器. 写此系列博客目的一是学习的时候加深印象二是为了方便自己随时复习. 后面如果在其他书籍或课程中学习了相关的知识, 可能会对文章内容进行适量增删. 谢谢你!
PPT下载


下面介绍两种常用的模型选择方法.

1.5 正则化与交叉验证

1.5.1 正则化

正则化的一般形式:
$$\min_{f\in\mathcal{F}}\frac{1}{N}\sum_{i=1}^NL\left(y_i, f(x_i)\right)+\lambda J(f)$$
正则化项可以取不同的形式. 例如, 回归问题中, 损失函数是平方损失, 正则化项可以是参数向量的$L_2$范数:
$$L(w)=\frac{1}{N}\sum_{i=1}^N\left(f(x_i;w)-y_i\right)^2+\frac{\lambda}{2}\Vert w\Vert^2 $$
也可以是参数向量的$L_1$范数:
$$L(w)=\frac{1}{N}\sum_{i=1}^N\left(f(x_i;w)-y_i\right)^2+\lambda\Vert w\Vert_1$$

1.5.2 交叉验证

简单交叉验证

随机地将已给的数据分成两部分, 一部分(70%)作为训练集, 另一部分(30%)作为测试集; 然后用训练集在各种条件下(例如, 不同的参数个数)训练模型, 从而得到不同的模型; 在测试集上评价各个模型的测试误差, 选出测试误差最小的模型.

S折交叉验证

首先随机地将已给数据切分为S个互不相交的大小相同的子集; 然后利用S-1个子集的数据训练模型, 利用余下的子集测试模型; 将这一过程重复进行S次; 最后选出S次评测中平均测试误差最小的模型.

留一交叉验证

在S折交叉验证, 当S=N时, 称为留一交叉验证, 往往在数据缺乏的情况下使用.

1.6 泛化能力

1.6.1 泛化误差

在上一篇中我们已经提到了风险函数(或期望损失), 其实它就是这里要说的泛化误差.
如果学到的模型是$\hat{f}$, 那么用这个模型对未知数据的误差即为泛化误差:
$$R_{exp}(\hat{f})=E_p\left[L(Y, \hat{f}(X)\right]=\int_{\mathcal{X}\times \mathcal{Y}}L\left(y,\hat{f}(x)\right)P(x,y)dxdy$$

1.6.2 泛化误差上界

通过比较两种学习方法的泛化误差上界来决定它们的优劣. 泛化误差上界通常具有以下性质: 它是样本容量的函数, 当样本容量增加时, 泛化上界趋于0; 它是假设空间容量的函数, 假设空间越大, 模型就越难学, 泛化误差上界就越大.
为了求出泛化误差上界, 这里先介绍Hoeffding不等式, 这里需要注意的是, 书中给出的Hoeffding不等式的右边$-2t^2$应该为$-2t^2n^2$, 书中漏了一个$n^2$. 并且书中给出的是一般情况下的Hoeffding不等式, 对于二分类问题而言, 我们可以进一步令$X_i$同分布于$\text{Bernoulli}(\phi)$, 即$P(X_i=1)=\phi$, $P(X_i=0)=1-\phi$. 令$\hat{\phi}=\frac{1}{n}\sum_{i=1}^nX_i$, 对于任意$t\ge0$, 都有以下不等式成立:
$$P(\phi − \hat{\phi}\ge t)\lt\exp(−2t^2n)$$
$$P(|\phi − \hat{\phi}|\ge t)\lt2\exp(−2t^2n)$$
有了Hoeffding不等式后, 考虑一个二分类问题, 训练集为$T=\{(x_1,y_1), (x_2,y_2), …, (x_N,y_N)\}$, 假设空间是函数的有限集合$\mathcal{F}=\{f_1, f_2, …,f_d\}$, $d$是函数个数. 设$f$是从$\mathcal{F}$中选取的函数. 损失函数是0-1损失. 关于$f$的期望风险和经验风险分别是:
$$R(f)=E\left[L(Y, f(X)\right]$$
$$\hat{R}(f)=\frac{1}{N}\sum_{i=1}^NL\left(y_i,f(x_i)\right)$$
由Hoeffding不等式, 对$\epsilon \gt 0$
$$P(R(f) − \hat{R}(f)\gt \epsilon)\lt\exp(−2N\epsilon^2)$$
由于$\mathcal{F}=\{f_1, f_2, …,f_d\}$是一个有限集合, 故
$$\begin{align}
P(\exists f\in \mathcal{F}:R(f) − \hat{R}(f)\gt \epsilon) & = P(\bigcup_{f\in \mathcal{F}}\{R(f) − \hat{R}(f)\gt \epsilon\}) \\
\\
& \le \sum_{f\in \mathcal{F}}P(R(f) − \hat{R}(f)\gt \epsilon) \\
\\
& \le d\exp(-2N\epsilon^2)
\end{align}$$
等价的, 对于任意$f\in \mathcal{F}$, 有
$$P(R(f) − \hat{R}(f)\lt \epsilon)\ge 1-d\exp(−2N\epsilon^2)$$

$$\delta=d\exp(−2N\epsilon^2)$$

$$P(R(f) − \hat{R}(f)\lt \epsilon)\ge1-\delta$$
即至少以概率$1-\delta$有$R(f)\lt \hat{R}(f)+\epsilon$
定理1.1(泛化误差上界) 对二分类问题, 当假设空间是有限个函数的集合$\mathcal{F}=\{f_1, f_2, …,f_d\}$时, 对任意一个函数$f\in \mathcal{F}$, 至少以概率$1-\delta$, 以下不等式成立:
$$R(f)\le \hat{R}(f)+\epsilon$$
其中,
$$\epsilon(d, N, \delta)=\sqrt{\frac{1}{2N}\left(\log d+\log \frac{1}{\delta}\right)}$$
不等式左端为泛化误差, 右端即为泛化误差上界. 在泛化误差上界中, 第1项是训练误差,训练误差越小, 泛化误差也越小. 第2项$\epsilon(d, N, \delta)$是$N$的单调递减函数, 当$N$趋于无穷时趋于0; 同时它也是$\sqrt{\log d}$的函数, 假设空间$\mathcal{F}$包含的函数越多, 其值越大.

1.7 生成模型与判别模型

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

类型 概念 特点 例子
生成方法 生成方法由数据学习联合概率分布$P(X,Y)$, 然后求出条件概率分布$P(Y\mid X)$作为预测的模型 生成发发可以还原出联合概率分布$P(X,Y)$, 而判别方法则不能; 生成方法的学习收敛速度更快, 即当样本容量增加时, 学到的模型可以更快地收敛于真实的模型; 当存在隐变量时, 仍可以使用生成方法学习, 此刻判别方法就不能用 朴素贝叶斯法, 隐马尔科夫模型
判别方法 判别方法由数据直接学习决策函数$f(X)$或者条件概率分布$P(Y\mid X)$作为预测的模型, 即判别模型. 判别方法关心的是对于给定的输入$X$, 应该预测什么样的输出$Y$ 判别方法直接学习的是条件概率$P(Y\mid X)$或决策函数$f(X)$, 直接面对预测, 往往学习的准确率更高; 由于直接学习$f(X)$或$P(Y\mid X)$, 可以对数据进行各种程度上的抽象, 定义特征并使用特征, 因此可以简化学习问题 k近邻法, 感知机, 决策树, 逻辑斯蒂回归模型, 最大熵模型, 支持向量机, 提升方法和条件随机场