Curse of Dimensionality

2021-06-22 本文已影响0人 Boye0212

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

1 Curse of dimensionality

2 高维问题举例

2.1 高维中的 $1$ -NN

2.2 高维中的LS

参考文献

猜你喜欢

热点阅读

Curse of Dimensionality

1 Curse of dimensionality

2 高维问题举例

2.1 高维中的-NN

2.2 高维中的LS

参考文献

猜你喜欢

热点阅读

2.1 高维中的 $1$ -NN