《统计学习方法》学习笔记之第一章

统计学习方法的学习笔记：第一章

第一节统计学习的定义与分类

统计学习的概念

统计学习的分类

第二节统计学习方法的基本分类

监督学习

无监督学习

强化学习

第三节统计学习方法三要素

模型

策略

第四节模型评估与模型选择

训练误差与测试误差

过拟合与模型选择

第五节正则化和交叉验证

正则化：实现结构风险最小化策略

交叉验证

第六节泛化能力

泛化误差

泛化误差上界

二分类问题

第七节生成模型与判别模型

生成模型和判别模型

生成模型VS判别模型

第八节监督学习的应用

分类问题

标注问题

回归问题

第一节统计学习的定义与分类

统计学习的概念

以计算机和网络为平台
以数据为研究对象
以预测和分析数据为目的
以方法为中心
是多领域交叉的学科

定义：

统计学习(Statistical Machine Learning)是关于计算机基于数据后见概率统计模型并运用模型对数据进行预测与分析的一门学科。

统计学习方法的具体步骤：

得到一个有限的训练数据集合
确定学习模型的集合(模型)
确定模型选择的准则(策略)
实现求解最优模型的算法(算法)
通过学习方法选择最优模型
利用学习的最有名模型对新数据进行预测和分析

统计学习的分类

第二节统计学习方法的基本分类

监督学习

定义：监督学习(Supervised Learning)是指从标注数据中学习预测模型的机器学习问题，其本质是学习输入到输出的映射的统计规律。

输入空间(Input Space):输入的所有可能取值的集合
实例(Instance):每一个具体的输入，通常由特征向量(Feature Vector)表示
特征空间(Feature Space):所有特征向量存在的空间
输出空间(Output Space):输出的所有可能取值的集合

例：核技巧

输入空间： $R^2$ ; 实例： $x=(x^{(1)},x^{2)})^T$

$\phi (x):R^2\rightarrow {H};$ $\phi{(x)}=((x^{(1)})^2,\sqrt{2}x^{(1)}x^{(2)},(x^{(2)})^2)^T$

根据变量类型不同：

-输入变量与输出变量均为连续变量的预测问题(回归问题)

-输出变量为有限个离散变量的预测问题(分类问题)

-输入变量与输出变量均为变量序列的预测问题(标注问题)

符号表示

输入变量：X;输入变量的取值：x
输出变量：Y;输出变量的取值：y
输入实例x的特征向量表示：

$x=(x^{(1)},x^{(2)},...,x^{(j)},...,x^{(n)})^T$

以 $x_i$ 表示多个输入变量中的第i个变量：

$x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(j)},...,x_i^{(n)})^T$

样本容量为N的训练集：

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

监督学习的基本假设：X和Y具有联合概率分布P(X,Y)
监督学习的目的：学习一个输入到输出的映射，这一映射以模型表示
模型的形式：条件概率分布P(Y|X)或决策函数Y=f(X)
假设空间(Hypothesis Space):所有这些可能模型的集合

对具体的输入进行相应的输出与测试，表达为：

P(y|x)或y=f(x)

无监督学习

定义：无监督学习(Unsupervised Learning)是指从无标注数据中学习预测模型的机器学习问题，其本质是学习数据中的统计规律或潜在结构。

监督学习VS无监督学习

输入空间： $\chi$
隐式结构空间： $Z$
模型：函数 $z=g(x)$ ,条件概率分明 $P(z|x)$ 或条件概率分布 $P(x|z)$
假设空间(Hypothesis Space)：所有这些可能模型的集合
目的：选出在给定评价标准下的最优模型
样本容量为N的训练集：

$U={x_1,x_2,...,x_N}$

强化学习

第三节统计学习方法三要素

统计学习方法=模型+策略+算法

模型

定义：假设空间(Hypothesis Space):所有可能的条件概率分布或决策函数，用F表示

