[强基计划] 统计学习方法以及监督学习方法的讨论

统计学习以及监督学习的讨论

1.1 统计学习

学习的定义是什么呢？Herbert A Simon认为，如果一个系统能够通过执行某个过程改善它的性能，那么这就是学习。统计学习，就是利用数据统计来提升系统表现性能的一种方法。

统计学习利用数据，提取它的特征，抽象出数据的模型，并用于预测未来的数据。通常，统计学习可以分为监督学习、无监督学习、强化学习、自监督学习（一种无监督学习）。实现统计学习的步骤如下所示：

（1）准备训练数据集合

（2）确定学习模型的集合，建立假设空间。

（3）确定模型选择的准则，也就是说学习的策略

（4）确定求解最优模型的算法，也就是学习算法

（5）通过学习方法选择最优模型

（6）利用学习的最优模型对新数据进行预测或者分析

1.2.1 学习方法分类

监督学习利用标注的数据，学习出一组模型。它最终会学出条件概率分布P(Y|X) （X为输入，Y为输出），或者决策函数 $Y=\hat f(X)$ 。本质是学习输入-》输出的映射规律。

无监督学习使用大量的无标注数据来进行学习，并预测出适合的模型。与监督学习的关键不同，是无监督学习的输出属于隐式结构空间。也就是说，输入 $x\in X$ ，输出z $\in$ Z隐式结构空间（潜在的结构）。无监督学习的本质是通过学习来推断数据中的重要统计规律和潜在结构。

半监督学习：利用未标注的数据辅助标注的数据。

主动学习：不停产生实例，让外界互动者进行标注。

1.2.2 模型分类

概率模型(probabilistic model)：使用条件概率分布形式 $P(y|x)$ 来作为模型，代表的模型有决策树、朴素贝叶斯模型、隐马尔可夫模型、条件随机场、概率潜在语义分析、潜在第利克雷分配、高斯混合模型等为概率模型。

非概率模型(non-probabilistic model)：感知机、支持向量机、k近邻、adaboost、k均值、潜在语义分析、以及神经网络都是非概率模型，他们实际就是算一个函数分布 $y=f(x)$ 。

另外，统计学习模型还可以分为线性模型与非线性模型，我们熟知的感知机、线性支持向量机、k近邻、k均值、潜在语义分析都属于线性模型。核函数支持向量机、Adaboost、以及神经网络都属于非线性模型。

参数化模型的参数固定维度，反之则为非参数化模型。

最后，模型还可以根据学习的算法，分为online learning（在线学习）与batch learning（批量学习）

1.2.3 两种重要的学习技巧

贝叶斯估计法：公式为
$P(\theta|D)= \frac{P(\theta)P(D|\theta)}{P(D)} \tag{1-1}$
其中，D为我们的数据， $\theta$ 为我们的模型参数，那么这就表示“在当前给定数据下，参数为 $\theta$ 的概率，等价于参数为θ的概率（先验概率）乘以 $P(D|\theta)$ （参数θ情况下取得当前数据的概率，或者似然函数）除以参数D本身所知的概率”。

我们在预测贝叶斯模型的概率参数时，计算期望值：
$P(x|D)=\int P(x|\theta, D)P(\theta|D)d\theta$
这个公式的意思是，利用我们计算出来的 $P(\theta|D)$ 后验概率，和P(x)来对期望值进行计算。由于x与 $\theta D$ 都有关系，所以形式如上式。

核函数 kernel method：使用核函数进行计算。核函数是什么呢？

核函数：是映射关系 $\phi(x)$ 的内积，映射函数本身仅仅是一种映射关系，并没有增加维度的特性，不过可以利用核函数的特性，构造可以增加维度的核函数，这通常是我们希望的。

二维映射到三维，区分就更容易了，这是聚类、分类常用核函数的原因。为什么PCA这样一个降维算法也用核函数呢？

PCA

核函数

如上图所示。

1.3.1 统计学习方法三要素：模型

