《统计学习方法》读书手札-第一章
Every oak must be an acorn.
一、学习分类
统计学习主要由以下几种组成：
①监督学习（Supervised learning）；
②非监督学习（Unsupervised learning）；
③半监督学习（Semi-supervised learning）；
④强化学习（Reinforcement learning）。
在《统计学习方法》一书中，主要围绕监督学习（Supervised learning）进行。
二、三要素
统计学习方法由如下三要素构成：
①模型（model）；
②策略（strategy）；
③算法（algorithm）。
统计学习方法可以简单的表述成：1
方法 = 模型 + 策略 + 算法
2.1 模型
模型（model）就是所要学习的条件概率分布或决策函数。其中由条件概率表示的模型称为概率模型，而由决策函数表示的模型则称为非概率模型。
模型的本质是一个从输入到输出的映射。给定输入、输出数据的情况下，满足映射关系的模型是非常多的，这些映射关系所组成的集合就称为假设空间(hypothesis space)，而学习的目的则在于从假设空间中寻找到最优的模型。
2.1.1 决策函数
以决策函数的集合定义的假设空间表达式为：
式中：
X——是定义在输入空间上的变量；
Y——是定义在输出空间上的变量。
通常假设空间是由一个n(n ∈ R^n)维的参数向量θ控制的，称为参数空间(parameter space)。
2.1.2 条件概率
以条件概率的集合定义的假设空间表达式为（式中X、Y含义同上）：
2.2 策略
所谓策略是我们从假设空间选取最优模型的学习准则或者学习方法。包含损失函数、风险函数、结构函数。
2.2.1 损失函数
损失函数(loss function)（也称作代价函数(cost function)），用来评估模型单次预测的好坏。它是模型f(x)和输出Y的非负实值函数，记作：L(Y , f(X))。常用损失函数如下：
①0 — 1损失函数(0-1 loss function)
②平方损失函数(quadratic loss function)
③绝对损失函数(absolute loss function)
④对数损失函数(logarithmic loss function) 或 对数似然损失函数(log-likelihood loss function)
2.2.2 风险函数 VS 经验风险
所谓风险函数(Risk Function)也称作期望损失(Expected Loss)，是对损失函数求期望，它是关于联合分布P(X,Y)的期望损失，本质仍然是期望，定义式为：
由上式可知，损失函数L(y,f(x))我们可以自己选择，但要求得模型的风险值，还需要知道输入X和输出Y两个随机变量的联合分布P(X,Y)，而这个联合分布又是未知的，所以直接求解风险函数是不现实的，通常是通过求解经验风险来实现模型评估的。
所谓经验风险(Empirical Risk)也称作经验损失(Empirical Loss)，是对损失函数求平均值，它是关于训练样本集的平均损失，本质是均值，定义式为：
式中(xi,yi)表示第i个训练样本，N则表示训练集中样本总数，由大数定律可知，当训练样本总数N趋近于∞时，经验风险Remp(f)趋近于期望风险Rexp(f)。也即当我们手里有大量训练样本时，可以使用经验风险去估计期望风险，但是现实中往往训练样本数量有限，这个时候再使用经验风险去估计就会出现较大偏差，使得模型准确性较低，这个时候就需要对经验风险进行矫正，结构风险就应运而生了。
2.2.3 过拟合 VS 结构风险
所谓过拟合(Over-fitting) ，是指我们根据已有数据建立的模型过于复杂，以至于该模型在已有数据上表现的非常完美而在新的数据集上却非常差，也即缺乏泛化能力。过拟合现象如下图所示：
上图中黑色曲线是加入了正则化项的较好的拟合模型，而绿色曲线则是过拟合模型，可以看出两个模型中，过拟合模型对已有数据的拟合是相当完美的，成功的区分了每一个红色和蓝色圆点。但是当我们把这个模型用到新的数据集上时，新的样本稍微有点抖动，过拟合模型就会分类错误。对于噪声数据，也会相当敏感。
所谓 结构风险(Structural Risk)是在经验风险的基础上加了一个用来评估模型复杂度的正则化项(Regularizer)也称作罚项(Penalty Term)，用来约束模型的复杂度，其定义为：
图中红色部分即为正则化项或罚项，其中J(f)为模型的复杂度函数，正比于模型复杂度。λ(≥0)为调节系数，用来调节经验风险和模型复杂度。
2.2.4 经验风险最小化 VS 结构风险最小化
顾名思义，经验风险最小化(Empirical Risk Minimization)-简称ERM是对经验风险函数求最小值。因为经验风险正比于损失函数，所以最小化经验风险即是最小化损失，也就是最小化模型的误差或者说最大化模型的精度。按照ERM策略求解模型即是求：
前已述及，ERM策略适合样本容量较大的情况。ERM的一个典型例子是：极大似然估计(Maximum Likelihood Estimation)，它是模型为条件概率分布，损失函数取对数损失的情况。
样本较少时，ERM策略选择出的模型并非是最优的，因为它通常会导致训练模型复杂化（过拟合）。为了控制这种风险，引入了结构风险最小化。
顾名思义，结构风险最小化(Structural Risk Minimization)-简称SRM是对结构函数求最小值。因为结构函数中的正则化项正比于模型复杂度，所以最小化结构风险相当于平衡了模型复杂度和经验风险，使模型泛化能力和准确率均最优。按照SRM策略约束模型即是求：
2.2.5 策略小结
最后，用一张图来简单说明上述概念之间的关系，如下所示：
2.3 算法
所谓算法是指模型具体的计算方法，主要是求解最优化问题的算法。它要解决两个问题：一是高效，二是全局最优。这里先做个引子，后面会有大量篇幅讲解算法。
三、进阶
3.1 再谈模型
3.1.1 训练误差 VS 测试误差
确定了损失函数后，通常就采用基于损失函数的训练误差(Traning Error)和测试误差(Test Error)来评估模型的优劣。顾名思义，前者是基于训练数据集的，而后者是基于测试数据集的。
训练误差定义表达式为：
式中N是训练数据集样本容量。f^(X)为我们学习到的模型。训练误差的大小对判定我们处理的问题是否容易学习得到对应的模型有意义，但也仅限于此，对模型的泛化能力无贡献。测试误差则反映了学习方法对未知的测试数据集的预测能力。
测试误差定义表达式为：
式中N’则是测试数据集样本容量。
3.1.2 模型选择
模型选择(Model Selection)是从假设空间中挑选出最逼近真实模型的假设模型。包含两个方面：一是模型类型（比如多项式模型、正弦模型），二是参数个数（比如二次多项式、三次多项式）。
模型选择的宗旨是在尽量逼近真实模型的同时避免过拟合问题。
模型复杂度、训练误差、测试误差三者的关系图如下所示：
从上图可以明显看出，模型复杂度超过某个值之后，测试误差反而会越来越大，这就是过拟合造成的。
3.1.3 生成模型 VS 判别模型
对于监督学习，其任务就是利用训练数据学习一个模型，其学习方法分成两类：一是生成方法(Generative Approach)，二是判别方法(Discriminative Approach)，对应学习到的模型分别称为生成模型(Generative Model)和判别模型(Discriminative Model)。
生成方法是由训练数据学习联合概率分布P(X,Y)，并藉此求出条件概率分布P(Y|X)作为预测模型的方法。它表示了在给定输入X时，产生输出Y的生成关系，比如：朴素贝叶斯、隐马尔科夫模型。
判别方法则是由训练数据直接学习决策函数f(X)或者条件概率分布P(X,Y)作为预测模型的方法。该方法关心的是给定输入X时，应该预测什么样的输出Y，比如：K近邻法，感知机，决策树等等。
两种模型的优缺点如下：
①生成方法：可还原P(X,Y)，判别方法不可以；收敛快；可用于隐变量模型，判别方法不可以。
②判别方法：可直接得到P(Y|X)或f(X)；准确率更高；简化学习问题。
3.2 泛化
3.2.1 正则化项
正则化是模型选择典型的方法，正则化项可以取不同的形式，以参数向量w为例，正则化项可以取w的N(≥0)范数，符合奥卡姆剃刀(Occam's Razor)原理。
奥卡姆剃刀原理即为：如果关于同一个有许多种理论，每一种都能作出同样准确的预言，那么应该挑选其中使用假定最少的（即最简单的）。
3.2.2 交叉验证
另一种常用的模型选择方法是交叉验证(Cross Validation)，它将给定数据集分成三部分（通常是样本较为充足的情况下，如果样本不足则一般只分成训练和测试数据集）：训练集(Training Set)——用于训练模型、验证集(Validation SET)——用于选择模型、测试集(Test Set)——用于最终对模型评估。其核心思想是重复利用数据，可分为：
①简单交叉验证。对数据集的划分方法如下图（它没有验证集）：
②S折交叉验证(S-fold cross validation)，对数据集的划分如下（应用最广）：
③留一交叉验证(Leave-one-out Cross Validation)。本质上是S折交叉验证中S=N（划分数量等于样本数量，即每个样本作为一个数据集）的情况，通常在数据缺乏时使用。
3.2.3 泛化误差
所谓泛化误差(Generalization Error)是指将学习到的模型f^对未知数据进行预测时的误差，表达式如下：
泛化误差的上界称为泛化误差上界(Generalization Error Bound)，它反比于样本容量（样本容量越大，泛化误差上界越小），正比于假设空间容量（假设空间越大，模型越难学习，泛化误差上界也越大）。一个关于泛化误差上界的定理（二分类问题）如下：
式中等号左端为泛化误差，右端为泛化误差上界（其中第一项为训练误差）,d表示假设空间中可能模型的数目,N为样本容量。上述不等式以至少1-δ的概率成立。
3.3 监督学习
3.3.1 三大问题
监督学习的三大问题包括：分类问题、标注问题、回归问题。分述如下：
①分类问题是监督学习的一个核心问题，该类问题的输出变量Y必须是有限个离散值，输入变量则没有要求。按照输出类别数目可以分成二分类（输出只有两种类型）和多分类（输出类别在两种以上）。利用已有的数据学习到的模型称为分类器，关于分类器我们会在3.3.2节中进一步讲解。
②回归问题是监督学习中另一个核心问题，它与分类问题相对应，它的输出变量Y则是连续型数值，它的本质是函数拟合。按照输入变量个数划分成一元回归（有且仅有一个输入变量）、多元回归（有多个输入变量）。按照输入变量和输出变量的关系又可以分为线性回归（线性关系）和非线性回归（非线性关系）。最常使用的是平方损失函数，可由著名的最小二乘法(Least Squares)求解。
③标注问题也属于监督学习的一个问题，它属于分类问题的一个推广，该类问题的输入时一个观测序列，而输出则是标记序列（或状态序列），标注常用的学习方法有：隐马尔科夫模型和条件随机场。在信息抽取和自然语言处理中用的较多。
3.3.2 分类器指标
评价分类器性能的指标一般是准确率(Accuracy)，定义为：给定测试数据集，正确分类样本数占样本总数比例。二分类问题用的更多的是精确率(Precision)和召回率(Recall)。
精确率定义为：
召回率定义为：
此外还有二者的调和均值F1值：
式中：
TP（也称真阳）——表示正类预测为正类数量；
FN（也称假阴）——表示正类预测为负类数量；
FP（也称假阳）——表示负类预测为正类数量；
TN（也称真阴）——表示负类预测为负类数量；
3.4 本章证明
本章只有一个证明，就是前面3.2.3节中提到的泛化误差上界问题，因为涉及的公式和定理较多，篇幅较长，所以放在文章最后，供有兴趣的同学参考。
3.4.1 Hoeffding’s inequality（霍夫丁不等式）
对n个值域为[ai , bi]的独立随机变量Xi，··· ···，Xn，Hoeffding不等式定义如下：
上面的表达式是用这n个独立随机变量的经验均值表示的，即有：
如果用求和表达式来表示Hoeffding不等式，则有：
其中的Sn表达式为：
备注：关于Hoeffding不等式的证明请参考维基百科链接Hoeffding’s_inequality，在此不赘述。
Hoeffding不等式的本质用大白话说就是抽样计算中，样本容量取多大时，与真实情况的误差能足够小。它反映的是样本容量和这个误差（假设模型和真实模型之间）的数值关系。换在机器学习上来说，就是当我们用训练及验证数据集（抽样样本）找到一个符合要求的模型f后，这个模型在测试以及未来任意可能的数据集（整体）上的表现是否也符合要求。
3.4.2 泛化上界证明
对假设空间F中的任意函数f，记R^(f)为n个独立随机变量L(Y , f(X))的样本均值，R(f)为n个独立随机变量L(Y , f(X))的（总体）期望值。
再设对所有随机变量，其值域[ai , bi] = [0 , 1]，则有(bi - ai)2 = 1，代入图3-11的Hoeffding不等式有：
同时假定假设空间是有限的集合，F = {f1 , f2 , ··· , fd} ，故对假设空间中的所有函数有：
也可以等价为：
再另δ = d·exp(-2nε2)，则有：
即假设与真实模型差异控制在在ε范围内的概率（把握）至少有1 - δ。
式中ε的值可由等式δ = d·exp(-2nε2) = d·e-2nε2，将系数d移至δ侧，然后两边同时取对数有：
所以有：
然后有：
最后有：
证毕！