若定义为决策函数的集合： $F=\{f|Y=f(X)\}$
F是有一个参数向量决定的函数族构成： $F=\{f|Y=f_\theta(X),\theta\epsilon R^n\}$
参数空间： $\theta = \{\theta|\theta\epsilon R^n\}$

例：线性回归

实例： $x=(x^{(1)},x^{(2)},...,x^{(n)})^T$

决策函数： $f(x)=w^{(1)}x^{(1)}+w^{(2)}x^{(2)}+...+w^{(n)}x^{(n)}+b$

向量形式： $f(x)=w\cdot x+b$ ,其中， $w=(W^{(1)},w^{(2)},...,w^{(n)})$

若定义为条件概率的集合： $F={P|P(Y|X)}$

F由一个参数向量决定的条件概率分布族构成：

$F=\{P|P_\theta(Y|X),\theta\epsilon R^n\}$

例：Logistic回归

实例： $x=(x^{(1)},x^{(2)},...,x^{(n)})^T$

条件概率分布：

$\begin{Bmatrix}P(Y=1|x)=\frac{\exp(w\cdot x+b)}{1+\exp(w \cdot x+b)} \\ P(Y=0|x)=\frac{1}{1+\exp(w \cdot x+b)} \end{matrix}$

策略

损失函数：度量模型一次预测的好坏，记作 $L{(Y, f(x))}$

风险函数：度量平均意义下模型预测的好坏

$R_{exp}(f) = E_p{[L(Y, f(x))]} \\$

经验风险：模型 $f(X)$ 关于训练集的平均损失

$\frac{1}{N}\sum\limits_{i=1}^NL(y_i, f(x_i))$

其中，训练集 $T = \{(x_1, y_1), (x_2, y_2),...,(x_N, y_N)\}$

四种常见的损失函数

0-1损失函数（分类问题）
平方损失函数（回归问题）
绝对损失函数（回归问题）
对数损失函数（概率模型）

经验风险最小化：

$\min\limits_{ f\epsilon F}\frac{1}{N}L(y_i, f(x_i))$

结构风险：

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

结构风险最小化：

$\min\limits_{f\epsilon F}\frac{1}{N}L(y_i, f(x_i)) + \lambda J(f))$

根据大数定律，当样本容量N->正无穷时，经验风险趋近于风险函数

结构风险在经验风险的基础上加了正则项（针对模型的复杂度），平衡了经验风险和模型的复杂度

选取目标函数：经验风险函数或者结构风险函数

最优模型：不存在显示解析解的情况下，可以使用梯度下降的数值运算方法

第四节模型评估与模型选择

训练误差与测试误差

1. 训练误差

学习到的模型: $Y=\hat f(X)$
训练集（Training Set）:

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

训练误差（Training Error）：

$R_{emp}(\hat f) = \frac{1}{N}\sum\limits_{i=1}^NL(y_i, \hat f(x_i))$

2. 测试误差

学习到的模型: $Y=\hat f(X)$
训练集（Test Set）:

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

训练误差（Test Error）：

$e_test = \frac{1}{{N}'} \sum\limits_{i'=1}^{N'}L(y_i',\hat f(x_{i'}))$

误差率(Error Rate):

$e_test = \frac{1}{N'}\sum\limits_{i'=1}^{N'}I(y_i \neq \hat f(x_{i'}))$

准确率(Accuracy):

$r_test = \frac{1}{N'}\sum\limits_{i'=1}^{N'}I(y_i=\hat f(x_{i'}))$

注：

$r_{test} + e_{test} = 1$

M次多项式：

$f_M(x, w)=w_0+w_1x+w_2x^2+...+w_Mx^M = \sum\limits_{j=0}^M w_jx^j$

经验风险：

$L(w) = \frac{1}{2}\sum\limits_{i=1}^N(f_M(x_i, w)-y_i)^2$

带入多项式：

