第一节 统计学习

统计学习（statistical learning）是关于计算机基于数据构建概率统计模型并运用模型对数据进行预测与分析的学科。

统计学习研究的对象是数据。

统计学习目的是对数据进行预测与分析。

统计学习的方法是基于数据构建概率统计模型从而对数据进行预测与分析。
统计学习由监督学习（supervised learning）、无监督学习（unsupvised learning）和强化学习（reinforcement learning）等组成。

统计学习三要素：模型（model）、策略（strategy）和算法（algorithm）。

实现统计学习步骤：

1. 得到一个有限的训练数据集合；
2. 确定包含所有可能的模型的假设空间，即学习模型的集合；
3. 确定模型选择的准则。即学习的策略；
4. 实现求解最优模型的算法，即学习的算法；
5. 通过学习方法选择最优的模型；
6. 利用学习的最优模型对新数据进行预测或分析。

第二节 统计学习的分类

基本分类

1. 监督学习
   监督学习是指在标注数据中学习预测模型的机器学习问题。标注数据表示输入输出的对应关系，预测模型对给定的输入产生相应的输出。监督学习的本质是学习输入到输出的映射的统计规律。

2. 无监督学习
   无监督学习是指在无标注数据中学习预测模型的机器学习问题。无标注数据是自然界中得到的数据，预测模型表示数据的类别、转换和概率。无监督学习的本质是学习数据中的统计规律或潜在结构。

3. 强化学习
   强化学习是指智能系统与在环境的连续互动中学习的最优行为策略的机器学习问题问题。假设智能系统与环境的互动基于马尔科夫决策过程，智能系统能观测到的是与环境互动得到的数据预测。强化学习的本质是学习最优的序贯决策。

按模型分类

1. 概率模型与非概率模型
   在监督学习中，概率模型取条件概率分布形式 $P(y|x)$P(y∣x)，非概率模型取函数形式 $y = f(x)$y=f(x) 。在无监督学习中，概率模型是取条件概率分布形式 $P(z|x)$P(z∣x)或$P(x|z)$P(x∣z) ，非概率模型取函数形式 $z = g(x)$z=g(x) 。在监督学习中，概率模型是生成模型，非概率模型是判别模型。

2. 线性模型与非线性模型

3. 参数模型与非参数模型

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

1. 模型

统计学习首先要考虑的就是学习什么样的模型。在监督学习过程中，模型就是所有学习的条件概率分布或决策函数。模型的假设空间包含所有可能的条件概率分布或者决策函数。
假设空间用 $\tag{1.1}\mathscr{F} = \left\{f|Y = f(X)\right\}.$F={f∣Y=f(X)}.(1.1)
其中，$X$X和$Y$Y是定义在输入空间 $\mathscr{X}$X 和输出空间 $\mathscr{Y}$Y 上的变量 。这时 $\mathscr{F}$F 通常是由一个参数向量决定的函数簇：
$\tag{1.2}\mathscr{F} = \left\{f|Y = f_{\theta}(X), \theta \in \mathbf{R}^n\right\}.$F={f∣Y=fθ​(X),θ∈Rn}.(1.2)
参数向量 $\theta$θ 取决于 $n$n 维欧式空间 $\mathbf{R}^n$Rn，称为参数空间。

假设空间也可以定义为条件概率的集合：
$\tag{1.4}\mathscr{F} = \left\{P|P(Y|X)\right\}.$F={P∣P(Y∣X)}.(1.4)
其中，$X$X和和$Y$Y是定义在输入空间 $\mathscr{X}$X 和输出空间 $\mathscr{Y}$Y 上的随机变量。这时$\mathscr{F}$F 通常是由一个参数向量决定的条件概率分布簇：
$\tag{1.5}\mathscr{F} = \left\{P|P_{\theta}(Y|X), \theta\in\mathbf{R}^n\right\}.$F={P∣Pθ​(Y∣X),θ∈Rn}.(1.5)
参数向量$\theta$θ取决于$n$n 维欧式空间 $\mathbf{R}^n$Rn，也称为参数空间。

2. 策略

1. 损失函数和风险函数

损失函数是$f(X)$f(X)和$Y$Y的非负实值函数，记住$L(Y, f(X)).$L(Y,f(X)).

统计学习常用的损失函数有以下几种：

1. 0-1损失函数
   $\tag{1.6}L(Y, f(X)) = \begin{cases} 1, \ Y\neq f(X) \\[3ex] 0, \ Y = f(X) \end{cases}$L(Y,f(X))=⎩⎪⎨⎪⎧​1, Y​=f(X)0, Y=f(X)​(1.6)
