统计机器学习理论

Statistical learning

The frequentist approach views the model parameters as unknown constants and estimates them by matching the model to the available training data using an appropriate metric.

框架

泛化能力（generalization ability）

泛化能力是指该学习方法对未知数据的预测能力，是学习方法本质上重要的性质。依据测试数据集对模型的泛化能力加以评价是不可靠的，统计学习理论试图从理论上对学习方法的泛化能力进行分析。
泛化误差：

$\begin{aligned} R_{\exp }(\hat{f}) &=E_{P}[L(Y, \hat{f}(X))] \\ &=\int_{\mathcal{X} \times \mathcal{Y}} L(y, \hat{f}(x)) P(x, y) \mathrm{d} x \mathrm{~d} y \end{aligned}$

事实上，泛化误差就是所学习到的模型的期望风险

泛化误差上界

学习方法的泛化能力分析往往是通过研究泛化误差的概率上界进行的，简称为泛化误差上界(generalization error bound)。

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

当假设空间是有限个函数的集合时我们有：

证明用到了 Hoeffding 不等式：

$\mathrm{P}[E(\bar{X})-\bar{X} \geqslant t] \leqslant \exp \left(-\frac{2 N^{2} t^{2}}{\sum_{i=1}^{N}\left(b_{i}-a_{i}\right)^{2}}\right)(t>0)$

监督学习

生成方法和判别方法

监督学习的方法可以分为生成方法和判别方法，两种方法分别产生生成模型和判别模型。
生成方法是指根据给定的数据学习他们的联合概率分布，求出条件概率分布作为预测的模型。如朴素贝叶斯法和隐马尔可夫模型
判别方法是直接根据给定的数据直接学习出决策函数或者条件概率分布。如感知机，决策树，支持向量机

生成方法的特点：

• 生成方法的学习收敛速度更快
• 当存在隐变量时，仍可以用生成方法学习，此时判别方法就不能用。

判别方法的特点：

• 直接面对预测，往往学习的准确率更高：
• 由于直接学习 P(Y|X)或 f(X),可以对数据进行各种程度上的抽象、定义特征并使用特征，因此可以简化学习问题。

模型评价

分类问题

评价指标

评价分类性能的指标一般是分类准确率：分类正确的样本与总样本数量比（0-1 损失函数时的经验风险）。

二分类问题

通常以我们关注的类为正类，分类器在测试数据集的预测为正确或不正确。

精确率(precision，也叫查准率)又叫 Senstivity
召回率(recall，也叫查全率)又叫 TPR(true positive rate)
FPR（误诊率)=1-特异度（specificity）
FNR（漏诊率)=1-敏感度（sensitivity）

% Please add the following required packages to your document preamble:
% \usepackage{multirow}
% \usepackage[table,xcdraw]\{xcolor\}
% If you use beamer only pass "xcolor=table" option, i.e. \documentclass[xcolor=table]{beamer}
\begin{table}[]
	\begin{tabular}{|cc|cc|c|}
		\hline
		\multicolumn{2}{|l|}{} &
		\multicolumn{2}{c|}{\cellcolor[HTML]{9698ED}\textbf{Predicted Class}} &
		\\ \cline{3-4}
		\multicolumn{2}{|c|}{\multirow{-2}{*}{}} &
		\multicolumn{1}{c|}{\cellcolor[HTML]{96FFFB}\textbf{Positive}} &
		\cellcolor[HTML]{96FFFB}\textbf{Negative} &
		\multirow{-2}{*}{\textbf{Rate}} \\ \hline
		\multicolumn{1}{|c|}{\cellcolor[HTML]{9698ED}} &
		\cellcolor[HTML]{96FFFB}\textbf{Positive} &
		\multicolumn{1}{c|}{\begin{tabular}[c]{@{}c@{}}True Positive(TP)\\ (真正例)\end{tabular}} &
		\begin{tabular}[c]{@{}c@{}}False Negative(FN)\\ (假反例)\end{tabular} &
		\cellcolor[HTML]{96FFFB}{\color[HTML]{000000} \textbf{\begin{tabular}[c]{@{}c@{}}Recall\\ $\frac{TP}{TP+FN}$$
\end{tabular}}} \\ \cline{2-5}
		\multicolumn{1}{|c|}{\multirow{-2}{*}{\cellcolor[HTML]{9698ED}\textbf{Actual Class}}} &
		\cellcolor[HTML]{96FFFB}\textbf{Negative} &
		\multicolumn{1}{c|}{\begin{tabular}[c]{@{}c@{}}Flase Positive(FP)\\ (假正例)\end{tabular}} &
		\begin{tabular}[c]{@{}c@{}}True Negative(TN)\\ (真反例)\end{tabular} &
		\cellcolor[HTML]{96FFFB}{\color[HTML]{000000} \textbf{\begin{tabular}[c]{@{}c@{}}Specificity\\ $\frac{TN}{TN+FP}$$
\end{tabular}}} \\ \hline
		\multicolumn{2}{|c|}{Rate} &
		\multicolumn{1}{c|}{\cellcolor[HTML]{96FFFB}\textbf{\begin{tabular}[c]{@{}c@{}}Precision\\
					$\frac{TP}{TP+FP}$$
\end{tabular}}} &
		\cellcolor[HTML]{96FFFB} &
		\cellcolor[HTML]{96FFFB}{\color[HTML]{000000} \textbf{\begin{tabular}[c]{@{}c@{}}Accurancy\\ $\frac{TP+TN}{TP+TN+FP+FN}$$
\end{tabular}}} \\ \hline
	\end{tabular}
