统计学习方法笔记

25 Oct 2016

第一章

统计学习方法：

从训练数据（training data）（给定的、有限的集合）出发，
（假设数据是独立同分布产生的）
运用某个（某评价标准evaluation criterion）（从假设空间hypothesis space）选出的最优模型（由算法实现）
（假设空间：假设要学习的模型属于某个函数的集合）
对~~已知训练数据和~~未知测试数据（在评价标准下）有最优的预测
- 三要素：→ “模型的假设空间”（model） → “模型的选择准则”（strategy） → “模型学习的算法”（algorithm）
- 方法 = 模型 + 策略 + 算法

步骤：

得到一个有限的训练数据的集合
确定包含所有可能的模型的假设空间（学习模型的集合）
确定模型选择的准则（学习的策略）
实现求解最优模型的算法（学习的算法）
通过学习方法选择最优模型
利用学习的最优模型对心的数据进行预测或分析

统计学习包括监督学习、非监督学习、半监督学习和强化学习

监督学习

监督学习：利用训练数据集学习一个模型，再用模型对测试样本集进行预测

模型：概率函数或者非概率函数（决策函数）

决策函数（之假设空间$\mathcal F$）:

$\mathcal F=\{f\mid Y=f_\theta(x),\theta\in\mathbf R^n\}$

条件概率函数（之假设空间$\mathcal F$）:

$\mathcal F=\{P\mid P_\theta(Y\mid X),\theta\in\mathbf R^n\}$

策略：误差最小化（经验风险/结构风险最优化(最小化)问题）（结构风险 = 经验风险 + $\lambda*J(f)$）

误差用损失函数（loss function）（非负实值函数）表示：$L(Y,f(X))$

期望损失/期望风险（$=$损失函数的期望）（输入、输出$(X,Y)$为随机变量，遵循联合分布$P(X,Y)$（未知）→所以期望风险无法直接计算，需要‘学习’）：

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

经验损失/经验风险（即给定训练数据集$T={(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)}$，模型$f(X)$关于$T$的平均损失）：

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

根据大数定律，当样本容量$N$趋于无穷时，经验风险$R_{emp}(f)$趋于期望风险$R_{exp}(f)$

当样本容量足够大时，可直接用经验风险最小化作为策略：

例如极大似然估计： 当模型为条件概率分布，损失函数为对数损失函数时，经验风险最小化等价于极大似然估计

当样本容量很小时，只利用经验风险最小化作为策略，容易出现过拟合(over-fitting)现象，所以提出结构风险最小化(structural risk minimization, SRM)为策略

结构风险（$J(f)$为模型的复杂度(越复杂越大)，是定义在假设空间$\mathcal F$上的泛函，是对复杂模型的惩罚）：

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

贝叶斯估计中的最大后验概率估计就是结构风险最小化的例子：当模型为条件概率分布、损失函数是对数损失函数、模型复杂度由模型的先验概率表示时，结构风险最小化等价于最大后验概率估计

算法：求解最优解的具体计算方法

如果有显式解析解，最优化问题比较简单

但通常解析解不存在，就需要用数值计算的方法求解

如何保证找到全局最优解，并使求解过程非常高效，是一个重要问题

训练误差：模型在训练数据上的误差（本质上不重要） 测试误差：模型在测试数据上的误差（非常重要）→→ 测试误差小的方法具有更好的预测能力，是更有效的方法

过拟合：选择的模型所含参数过多（比真模型多）：

一味追求缩小测试误差，所选模型复杂度（如参数个数）往往比真模型高（过拟合），以致于出现对已知数据预测很好，对未知数据预测很差的现象。→ 模型选择旨在避免过拟合并提高模型的预测能力

以多项式拟合为例：

给定一个训练集$T$
假设数据由$M$次多项式函数$f$生成（目标 → 选择一个对已知数据和未知数据都有很好预测能力的函数（模型））
解决办法：
- 首先确定模型的复杂度（即确定多项式的次数$M$）
- 再按经验风险最小化的策略，求解参数（即多项式的系数）
  - 可用最小二乘法求得拟合多项式系数的唯一解（简单的最优化问题）
- 结果分析：
  - $M = 0$ 时，多项式曲线是一个常数，数据拟合效果很差
  - $M = 1$ 时，多项式曲线是一条直线，效果也很差
  - $M = 3$ 时，曲线对训练数据拟合效果足够好，模型也比较简单，是比较好的选择
  - $M = 9$ 时，曲线通过每个数据点，训练误差为0，但是对未知数据预测能力不好，过拟合，不可取

多项式拟合可以看到：

随着多项式次数（模型复杂度）增加，训练误差会减小，直至趋于0
但测试误差会随着多项式次数的增加，先减小后增大 → 最终目的是使测试误差达到最小：为此要选择合适的多项式次数（对一般模型选择也成立）

两种常用的模型选择方法：正则化和交叉验证

正则化(regularization)：是结构风险最小化策略中的罚项(penalty term 或叫正则化项regularizer)$\lambda J(f)$，一般是模型复杂度的单调递增函数，比如可以是模型参数向量的范数

正则化的作用：选择经验风险和模型复杂度同时较小的模型
从贝叶斯估计角度看：正则化项 → 模型的先验概率（模型复杂，先验概率较小）