$L(w) = \frac{1}{2}\sum\limits_{i=1}^N(\sum\limits_{j=0}^Mw_jx_i^j-y_i)^2$

通过最小二乘法求解参数。

过拟合与模型选择

过拟合（Over-Fitting）：学习所的模型包含参数过多，出现对已知数据预测很好，但对位置数据预测预测很差的现象。

第五节正则化和交叉验证

正则化：实现结构风险最小化策略

一般形式：

$\min\limits_{f\epsilon F}\frac{1}{N}\sum\limits_{i=1}^NL(y_i,f(x_i)) + \lambda J(f)$

经验风险：

$\frac{1}{N}\sum\limits_{i=1}^NL(y_i,f(x_i))$

正则化项：

$\lambda J(f)$

其中， $\lambda$ 权衡经验风险和模型复杂度

最常见的两种正则化项

$L_1$ 范数：

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

其中， $||w||_1=\sum\limits_j|w_j|$

使某些参数为零，可以起到特征筛选的作用，稀疏模型，非零参数个数很少

$L_2$ 范数：

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

其中， $||w||_2=\sqrt{\sum\limits_jw_j^2}, ||w||_2^2 = \sum\limits_jw_j^2$

参数可以无限接近于零，使得模型越来越简单，防止过拟合。

奥卡姆剃刀原理

在模型选择时，选择所有可能模型中，能很好解释已知数据并且十分简单的模型。

交叉验证

数据充足的情况下：

训练集(Training Set):用以训练模型
验证集(Validation Set):用以选择模型
测试集(Test Set):用以最终对学习方法的评估

数据不充足的情况下：

简单交叉验证：随机将数据分为两部分，即训练集和测试集
S折交叉验证：随机将数据分为S个互不相交、大小相同的子集，其中以S-1个子集作为训练集，余下的子集作为测试集
留一交叉验证：S折交叉验证的特殊情形，S=N，在数据非常缺乏的情况下使用

第六节泛化能力

泛化误差

若所学习到的模型是 $\hat f$ ,那么这个模型对未知数据预测的误差即为泛化误差(Generalization Error):

$R_{exp}(\hat f)=E_p{[Y, \hat f(X)]}=\int _{x\times y}L(y, \hat f(x))P(x, y)dxdy$

损失函数的期望值，所求的积分是在全样本上进行的

泛化误差上界

泛化误差上界(Generalization Error Bound)：指泛化误差的概率上界。两种学习方法的优劣，通常通过他们的泛化误差上界进行比较。

性质：

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

假设空间：所有可能的模型

例子：

二分类问题

训练数据集：

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

其中，T是从联合概率分布P(X,Y)独立同分布产生的， $X\epsilon R^n,Y \epsilon \{-1, +1\}$

假设空间：

$F = \{f_1, f_2,...,f_d\}$

其中，d是函数个数

假设 $f\epsilon F$ ,损失函数为0-1损失，

期望风险：

$R(f)=E{[L(Y,f(X))]}$

经验风险：

$\hat R(f) = \frac{1}{N}\sum\limits_{i=1}^NL(y_i,f(x_i))$

经验风险最小化：

$f_N =\arg \min\limits_{f\epsilon F}\hat R(f)$

$f_N$ 的泛化能力：

$R(f_N)=E{[L(Y,f_N(X))]}$

定理(泛化误差上界)：

对于二分类问题，当假设空间是有限个函数的集合 $F = \{f_1, f_2,...,f_d\}$ 时，对于 $\forall f\epsilon F$ ,至少以概率 $1-\delta$ , $0 < \delta < 1$ ,以下不等式成立：

$R(f)\leq \hat R(f)+\varepsilon (d,N,\delta)$

训练误差 $\hat R(f)$ ，泛化误差上界 $\varepsilon (d,N,\delta)$

其中，

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

