是来自 Beyer 等人的相对对比定理。论文:“关于高维空间中距离度量的令人惊讶的行为”误导?

机器算法验证 机器学习 距离函数 高维
2022-03-24 23:27:18

这在提到维度灾难时经常被引用并且去

(右手公式称为相对对比度)

limdvar(||Xd||kE[||Xd||k])=0,then:DmaxdkDmindkDmindk0

该定理的结果表明,到给定查询点的最大和最小距离之间的差异不会像到高维空间中任何点的最近距离一样快。这使得邻近查询变得毫无意义且不稳定,因为最近和最远邻居之间的区别很差。

关联

然而,如果一个人真的尝试计算样本值的相对对比度,这意味着一个人采用一个包含非常小的值的向量并计算到零向量的距离,并对一个包含更大值的向量做同样的事情,然后一个人比较这些值3 的维度和109倍大的维度,人们会看到,虽然比率确实降低了,但变化非常小,以至于与实际使用的维度数量无关(或者有人知道有人在工作吗?数据的尺寸与格雷厄姆数的大小相同——我猜这是描述论文实际相关的效果所需的大小——我认为不是)。

如前所述,这个定理经常被引用来支持这样一种说法,即在高维空间中基于欧几里得空间测量接近度是一种糟糕的策略,作者自己这么说,但所提出的行为实际上并没有发生,这让我认为这个定理被以一种误导的方式使用。

示例:带d维度

a=np.ones((d,)) / 1e5
b=np.ones((d,)) * 1e5
dmin,dmax=norm(a), norm(b)
(dmax-dmin)/dmin

对于 d=3
9999999999.0
对于 d=1e8
9999999998.9996738

并且使用 1e1 而不是 1e5(假设数据是标准化的)
对于 d=3
99.0
对于 d=1e8
98.999999999989527

2个回答

不,这个定理没有误导性。它当然可以被错误地应用,但对于任何定理都是如此。

这是一个简单的 MATLAB 脚本来演示它是如何工作的:

xd = randn(1e5,10000);
%%
cols = [1,10,100,1000,10000];
for c = cols
    xdt = table(xd(:,1:c));
    res = table2array(rowfun(@norm,xdt));
    mr = mean(res);
    res1 = var(res/mr);
    res2 = (max(res) - min(res))/min(res);
    fprintf('res1: %f, res2: %f\n',res1,res2)
end

输出:

res1: 0.568701, res2: 2562257.458668
res1: 0.051314, res2: 9.580602
res1: 0.005021, res2: 0.911065
res1: 0.000504, res2: 0.221981
res1: 0.000050, res2: 0.063720

在我的代码中, res1 和 res2 是论文中等式中的两个表达式:一个用于方差,第二个用于对比。

当维度从 1 变为 10,000 时,您可以看到两者是如何变为零的。

首先,论文的名称在您的问题中是错误的:您的意思是 Beyer 等人的这篇论文是最初介绍定理的地方,而不是Aggarwal 等人的 这篇论文,您在 OP 中错误地命名了这篇论文,并且是在论文之后写的拜尔等人。人。

接下来,您所说的“误导”是什么意思?如果出现以下情况,则会产生误导:

  1. Beyer 等人的这个定理存在一个反例,这是不可能的,因为他们在第一篇论文中的证明是正确的。我在评论中看到人们要求一个具体的例子,如下所示。

  2. 引用你的话“这个定理经常被引用来支持这样一种说法,即基于欧几里得空间测量接近度是高维空间中的一种糟糕策略,作者自己这么说,但所提出的行为实际上并没有发生,这让我认为这个定理被以一种误导的方式使用。 ”同样,bahavio(u)r 确实出现在高维中,如下面的示例系列所示:关键要素是具有随机变量生成的 iid 特征/组件iid 随机样本。

满足 Beyer 等定理假设的一系列例子。人。(相对方差 " 变为零),因此该声明也成立(相对对比度为零),在本文“分数距离的集中(Wertz. et. al.) ”中给出,它基本上指出(参见其定理 5,第 878 页)Var[||X(d)||E||X(d)||]

定理 5:如果维随机向量,则X(d)=(X1Xd)Rdd||X(d)||E||X(d)||p1Var[||X(d)||E||X(d)||]0,d.

所以这意味着如果你生成的 iid 随机样本使用一个随机向量,其分量是 iid(例如一个正常的随机向量),那么它的“相对方差 " 将归零,因此根据拜尔定理,最大范数(=距离作为原点的查询点)除以最小范数(=作为原点的查询点的距离)将收敛于概率为或等效地为“相对对比度”(即最远点和最近点之间的距离与原点,减一)也将归零。N(0,Id)Var[||X(d)||E||X(d)||]1,

PS 对于有应用意识的人,欢迎您在这里查看我的相关问题,寻求这些定理的实际应用