监督学习概述<2>

原书《The Elements of Statistical Learning》，最近打算学习并翻译这本书。有兴趣的同学可以联系我。

email: 769900937@qq.com

2.5 高维空间中的局部方法

到目前为止，我们已经学习了两种预测的方法：稳定的但是偏差很大额线性模型和不太稳定但是偏差很小的KNN算法。并且看起来，对于一个足够大的训练集，我们总是可以通过KNN算法找到一个理论上的最佳的条件期望，因为我们能够找到足够大的靠近$x$的区域，并且对它们取平均。然后这种方法和我们的直觉在高维空间中会崩然倒塌，这个现象在《维数的灾难》一本书中提到。这个问题会有很多表现，接下来，我们会涉及到其中的一些。

对于KNN算法，其输入均匀分布在一个$p$维的单位的超立方体，如图2.6。

假设我们利用一个关于目标点的超立方体来获取训练集中的$r$比例的观察值。因为这对应于单位体积的$r$，因此边的长度期望为$e_p(r)=r^{1/p}$。在一个10维的空间中$e_{10}(0.01)=0.63$，$e_{10}(0.1)=0.80$，然而每个输入的整个的变化范围为1.0。因此要想获取数据的1%或者10%来得到一个局部分平均值。我们必须要覆盖每个输入数据的63%或者80%的变化范围。这种情况下的邻域再也不是局部了。即使急剧减小$r$的大小也不会有很大的改善，因为这样的的话，我们覆盖的观察数据就会越少，造成拟合的方差也会越大。

另外一个在高维空间稀疏采样的后果所有的采样点可能都会靠近其中的一条边。考虑N个数据点均匀分布在一个以原点为中心的p-维球体重。假设我们在原点使用最近邻算法估计。从原点到最近点的距离中位值的$d(p.N)=(1-(1/2)^{1/N})^{1/p}.........(2.24)$
还存在一个更复杂的倒最邻近点的平均距离。当$N=500,p=10,d(p.N)\approx 0.52$, 离边界的距离很近。因此大部分数据点离取样空间的边界比任何其他的数据点更近。这会造成一个问题，就是靠近训练取样的边界会让预测更加的困难。因为这样的预测的时候相当于从外部的推断而不是内部的插值推断。

另一个维数的灾难便是取样密度和 成正比。其中p是输入空间的维数，N是取样的大小。因此，当$N_1=100$时代表的是一个单输入的稠密的取样。然而对于一个输入空间维数为10的时候，要达到同样的额取样密度，$N_{10}=100^{10}$。因此训练数据将会稀疏的分布在高维的输入空间中。
让我们接下来构造一个均匀分布的例子。假设我们有1000个训练样本均匀分布在 。 假设X和Y的真实的关系是
$Y=f(X)=e^{-8||X||^2}$
同时，没有任何测量误差。我们使用1-NN规则来预测测试点$x_0=0$时$y_0$的值。用$T$代表训练集。我们可以按照我们之前提到的流程来计算出预测误差的期望。对取样空间中1000个点取平均值。因为这个问题是确定的，因此预测 均方误差为：

$$\begin{eqnarray*} MSE(x_0) &=&E_T[f(x_0)-\hat{y_0}]^2 \\ &=&E_T[\hat{y_0}-E_T(\hat{y_0})]^2 + [E_T(\hat{y_0})-f(x_0)]^2\\ &=&Var_T{\hat{y_0}}+Bias^2(\hat{y_0}).........(2.25) \end{eqnarray*}$$
图2.7诠释了这个公式的具体含义。我们将MSE拆分为我们熟悉的两部分：方差和偏差平方。这种分解方法通常很可能构造出来并且很有用，被称作$bias-variance decomposition$（偏差-方差分解）。除非最临近的点是0点，否则在这个例子中 $\hat{y_0}$将会比 小$f(0)$，因此预测的平均值也会偏小。方差是1-NN的取样方差。在低维空间中，当$N=1000$时，最临近的点将会距离0点非常非常近，因此这个时候方差和偏差都会非常小。然而随着维数的增大，最近的点将会离目标点越来越远。同时，偏差和方差也会越来越大。当$p=10$时，超过99%的点离原点的距离大于0.5。因此当$p$增大时，$MSE$将会最终增大到1，偏差也是但是方差会开始降低。

