Является ли теорема об относительном контрасте от Beyer et al. статья: «Об удивительном поведении дистанционных метрик в многомерном пространстве» вводит в заблуждение?

Это часто упоминается, когда упоминается проклятие размерности и идет

(формула справа называется относительным контрастом)

\underset{d \to \infty}{Ит} вар (\frac{| | {Икс}_{d} | |_{К}}{Е [| | {Икс}_{d} | |_{К}]}) знак равно 0, тогда : \frac{D_{{Максимум}_{d}^{К}} - D_{{мин}_{d}^{К}}}{D_{{мин}_{d}^{К}}} \to 0

$\lim_{d\rightarrow \infty} \text{var} \left(\frac{||X_d||_k}{E[||X_d||_k]} \right) = 0, \text{then}: \frac{D_{\max^{k}_{d}} - D_{\min^{k}_{d}}}{D_{\min^{k}_{d}}} \rightarrow 0$

Результат теоремы показывает, что разница между максимальным и минимальным расстояниями до заданной точки запроса не увеличивается так же быстро, как расстояние до ближайшей к любой точке в многомерном пространстве. Это делает запрос на близость бессмысленным и нестабильным, потому что между ближайшим и самым дальним соседом существует плохая дискриминация.

ссылка на сайт

Тем не менее, если кто-то действительно пытается вычислить относительный контраст для значений выборки, то есть он берет вектор, содержащий очень маленькие значения, и вычисляет расстояние до нулевого вектора и делает то же самое для вектора, содержащего гораздо большие значения, а затем сравнивает значения для размерность 3 и размерность в раз больше, вы увидите, что, хотя соотношение действительно уменьшается, изменение настолько исчезающе мало, что не имеет значения для числа измерений, фактически используемых на практике (или кто-нибудь знает кого-нибудь, кто работает с данными, имеющими размеры, размер числа Грэма - который, я бы предположил, - это размер, необходимый для того, чтобы описанный эффект действительно соответствовал статье - я думаю, что нет). $10^9$

Как упоминалось ранее, эту теорему очень часто цитируют в поддержку утверждения, что измерение близости на основе евклидова пространства является плохой стратегией в многомерном пространстве, считают сами авторы, и тем не менее предложенное поведение фактически не имеет места, что заставляет меня думаю, что эта теорема была введена в заблуждение.

Пример: с 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

machine-learning distance-functions high-dimensional Nimitz14
источник

3 + 10^{9}

$3 + 10^9$

Вы проверяли условие на дисперсию?

Аксакал

Нет, теорема не вводит в заблуждение. Это, конечно, может быть применено неправильно, но это верно для любой теоремы.

Вот простой скрипт 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 до 10000.

Аксакал
источник

Теперь я чувствую, что возникает вопрос: для каких распределений Xпроисходит дисперсия, сводящаяся к нулю?

Nimitz14

@ Nimitz14 Это был бы отличный вопрос, который можно задать сам по себе.

Sycorax говорит восстановить Monica

@ Nimitz14 эта теорема не должна работать для Коши, вы можете легко проверить ее, заменив обычную на студент t (1). В противном случае, я думаю, что все регулярные дистрибутивы, такие как нормальное, равномерное, бета и т. Д. Должны быть покрыты

Аксакал

Ответы: