统计学习第一章

第一章 基础

1. 一般步骤:

  1. 得到一个有限训练集(Date Set)
  2. 确定假设空间(学习模型的集合Model Set)
  3. 确定模型的选择准则(学习策略Strategy)
  4. 实现求解最优化模型的算法(Algotithm)
  5. 通过学习方法选择最有模型
  6. 利用学习的最优模型对新数据集进行预测或分析

2. 模型

2.1 非概率模型
  • 决策函数空间:
  • 参数向量$ \theta \in \mathbf{R}^n $决定的函数族:
2.2 概率模型

  • 条件概率集合:

  • 参数向量$$$\theta \in \mathbf{R}^n$$$决定的条件概率分布族:

3. 策略

3.1 损失函数或风险函数
  • $ \text{0-1}\ Loss\ Function $

\[
L(Y,f(X)) =
\begin{cases}
1, &\text{$Y \ne f(X)$}\\\
0, &\text{$Y=f(X)$}
\end{cases} \tag{5}
\]

  • $ Quadratic\ Loss\ Function $

\[
L(Y,f(X)) = (Y-f(X))^2 \tag{6}
\]

  • $ Absolute\ Loss\ Function $

\[
L(Y,f(X)) = |Y-f(X)| \tag{7}
\]

  • $ Logarithmic\ Loss\ Function\ or\ \text{log-likelihood}\ Loss\ Function $

\[
L(Y,P(Y|X)) = -logP(Y|X) \tag{8}
\]

  • $ Risk\ Function\ or\ Expected\ Loss $

\[
R_{exp}(f)=E_p[L(Y,P(Y|X))]= \int_\{x \times y\} L(y,f(x))P(x,y)dxdy \tag{9}
\]

联合分布$ P(X,Y) $未知, $ R_{exp}(f) $不能直接计算.

  • $ Empirical\ Risk\ or\ Empirical\ Loss $

\[
R_{emp}(f)=\frac{1}{N} \sum_{i=1}^{N}L(y_i,f(x_i)) \tag{10}
\]

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

根据大数定律 $ \lim_{N\to\infty}R_{emp}=R_{exp} $.可用经验风险估计期望风险.

  • 经验风险最小化:

\[
min_{f \in \mathscr{F}}R_{emp}(f)=min_{f \in \mathscr{F}}\frac{1}{N} \sum_{i=1}^{N}L(y_i,f(x_i)) \tag{11}
\]

当样本容量足够大,经验风险最小化能保证很好的学习效果,如MLE$ 极大似然估计(Maximum\ Likelihood\ Estimation) $.

当模型是条件概率分布,损失函数是对数函数时,经验风险最小化(EMP)等价于极大似然估计(MLE).

但是,当样本容量很小时,会产生过拟合(over-fitting)现象.于是,为了防止过拟合,可采用结构风险最小化(Structural Risk Minimization,SRM).

  • $ Structural\ Risk\ or\ Structural\ Loss $

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

结构风险在经验风险上加上表示模型复杂度的正则化项(regularizer)或罚项(penalty term).

结构风险最小化(SRM)等价于正则化(Regularization).

$ J(f) $为模型的复杂度,是定义在假设空间$ \mathscr{F} $上的泛函.模型越复杂,复杂度越大,复杂度一定意义上表示了对复杂模型的惩罚.

  • 结构风险最小化:

\[
min_{f \in \mathscr{F}}R_{srm}(f)=min_{f \in \mathscr{F}}\frac{1}{N} \sum_{i=1}^{N}L(y_i,f(x_i)) + \lambda J(f) \tag{13}
\]

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

当模型是条件概率分布,损失函数是对数函数,模型复杂度由模型的先验概率表示时,结构风险最小化(SRM)等价于最大后验概率估计(MAP).

4. 算法

统计学习问题归结为最优化问题,统计学习的算法成为求解最优化问题的算法.

  1. 有解析式,解析求解
  2. 无解析式,数值计算

5. 模型评估与模型选择

5.1 训练误差与测试误差
  1. 基于损失函数的训练误差(training error).训练误差的大小,对判断给定的问题是不是一个容易学习的问题是有意义的,但本质上不重要.
  2. 基于模型的测试误差(test error).测试误差反映了学习方法对未知的测试数据集的预测能力,测试误差小的方法通常有更好的预测能力(也称泛化能力generralization ability),是更有效的方法.

Remarks:学习时具体采用的损失函数未必是评估时使用的损失函数.当然,让二者一致是比较理想的.

  • 训练误差是学习到的模型$ \widehat{Y}=\widehat{f}(X) $ 关于训练集的平均损失:

\[
R_{emp}(\widehat{f})=\frac{1}{N} \sum_{i=1}^{N}L(y_i,\widehat{f}(x_i)) \tag{14}
\]

  • 测试误差是学习到的模型$ \widehat{Y}=\widehat{f}(X) $ 关于测试集的平均损失:

\[
e_{test}(\widehat{f})=\frac{1}{M} \sum_{i=1}^{M}L(y_i,\widehat{f}(x_i)) \tag{15}
\]

e.g. 当损失函数是0/1损失时,测试误差就变成了常见的测试数据集上的误差率(error rate)

\[
e_{test}(\widehat{f})=\frac{1}{M} \sum_{i=1}^{M}I(y_i \ne \widehat{f}(x_i)) \tag{16}
\]

相应的,常见测试数据集上的准确率(accuracy):