\end{table}

此外还可能会用到$F_1$，精确率和召回率的调和平均值

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

当 P 和 R 所占权重不一致时，需要引入加权调和平均：$F_\beta$：

$\frac{1}{F_{\beta}}=\frac{1}{1+\beta^{2}} \cdot\left(\frac{1}{P}+\frac{\beta^{2}}{R}\right)$

$\beta$越大，R 所占权重越大。

ROC

ROC 曲线是一种常用的二分类模型评价方法，它通过调整分类器的阈值，计算多组 TPR(查准率)和 FPR(误诊率，1-查全率)，然后以 FPR 为横轴，TPR 为纵坐标绘制出来的曲线。

阈值的差异可以类比现实世界中不同的人对善恶的定性来理解,阈值的大小将会直接影响到模型的查准率和查全率，来反映学习器在不同任务下的期望泛化性能的好坏。

周志华老师《机器学习》一书中介绍 ROC 时并没有引入阈值的概念，而是使用了"截断点"的概念，我们根据对样本数据的概率预测结果对样本数据进行排序，将最可能为正例的排在最前面，那么阈值的问题就可以看成在哪个样本数据处截断的问题。

最理想的模型是在左上角，即 TPR=1，FPR=0，即没有误诊，所有的正例都被正确诊断。而最差的模型是在右下角，即 TPR=0，FPR=1，即所有的正例都被错误诊断为反例。
因此可以说越接近左上方的点被认为模型的性能越好
接着也就为了比较两个学习器的性能，也就引出了 AUC(Area Under ROC Curve)的概念，AUC 越大，模型越好。

标注问题

标注问题可以看做更复杂的分类问题，与分类问题不同的是，标注问题的输出是一个标记序列或者叫状态序列。标注问题在信息抽取和自然语言处理领域被广泛应用。如自然语言处理中的词性标注问题，信息抽取中的从英文文章中抽取名词短语等。

偏差-方差分解

以射靶子举个例子，我们每一次射都是希望能正中靶心。但是我们的每一次射箭都会受到其他因素的影响。模型的偏差是说射中位置距离靶心（期望输出）的平均距离，而模型的方差则衡量了射箭位置的波动性，即箭的聚集程度，衡量的是我们在其他因素改变时射箭水平是否稳定的

偏差-方差理论试图将模型的泛化误差进行分解，加深我们对泛化误差来源的认识，我们知道，相同算法在不同训练集上学到的结果可能不同，实际用于训练的数据可能会存在噪声（标注错误），从这两个实际假设出发，想一下下边的这个场景:
对于来源于同一个分布的若干个数据集$D$,假设这些数据的标签为$y_D$,实际标记为$y$，对于某一学习算法学习得到的模型为$\hat{f}$,$\hat{f}(x;D)$为算法在训练集 D 上的预测输出，因为这里考虑有多个训练集，那么就会有多个$f$。这里将学习算法的期望泛化误差进行分解。
首先，使用不同训练集训练得到的模型会产生不同的预测输出，因此可以引出使用样本数相同的不同训练集产生的方差为:

$var(x)=E_D[(f(x;D)-E_D(f(x;D))^2]$

数据集本身的噪声 noise 为:

$noise^2=E_D[(y_D-y)^2]$

期望输出与真实标记的差别为偏差(bias)，即:

$bias^2(x)=E_D[(E_D(f(x;D))-y)^2]$

为了顺利分解，还需要引入假定噪声的期望为 0，即$E_D[y_{D}-y]=0$。对于线性回归来说，一般会假设成$y=y_D+\epsilon$的形式，可以理解为测量误差或者是噪声影响导致。

于是我们对期望泛化误差的分解有:

$\begin{aligned} E(f ; D)=& \mathbb{E}_D\left[\left(f(x ; D)-y_D\right)^2\right] \\ =& \mathbb{E}_D\left[\left(f(x ; D)-\bar{f}(\boldsymbol{x})+\bar{f}(\boldsymbol{x})-y_D\right)^2\right] \\ =& \mathbb{E}_D\left[(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))^2\right]+\mathbb{E}_D\left[\left(\bar{f}(\boldsymbol{x})-y_D\right)^2\right] \\ &+\mathbb{E}_D\left[2(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))\left(\bar{f}(\boldsymbol{x})-y_D\right)\right] \\ =& \mathbb{E}_D\left[(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))^2\right]+\mathbb{E}_D\left[\left(\bar{f}(\boldsymbol{x})-y_D\right)^2\right] \\ =& \mathbb{E}_D\left[(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))^2\right]+\mathbb{E}_D\left[\left(\bar{f}(\boldsymbol{x})-y+y-y_D\right)^2\right] \\ =& \mathbb{E}_D\left[(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))^2\right]+\mathbb{E}_D\left[(\bar{f}(\boldsymbol{x})-y)^2\right]+\mathbb{E}_D\left[\left(y-y_D\right)^2\right] \\ &+2 \mathbb{E}_D\left[(\bar{f}(\boldsymbol{x})-y)\left(y-y_D\right)\right] \\ =& \mathbb{E}_D\left[(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))^2\right]+(\bar{f}(\boldsymbol{x})-y)^2+\mathbb{E}_D\left[\left(y_D-y\right)^2\right], \end{aligned}$

