机器学习-1-概论

统计学习

学习：如果一个系统能够通过执行某个过程改进它的性能，就是学习。
分类：监督学习、非监督学习、半监督学习和强化学习。
三要素：模型、策略和算法。

统计学习的步骤：

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

监督学习

学习一个模型，使模型能够对任意给定的输入，对其相应的输出作出一个好的预测。

输入空间：输入的所有可能取值的集合。
输出空间：输出的所有可能取值的集合。
特征空间：特征向量存在的空间。有时输入空间与特征空间相同，有时不同，需要将输入空间映射到特征空间。
假设空间：输入空间到输出空间的映射模型的集合，假设空间的确定意味着学习范围的确定，学习的目的就是找到最好的模型。

回归问题：输入变量与输出变量均为连续变量。
分类问题：输出变量为有限个离散变量。
标注问题：输入变量与输出变量均为变量序列。

联合概率分布：监督学习假设输入与输出的随机变量$X$和$Y$遵循联合概率分布$P(X,Y)$。在学习过程中，假定该这一联合概率分布存在，但对学习系统来说，联合概率分布的具体定义是未知的。训练数据和测试数据被看做是依联合概率分布$P(X,Y)$独立同分布产生的。

学习三要素

一、模型

模型就是所要学习的条件概率分布或决策函数。模型的假设空间包含所有可能的条件概率分布或决策函数。

决策函数：

$\mathcal{F}=\left\{f | Y=f_{\theta}(X), \theta \in \mathbf{R}^{n}\right\}$

条件概率分布：

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

由决策函数表示的模型为非概率模型，由条件概率表示的模型为概率模型。

二、策略

损失函数：度量模型一次预测的好坏。常见损失函数有以下几种：