\[
r_{test}(\widehat{f})=\frac{1}{M} \sum_{i=1}^{M}I(y_i = \widehat{f}(x_i)) \tag{16}
\]

显然, \[ e_{test} + r_{test} = 1\]

5.2 过拟合与模型选择

过拟合(Over-fitting):学习时选择的模型所包含的参数过多,以致于出现模型对已知数据(训练集)预测很好,对未知数据预测很差的现象.

多项式拟合的例子(P27)说明:当模型的复杂度增大时,训练误差会逐渐减小并趋向0;而测试误差会先减小后增大.当选择的模型复杂度过大,过拟合的现象就会发生.

5.3 正则化与交叉验证
  • 正则化(Regularization):正则化是结构风险最小化策略的实现,是经验风险加上一个正则化项或罚项,正则化项一般是模型复杂度的单调递增函数,比如模型参数向量的范数.

e.g.:回归问题中,损失函数是平方损失,正则化项可以是参数向量的$ L_2 $范数.

\[L(w)=\frac{1}{N} \sum_{i=1}^{N}(f(x_i;w)-y_i))^2 + \frac{\lambda}{2}||w||_1 \tag{17}\]

  • 能够很好地解释已知数据并且十分简单才是好地模型.
  • 从贝叶斯估计的角度来看,正则项对英语模型的先验概率,可以假设复杂的模型有较大的先验概率.
  • 交叉验证(Cross Validation):

数据充足时,随机分层:

  • training set
  • validation set
  • test set

数据不足时,交叉验证:重复使用数据,将给定的数据进行切分,将切分的数据合为训练集和测试集,在此基础上反复进行训练.

  1. 简单交叉验证:(70%training set,30%test set)
  2. S-fold cross validation:随机分成S个互不相交的大小相同的子集,S-1个用于训练,余下测试;对可能的S种组合重复选择,选出S次评测种平均测试误差最小的.
  3. 留一交叉验证(leave-one-out cross validation):S=N,往往数据缺乏的情况下使用.

6.泛化能力

Generalization Ability:对未知数据的预测能力.一般通过测试误差来评价.

6.1 泛化误差(generalization error)

事实上,范化误差就是所学习到的模型的期望风险.
\[
R_{exp}(\widehat{f})=E_p[L(Y,\widehat{f}(X))]= \int_\{x \times y\} L(y,\widehat{f}(x))P(x,y)dxdy \tag{18}
\]

6.2 泛化误差上界(generalization error bound)
  • 性质
    • 它是样本容量的函数
    • 它是假设空间的函数

e.g.:二分类问题的泛化误差上界
Hoeffding不等式: $ S_n=\sum_{i=1}^{n}X_i $是独立随机变量$ X_1,X_2,..,X_n $之和,$ X_i \in [a_i,b_i] $,则对任意$ t>0 $,以下不等式成立:

\[
P(S_n-E[S_n] \geqslant t) \leqslant \exp{\frac{-2t^2}{\sum_{i=1}^{n}(b_i-a_i)^2}} \tag{19}
\]

\[
P(E[S_n] - S_n \leqslant t) \geqslant \exp{\frac{-2t^2}{\sum_{i=1}^{n}(b_i-a_i)^2}} \tag{20}
\]

7. 生成模型与判别模型

  1. 监督学习的任务就是学习一个模型决策函数$ Y=f(X) $或条件概率分布$ P(Y|X) $
  2. 监督学习的方法可以分为生成方法(generative approach)和判别方法(discriminative approach)
7.1 生成模型(Generative Model)

由数据学习联合概率分布$ P(X,Y) $,然后求出条件概率分布$ P(Y|X) $.即给定X,输出Y.

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

e.g.:

  • 朴素贝叶斯
  • 隐马尔可夫链HMM

特点:

  • 可还原出联合概率分布$ P(X,Y) $
  • 收敛速度更快
  • 存在隐变量时仍适用
7.2 判别模型(Discriminative Model)

直接学习决策函数$ Y=f(X) $或条件概率分布$ P(Y|X) $.对应给定的输入X,应该预测什么样的输出Y

e.g.:

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

特点:

  • 直接面对预测,往往准确率更高
  • 可以对数据进行各种程度的抽象,定义特征并适用,简化学习问题

8.分类问题

输出变量Y是有限个离散值时,监督学习的预测问题变成分类问题.输入变量X可以是离散的,也可以是连续的.

  • classifier
  • prediction->classification
  • class
8.1 二分类问题
  • $ TP $ 将正类预测为正类
  • $ FN $ 将正类预测为负类
  • $ FP $ 将负类预测为正类
  • $ TN $ 将负类预测为负类
  • 精确率(precision) \[P=\frac{TP}{TP+FP}\]
  • 召回率(recall) \[R=\frac{TP}{TP+FN}\]
  • $ F_1 $值:精确率和召回率的调和平均 \[F_1=\frac{2TP}{2TP+FP+FN}\]
8.2 标注问题(tagging)

输入一个观测序列,输出一个标记序列或状态序列,是分类问题的一个推广.

  • HMM
  • SGD
  • 信息抽取,NLP

9.回归问题(Regression)

用于预测输入变量X(自变量)和输出变量Y(因变量)之间的关系,等价于函数拟合.

  • 一元回归和多元回归
  • 线性回归和非线性回归
  • 平方损失函数->最小而乘法(Least Squares)
  • 应用于市场预测／产品质量管理／客户满意度／投资风险分析等

Roadmap

Comments