d为假设空间中函数的个数，N表示i训练集中的样本个数；N趋于无穷大， $R(f)$ 趋于0；当d趋于无穷大时，即假设空间越来越复杂时，泛化误差上界增大。

泛化误差上界定理证明：

Hoeffding不等式(第一版)

设 $X_1,X_2,...X_N$ 是独立随机变量，且 $X_i\epsilon[a_i,b_i],i=1,2,...,N;S_n=\sum\limits_{i=1}^NX_i$ ,则对任意 $t > 0$ ,以下不等式成立：

$P[S_N-E(S_N)\geq t] \leq \exp[-\frac{2t^2}{\sum\limits_{i=1}^N(b_i-a_i)^2}]$

$P[E(S_N)-S_N\geq t] \leq \exp[-\frac{2t^2}{\sum\limits_{i=1}^N(b_i-a_i)^2}]$

Hoeffding不等式(第二版)

设 $X_1,X_2,...X_N$ 是独立随机变量，且 $X_i\epsilon[a_i,b_i],i=1,2,...,N;$ $\overline{X}$ 是 $X_1,X_2,...X_N$ 的经验平均值， $\overline{X}=\frac{1}{N}\sum\limits_{i=1}^NX_i$ ,则对任意 $t > 0$ ,以下不等式成立：

$P[\overline{X}-E(\overline{X})\geq t] \leq \exp[-\frac{2N^2t^2}{\sum\limits_{i=1}^N(b_i-a_i)^2}]$

$P[E(\overline{X})-\overline{X}\geq t] \leq \exp[-\frac{2N^2t^2}{\sum\limits_{i=1}^N(b_i-a_i)^2}]$

第一版：

$P[S_N-E(S_N)\geq t] \leq \exp[-\frac{2t^2}{\sum\limits_{i=1}^N(b_i-a_i)^2}]$

$\Rightarrow P[\frac{S_N}{N}-E(\frac{S_N}{N})\geq \frac{t}{N}] \leq \exp[-\frac{2t^2}{\sum\limits_{i=1}^N(b_i-a_i)^2}]$

令 $\overline{X} = \frac{1}{N}\sum\limits_{i=1}^NX_i$ , $t' = \frac{t}{N}$ ,则 $\overline{X}=\frac{S_N}{N}$ , $t = t'N$ ,从而有，

$P[\overline{X}-E(\overline{X})\geq t'] \leq \exp[-\frac{2(t'N)^2}{\sum\limits_{i=1}^N(b_i-a_i)^2}]$

第二版：

$P[\overline{X}-E(\overline{X})\geq t] \leq \exp[-\frac{2N^2t^2}{\sum\limits_{i=1}^N(b_i-a_i)^2}]$

证明：

$X_i=L(y_i,f(x_i))$ ,则

$\overline{X}$ :

$\overline{X}=\frac{1}{N}\sum\limits_{i=1}^NL(y_i,f(x_i))$

$=\hat R(f)$

对所有的i,

$[a_i, b_i]=[0,1]$

$E(\overline{X})$ :

$E(\overline{X})=E(\frac{1}{N}\sum\limits_{i=1}^NL(y_i, f(x_i)))$

$=\frac{1}{N}\sum\limits_{i=1}^NE(L(y_i,f(x_i)))$

$=\frac{1}{N}\sum\limits_{i=1}^NE(L(Y,f(X)))$

$=E(L(Y,f(X)))$

$=R(f)$

根据Hoeffding不等式，对 $\varepsilon > 0$ ,有：

$P(R(f)-\hat R(f) \geq{\varepsilon}) \leq{\exp(-2N\varepsilon^2)}$

假设空间有限，则，

$P(\exists f\epsilon F:R(f)-\hat R(f) \geq \varepsilon)$

$=P(\bigcup\limits_{f\epsilon F}\{R(f)-\hat R(f)\geq{\varepsilon}\})$

$\leq{\sum\limits_{f\epsilon F}P(R(f)-\hat R(f))\geq\varepsilon}$

