Curse of Dimensionality

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})为各样本到原点距离的最小值，计算它的累积分布函数

[egin{aligned} &F(d)\ =& Pr(Dleq d)\ =& 1-Pr(Dgt 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 ight]^{N} end{aligned} ]

想知道距离的中位数，只需让累积分布函数取值(1/2)即可。可以算出，最近距离的中位数(d(N,p)=left[1-left(1/2 ight)^{1/N} ight]^{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，均方误差）做分解：

[egin{aligned} & ext{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=Xeta+epsilon)，其中(epsilonsim N(0,sigma^2 I_N))且与(X)无关，我们还是要估计(x_0)处的(y_0)。

首先利用最小二乘法，我们有(hateta=(X'X)^{-1}X'y=eta+(X'X)^{-1}X'epsilon)，(hat y_0=x_0'hateta=x_0'eta+x_0'(X'X)^{-1}X'epsilon)，在这里，我们关注在(x_0)处的expected (squared) prediction error（期望预测误差）( ext{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'eta)+(x_0'eta -hat{y}_0) ]

由简单的计算，可将第一项的平方项化为(E_{y_0|x_0}E_{mathcal{T}} (y_0-x_0'eta)^2=sigma^2)，将第二项的平方项化为

[E_{y_0|x_0}E_{mathcal{T}}(x_0'eta -hat{y}_0) ^2 =[x_0'eta-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'eta+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) ight]=0)，可知(E_{mathcal{T}}(hat{y}_0)=x_0'eta)，上式第一项即bias的平方为(0)，最终只剩variance，并可进一步化为

[egin{aligned} &E_{y_0|x_0}E_{mathcal{T}}(x_0'eta -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'epsilonepsilon' X (X'X)^{-1}x_0]\ =& x_0' E_{mathcal{X}} left[ (X'X)^{-1}X' [E_{mathcal{Y|X}}(epsilonepsilon')]X (X'X)^{-1} ight] x_0\ =&x_0' E_{mathcal{X}} left[(X'X)^{-1} ight]x_0 sigma^2 end{aligned} ]

最后，再次利用(E_{mathcal{T}}(hat{y}_0)=x_0'eta)，交叉项为

[egin{aligned} &2E_{y_0|x_0}E_{mathcal{T}}[(y_0-x_0'eta)(x_0'eta -hat{y}_0)]\ =& 2E_{y_0|x_0}left[(y_0-x_0'eta)E_{mathcal{T}} (x_0'eta -hat{y}_0) ight]\ =& 0 end{aligned} ]

汇总以上3个结果，有：

[ ext{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} ight]x_0 sigma^2 ]

若(mathcal{T})为随机抽取的样本，假定(E(x)=0)，当(N oinfty)时，(X'X o N ext{Cov}(x))，再对于所有(x_0)取期望，有

[egin{aligned} &E_{x_0} ext{EPE}(x_0)\ sim& sigma^2+dfrac{sigma^2}{N} E_{x_0} [x_0' ext{Cov}(x)^{-1} x_0]\ =& sigma^2+dfrac{sigma^2}{N} ext{tr} left[ ext{Cov}(x)^{-1} E_{x_0} (x_0x_0' ) ight]\ =& sigma^2+dfrac{sigma^2}{N} ext{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.