交叉验证(cross validation)：（基本思想：重复使用数据）把给定的数据随机切分为训练集~~、验证集~~和测试集，在此基础上反复进行训练、测试以及模型选择

例如，数据随机分为两部分，70%为训练集，30%为测试集
然后用训练集在各种条件下（例如，不同参数个数）训练模型，从而得到不同的模型
再在测试集上评价各个模型的测试误差，选出误差最小的模型

泛化能力

泛化能力/推广能力（generalization ability）：指由该方法学习到的模型对未知数据的预测能力

泛化误差（generalization error）：如果学到的模型是$\hat f$，则用这个模型对未知数据预测的误差即为泛化误差（其实就是模型的期望风险）

$R_{exp}(\hat f)=E_P[L(Y,\hat f(X))]=\int_{x*y} L(y,\hat f(x))P(x,y)dxdy$

泛化误差上界(generalization error bound)：泛化能力分析往往是通过研究泛化误差的概率上界进行的.

它是样本容量的函数，当样本容量增加时，泛化上界趋于0
它是假设空间容量(capacity)的函数，假设空间容量越大，模型就越难学，泛化误差上界就越大

定理（泛化误差上界） 对二类分类问题，当假设空间是有限个函数的集合$\mathcal F={f_1,f_2,\cdots,f_d}$时，对任意一个函数$f\in\mathcal F$，至少以概率$1-\delta$，以下不等式成立（即以下不等式成立的概率大于等于$1-\delta$）：
$R(f)\le\hat R(f)+\varepsilon (d,N,\delta)$
其中， $ \varepsilon(d,N,\delta)=\sqrt{\frac{1}{2N}(\log d +\log\frac{1}{\delta})}$

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

算法/统计（监督）学习方法

分为生成方法（generative approach）（得到的模型称为生成模型）和判别方法（discriminative approach）（得到的模型称为判别模型）

生成方法：数据由联合概率分布$P(X,Y)$学习，求出条件概率分布$P(Y\mid X)$作为预测模型，即得生成模型：

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

模型表示了给定输入$X$产生输出$Y$得生成关系；
典型的生成模型：朴素贝叶斯法和隐马尔可夫模型；
此法可还原出联合概率分布$P(X,Y)$，而判别方法则不能；
学习收敛速度更快：当样本容量增加时，学到的模型可以更快地收敛于真实模型；
当存在隐变量时，此法仍可用，但判别方法不能用.

判别方法：数据直接学习决策函数$f(X)$或者条件概率分布$P(Y\mid X)$作为预测的模型，即为判别模型。

关心的是对给定的输入$X$，应该预测什么样的输出$Y$；
典型的判别模型：$k$邻近法、感知机、决策树、逻辑斯蒂回归模型、最大熵模型、支持向量机、提升方法和条件随机场等；
学习准确率更高；
可以对数据进行各种程度上地抽象、定义特征并使用特征，因此可以简化学习问题.

分类问题

分类问题：当输出变量$Y$取有限个离散值时（无论输入变量是离散还是连续），预测问题便成为分类问题.

分类问题地模型称为分类器（classifier）.
分类器对输入进行输出的预测，称为分类，可能地输出称为类，类别为多个时，称为多类分类问题.
过程：从已知的训练集学习一个分类器，再用分类器对新的数据进行分类.
评价分类器性能的指标一般是分类准确率（accuracy）：对给定的测试数据集，分类器正确分类的样本数与总样本数之比。也就是损失函数是0-1损失时测试数据集上的准确率
二类分类问题常用的评价指标是精确率（precision）和召回率（recall）。通常以关注的类为正类，其他类为负类：
- $TP$——将正类预测为正类数；
- $FN$——将正类预测为负类数；
- $FP$——将负类预测为正类数；
- $TN$——将负类预测为负类数；
- 精确率定义为
- 召回率定义为
- $F_1$值，为精确率和召回率的调和均值，即
- 精准率和召回率都高时，$F_1$值也会高
可用于分类的统计学习方法：$k$邻近法、感知机、朴素贝叶斯法、决策树、决策列表、逻辑斯蒂回归模型、支持向量机、提升方法、贝叶斯网络、神经网络、Winnow等.
应用举例：
- 银行业务，可以构建客户分类模型，对客户按照贷款风险的大小进行分类；
- 网络安全，可以利用日志数据的分类对非法入侵进行检测；
- 图像处理，可以用分类检测图像中是否有人脸出现
- 手写识别，可以用分类识别手写的数字；
- 互联网搜索，网页的分类可以帮助网页的抓取、索引和排序

标注问题

标注问题（tagging）：是分类问题的一个推广，又是更复杂的结构预测（structure prediction）问题的简单形式。其输入是一个观测序列，输出是一个标记序列或状态序列

评价标准同分类问题;
常用的统计学习方法：隐马尔可夫模型、条件随机场；
在信息抽取、自然语言处理等领域被广泛应用，是这些领域的基本问题；
应用举例：如对英文句子中的名词短语进行标记。

回归问题

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

常用的损失函数为平方损失函数，可以由最小二乘法求解。
应用举例：市场趋势预测、产品质量管理、客户满意度调查、投资风险分析

清心斋 我心素已闲，清川澹如此。

统计学习方法笔记

第一章