尽管这是一个我们人为的举例，但是类似的现象发生的更普遍。很多有很多变量的函数的复杂度将会随着维数的增加而呈指数增加。因此当我们希望达到低维度时同样的精确度，我们就需要指数增加我们取样的大小。在这个例子中，这个函数是所有$p$个变量都相互作用的例子。

偏差项处于主导地位依赖于一些事实，但是在1-NN中并不是总是处于支配地位。例如，在函数总是和一些维数有关如图2.8所示，此时方差将会占据主导地位。
另一方面，假设Y和X的关系是线性的：
$Y=X^T\beta + \epsilon.........(2.26)$
其中$\epsilon ～N(0,\sigma^2)$。
我们通过最小二乘法来拟合模型。
对于任意一个测试点$x_0$，我们有$\hat{y_0}={x_0}^T\hat{\beta}$可以重写为
$\hat{y_0}={x_0}^T\beta+\sum_{i=1}^{N}l_i(x_0)\epsilon_{i}$，其中$l_i(x_0)$是$X(X^TX)^{-1}x_0$的第$i$个元素。
因为在这个模型下最小二乘的估计是无偏的。可以得到：
$$\begin{eqnarray*} EPE(x_0)&=&E_{y_0|x_0}E_T(y_0-\hat{y_0})^2\\ &=&Var(y_0|x_0)+E_{T}[\hat{y_0}-E_T{\hat{y_0}}]^2+[E_T\hat{y_0}-x_0^T\beta]^2\\ &=&\sigma^2 + E_Tx_0^T(X^TX)^{-1}x_0\sigma^2+0^2.........(2.27) \end{eqnarray*}$$
ps:推导过程：
$y_0-\hat{y_0}=(y_0-x_0^T\beta) + (E_T\hat{y_0}-\hat{y_0})+(x_0^T\beta-E_T{\hat{y_0}})$
$U_1=(y_0-x_0^T\beta)$,
$U_2=E_T\hat{y_0}-\hat{y_0}$,
$U_3=x_0^T\beta-E_T{\hat{y_0}}$。
则

$$\begin{eqnarray*} EPE(x_0)&=&E_{y_0|x_0}E_T(y_0-\hat{y_0})^2\\ &=&E_{y_0|x_0}E_T(U_1+U_2+U_3)^2\\ &=&E_{y_0|x_0}E_T({U_1}^2+{U_2}^2+{U_3}^2+2*(U_1U_2+U_2U_3+U_1U_3))\\ \end{eqnarray*}$$
接下来分析每个项
$E_{y_0|x_0}E_TU_1^2=Var(y_0|x_0)=\sigma^2$
$E_{y_0|x_0}E_TU_2^2=E_{y_0|x_0}Var_T(\hat{y_0})$
将$\hat{y_0}=x_0^T\hat{\beta}=x_0^T(\beta+(X^TX)^{-1}X^T\epsilon)$代入：

