Что такое проклятие размерности?

21

В частности, я ищу ссылки (документы, книги), которые будут строго показывать и объяснять проклятие размерности. Этот вопрос возник после того, как я начал читать эту белую бумагу по Лафферти и Вассермана. В третьем абзаце упоминается «хорошо известное» уравнение, из которого следует, что наилучшая скорость сходимости равна $n^{-4/(4-d)}$ ; если кто-то может объяснить это (и объяснить), это было бы очень полезно.

Кроме того, кто-нибудь может указать мне ссылку, которая выводит "хорошо известное" уравнение?

theory Хода
источник

7

Я не могу объяснить, но я думаю, что я слышал, что звучит как три разные версии проклятия: 1) более высокие измерения означают экспоненциально увеличивающийся объем работы, и 2) в более высоких измерениях вы получите все меньше и меньше примеров в любой части. вашего образца пространства, и 3) в больших измерениях все имеет тенденцию быть в основном равноудаленными, что затрудняет проведение каких-либо различий.

Уэйн

5

Вы можете интерпретировать это геометрически. Скажем, у вас есть сфера в D измерениях с радиусом r = 1. Затем вы можете задать вопрос о том, какая доля объема сферы находится между радиусом r = 1 и r = 1-e. Поскольку мы знаем, что объем сферы масштабируется как k (d) * r ^ (d), где d - число измерений, мы можем вывести, что доля задается как 1- (1-e) ^ d. Таким образом, для больших размерных сфер большая часть объема сосредоточена в тонкой оболочке вблизи поверхности. Подробнее об этом читайте в книге епископов «Распознавание образов и машинное обучение».

д-р Майк

@ Уэйн Конечно; плюс 5) больше тусклости обычно означает больше шума.

Доктор Майк, я не следую логике. Похоже, вы говорите, что «поскольку большая часть объема сконцентрирована в тонкой оболочке вблизи поверхности сферы высокой размерности, вы прокляты размерностью». Можете ли вы объяснить дальше, и, возможно, явно показать мне, как аналогия связана со статистикой?

Ход

9

В продолжение richiemorrisroe, вот соответствующее изображение из Элементы статистического обучения , глава 2 (стр. 22-27):

ESL стр. 25

Как видно из верхней правой панели, больше соседей на 1 единицу в 1 измерении больше, чем соседей на 1 единицу в 2 измерениях. 3 размеры были бы еще хуже!

Zach
источник

7

Это не дает прямого ответа на ваш вопрос, но у Дэвида Донохо есть хорошая статья об анализе многомерных данных: проклятия и благословения размерности (связанные слайды здесь ), в которой он упоминает три проклятия:

$D$ $(1/\epsilon)^D$ $\epsilon$
$d$ $(1/\epsilon)^D$ $\epsilon$
$D$ $(1/\epsilon)^D$ $\epsilon$

raegtin
источник

6

Я знаю, что продолжаю ссылаться на это, но есть отличное объяснение этому - Элементы Статистического Обучения , глава 2 (стр. 22-27). Они в основном отмечают, что по мере увеличения измерений объем данных должен увеличиваться (экспоненциально) вместе с ним, или не будет достаточно точек в большем пространстве выборки для проведения любого полезного анализа.

В качестве источника они ссылаются на статью Беллмана (1961), которая, по-видимому, является его книгой «Адаптивные процессы управления», доступной на Amazon здесь.

richiemorrisroe
источник

+1. Объяснение в ESL великолепно, и связанные с ним диаграммы очень помогают.

Зак

2

введите описание изображения здесь

Возможно, наиболее печально известное влияние охватывается следующим пределом (который (косвенно) показан на рисунке выше):

lim_{d i m \to \infty} \frac{d i s t_{m a x} - d i s t_{m i n}}{d i s t_{m i n}}

$\lim_{dim\rightarrow\infty}\frac{dist_{max}-dist_{min}}{dist_{min}}$

$L_2$ $k$ $L_k$

Влияние размерности на данные в картинках

Раффаэль
источник

Что такое проклятие размерности?

Ответы: