如何理解 curse of dimensionality - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>DataSciences - 数据科学

如何理解 curse of dimensionality

如何理解 curse of dimensionality# DataSciences - 数据科学

x*02015-04-12 07:04

1 楼

前几天和人讨论dimensional reduction,有人提到这个 curse of dimensionality。自
己不是科班出身，不太明白怎么回事，所以回来查了一下。
目前我自己的理解是：dimension 越多，需要的数据量就呈几何增长，比如，1-
dimension 需要10个sample的话，2-dimension 就需要 100个， 3-dimension 就需要
1000个，4-dimension 就需要 10000个，...
请问我的理解对么？或者有没有其他含义我没领会到？
谢谢

d*e2015-04-12 07:04

2 楼

最简单的理解是，维度越高，需要估计的参数就越多，这种情况下，如果要保障所有的
参数同时都能估计准，就变得很难。
下面给你举个简单的例子。比如我们有n个iid sample X_1,...,X_n来自一个d维的正态
分布N(0,I)。假设Mean不知道，我们要估计Mean。如果我们用sample mean X_bar来估
计的话，我们知道这个estimator的分布是N(0,I/n)。那么这时，我们知道2-norm的估
计误差的期望是E||X_bar-0||_2^2 = d/n. 这就意味着，如果你想要2-norm的估计误差
的期望小于0.1（我们姑且认为小于0.1就是准确的），那么你需要n>10d.
不存在curse of dimensionality的情况一般是指样本数量n远大于维度d，比如n=1e5，
而d=10，这种情况下，我们能拿到一个准确的估计。
而对于curse of dimensionality的情况，样本数量n稍稍大于d，或者小于d，这种情况
下，拿到一个准确的估计就不太可能了。
以上的问题比较简答，基本是要求n>常数＊d就可以了。对于更复杂的模型，我们可能
需要n>常数＊d的多项式，甚至n>常数＊exp(d的多项式)，这就属于你说的情况。
所以curse of dimensionality另一个说法就是small sample size，样本太少，不够用。
不知道这么说你能不能理解。

要

【在 x*********0 的大作中提到】

: 前几天和人讨论dimensional reduction,有人提到这个 curse of dimensionality。自
: 己不是科班出身，不太明白怎么回事，所以回来查了一下。
: 目前我自己的理解是：dimension 越多，需要的数据量就呈几何增长，比如，1-
: dimension 需要10个sample的话，2-dimension 就需要 100个， 3-dimension 就需要
: 1000个，4-dimension 就需要 10000个，...
: 请问我的理解对么？或者有没有其他含义我没领会到？
: 谢谢

c*h2015-04-12 07:04

3 楼

所以就产生了manifold learning这样的奇葩研究

【在 d******e 的大作中提到】

: 最简单的理解是，维度越高，需要估计的参数就越多，这种情况下，如果要保障所有的
: 参数同时都能估计准，就变得很难。
: 下面给你举个简单的例子。比如我们有n个iid sample X_1,...,X_n来自一个d维的正态
: 分布N(0,I)。假设Mean不知道，我们要估计Mean。如果我们用sample mean X_bar来估
: 计的话，我们知道这个estimator的分布是N(0,I/n)。那么这时，我们知道2-norm的估
: 计误差的期望是E||X_bar-0||_2^2 = d/n. 这就意味着，如果你想要2-norm的估计误差
: 的期望小于0.1（我们姑且认为小于0.1就是准确的），那么你需要n>10d.
: 不存在curse of dimensionality的情况一般是指样本数量n远大于维度d，比如n=1e5，
: 而d=10，这种情况下，我们能拿到一个准确的估计。
: 而对于curse of dimensionality的情况，样本数量n稍稍大于d，或者小于d，这种情况

d*e2015-04-12 07:04

4 楼

我说的和manifold learning还是差个十万八千里的... ...
而且对于所有依赖于使用Euclidean distance和Local Linearity来做的manifold
learning方法来说，Curse of dimensionality都无法避免。

【在 c*******h 的大作中提到】

: 所以就产生了manifold learning这样的奇葩研究

z*e2015-04-12 07:04

5 楼

或者另一个简单的理解是同样的误差程度，维度越大，偏离真实值的程度就越大。

【在 d******e 的大作中提到】

x*02015-04-12 07:04

6 楼

谢谢。
那是否可以说：只要我们有足够多的sample,curse of dimensionality 就不存在了？

p*o2015-04-12 07:04

7 楼