模型：统计学习方法需要学习出什么样的模型呢？在监督学习中，模型就是所要学习的条件概率分布或者决策函数，其假设空间(hypothesis space)包含所有可能的条件概率分布或者决策函数。从这个角度，可以抽象出假设空间的定义：
$F=\{f|Y=f(X)\}$
X,Y分别为定义在输入空间和输出空间上的变量。通常，F也可以表示为：
$F = \{f|Y=f_\theta(X),\theta \in R^n\}$
$R^n$ 被称为参数空间。

类似的，把上面的F替换为条件概率表示形式，也成立，如：
$F=\{P|P_\theta(Y|X),\theta \in R^n\}$

1.3.2 统计学习方法三要素：策略

策略：接下来要考虑要用什么样的策略学习这个模型。通常我们引入损失函数和风险函数，用来评估我们的估计值 $\hat y$ 与实际值y之间的差距。下面是一些常用的损失估计函数：

0-1损失函数:
$\begin{align*} \begin{split} L(Y,f(X)) = \left\{ \begin{array} x1, &Y\ne f(X)\\ 0, &Y = f(X) \end{array} \right. \end{split} \end{align*}$
平方损失函数：
$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_{exp}(f)=E_P[L(Y,f(X))]=\int_{X\times Y}L(y,f(x))P(x,y)dxdy$
这就是我们的模型在平均意义下的损失，我们称其为风险函数或者期望损失。(expected loss or risk function)。但是，很可惜， $R_{exp}(f)$ 是无法直接计算的，因为我们不知道P(X,Y)的概率分布。模型根据期望风险最小的原则进行学习，想要知道期望又需要知道P(X,Y)，而知道了它其实就已经能够求出来结果了，所以监督学习是一种病态问题(ill-formed problem)。

假设我们有一个训练集：
$T = \{(x_1,y_1),(x_2,y_2),...,(x_n,y_n)\}$
我们可以根据y的标签和x输入来计算经验损失，公式为：
$R_{emp}(f)=\frac{1}{N}\sum_{i=1}^{N}L(y_i,f(x_i))$
根据大数定律，当基数 $C(T)$ 趋近于∞时， $R_{emp}$ 便会自然的趋近于 $R_{exp}$ ，但现实的有标注数据不会有这么多，这就带来了新的学习问题。

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

Empirical risk minimization ERM believe the best model have minimum empirical risk. 我们有下式：
$\min\limits_{f\in F} \frac{1}{N}\sum^N_{i=1}L(y_i,f(x_i))$
结构风险最小化(structural risk minimization, SRM) 是为了防止过拟合而提出的一种策略，它最小等价于正则化（regularization)，它在经验风险之上加入了表示模型复杂度的正则化项和惩罚项目(regularizer and penalty term),
$R_{srm} (f)=\frac{1}{N}\sum^N_{i=1}(y_i,f(x_i))+\lambda J(f)$
这里， $J(f)$ 代表了模型的复杂度，它是定义在假设空间 $F$ 上的泛函？？（泛函是什么）泛函就是函数的函数，可以把函数-》数，更科学一点，泛函就是定义域是一个函数集，而值域是实数集或者实数集的一个子集。一个例子是，最大后验概率估计（MAP, maximium posterior probability estimation)。这样，我们只需要对上式做最小化，也就是有
$\min\limits_f\in F \frac{1}{N}\sum_{i=1}^N L(y_i,f(x_i))+\lambda J(f)$

1.3.3 统计学习方法三要素：算法

算法是统计学习模型的具体计算方法，统计学习基于训练数据集，根据学习策略，从假设空间中选择合适的模型，但计算方法也可能有差异。

**待补充。

1.4.1 模型评估：训练误差与测试误差

假设我们学习到的模型为 $Y=\hat f(X)$ ，定义在经验情况下的训练误差为：
$R_{emp}(\hat f)=\frac{1}{N}\sum^N_{i=1}L(y_i, \hat f(x_i))$
其中，N为样本的容量，类似的，测试样本的误差为：
$e_{test}=\frac{1}{N^{'}}\sum^{N^{'}}_{i=1} L(y_i, \hat f(x_i))$

1.4.2 模型选择