$$\begin{eqnarray*} U_3&=&E_T{[x_0^T(\beta+(X^TX)^{-1}X^T\epsilon)-x_0^T\beta]}\\ &=&E_T[x_0^T(X^TX)^{-1}X^T\epsilon]\\ &=&E_T[x_0^T(X^TX)^{-1}X^T]E_T(\epsilon)\\ &=&0 \end{eqnarray*}$$
因此，$U_1U_3$,$U_2U_3$也为0。
$U_1U_2=(y_0-x_0^T\beta)(E_T\hat{y_0}-\hat{y_0})$,注意到$\hat{y_0}$和$y_0$没有任何关系。因此，$E_T(U_1U_2)=0$。
剩下最后的就是求$E_{y_0|x_0}E_TU_2^2=E_{y_0|x_0}Var_T(\hat{y_0})$。
考虑到$E(\hat{y_0})=x_0^T\beta$
$$\begin{eqnarray*} Var_T(\hat{y_0})&=&E_T[\hat{y_0}-x_0^T\beta]^2\\ &=&E_T[x_0\hat{\beta}-x_0^T\beta]^2\\ &=&E_T[x_0^T(X^TX)^{-1}X^T\epsilon\epsilon^TX(X^TX)^{-1}x_0]\\ &=&\sigma^2x_0^TE_T[(X^TX)^{-1}]x_0 \end{eqnarray*}$$
因此得到(2.27)式。观察可以得到，由于我们的目标是非确定性的，预测误差中多了一个方差$\sigma^2$。这里是无偏估计，方差取决于$x_0$。当$N$很大，并且任意选择$T$时，可以假设$E(X)=0$，那么就可以得到$X^TX\to NCov(X)$,因此：
ps:关于推导$X^TX\to NCov(X)$
将$X$写成一个$[x_0;x_1;x_2;...x_i;...x_N ]$;因此
$X^TX=[x_0^T,x_1^T,x_2^T,...x_i^T,...x_N^T]*[x_0;x_1;x_2;...x_i;...x_N]=\sum_{i=1}^{N}x_i^Tx_i$
$X^TX\to NCov(x_0)$
$$\begin{eqnarray*} E_{x_0}EPE(x_0)&\approx& E_{x_0}x_0^TCov(X)^{-1}x_0\sigma^2/N+\sigma^2\\ &=&trace[Cov(X)^{-1}Cov(x_0)]\sigma^2/N+\sigma^2\\ &=&\sigma^2(p/N)+\sigma^2.........(2.28) \end{eqnarray*}$$

在这里，我们可以看到期望$EPE$会随着$p$的增大而增大，斜率是 $\sigma^2/N$。 如果$N$很大或者方差$\sigma^2$很小，这种增长是可以忽略的（非常接近0）。通过揭露一些拟合的模型的严重的限制，我们可以避免这种维数所造成的灾难。

图2.9在两种情况下比较了1-NN算法和最小二乘算法，两者的模型都是$Y=f(X)+\epsilon$,其中$X$像之前一样均匀分布，$\epsilon～N(0,1)$。取样的大小是$N=500$。如图2.8，对于红色曲线，$f(x)$ 和第一个坐标成正比，对于绿色曲线，成立方关系。 立方。从图2.9中可以看出，对于线性关系来说，EPE的相对关系从2开始。最小二乘方法在这种情况下是无偏的。它的$EPE$比$\sigma^2=1$稍大。而1-NN的$EPE$则总是比2大，同时随着维数的增加，最邻近点离目标点越来越远。在立方关系的情况下，最小二乘法是有偏的，这缓和了比率的大小。

由于依赖严格的假设，线性模型没有任何偏差，而在1-NN算法中误差可能会很大。然而，假如假设是错误的话，此时，1-NN算法可能会占据主导地位，我们将会看到在严格的线性模型和非常灵活的1-NN算法之间的模型。每一个都有它们的假设和偏差，然而这些算法依赖于这些假设可以避免高维空间中计算复杂度的指数增长。

在我们更深入的讨论之前，让我们介绍一些统计模型的概念，并且看看它们是如何用在预测的框架中。

2.6 统计模型，监督学习和函数近似

我们的目标是找到一个有效的函数$\hat{f(x)}$来近似表示揭示输入和输出的预测关系的函数$f(x)$。在2.4节的理论设置中，我们看到平方误差损失导致我们对回归函数$f(x)=E(Y|X=x)$有一个定量的响应。临近算法可以被看做是条件期望的直接估计。但是我们看到在两种情况下将会失败：

• 如果输入空间的维数太高，那么临近算法将离目标点不会太近，导致很大的误差；