上面的回答不完全对。drburnie 回答的是large p small n 导致的问题。这不是传统
意义上的curse of dimensionality。这个词是专在non parametric estimation 里才
用到的，近几年却因为high dim 的火热被人张冠李戴了很多。
直观解释的确是需要的数据随着dim 增加而迅速增长。但最早是专指kernel density
estimation 中收敛速度会变慢。估计density 时，把数据按照小窗口来分，一个一个
小窗口来估计。单位面积内分割的小窗口的个数是维度的指数，如果每个小方格里需要
一个点，在三维下就已经需要1000个数据了。这个困难扩展到kernel smoothing 和其
他的non parametric regression。
如果把curse of dim 理解成“估计的精确度随着维数增加而下降”，那就作为一个现
象永远存在。无论有多少样本，无论维数是多少。哪怕样本数是10000，或者更多，只
要维数增加了，哪怕只是从2加到3，它还是存在。

d*e2015-04-12 07:04

8 楼

你好歹看完我的帖子再判断我说的是什么... ...
我后面说了更复杂的模型，根本不是直接比较d和n。
LZ根本不是统计专业，让他来理解nonparametric太困难了。
BTW：你可以问问LZ你那KDE的解释方式，他能理解多少。

【在 p***o 的大作中提到】

: 上面的回答不完全对。drburnie 回答的是large p small n 导致的问题。这不是传统
: 意义上的curse of dimensionality。这个词是专在non parametric estimation 里才
: 用到的，近几年却因为high dim 的火热被人张冠李戴了很多。
: 直观解释的确是需要的数据随着dim 增加而迅速增长。但最早是专指kernel density
: estimation 中收敛速度会变慢。估计density 时，把数据按照小窗口来分，一个一个
: 小窗口来估计。单位面积内分割的小窗口的个数是维度的指数，如果每个小方格里需要
: 一个点，在三维下就已经需要1000个数据了。这个困难扩展到kernel smoothing 和其
: 他的non parametric regression。
: 如果把curse of dim 理解成“估计的精确度随着维数增加而下降”，那就作为一个现
: 象永远存在。无论有多少样本，无论维数是多少。哪怕样本数是10000，或者更多，只

T*u2015-04-12 07:04

9 楼

其实身边就有这样的例子。本来大家都住平房，出门就能看到人，来来去去打招呼热热
闹闹的，找个人办个事也方便，方法就是吆喝一声；后来都搬到100层的高层去了，还
是那么多人，一层住不了几个，每天打开门跟闹鬼一样，一个人也看不到，再吆喝也没
人应，跟闹鬼似的。平房的沟通方法都失效了，因为他们被高层curse了，所以叫---。

c*h2015-04-12 07:04

10 楼

联系在于高维情况下数据的渐近性难以实现。人们当初设想如果数据在流型上的话，
相当于有效的减少了维度。但关键是一这没有足够的数学工具去建立流型上的统计，
二是做研究的人很少懂流型，基本上都是欧氏几何去照搬。局部线性和局部欧不是
一个概念；局部线性是一个微分概念。所以与其说是流型学习，还不如说是曲面学
习。但无论怎样，统计分布都应该建立在微分几何或者流型上的微积分上。你要真
能把人脸从不同角度和光照下拍出来的照片局部同胚到三维球面上来，自然就没有
了curse of dimensionality

【在 d******e 的大作中提到】

: 我说的和manifold learning还是差个十万八千里的... ...
: 而且对于所有依赖于使用Euclidean distance和Local Linearity来做的manifold
: learning方法来说，Curse of dimensionality都无法避免。

d*e2015-04-12 07:04

11 楼

So what's your point?
你有免于curse of dimensionality的manifold learning方法？

【在 c*******h 的大作中提到】

: 联系在于高维情况下数据的渐近性难以实现。人们当初设想如果数据在流型上的话，
: 相当于有效的减少了维度。但关键是一这没有足够的数学工具去建立流型上的统计，
: 二是做研究的人很少懂流型，基本上都是欧氏几何去照搬。局部线性和局部欧不是
: 一个概念；局部线性是一个微分概念。所以与其说是流型学习，还不如说是曲面学
: 习。但无论怎样，统计分布都应该建立在微分几何或者流型上的微积分上。你要真
: 能把人脸从不同角度和光照下拍出来的照片局部同胚到三维球面上来，自然就没有
: 了curse of dimensionality

c*h2015-04-12 07:04

12 楼

the point is that manifold learning as an attempt for alleviating
the challenge of high dimensionality is far from being grounded.

【在 d******e 的大作中提到】

: So what's your point?
: 你有免于curse of dimensionality的manifold learning方法？