假设一M次多项式：
$f_M(x,w)=w_0+w_1x+w_2x^2+...+w_Mx^M=\sum^M_{j=0}w_jx^j$
我们求解以下等式：
$L(w)=\frac{1}{2}\sum^N_{i=1} (f(x_i,w)-y_i)^2$
加 $\frac{1}{2}$ 是因为求导更容易计算，然后我们把模型与训练数据带入上式，有：
$L(w)=\frac{1}{2}\sum^N_{i=1} \left( \sum^M_{j=0}w_jx^j_i-y_i \right)^2$
解决这个方程可用最小二乘法，这在机器学习入门之道（中井悦司）的书中被提及。这样我们就可以得到这个模型的参数解（传统机器学习）。

1.5 正则化与交叉验证

正则化(regularization)是结构风险最小化的一种实现，它给经验风险加入一个惩罚（penalty term)或者正则项(regularizer)。根据Occam's razor理论，在所有的模型中，符合选择且十分简单的模型才是最好的模型。可以用 $||w||^2$ 二范数或者一范数 $||w||$ 来表示。

交叉验证(cross validation),包括简单交叉验证，S折交叉验证，留一交叉验证。这些方法在传统学习模型中非常常用。

1.6 泛化能力

所谓泛化能力，就是指训练出来的模型对未来的预测能力。泛化误差(generalization error):
$R_{exp}(f)=E_P[L(Y,\hat f(X))]=\int_{X\times Y}L(y,\hat f(x))P(x,y)dxdy \tag{1.6-1}$
generalization error bound 泛化误差上界（概率）常用来比较不同学习方法的泛化能力，对于一个问题，数据集越大，那么泛化上界就越小，模型的假设空间容量越大，那么泛化误差上界就越大。为了研究泛化误差上界的计算，设 $T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$ 为一从联合概率分布 $P(X,Y)$ 产生的数据集，其中， $X\in R^n$ , $Y\in \{-1,+1\}$ ，假设空间是一个函数的有限集合 $\{f_1,f_2,...,f_d\}$ （有限的假设空间），那么关于f的期望风险与经验风险为：
$R(f) = E[L(Y,f(X))] \tag {1.6-2}$

$R(f) = \frac{1}{N}\sum^N_{i=1}L(y_i,f(x_i)) \tag {1.6-3}$

经验最小化函数为：
$f_n = arg\min\limits_{f\in F} \hat R(f) \tag {1.6-4}$
它的泛化能力根据定义可以推导为：
$R(f_N)=E[L(Y,f_N(X))] \tag {1.6-5}$
也就是说，loss的期望(expectation)。

我们从之前的假设空间 $\{f_1,f_2,...,f_d\}$ 中任选一个函数 $f\in F$ ，至少以概率 $1-\delta,0<\delta<1$ ，以下的结论成立：
$R(f)\le \hat R(f)+\epsilon(d,N,\delta) \tag {1.6-6}$
其中：
$\epsilon(d,N,\delta)=\sqrt{\frac{1}{2N}(logd+log\frac{1}{\delta})} \tag {1.6-7}$
d:函数的个数，或者假设空间的容量。 $\hat R(f)$ 泛化误差上界。