• 如果已知具体的结构是存在的，将可以用来同时降低估计的偏差和方差。

我们希望对$f(x)$使用其他的模型，在很多情况下尤其是设计的用来克服维数问题，在这里我们将讨论一个用来将它们吸收进预测问题的框架。

2.6.1 一个关于联合分布的统计模型

假设我们的数据是从一下统计模型中产生的：
$Y=f(X)+\epsilon.........(2.29)$
其中随机误差$\epsilon$有$E(\epsilon)=0$,并且独立于$X$。注意到在这个模型中,$f(x)=E(Y|X=x)$，而且事实上条件分布$Pr(Y|X)$只有通过均值$f(x)$依赖于$X$。
加性误差模型对于事实来说是一个非常有用的近似。对于大多数系统的输入输出$(X,Y)$ 将不会有一个确定的关系：$Y=f(X)$。通常来说可能还存在其他未测量的影响$y$的变量，包括测量误差。加性模型假设我们可以从一个确定的模型中通过误差 捕获到$\epsilon$这些所有的影响。

对于一些问题来说，这些确定的模型确实存在。很多机器学习中的分类问题就属于这种形式，其中响应平面可以被认为是一个在$R^p$中的涂色地图。训练数据包含一些地图$(x_i,y_i)$中的涂色例子，而我们的目标就是对任意一个点涂色。这里的函数就是确定的，而任意一个训练点的位置$x$会包含随机性。我们现在不会细究这些问题，但是将会看到这些都可以通过基于误差的模型的近似技术来处理。

在(2.29)中的误差是独立同分布的假设并不是严格必须的。但是当我们求$EPE$标准中的均方误差时，这种观点深深的存在于我们脑海深处。对于这样的一个模型，使用最小二乘作为模型估计的数据标准便变得非常自然。简单的修改就可以使这个模型避免这种独立性假设。例如，我们可以有$Var(Y|X=x)=\sigma(x)$，这样的话，均值和方差便都和X有关系。通常条件分布可以以复杂的方式依赖于X，但是加性模型可以避免这些。

到目前为止，我们一直关注在定量的响应上。加性误差模型通常不会用在定性的输出$G$中，在这种情况下，目标函数$p(X)$是条件概率密度，可以直接用来建模。例如，对于二类的数据，假设数据从独立的0-1中产生是合理的，当求得其中一种的概率为$p(X)$时，另一种就为$1-p(X)$。因此假如$Y$是$G$的0-1编码，那么$E(Y|X=x)=p(x)$，同时方差也依赖于$x$：$Var(Y|X=x)=p(x)[1-p(x)]$。

2.6.2 监督学习

在我们用统计的术语描述之前，先从机器学习的观点来讲述下函数拟合的流程。为简单我们假设误差是可加的，并且模型$Y=f(X)+\epsilon$是一个合理的假设。监督学习试图从这些例子中学到$f$。收集一个观察到的数据集$T=(x_i,y_i),i=1,...N$，观察到的输入$x_i$输入到人工系统中，其中的学习算法将会产生输出$\hat{f(x)}$作为输入的响应。学习算法能够修改输入输出的关系$\hat{f}$作为$y_i-\hat{f(x_i)}$原始输出和产生的输出之间差异性的响应。这个过程被称作Learning the example。然而这种情况下我们的希望就是在所有实际中遇到的输入所对应的人工的输出和真正的输出是非常接近的。

2.6.3 函数近似

上一节中提到的函数近似已经成为机器学习和神经网络领域监督学习领域的研究热点。函数近似和估计的方方面面都用到了数学和统计学中的方法。在这里，数据点$(x_i,y_i)$被看做是一个$(p+1)$维的欧几里得空间中的点。函数$f(x)$的定义域是一个$p$维的输入子空间，并且通过一个类似$y_i=f(x_i)+\epsilon_i$的模型和数据联系起来。在本章为了方便我们将会假设定义域为$R^p$,一个$p$维的欧几里得空间，尽管通常输入是一个混合类型。我们的目标就是获得一个有效的$f(x)$的近似对所有的在$R^p$中某些区域的$x$。尽管相比学习流程，没那么迷人的是将监督学习看做一个函数近似问题极大地鼓舞了在欧几里得空间中的几何学和概率推断中的数学概念在本问题中的应用。这也是本书将要采用的方法。

