本系列笔记，主要是整理统计学习方法的知识点和代码实现各个方法，来加强笔者对各个模型的理解，为今年找到好工作来打下基础。

计划在一个月内更新完这本书的笔记，在此立一个flag: 从2019/2/17开始 到 2019/3/17结束。

在本章中，我们需要了解这些概念：统计学习的定义、研究对象、方法；监督学习；统计学习方法的三要素：模型、策略和算法；模型选择；正则化、交叉验证和学习的泛化能力；生成模型与判别模型；分类问题、标注问题与回归问题。

统计学习的定义：

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

统计学习的研究对象：

    统计学习的对象是数据。它从数据出发，提取数据的特征，抽象出数据的模型，发现数据中的知识，又回到对数据的分析与预测中去。统计学习关于数据的基本假设是同类数据具有一定的统计规律性，这是统计学习的前提。这里的同类数据是指具有某种共同性质的数据。

统计学习的方法：

    统计学习的方法是基于数据构建统计模型从而对数据进行预测与分析，统计学习由监督学习、非监督学习、半监督学习和强化学习等组成。

    我们主要讨论监督学习，这种情况下统计学习的方法可以概括如下：从给定的、有限的、用于学习的训练数据集合出发，假设数据是独立同分布产生的；并且假设要学习的模型属于某个函数的集合，称为假设空间；应用某个评价准则，从假设空间种选取一个最优的模型，使它对已知的数据及未知的测试数据在给定的评价准则下有最优的预测；最优模型的选取由算法实现。这样，统计学习方法包括模型的假设空间、模型选择的准则以及模型学习的算法，称其为统计学习方法的三要素，模型、策略和算法

监督学习：

    在监督学习中，每个具体的输入是一个实列，通常由特征向量表示。这时，所有特征向量存在的空间称为特征空间，特征空间的每一维对应一个特征，模型实际上都是定义在特征空间上的。

    监督学习的模型可以是概率模型或非概率模型，由条件概率分别$P(Y|X)$或决策函数$Y = f(X)$表示，随具体学习方法而定，对具体的输入进行相应的输出预测时，写作$P(y|x)$或$y = f(x)$。

统计学习三要素：

方法=模型+策略+算法

模型：统计学习首要考虑的问题是学习什么样的模型。在监督学习过程中，模型就是所要学习的条件概率分布或决策函数。模型的假设空间包含所有可能的条件概率分布或决策函数。

策略：有了模型的假设空间，统计学习接着需要考虑的是按照什么样的准则学习或者选取最优的模型？为了回答这一问题，首先引入损失函数和风险函数的概念：损失函数度量模型一次预测的好坏，风险函数度量平均意义下模型预测的好坏。

    损失函数和风险函数：监督学习问题是在假设空间$F$中选取模型$f$作为决策函数，对于给定的输入$X$，由$f(X)$给出相应的$Y$，这个输出的预测值$f(X)$与真实值$Y$可能一致也可能不一致，用一个损失函数（loss function）或代价函数（cost function）来度量预测错误的程度。损失函数是$f(X)$和$Y$的非负实值函数，记作$L(Y,f(X))$。

    常用的损失函数有以下几种：

    （1）0-1 损失函数（0-1 loss function）:

$$L(Y,f(X)) = \left\{\begin{matrix}
1, & Y \neq f(X) \\
0, & Y= f(X)
\end{matrix}\right.$$

    （2）平方损失函数（quadratic loss function）:

$$L(Y,f(X)) = (Y – f(X))^2$$

    （3）绝对损失函数（absolute loss function）

$$L(Y,f(X)) = |Y – f(X)|$$

    （4）对数损失函数（logarithmic loss function）或对数似然损失函数（log-likelihood loss function）:

$$L(Y,P(Y|X)) = -logP(Y|X)$$

     损失函数值越小，模型就越好。由于模型的输入、输出$(X,Y)$是随机变量，遵循联合分布$P(X,Y)$，所以损失函数的期望是：

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

这是理论上模型$f(X)$关于联合分布$P(X,Y)$的平均意义下的损失，称为风险函数或期望损失（expected loss）.学习的目标就是选择期望风险最小的模型，由于联合分布$P(X,Y)$是未知的，$R_{exp}(f)$不能直接计算。实际上，如果知道联合分布$P(X,Y)$，可以从联合分布直接求出条件概率分布$P(Y|X)$,也就不需要学习了。那么如何解决这个问题呢？

    给定一个训练数据集：

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

模型$f(X)$关于训练数据集的平均损失称为经验风险或经验损失（empirical loss），记作$R_{emp}$:

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

    期望风险$R_exp(f)$是模型关于联合分布的期望损失，经验风险$R_{emp}(f)$是模型关于训练样本集的平均损失。根据大数定律，当样本容量N趋于无穷时，经验风险$R_{emp}(f)$趋于期望风险R_{exp}(f)。所以，我们使用经验风险估计期望风险。但是，有一个问题：现实中，训练数目有限，用经验风险估计期望风险并不理想。如何解决这个问题呢？既然是经验风险引起的问题，那么我们需要对问题来源做改动：对经验风险进行一定的矫正，这就关系到监督学习的两个基本策略：经验风险最小化和结构风险最小化。

    经验风险最小化（empirical risk minimization,ERM）与结构风险最小化（structural risk minimization, SRM）：

    在假设空间、损失函数以及训练数据集确定的情况下，经验风险最小化的策略认为，经验风险最小的模型就是最优的模型。根据这一策略，按照经验风险最小化求最优模型就是求解最优化问题：

$$\min_{f\in\mathcal{F}}\frac{1}{N}\sum_{i=1}^{N}L(y_i,f(x_i))$$

其中，$\mathcal{F}$是假设空间。

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

$$\arg \min_{\theta}-\frac{1}{N}\sum_{i=1}^{N}logP(y_i|x_i,\theta)$$

$$\arg \max_{\theta}\frac{1}{N}\sum_{i=1}^{N}logP(y_i|x_i,\theta)$$

    但是，当样本容量很小时，经验风险最小化学习的效果就未必很好，会产生过拟合（over-fitting）现象。如何解决这个样本容量小时造成过拟合问题呢？其中一个解决方法（有多个）是使用结构风险最小化来代替经验风险最小化。

    结构风险最小化：是为了防止过拟合而提出来的策略。结构风险最小化等价于正则化（regularization）。结构风险在经验风险上加上表示模型复杂度的正则化项或罚项（penalty term）。在假设空间、损失函数以及训练数据集确定的情况下，结构风险的定义为：

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

其中$J(f)$为模型的复杂度。如，贝叶斯估计中的最大后验概率估计（maximum posterior probability estimation, MAP）就是结构风险最小化的一个例子。当模型是条件概率分布、损失函数是对数损失函数、模型复杂度由模型的先验概率表示时，结构风险最小化就等价于最大后验概率估计：

    在这里简单介绍一下最大后验概率（参考博客），贝叶斯公式：

$$p(\theta | X) = \frac{p(X|\theta)p(\theta)}{p(X)}$$

每一项表示：$$posterior = \frac{likehood\ast prior}{evidence}$$

posterior：通过样本$X$得到参数$\theta$的概率；likehood：通过参数$\theta$得到的样本$X$的概率；

prior：参数$\theta$的先验概率，一般是根据人的先验知识得出来的，像L1，L2正则化就是对参数引入了拉普拉斯先验分布和高斯先验分布；

evidence：样本$X$发生的概率。

对于给定的数据集：极大似然估计：

$$P(X|\theta) = \sum_{x_{1}}^{x_{N}}logP(x_i|\theta)$$

最大后验概率：

$$\arg \max_{\theta}p(\theta|X) =\frac{p(X|\theta)p(\theta)}{p(X)} = \arg \max_{\theta}p(X|\theta)p(\theta) = \arg \max_{\theta}(\sum_{x_{1}}^{x_{N}}logp(x_i|\theta) + logp(\theta))$$

    所以，结构风险最小化的策略认为结构风险最小的模型是最优的模型。所以，求最优的模型，就是求解最优化问题：

$$\min_{f\in\mathcal{F}}\frac{1}{N}\sum_{i=1}^{N}L(y_i,f(x_i)) + \lambda J(f)$$

    算法：算法是指学习模型的具体计算方法。统计学习基于训练数据集，根据学校策略，从假设空间中选择最优模型，最后考虑用什么样的计算方法求解最优模型。

模型选择：

    首先介绍两个概念：训练误差和测试误差，这个比较好理解，训练误差就是指学到的模型对训练数据上使用损失函数来评估，测试误差亦如此。

    当假设空间含有不同复杂度（例如，不同的参数个数）的模型时，就面临模型选择的问题。如果一味追求提高对训练数据的预测能力，所选模型的复杂度则往往会比真模型更高，这种现象称为过拟合（指学习时选择的模型所包含的参数过多）。那怎样选择一个好的模型呢？两种常用的模型选择方法：正则化与交叉验证

正则化和交叉验证：

    正则化：是结构风险最小化策略的实现，是在经验风险上加一个正则化项。正则化项一般是模型复杂度的单调递增函数，模型越复杂，正则化值就越大。比如：正则化项可以是模型参数向量的范数。例如，在回归问题中，损失函数是平方损失，正则化可以是参数向量的$L_2$范数：

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

这里，$||w||$表示参数向量$w$的$L_2$范数。

正则化项也可以是参数向量的$L_1$范数：

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

这里，$||w||_1$$表示参数向量$w$的$L_1$范数。

    正则化的作用是选择经验风险与模型复杂度同时较小的模型。正则化符合奥卡姆剃刀（Occam’s razor）原理：在所有可能选择的模型中，能够很好地解释已知数据并且十分简单才是最好的模型，也就是应该选择的模型。从贝叶斯估计的角度来看，正则化项对应于模型的先验概率。可以假设复杂的模型有较小的先验概率，简单的模型有较大的先验概率。

    交叉验证：如果给定的样本数据充足，进行模型选择的一种简单方法是随机地将数据集切分成三部分，分别是训练集、验证集和测试集。训练集用来训练模型，验证集用于模型的选择，测试集用于对于最后方法的评估。当数据是不充足时，为了选择好的模型，可以采用交叉验证方法。交叉验证的基本想法时重复地使用数据；把给定的数据进行切分，将切分的数据集组合为训练集与测试集，在此基础上反复地进行训练、测试以及模型选择。

    简单交叉验证：首先随机地将已给数据分为两个部分，一部分作为训练集，另一部分作为测试集；然后用训练集在各种条件下（例如，不同的参数个数）训练模型，从而得到不同的模型；在测试集上评价各个模型的测试误差，选出测试误差最小的模型。

    $S$折交叉验证：首先随机地将已给数据切分为$S$个互不相交的大小相同的子集；然后利用$S – 1$个子集的数据训练模型，利用余下的子集测试模型；将这一过程对可能的$S$种选择重复进行；最后选出$S$次评测中平均测试误差最小的模型。

    留一交叉验证：$S$折交叉验证的特殊情形是$S = N$。

泛化能力：

    学习方法的泛化能力是指该方法学习到的模型对未知数据的预测能力。

生成模型与判别模型：

    监督学习的任务就是学习一个模型，这个模型的一般形式为决策函数：

$$Y = f(X)$$

或者条件概率分布：

$$P(Y|X)$$

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

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

典型的生成模型有：朴素贝叶斯法和隐马尔可夫模型。生成方法的特点：生成方法可以还原$P(X,Y)$，而判别方法不能；生成方法的学习收敛速度更快，即当样本容量增加的时候，学到的模型可以更快地收敛于真实模型；当存在隐变量时，仍可以用生成方法学习，此时判别方法就不能用。

    判别方法由数据直接学习接层函数$f(X)$或者条件概率分布$P(Y|X)$作为预测的模型，即判别模型；典型的判别模型：$k$近邻法、感知机、决策树、逻辑斯谛回归模型、最大熵模型、支持向量机、提升方法和条件随机场等。判别方法的特点：判别方法直接学习的是条件概率$P(Y|X)$或决策函数$f(X)$，直接面对预测，往往学习的准确率更高；由于直接学习$P(Y|X)$或$f(X)$，可以对数据进行各种程度上的抽象、定义特征并使用特征，因此可以简化学习问题。

分类问题、标注问题与回归问题：

分类问题：当输出变量$Y$取有限个离散值时，预测问题便成为了分类问题。这时，输入变量$X$可以是离散的，也可以是连续的。对于二分类问题常用的评价指标是精确率（precision）与召回率（recall）：精确率定义：$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{2TP}{2TP + FP + FN}$$

在这里，$TP$：将正类预测为正类数；$FN$：将正类预测为负类数；$FP$：将负类预测为正类数；$TN$：将负类预测为负类数。

标注问题：可以认为标注问题是分类问题的一个推广，标注问题又是更复杂的结构预测问题的简单形式。标注问题的输入是一个观测序列，输出是一个标记序列或状态序列。标注问题的目标是在于学习一个模型，使它能够对观测序列给出标记序列作为预测。

回归问题：回归用于预测输入变量和输出变量之间的关系，特别是当输入变量的值发生变化时，输出变量的值随之发生的变化。回归模型正是表示从输入变量到输出变量之间映射的函数。回归问题的学习等价于函数拟合：选择一条函数曲线使其很好地拟合已知数据且很好地预测未知数据。