2. 平方损失函数
   $\tag{1.7}L(Y, f(X)) = (Y-f(X))^2$L(Y,f(X))=(Y−f(X))2(1.7)
3. 绝对损失函数
   $\tag{1.8}L(Y, f(X)) = |Y-f(X)|$L(Y,f(X))=∣Y−f(X)∣(1.8)
4. 对数损失函数或对数似然损失函数
   $\tag{1.9}L(Y, P(Y|X)) = -\log P(Y|X)$L(Y,P(Y∣X))=−logP(Y∣X)(1.9)
   损失函数值越小，模型越好。由于模型的输入、输出 $(X, Y)$(X,Y) 是随机变量，遵循联合分布 $P(X, Y)$P(X,Y) ，所以损失函数的期望是：
   $\tag{1.10} \begin{aligned} R_{exp}(f) &= E_{P}\left[ L(Y, f(X))\right]\\ &=\int_{\mathscr{X}\times\mathscr{Y}}L(y, f(x))P(x,y)dxdy \end{aligned}$Rexp​(f)​=EP​[L(Y,f(X))]=∫X×Y​L(y,f(x))P(x,y)dxdy​(1.10)
   这是理论上模型 $f(X)$f(X) 关于联合分布 $P(X,Y)$P(X,Y) 的平均意义下的损失，称为风险函数或期望损失。

学习的目标就是选择期望风险最小的模型。由于联合分布 $P(X, Y)$P(X,Y) 是未知的·，$R_{exp}(f)$Rexp​(f) 不能直接计算。实际上，如果知道联合分布 $P(X,Y)$P(X,Y) 也就不需要学习了，直接求出条件概率分布 $P(Y|X)$P(Y∣X) 即可。正是因为不知道联合概率分布，所以我们才需要设计模型去学习。这样一来，一方面期望风险最小最小模型要用到联合分布，另一方面联合分布又是未知的，所以监督学习就成为了一个病态问题。

给定一个训练数据集
$\tag{1.11}T = \left\{(x_1, y_1), \cdots, (x_N, y_N)\right\}$T={(x1​,y1​),⋯,(xN​,yN​)}(1.11)
模型 $f(X)$f(X) 关于训练数据集的平均损失称为经验风险或经验损失，记作 $R_{emp}$Remp​：
$R_{emp}(f) = \frac{1}{N}\sum_{i=1}^{N}L(y_i, f(x_i)) \kern{3cm}$Remp​(f)=N1​i=1∑N​L(yi​,f(xi​))

期望风险$R_{exp}(f)$Rexp​(f)是模型关于联合分布的期望损失，经验风险 $R_{emp}(f)$Remp​(f) 是模型关于训练样本集的平均损失。根据大数定律，当样本容量 $N$N 区域无穷的时候，经验风险函数 $R_{emp}(f)$Remp​(f) 趋于期望风险 $R_{exp}(f)$Rexp​(f) 。

2. 经验风险最小化与结构风险最小化

经验风险最小化
在假设空间、损失函数以及训练数据集确定的情况下，经验风险函数式（1.11）就是确定的。经验风险最小化的策略认为，经验风险最小的模型就是最优的模型。于是：
$\tag{1.12}\min_{f \in \mathscr{F}}\frac{1}{N}\sum_{i=1}^{N}L(y_i, f(x_i))$f∈Fmin​N1​i=1∑N​L(yi​,f(xi​))(1.12)
当样本足够大时，经验风险最小化确实能保证有很好的学习效果。但是，当样本容量很小时，经验风险函数最小化学习的效果就不一定很好，会产生过拟合现象。

结构风险最小化
结构风险最小化（structural risk minimization,SRM）是为了防止过拟合而提出的策略。结构风险最小化等价于正则化。在假设空间、损失函数确定情况下，结构风险定义为：
$\tag{1.13}R_{srm}(f)=\frac{1}{N}\sum_{i=1}^{N}L(y_i, f(x_i))+\lambda J(f)$Rsrm​(f)=N1​i=1∑N​L(yi​,f(xi​))+λJ(f)(1.13)
其中 $J(f)$J(f) 为模型的复杂度，是定义在假设空间 $\mathscr{F}$F 上的泛函。模型 $f$f越复杂，则复杂度 $J(f)$J(f) 就越大。