0-1函数函数： $L(Y, f(X))=\left\{\begin{array}{ll}{1,} & {Y \neq f(X)} \\ {0,} & {Y=f(X)}\end{array}\right.$
平方损失函数： $L(Y, f(X))=(Y-f(X))^{2}$
绝对损失函数： $L(Y, f(X))=|Y-f(X)|$
对数损失函数： $L(Y, P(Y | X))=-\log P(Y | X)$ 损失函数值越小，模型就越好。

风险函数（期望损失）：度量平均意义下模型预测的好坏。由于模型的输入、输出$(X,Y)$是随机变量，遵循联合分布$P(X, Y)$，所以损失函数的期望是：

$R_{\mathrm{exp}}(f)=E_{p}[L(Y, f(X))]=\int_{\mathrm{x*y}} L(y, f(x)) P(x, y) \mathrm{d} x \mathrm{d} y$

这是理论上模型$f(X)$关于联合分布$P(X, Y)$的平均意义下的损失。学习的目的就是选择期望风险最小的模型，但联合分布$P(X, Y)$未知，$R_{\mathrm{exp}}(f)$不能直接计算。

经验风险（经验损失）：给定$N$个样本的训练集，模型$f(X)$关于训练数据集的平均损失称为经验损失：

$R_{\mathrm{emp}}(f)=\frac{1}{N} \sum_{i=1}^{N} L\left(y_{i}, f\left(x_{i}\right)\right)$

期望风险$R_{\mathrm{exp}}(f)$是模型关于联合分布的期望损失，经验风险$R_{\mathrm{emp}}(f)$是模型关于训练集的平均损失。根据大数定律，当样本容量$N$趋于无穷时，经验风险$R_{\mathrm{emp}}(f)$趋于期望风险$R_{\mathrm{exp}}(f)$，所以很自然的想法是用经验风险估计期望风险。但在样本数比较小的时候，需要引入结构风险对经验风险进行矫正。

经验风险最小化和结构风险最小化
经验风险最小化认为经验风险最小的模型就是最优的模型，优化目标为：

$\min _{f \in \mathcal{F}} \frac{1}{N} \sum_{i=1}^{N} L\left(y_{i}, f\left(x_{i}\right)\right)$

当样本量足够大时，经验风险最小化能保证有很好的学习效果。极大似然估计就是经验风险最小化的一个例子。当模型是条件概率分布，损失函数是对数损失函数时，经验风险最小化就等价于极大似然估计。

但样本容量很小时，经验风险最小化最小化会产生过拟合现象。

结构风险最小化是为了防止过拟合而提出来的策略，其在经验风险上加上表示模型复杂度的正则化项。

$R_{\mathrm{srm}}(f)=\frac{1}{N} \sum_{i=1}^{N} L\left(y_{i}, f\left(x_{i}\right)\right)+\lambda J(f)$

其中$J(f)$为模型的复杂度，是定义在假设空间$\mathcal{F}$上的泛函。模型$f$越复杂，复杂度$J(f)$就越大，反之模型$f$越简单，复杂度$J(f)$就越小。复杂度表示了对复杂模型的惩罚。$\lambda \ge 0$是系数，用以权衡经验风险和模型复杂度，结构风险小需要经验风险与模型复杂度同时小，结构风险小的模型往往对训练数据和未知的测试数据都有较好的预测。

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

结构风险最小化的策略认为结构风险最小的模型是最优的模型。

$\min _{f \in \mathcal{F}} \frac{1}{N} \sum_{i=1}^{N} L\left(y_{i}, f\left(x_{i}\right)\right)+\lambda J(f)$

三、算法

算法是指学习模型的具体计算方法。统计学习基于训练数据集，根据学习策略，从假设空间中选择最优模型，最后需要选择合适的算法求解最优化问题。

模型评估与模型选择

假设学习到的模型是$Y=\hat{f}(X)$。
训练误差是模型$Y=\hat{f}(X)$关于训练数据集的平均损失：

$R_{\mathrm{emp}}(\hat{f})=\frac{1}{N} \sum_{i=1}^{N} L\left(y_{i}, \hat{f}\left(x_{i}\right)\right)$

测试误差是模型$Y=\hat{f}(X)$关于测试数据集的平均损失：

$e_{\mathrm{test}}=\frac{1}{N^{\prime}} \sum_{i=1}^{N^{\prime}} L\left(y_{i}, \hat{f}\left(x_{i}\right)\right)$

泛化能力：学习方法对未知数据的预测能力。
过拟合：随着模型的复杂度比真实模型更高，所选择的模型包含的参数过多，模型对已知数据预测得很好，但对未知数据预测很差。

模型选择旨在避免过拟合并提高模型的预测能力。

下图描述了训练误差和测试误差与模型的复杂度之间的关系。当模型的复杂度增大时，训练误差会逐渐减小并趋向于0；而测试误差会先减小，达到最小值后又增大。当选择的模型复杂度过大时，过拟合现象就会发生。因此需要选择适当的模型，以达到测试误差最小的目的。常用的模型选择方法：正则化与交叉验证。
mark

模型选择之正则化

正则化是结构风险最小化策略的实现，是在经验风险上加一个正则化项，正则化项一般是模型复杂度的单调递增函数，模型越复杂，正则化值就越大。通常，正则化项是模型参数向量的范数。一般形式为：

$\min _{f \in \mathcal{F}} \frac{1}{N} \sum_{i=1}^{N} L\left(y_{i}, f\left(x_{i}\right)\right)+\lambda J(f)$

$L_2$正则：

$L(w)=\frac{1}{N} \sum_{i=1}^{N}\left(f\left(x_{i} ; w\right)-y_{i}\right)^{2}+\frac{\lambda}{2}\|w\|^{2}$

$L_1$正则：

$L(w)=\frac{1}{N} \sum_{i=1}^{N}\left(f\left(x_{i} ; w\right)-y_{i}\right)^{2}+\lambda\|w\|_{1}$

第一项的经验风险较小的模型可能较复杂，这时第二项的模型复杂度会较大。正则化的作用是选择经验风险与模型复杂度同时较小的模型。

正则化符合奥卡姆原理：在所有可能选择的模型中，能够很好地解释已知数据并且十分简单才是最好的模型，也就是应该选择的模型。

先验：从贝叶斯估计的角度来看，正则化项对应于模型的先验概率，通常较复杂的模型有较大的先验概率，简单的模型有较小的先验概率。

模型选择之交叉验证

简单交叉验证：首先随机地将数据分为两部分，一部分作为训练集(70%)，另一部分作为测试集(30%)；然后用训练集在各种条件下训练模型，从而得到不同的模型；在测试集上评价各个模型的测试误差，选出测试误差最小的模型。
$S$折交叉验证：首先随机地将已给数据切分为$S$个互不相交的大小相同的子集；然后利用$S-1$个子集的数据训练模型，利用余下的子集测试模型；将这一过程对可能的$S$中选择重复进行；最后选出$S$次评测中平均测试误差最小的模型。
留一交叉验证：$S$折交叉验证的特殊情形是$S=N$，称为留一交叉验证，往往在数据缺乏的情况下使用。

泛化能力

泛化能力：学习到的模型对未知数据的预测能力。
泛化误差：如果学习的模型是$\hat{f}$，那么用这个模型对未知数据预测的误差即为泛化误差：

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

泛化误差反映了学习方法的泛化能力，如果一种方法学习的模型比另一种方法学习的模型有更小的泛化误差，那么这种方法就更有效。泛化误差就是所学习到的模型的期望风险。

泛化误差上界
通常通过比较两种学习方法的泛化误差上界的大小来比较它们的优劣。泛化误差上界的性质：它是样本容量的函数，当样本容量增加时，泛化上界趋于0；它是假设空间容量的函数，假设空间容量越大，模型就越难学，泛化误差上界就越大。

关于$f$的期望风险和经验风险如下：

$R(f)=E[L(Y, f(X))]$ $\hat{R}(f)=\frac{1}{N} \sum_{i=1}^{N} L\left(y_{i}, f\left(x_{i}\right)\right)$

经验风险最小化函数是：

$f_{N}=\arg \min _{f \in \mathcal{F}} \hat{R}(f)$

人们更关心$f_{N}$的泛化能力：

$R\left(f_{N}\right)=E\left[L\left(Y, f_{N}(X)\right)\right]$

对于二分类问题，当假设空间是有限个函数的集合$\mathcal{F}=\left\{f_{1}, f_{2}, \cdots, f_{d}\right\}$，泛化误差上界为：

$R(f) \leqslant \hat{R}(f)+\varepsilon(d, N, \delta)$

其中

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

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

生成模型与判别模型

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

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

这样的方法之所以称为生成方法，是因为模型表示了给定输入$X$产生输出$Y$的生成关系。常见的有朴素贝叶斯和隐马尔科夫模型。

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

生成方法的特点：生成方法可以还原出联合概率分布$P(X,Y)$，而判别方法则不能；生成方法的学习收敛速度更快，即当样本容量增加时，学到的模型可以更快地收敛于真实模型；当存在隐变量时，仍可以用生成方法学习，此时判别方法就不能用。

判别方法的特点：判别方法直接学习的是条件概率$P(Y|X)$或决策函数$f(X)$，直接面向预测，往往学习的准确率更高；由于直接学习$P(Y|X)$或$f(X)$，可以对数据进行各种程度上的抽象、定义特征并使用特征，因此可以简化学习问题。

分类问题

在监督学习中，当输出变量$Y$取有限个离散值时，则为分类问题。这时，输入变量$X$可以是离散的，也可以是连续的。

准确率：分类器正确分类的样本数与总样本数之比。

$A = \frac{TP+TN}{TP+TN+FP+FN}$

精确率：分类正确的正样本个数占分类器判定为正样本的样本个数的比例。

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

召回率：分类正确的正样本个数占真正的正样本个数的比例。

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

$F_1$值：精确率和召回率的调和均值。

${\frac{2}{F_{1}}=\frac{1}{P}+\frac{1}{R}}$ ${F_{1}=\frac{2 T P}{2 T P+F P+F N}}$

常见分类方法：$k$近邻法、感知机、朴素贝叶斯、决策树、决策列表、逻辑斯蒂回归模型、支持向量机、提升方法、贝叶斯网络、神经网络。

标注问题

标注问题是分类问题的一个推广。标注问题的输入是一个观测序列，输出是一个标记序列或状态序列。标注问题的目的在于学习一个模型，使它能够对观测序列给出标记序列作为预测。

标注问题的评价指标和分类指标一样，常用的有标注准确率、精确率和召回率。

常用的标注方法有：隐马尔科夫模型、条件随机场。

回归问题

回归用于预测输入变量和输出变量之间的关系。回归问题的学习等价于函数拟合：选择一条函数曲线使其很好地拟合已知数据且很好地预测位置数据。

回归学习最常用的损失函数是平方损失函数，可以由最小二乘法求解。

参考文献
统计学习方法. 李航