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


2. 模型
2.1 非概率模型
F=f|Y=f(X)
F=f|Y=fθ(X),θ∈Rn2.2 概率模型
条件概率集合:
F=P|P(Y|X)
参数向量$θ∈Rn$决定的条件概率分布族:
F=P|Pθ(Y|X),θ∈Rn3. 策略
3.1 损失函数或风险函数
L(Y,f(X))={1,Y≠f(X) 0,Y=f(X)
L(Y,f(X))=(Y−f(X))2
L(Y,f(X))=|Y−f(X)|
- Logarithmic Loss Function or log-likelihood Loss Function
L(Y,P(Y|X))=−logP(Y|X)
- Risk Function or Expected Loss
Rexp(f)=Ep[L(Y,P(Y|X))]=∫{x×y}L(y,f(x))P(x,y)dxdy
联合分布P(X,Y)未知, Rexp(f)不能直接计算.
- Empirical Risk or Empirical Loss
Remp(f)=1NN∑i=1L(yi,f(xi))
期望风险Rexp(f)是模型关于联合分布的期望损失, 经验风险Remp(f)是模型关于训练样本集的平均损失.
根据大数定律 lim.可用经验风险估计期望风险.
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. 算法
统计学习问题归结为最优化问题,统计学习的算法成为求解最优化问题的算法.
- 有解析式,解析求解
- 无解析式,数值计算
5. 模型评估与模型选择
5.1 训练误差与测试误差
- 基于损失函数的训练误差(training error).训练误差的大小,对判断给定的问题是不是一个容易学习的问题是有意义的,但本质上不重要.
- 基于模型的测试误差(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}
- 能够很好地解释已知数据并且十分简单才是好地模型.
- 从贝叶斯估计的角度来看,正则项对英语模型的先验概率,可以假设复杂的模型有较大的先验概率.
数据充足时,随机分层:
- training set
- validation set
- test set
数据不足时,交叉验证:重复使用数据,将给定的数据进行切分,将切分的数据合为训练集和测试集,在此基础上反复进行训练.
- 简单交叉验证:(70%training set,30%test set)
- S-fold cross validation:随机分成S个互不相交的大小相同的子集,S-1个用于训练,余下测试;对可能的S种组合重复选择,选出S次评测种平均测试误差最小的.
- 留一交叉验证(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. 生成模型与判别模型
- 监督学习的任务就是学习一个模型决策函数 Y=f(X) 或条件概率分布 P(Y|X)
- 监督学习的方法可以分为生成方法(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.:
特点:
- 可还原出联合概率分布 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)
输入一个观测序列,输出一个标记序列或状态序列,是分类问题的一个推广.
9.回归问题(Regression)
用于预测输入变量X(自变量)和输出变量Y(因变量)之间的关系,等价于函数拟合.
- 一元回归和多元回归
- 线性回归和非线性回归
- 平方损失函数->最小而乘法(Least Squares)
- 应用于市场预测/产品质量管理/客户满意度/投资风险分析等
Roadmap