结构风险最小化认为结构风险最小化的模型是最优的模型。所以求最优的模型就是等价于最优化问题：
$\tag{1.14}\min_{f\in \mathscr{F}}\frac{1}{N} \sum_{i=1}^{N}L(y_i, f(x_i)) + \lambda J(f)$f∈Fmin​N1​i=1∑N​L(yi​,f(xi​))+λJ(f)(1.14)

3.算法

算法是指学习模型的具体计算方法。

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

训练误差与测试误差

当损失函数给定时，基于损失函数的模型的训练误差与模型的测试误差就自然成为学习方法评估的标准。
注意，统计学习方法具体采用的损失函数未必就是评估时使用的损失函数，让两者统一是比较理想的。

假设学习到的模型是 $Y=\hat{f}(X)$Y=f^​(X) ，训练误差是模型 $Y=\hat{f}(X)$Y=f^​(X) 关于训练数据集的平均损失：
$\tag{1.15}R_{emp}(\hat{f}) = \frac{1}{N}\sum_{i=1}^{N}L(y_i, \hat{f}(x_i))(1.18)$Remp​(f^​)=N1​i=1∑N​L(yi​,f^​(xi​))(1.18)(1.15)
其中 $N$N 是训练样本的容量。

测试误差是模型 $Y=\hat{f}(X)$Y=f^​(X) 关于测试数据集的平均损失：
$\tag{1.16}e_{test}(\hat{f}) = \frac{1}{N^{'}}\sum_{i=1}^{N^{'}}L(y_i, \hat{f}(x_i))$etest​(f^​)=N′1​i=1∑N′​L(yi​,f^​(xi​))(1.16)
其中 $N^{'}$N′ 是测试样本的容量。

过拟合和模型选择

当我们可以选择的模型有多个时，我们就要考虑我们所选择的模型与数据实际的“真”模型应该尽可能的接近，但是如果一味追求提高对训练数据集的预测能力，则所选择的模型有可能复杂度很高，这种现象称为过拟合。
过拟合(over-fitting)是指在学习时所选择的模型所包含的参数过多，以致出现这一模型对已知数据预测很好，但对于未知数据预测的很差的现象。

第五节 正则化与交叉验证

正则化

正则化是结构风险最小化策略的实现，是在经验风险上加了一个正则项。
$\tag{1.17}\min_{f\in \mathscr{F}}\frac{1}{N} \sum_{i=1}^{N}L(y_i, f(x_i)) + \lambda J(f)$f∈Fmin​N1​i=1∑N​L(yi​,f(xi​))+λJ(f)(1.17)
其中，第一项是经验风险，第二项是正则化项，$\lambda \geq 0$λ≥0 是调整两者之间关系的系数。

正则化项可以取不同的形式。例如在回归问题中，损失函数是平方损失，正则化项是参数向量的2范数：
$\tag{1.18}L(w) = \frac{1}{N} \sum_{i=1}^{N}(y_i - f(x_i;w))^2 + \lambda ||w||^2$L(w)=N1​i=1∑N​(yi​−f(xi​;w))2+λ∣∣w∣∣2(1.18)
奥卡姆剃刀原理：在所有可能选择的模型当中，能够很好地解释已知数据并且十分简单才是最好的模型。

从贝叶斯的角度考虑，正则化项对应于模型的先验概率。可以假设复杂的模型有较小的先验概率，简单的模型有较大的先验概率。

交叉验证

1. 简单交叉验证
   随机将已知数据分为两部分。
2. $S$S 折交叉验证
   首先随机地将已知数据切分为 $S$S 个互不相交、大小相同的子集；然后利用 $S-1$S−1 个子集的数据训练模型，利用剩下的子集测试模型。将这一过程对可能的 $S$S 种选择重复进行；最后选出 $S$S 次评测中平均测试误差最小的模型。
3. 留一交叉验证
   $S$S 折交叉验证的特殊情形是 $S = N$S=N，称为留一交叉验证。在数据不足的情况下，$N$N 就是数据容量。

第六节 泛化能力

泛化误差

学习方法的泛化能力是指由该方法学习到的模型对位置数据的预测能力，是学习方法本质上重要性质。
如果学到的模型是 $\hat{f}$f^​ ，那么用这个模型对未知数据预测的误差即为泛化能力：
$\tag{1.19} \begin{aligned} R_{exp}(\hat{f}) &= E_{P}\left[ L(Y, \hat{f}(X))\right]\\ &=\int_{\mathscr{X}\times\mathscr{Y}}L(y, \hat{f}(x))P(x,y)dxdy \end{aligned}$Rexp​(f^​)​=EP​[L(Y,f^​(X))]=∫X×Y​L(y,f^​(x))P(x,y)dxdy​(1.19)

泛化误差上界

泛化误差的概率上界简称为泛化误差上界。

泛化误差上界通常具有下面两种性质：

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

如果考虑二分类问题。已知训练数据为$T = \left\{(x_1, y_1), \cdots, (x_N, y_N)\right\}$T={(x1​,y1​),⋯,(xN​,yN​)}
$N$N是样本容量，$T$T 是从联合概率分布 $P(X, Y)$P(X,Y) 独立同分布产生，$X\in R^n, Y\in {1, -1}$X∈Rn,Y∈1,−1。假设空间是函数的有限集合 $\mathscr{F} = \{f_1, \cdots, f_d\}$F={f1​,⋯,fd​}。设 $f$f 是从 $\mathscr{F}$F中选取的函数。损失函数是 0-1 损失。关于 $f$f 的期望风险和经验风险分别是
$\tag{1.20}R(f) = E[L(Y, f(X))]$R(f)=E[L(Y,f(X))](1.20)
$\tag{1.21}\hat{R}(f) = \frac{1}{N}\sum_{i=1}^{N}L(y_i, f(x_i))$R^(f)=N1​i=1∑N​L(yi​,f(xi​))(1.21)
经验风险最小化函数是
$\tag{1.22}f_N = \argmin_{f\in\mathscr{F}}\hat{R}(f)$fN​=f∈Fargmin​R^(f)(1.22)
$f_N$fN​依赖于训练数据集的样本容量 $N$N 。人们更关心的是 $f_N$fN​ 的泛化能力
$\tag{1.23}R(f_N) = E[L(Y, f_N(X))]$R(fN​)=E[L(Y,fN​(X))](1.23)
下面讨论从有限集合$\mathscr{F} = \left\{f_1, \cdots, f_d\right\}$F={f1​,⋯,fd​} 中任意选出函数 $f$f 的泛化能力上界。

定理1.1（泛化误差上界）对二分类问题，当假设空间是有限函数集合 $\mathscr{F} = \left\{f_1, \cdots, f_d\right\}$F={f1​,⋯,fd​} 时，对任意一个函数 $f \in \mathscr{F}$f∈F ,至少以概率 $1-\delta, 0< \delta < 1$1−δ,0<δ<1，以下不等式成立：
$\tag{1.24}R(f) \leq \hat{R}(f) + \varepsilon(d, N, \delta)$R(f)≤R^(f)+ε(d,N,δ)(1.24)其中，
$\tag{1.25}\varepsilon(d, N, \delta) = \sqrt{\frac{1}{2N}(\log d + \log \frac{1}{\delta})}$ε(d,N,δ)=2N1​(logd+logδ1​)​(1.25)

在泛化误差上界中，第一项是训练误差，训练误差越小，泛化误差也越小。第二项 $\varepsilon(d, N, \delta)$ε(d,N,δ) 是 $N$N 的单调递减函数，当 $N$N 趋于无穷时趋于0；同时它也是$\sqrt{\log d}$logd​ 阶的函数，假设空间 $\mathscr{F}$F 包含的函数越多，其值越大。

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

监督学习可以分为生成模型与判别模型。
生成模型是由数据学习联合概率分布 $P(X, Y)$P(X,Y) ，然后求出条件概率分布 $P(Y|X)$P(Y∣X) 作为预测的模型，即生成模型：
$\tag{1.30}P(Y|X) = \frac{P(X, Y)}{P(X)}$P(Y∣X)=P(X)P(X,Y)​(1.30)
这样的方法称为生成方法，是因为模型表示了给定输入 $X$X 产生 $Y$Y 的生成关系。典型的生成模型由朴素贝叶斯和隐马尔科夫模型。

判别方法是由数据直接学习决策函数 $f(X)$f(X) 或者条件概率模型 $P(Y|X)$P(Y∣X) 作为预测的模型，即判别模型。判别模型关心的是对给定的输入 $X$X ，应该预测什么样的输出 $Y$Y 。典型的判别模型包括： $k$k近邻， 感知机，决策树，逻辑斯谛回归模型，最大熵模型，支持向量机，提升方法，条件随机场。

生成方法的特点是：生成方法可以还原出联合概率分布，而判别方法则不可以。生成方法的收敛速度更快，即当样本容量增加时，学到的模型可以更快的收敛于真实模型。