美文网首页分析101
Curse of Dimensionality

Curse of Dimensionality

作者: Boye0212 | 来源:发表于2021-06-22 16:06 被阅读0次

1 Curse of dimensionality

我们知道，k-NN算法是一种非常简单又很有效果的算法，它的核心思想就是局部近似。究其原因，就是因为它可以很好地对条件期望进行近似，一方面它用样本均值代替了期望，另一方面它用给定某个点的邻域代替了该点，结合起来，就是用在邻域内的样本均值，取代了在该点处的条件期望。

但是，在高维问题中，k-NN会逐渐变得无效。为什么？还要从高维问题的一些特点说起。

首先，高维空中的样本，分布非常稀疏。假设有一个单位体积的超立方体（hypercube），即每个维度的“边长”都为1，它的“体积”也为1，而样本在里面均匀分布。如果我们想要取到它一定比例r的样本，也即取该超立方体r比例的体积，那么，每条边应该取多少的比例范围？很简单，每个边长应取e_p(r)=r^{1/p}。如果在10维空间中，仅仅想取它10\%的体积，就应取每条边的e_{10}(0.1)=0.80的长度，也就是对每条边都要取80\%的范围。

第二，高维空间中的样本，几乎都分布在“边缘”处。考虑p维空间中的N个样本，假设它们均匀分布在一个单位球中，球心就在原点，那么，距离原点最近的那个样本，它到原点的“距离”的中位数是多少？令D=\min_i\{\Vert x_i \Vert\}为各样本到原点距离的最小值，计算它的累积分布函数
\begin{aligned} &F(d)\\ =& \Pr(D\leq d)\\ =& 1-\Pr(D\gt d)\\ =& 1- \prod_{i=1}^{N} \Pr(\Vert x_i \Vert \gt d)\\ =& 1- \prod_{i=1}^{N} [1-\Pr(\Vert x_i \Vert \leq d)]\\ =& 1- \left[1-d^p\right]^{N} \end{aligned}

想知道距离的中位数，只需让累积分布函数取值1/2即可。可以算出，最近距离的中位数d(N,p)=\left[1-\left(1/2 \right)^{1/N}\right]^{1/p}。比如p=10，N=500的话，d(10,500)\approx 0.52，也就是说，离原点最近的那个点，就已经在一半距离以外了。

第三，在高维中，采样密度与N^{1/p}成比例。如果在1维时我们采样100个点，那么在10维时我们需要采样100^{10}个点才能维持一样的采样密度。

2 高维问题举例

2.1 高维中的1-NN

设定：N=1000，X为p维随机变量，且在[-1,1]^p上均匀分布，Y=f(X)=\exp(-8 \Vert X \Vert^2)，记训练集为\mathcal{T}，我们要用1-NN去预测x_0=0处的y_0。当然，我们已经知道了答案y_0=f(x_0)=1。

可以对MSE（mean squared error，均方误差）做分解：
\begin{aligned} &\text{MSE}(x_0)\\ =& E_{\mathcal{T}}[f(x_0)-\hat{y}_0]^2\\ =& [f(x_0)-E_{\mathcal{T}}(\hat{y}_0)]^2 +E_{\mathcal{T}}[E_{\mathcal{T}}(\hat{y}_0)-\hat{y}_0]^2 \end{aligned}
最后一个等式是因为E_{\mathcal{T}}\{[f(x_0)-E_{\mathcal{T}}(\hat{y}_0)](E_{\mathcal{T}}(\hat{y}_0)-\hat{y}_0)\}=0。第一部分为bias的平方，第二部分为variance。

在p=1时，1-NN算法找的最近的点，很可能不会在0处，因此必有E_{\mathcal{T}}(\hat{y}_0)\lt 0，但由于此时N=1000比较大，找的点基本上会离x_0比较近，因此bias和variance都不会太大。

但在高维时，问题就开始出现了。比如p=10，那么如上文所说，到原点的最短距离会大大增加：有99\%以上的样本，到x_0=0的最近距离会大于0.5。因此预测的\hat{y}_0有很高的概率接近于0，bias会非常大，就算variance很小，也会导致MSE接近于1了。

有时候不一定是bias过多影响了MSE，比如真正的函数关系只与其中几个维度有关的话，如f(X)=(X_1+1)^3/2，此时，bias不会太大，在MSE中是variance起了决定性作用。

2.2 高维中的LS

设定：真实的变量关系为y=X\beta+\epsilon，其中\epsilon\sim N(0,\sigma^2 I_N)且与X无关，我们还是要估计x_0处的y_0。

首先利用最小二乘法，我们有\hat\beta=(X'X)^{-1}X'y=\beta+(X'X)^{-1}X'\epsilon，\hat y_0=x_0'\hat\beta=x_0'\beta+x_0'(X'X)^{-1}X'\epsilon，在这里，我们关注在x_0处的expected (squared) prediction error（期望预测误差）\text{EPE}(x_0)=E_{y_0|x_0}E_{\mathcal{T}} (y_0-\hat{y}_0)^2。

与2.1节中的情况相比，这里多了一个扰动项\epsilon，我们将y_0-\hat{y}_0拆解为两部分：
y_0-\hat{y}_0=(y_0-x_0'\beta)+(x_0'\beta -\hat{y}_0)

由简单的计算，可将第一项的平方项化为E_{y_0|x_0}E_{\mathcal{T}} (y_0-x_0'\beta)^2=\sigma^2，将第二项的平方项化为
E_{y_0|x_0}E_{\mathcal{T}}(x_0'\beta -\hat{y}_0) ^2 =[x_0'\beta-E_{\mathcal{T}}(\hat{y}_0)]^2 +E_{\mathcal{T}}[E_{\mathcal{T}}(\hat{y}_0)-\hat{y}_0]^2
并且，由于E_{\mathcal{T}}(\hat{y}_0)=x_0'\beta+x_0'E_{\mathcal{T}} [(X'X)^{-1}X'\epsilon]，再利用E_{\mathcal{T}} [(X'X)^{-1}X'\epsilon]=E_{\mathcal{X}} E_{\mathcal{Y|X}} [(X'X)^{-1}X'\epsilon]=E_{\mathcal{X}} \left[ (X'X)^{-1}X' E_{\mathcal{Y|X}} (\epsilon)\right]=0，可知E_{\mathcal{T}}(\hat{y}_0)=x_0'\beta，上式第一项即bias的平方为0，最终只剩variance，并可进一步化为
\begin{aligned} &E_{y_0|x_0}E_{\mathcal{T}}(x_0'\beta -\hat{y}_0) ^2\\ =& E_{\mathcal{T}}[E_{\mathcal{T}}(\hat{y}_0)-\hat{y}_0]^2\\ =& E_{\mathcal{T}}[x_0'(X'X)^{-1}X'\epsilon\epsilon' X (X'X)^{-1}x_0]\\ =& x_0' E_{\mathcal{X}} \left[ (X'X)^{-1}X' [E_{\mathcal{Y|X}}(\epsilon\epsilon')]X (X'X)^{-1} \right] x_0\\ =&x_0' E_{\mathcal{X}} \left[(X'X)^{-1}\right]x_0 \sigma^2 \end{aligned}

最后，再次利用E_{\mathcal{T}}(\hat{y}_0)=x_0'\beta，交叉项为
\begin{aligned} &2E_{y_0|x_0}E_{\mathcal{T}}[(y_0-x_0'\beta)(x_0'\beta -\hat{y}_0)]\\ =& 2E_{y_0|x_0}\left[(y_0-x_0'\beta)E_{\mathcal{T}} (x_0'\beta -\hat{y}_0)\right]\\ =& 0 \end{aligned}

汇总以上3个结果，有：
\text{EPE}(x_0)=E_{y_0|x_0}E_{\mathcal{T}} (y_0-\hat{y}_0)^2=\sigma^2+x_0' E_{\mathcal{X}} \left[(X'X)^{-1}\right]x_0 \sigma^2

若\mathcal{T}为随机抽取的样本，假定E(x)=0，当N\to\infty时，X'X\to N \text{Cov}(x)，再对于所有x_0取期望，有
\begin{aligned} &E_{x_0}\text{EPE}(x_0)\\ \sim& \sigma^2+\dfrac{\sigma^2}{N} E_{x_0} [x_0' \text{Cov}(x)^{-1} x_0]\\ =& \sigma^2+\dfrac{\sigma^2}{N} \text{tr} \left[ \text{Cov}(x)^{-1} E_{x_0} (x_0x_0' )\right]\\ =& \sigma^2+\dfrac{\sigma^2}{N} \text{tr} (I_p)\\ =& \sigma^2+\dfrac{p}{N}\sigma^2 \end{aligned}

可以看出，EPE会随着p的增加而增加。

参考文献

  • Friedman, Jerome, Trevor Hastie, and Robert Tibshirani. The elements of statistical learning. Vol. 1. No. 10. New York: Springer series in statistics, 2001.

相关文章

网友评论

    本文标题：Curse of Dimensionality

    本文链接：https://www.haomeiwen.com/subject/wwhmyltx.html

    延伸阅读

    深度阅读

    • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

    栏目导航

    热点阅读

    分析101

    关于我们|服务条款|联系我们|Curse of Dimensionality|投稿指南|网站地图|RSS订阅|排版工具|手机版

    提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

    Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

    备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

    本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

    所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！