$\leq \exp(-2N\varepsilon^2)$

或者等价于， $\forall f \epsilon F,$

$P(R(f)-\hat R(f)<\varepsilon)\geq{1-d\exp(-2N\varepsilon^2)}$

令 $\delta=d \exp(-2N\varepsilon^2)$ ,

$P(R(f)) < \hat R(f)+\varepsilon) \geq 1-\delta$

又，

$\delta=d \exp(-2N\varepsilon^2)\Rightarrow \varepsilon^2=-\frac{1}{2N}\log(\frac{\delta}{d})=\frac{1}{2N}(\log d + \log \frac{1}{\delta})$

因此，对 $\forall f \epsilon F$ ,至少以概率 $1-\delta$ ，以下不等式成立：

$R(f)<\hat R(f)+\varepsilon (d, N, \delta)$

第七节生成模型与判别模型

生成模型和判别模型

生成模型

由数据学习联合概率分布P(X,Y)，然后求出P(Y|X)作为预测模型，即生成模型(Generative Model):

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

典型的生成模型：朴素贝叶斯法、隐马尔可夫模型

注：输入和输出变量要求为随机变量

判别模型

由数据直接学习决策函数f(X)或者条件概率分布P(Y|X)作为预测模型，即判别模型(Discriminative Model)

典型的判别模型：k近邻法、感知机、决策树等

注：不需要输入和输出变量均为随机变量

生成模型VS判别模型

生成模型：

所需数据量较大
可还原联合概率分布P(X,Y)
收敛速度更快
能反映同类数据本身得相似度
隐变量存在时，仍可以使用生成模型

判别模型：

所需样本的数量少于生成模型
可直接面对预测，准确率更高
可见化学习问题
不可以反映数据本身的特性

第八节监督学习的应用

分类问题

分类准确率

对于给定的测试数据集，分类器正确分类的样本数与总样本数之比成为分类准确率：

$r_test = \frac{1}{N'}\sum\limits_{i'=1}^{N'}I(y_{i'}=\hat f(x_{i'}))$

I表示当预测出来的分类与真实的类别一致时为1，否则为0

二分类问题:

真实

预测

正类

负类

正类

负类

精确率：

$P=\frac{TP}{TP+FP}$

召回率：

$R=\frac{TP}{TP+FN}$

F1-Score:

$\frac{2}{F_1} = \frac{1}{P}+\frac{1}{R}$

分类方法：感知机、k近邻、朴素贝叶斯、决策树、Logistic回归

应用：银行业务、网络安全、图像处理、手写识别、互联网搜索

标注问题

训练集：

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

-输入观测序列：

$x_i=(x_i^{(1)},x_i^{(2)},x_i^{(3)},...,x_i^{(n)})^T,i=1,2,...,N$

-输出观测序列：

$y_i=(y_i^{(1)},y_i^{(2)},y_i^{(3)},...,y_i^{(n)})^T,i=1,2,...,N$

学习的模型：

$P(Y^{(1)},Y^{(2)},...,Y^{(n)}|X^{(1)},X^{(2)},...,X^{(n)})$

预测

-新的输入观测序列：

$x_{N+1} = (x_{N+1}^{(1)},x_{N+1}^{(2)},...,x_{N+1}^{(n)})^T$

-预测的输出标记序列：

$y_{N+1} = (y_{N+1}^{(1)},y_{N+1}^{(2)},...,y_{N+1}^{(n)})^T$

方法：

隐马尔可夫模型

条件随机场

应用：

信息抽取

自然语言处理

例：

输入：At Microsoft Research,we have an insatiable curiosity and the desire to create new technology that will help define the computing experience.

输出：At/O Microsoft/B Research/E,we/O have/O an/O insatiable/B curiosity/E and/O the/O desire/BE to/O create/O new/B technology/E that/O will/O help/O define/O the/O computing/B experience/E.