证明：Hoeffding 不等式：设 $X_1,...,X_N$ 为独立随机变量，且 $X_i\in [a_i,b_i],i=1,2,3,...,N$ ， $\overline X$ 为变量的经验（比如根据数据推断的）均值， $\overline X$ 相当于 $\frac{1}{N}\sum^{N}_{i=1}X_i$ ，则对任意的t>0，有：
$P[\overline X-E(\overline X)\ge t] \le exp\left(-\frac{2N^2t^2}{\sum^N_{i=1}(b_i-a_i)^2}\right) \tag{1.6-8}$
也就是说，均值减去均值的方差大于t的概率，将会小于右边的等式。那么我们就可以由该不等式证明(1.6-6)式子的正确性。如果损失函数取值于[0,1]区间，那么由(1.6-8)可得出，对于任意的 $\epsilon>0$ ，有：
$P(R(f)-\hat R(f)\ge \epsilon)\le exp(-\frac{2N^2\epsilon^2}{N}) = exp(-2N\epsilon^2) \tag{1.6-9}$
我们在(1.6-9)的基础上考虑 $F=\{f_1,f_2,...,f_d\}$ ，对于每一个 $f\in F$ ，我们可以推出以下的式子：
$P(\exists f \in F:R(f)- \hat R(f) \ge \epsilon) = P(\bigcup_{f\in F} {R(f)-\hat R(f)\ge \epsilon\}) \le \sum_f \in F} P(R(f)- \hat R(f)) \le d exp (-2N \epsilon ^ 2) \tag {1.6-10}$
特别的，d为上面的假设空间的容量，我们把上面的概率反选，也就是对任意 $f\in F$ 有:
$P(R(f)-\hat R(f)< \epsilon)\ge 1-dexp(-2N\epsilon^2) \tag {1.6-11}$
令 $\delta= dexp(-2N\epsilon^2)$ ，则我们可以得到 $P(R(f)<\hat R(f)+\epsilon)\ge 1-\delta$ ，也就是至少有概率 $1-\delta$ ，使得 $R(f)\le \hat R(f)+\epsilon$ 。至于(1.6-7)则可以通过之前的代换得到，即
$\ln\frac{\delta}{d} = -2N\epsilon^2$
整理，得:

$\epsilon^2 = \frac{1}{2N}(ln d- ln \delta)=\frac{1}{2N}(lnd+ln\frac{1}{\delta})$
于是得证。

1.7 生成模型与判别模型

监督学习分为生成方法（generative approach)和判别方法（discriminative approach)，所学到的模型为生成模型（generative model)与判别模型（discriminative model)。生成方法由数据学习联合概率分布P(X,Y),然后再求出条件概率分布P(Y|X)。生成方法的学习收敛速度快，且可以在存在隐型变量的时候正常运行。

判别方法则是直接学习决策函数f(X)或者条件概率分布P(Y|X)，它只关心对于输入X，应该输出什么样的Y。判别方法的学习准确率一般更高，同时可以简化问题（无需考虑广泛的问题，可以进行各种程度的抽象）。

1.8 监督学习方法的应用

分类问题：当输出的变量Y为离散取值的时候，这个预测问题便可以直接的认为是分类问题。在这种任务中，我们需要学习出一个分类器(classifier)，它所做的预测我们称之为分类(classification)。分类问题包括学习与分类两个过程，但我认为这一节的重点是几个指标，并将在下面介绍。

首先，对于二分类问题，我们作如下假设，TP（True positive）真阳把正类分类为正类， FN (False negative) 假阴把正类分类为负类 FP (False positive) 假阳把负类分类为正类 TN(True negative) 真阴把负类分类为负类。为了体现 TP、TN、FN、FP对正确性的影响，设计指标如下：

精确率（precision) 就是真正为正类的数量除以判断为正类的数量TP+FP，也就是真正为正类的数量：
$P = \frac{TP}{TP+FP}$
召回率(recall)就是正类样本中假阴性的数量，显然更多的正类分错到了负类会降低召回率。
$R = \frac{TP}{TP+FN}$
数学上来说，调和均值十分有用， $F_1$ 值就是准确率和召回率的调和均值，它的表达式为：
$\frac{2}{F_1} = \frac{1}{P}+\frac{1}{R}$
代入之前的公式，我们有：
$F_1 = \frac{2TP}{2TP+FP+FN}$
当精确率高，召回率也高的时候， $F_1$ 便会变高，这样就可以一定程度衡量模型的质量（更加均衡的估计）。

标注问题：标注问题的输入是一个观测序列，输出则应当是一个标记序列，这个问题可以看作是分类问题的推广。对于一个观测序列 $X_{N+1}=(x^{(1)}_{N+1},x^{(2)}_{N+1},...,x^{(n)}_{N+1})^T$ ，找到使条件概率 $P((y^{(1)}_{N+1},y^{(2)}_{N+1},...,y^{(n)}_{N+1})^T|(x^{(1)}_{N+1},x^{(2)}_{N+1},...,x^{(n)}_{N+1})^T)$ 最大的标记序列。