很多我们将会遇到的问题都是和一系列能够修改的用来适合数据的参数$\theta$有关。例如线性模型$f(x)=x^T\beta$中有$\theta=\beta$。另外一个有效的近似可以被表示为linear basis expansions:
$f_{\theta}(x)=\sum_{k=1}^{K}h_k(x)\theta_k.........(2.30)$
其中，$h_k$是输入向量$x$的变换或者函数集合。传统的例子是多项式和三角函数，其中$h_k$可能是$x_1^2,x_1x_2^2,cos(x_1)$等等，我们也将会遇到非线性拓展，例如在神经网络中常见的sigmoid变换：
$h_k(x)=\frac{1}{1+exp(-x^T\beta_k)}.........(2.31)$
我们可以像在线性模型中那样使用最小二乘法来估计$f_\theta$中的$\theta$，通过最小化残差平方和
$RSS(\theta)=\sum_{i=1}^{N}(y_i-f_\theta(x_i))^2.........(2.32)$
将其作为$\theta$的函数。这看起来是可加性错误模型的一个合理的标准。我们将我们的参数化函数看作是一个$p+1$维空间中的平面。当$p=2$时，我们很容易可视化，纵坐标就是我们的输出$y$，例如图2.10。噪声就在输出坐标上，因此我们可以找到一系列参数让我们的拟合平面离观察点尽可能的近，这里，度量近是通过纵坐标的残差平方和$RSS(\theta)$的大小来衡量的。

对于线性模型我们可以通过最小化问题来得到一个简单的封闭解。在，基函数不含有任何隐藏参数的情况下，这对基函数方法也是可行的。否则，解可能就要么需要迭代方法要么需要数值最优化。

尽管最小二乘确实非常的方便，但是它并不是使用时唯一的标准，并且某些情况下，它可能没有任何作用。一个更普遍的估计原则是极大似然估计。假设我们有一个从密度为$Pr_\theta(y)$中随机的取样$y_i,i=1,...,N$。观察到的取样的对数概率为：
$L(\theta)=\sum_{i=1}^{N}logPr_{\theta}(y_i).........(2.33)$

极大似然原则假设最合理的参数$\theta$的值是那些让观察到的样例的概率最大的值。
对于可加性模型$Y=f_{\theta}(X)+\epsilon$,其中$\epsilon～N(0,\sigma^2)$，最小二乘法和使用条件概率的极大似然概率是等价的：
$Pr(Y|X,\theta)=N(f_{\theta}(X),\sigma^2).........(2.34)$
尽管另外的正态性假设很严格，但结果其实是一样的。数据的对数极大似然概率是：
$L(\theta)=-\frac{N}{2}log(2\pi)-Nlog\sigma-\frac{1}{2\sigma^2}\sum_{i=1}^{N}(y_i-f_{\theta}(x_i))^2.........(2.35)$
观察上式可以发现只有最后一项中包含$\theta$，实际上就是$RSS(\theta)$前面乘以一个负数因子。

一个更有趣的例子是对于定性输出$G$的回归函数$Pr(G|X)$的多项式似然概率。假设我们有一个模型对于$X$的任何一个种类都会有$Pr(G=G_k|X=x)=p_{k,\theta}(x),k=1,...,K$。然后对数似然概率（也被称作交叉熵cross-enropy）是
$L(\theta)=\sum_{i=1}^{N}logp_{g_i,\theta}(x_i).........(2.36)$
当最大化它的时候就相当于选了一组$\theta$的值使得数据的分布满足极大似然概率。
To Be Continued!!!