交叉项的乘积为 0 这里就不在详细说明，在得到这一步的基础上会有模型的泛化误差可以分解为方差、偏差和噪声之和:

$E(f ; D)=\operatorname{var}(\boldsymbol{x})+\operatorname{bias}^2(x)+noise^2$

这里再对三者的含义做一个说明:

• 方差度量了同样大小的数据集的表动所导致的学习性能的变化，刻画了数据扰动对学习性能的影响
• 偏差度量了学习算法的期望预测和真实结果的偏离程度，刻画了学习算法本身的拟合能力
• 噪声则是当前学习算法所能达到的期望泛化误差的下界，刻画了学习问题本身的难度。

周志华老师的书里说到，模型的泛化误差是由学习算法的能力(bias)、数据的充分性(noise)和学习任务本身的难度(Var)所共同决定的!

这里借助吴恩达老师在斯坦福 2014 年机器学习课程中提到的一个例子做一个进一步的解释，对于拟合一个房价和所在区域数据的模型，一次线性回归模型在数据趋近无穷大时的泛化误差会比五次更大，其实就是因为一次线性回归模型又更大的偏差，相比之下五次线性回归模型则对局部的 pattern 拟合较好，有一点过拟合的感觉，本质上说是模型受数据扰动影响太大，即方差太大。
Informally, we define the bias of a model to be the expected generalization error even if we were to fit it to a very (say, infinitely) large training set.
By fitting these “spurious” patterns in the training set, we might again obtain a model with large generalization error.

数据扰动的影响可以通过增大训练集来减弱，但是这同时会增大学习任务本身的难度，换言之，偏差和方差一定程度上是会有冲突的。方差与偏差的权衡，本质上也可以看成是过拟合和欠拟合的权衡。

最后强调一点，偏差方差分解的如此优美的形式只在回归问题中可以实现，分类任务中 0/1 损失函数的跳变性理论上推出偏差-方差分解很困难。

过拟合的解决办法

模型的过拟合问题一般是由于样本数量与特征维度大小不匹配所导致的，一般可以考虑的解决办法有:

• 增加样本数量
• 特征降维/特征选择
• 正则化（一种数学上的处理方法使得矩阵重新可逆，如岭回归，l2范数正则化)

正则化

模型选择的方法，正则化可以理解成一种对学习策略的改进（防止模型过拟合），在常规的风险函数或者损失函数的基础上加上一个正则化项或者叫罚项，一般具有以下形式：

前一项是风险函数（对损失函数取均值），后一项是正则化项。$\lambda$是超参数，需要利用验证数据(validafim data)进行估计

模型的参数化

统计学习模型可以分为参数化模型和非参数化模型，首先给出两个模型的定义:

A learning model that summarizes data with a set of parameters of fixed size (independent of the number of training examples) is called a parametric model. No matter how much data you throw at a parametric model, it won’t change its mind about how many parameters it needs.

Nonparametric methods are good when you have a lot of data and no prior knowledge, and when you don’t want to worry too much about choosing just the right features.

简单来说两类模型的主要区分方法是模型所假定的参数个数是否是有限的。大多数参数化模型都会结合对数据的认识来做出一些假设，这些假设会使得学习的函数的形式有所限制，换言之会使得学习的函数中参数的个数是给定的。而非参数模型则不会利用任何先验知识，因而其参数个数更多的是随着数据的变化而发生变化。其实本质来说就是是否对模型的学习函数做出了一些约束,大部分非参数化模型更多的是一种 algorithm 或者说是一种思想，至于如何去选择合适的函数去拟合或者逼近，并没有做出限制。

这里对这个概念产生误解的主要原因其实是有的时候对于模型和算法的概念没做一个很好的区分，这里所说的 SVM 和 KNN 更多的是一种思想，而并不指指定了特定函数形式的模型。

Basic SVM are linear classifiers, and as such parametric algorithms. Advanced SVM can work for nonlinear data, and if you have a SVM working for data not constrained to be in a family described by a finite number of parameters, then it is nonparametric.