Проклятие размерности

Проклятие размерности относится к различным явлениям , которые возникают при анализе и организации данных в многомерных пространствах , которые не встречаются в маломерных условиях , например, трехмерного физического пространства повседневного опыта. Выражение было придумано Ричардом Э. Беллманом при рассмотрении задач динамического программирования . ^{[1] [2]}

Проклятые в измерениях явления происходят в таких областях, как численный анализ , выборка , комбинаторика , машинное обучение , интеллектуальный анализ данных и базы данных . Общая тема этих проблем заключается в том, что при увеличении размерности объем пространства увеличивается так быстро, что доступные данные становятся разреженными. Такая разреженность проблематична для любого метода, требующего статистической значимости.. Чтобы получить статистически обоснованный и надежный результат, объем данных, необходимых для подтверждения результата, часто растет экспоненциально с увеличением размерности. Кроме того, организация и поиск данных часто основываются на обнаружении областей, в которых объекты образуют группы со схожими свойствами; Однако в данных большой размерности все объекты кажутся разреженными и непохожими во многих отношениях, что не позволяет использовать общие стратегии организации данных.

Домены [ править ]

Комбинаторика [ править ]

В некоторых задачах каждая переменная может принимать одно из нескольких дискретных значений, или диапазон возможных значений делится, чтобы дать конечное число возможностей. Взяв переменные вместе, необходимо рассмотреть огромное количество комбинаций значений. Этот эффект также известен как комбинаторный взрыв . Даже в простейшем случае двоичных переменных количество возможных комбинаций уже экспоненциально по размерности. Наивно, что каждое дополнительное измерение удваивает усилия, необходимые для опробования всех комбинаций.${\displaystyle d}$${\displaystyle 2^{d}}$

Выборка [ править ]

Существует экспоненциальное увеличение объема, связанное с добавлением дополнительных измерений в математическое пространство . Например, 10 ² = 100 равномерно распределенных точек выборки достаточно для выборки единичного интервала («одномерный куб») с не более чем 10 ^-2 = 0,01 расстоянием между точками; эквивалентная выборка 10-мерного единичного гиперкуба с решеткой, имеющей интервал 10 ^-2 = 0,01 между соседними точками, потребует 10 ²⁰ = [(10 ² ) ¹⁰ ] точек выборки. В общем, с интервалом 10 ⁻ⁿ 10-мерный гиперкуб оказывается множителем 10 ^{n (10-1)} = [(10ⁿ ) ¹⁰ / (10 ⁿ )] «больше», чем одномерный гиперкуб, который представляет собой единичный интервал. В приведенном выше примере n = 2: при использовании расстояния выборки 0,01 10-мерный гиперкуб оказывается на 10 ¹⁸ "больше", чем единичный интервал. Этот эффект представляет собой комбинацию задач комбинаторики, описанных выше, и задач функции расстояния, описанных ниже.

Оптимизация [ править ]

При решении задач динамической оптимизации с помощью численной обратной индукции целевая функция должна вычисляться для каждой комбинации значений. Это серьезное препятствие, когда размерность «переменной состояния» велика. ^[3]

Машинное обучение [ править ]

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

Типичное практическое правило состоит в том, что для каждого измерения в представлении должно быть не менее 5 обучающих примеров. ^[4] В машинном обучении и постольку , поскольку предсказание производительность обеспокоена, проклятие размерности используется взаимозаменяемо с вспучиванием явлением , ^[4] , который также известен как Hughes явление . ^[5] Этот феномен утверждает, что при фиксированном количестве обучающих выборок средняя (ожидаемая) предсказательная сила классификатора или регрессора сначала увеличивается по мере увеличения количества используемых измерений или функций, но за пределами определенной размерности она начинает ухудшаться, а не улучшаться. стабильно. ^{[6] [7] [8]}

Тем не менее, в контексте простого классификатора ( линейный дискриминантный анализ в многомерной гауссовской модели в предположении общеизвестной ковариационной матрицы) Zollanvari et al. ^[9]как аналитически, так и эмпирически показали, что до тех пор, пока относительная кумулятивная эффективность дополнительного набора функций (по отношению к функциям, которые уже являются частью классификатора) больше (или меньше), чем размер этого дополнительного набора функций, ожидаемая ошибка классификатор, построенный с использованием этих дополнительных функций, будет меньше (или больше), чем ожидаемая ошибка классификатора, построенного без них. Другими словами, как размер дополнительных функций, так и их (относительный) кумулятивный дискриминационный эффект важны для наблюдения за уменьшением или увеличением средней прогностической способности.

Функции расстояния [ править ]

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

Один из способов проиллюстрировать «необъятность» многомерного евклидова пространства - это сравнить пропорцию вписанной гиперсферы с радиусом и размерностью и гиперкуба с ребрами длины . Объем такой сферы равен , где - гамма-функция , а объем куба равен . По мере увеличения размера пространства гиперсфера становится незначительным объемом по сравнению с объемом гиперкуба. Это можно ясно увидеть , сравнив пропорции, когда размерность уходит в бесконечность:${\displaystyle r}$${\displaystyle d}$${\displaystyle 2r.}$${\displaystyle {\frac {2r^{d}\pi ^{d/2}}{d\;\Gamma (d/2)}}}$ Γ {\displaystyle \Gamma } ${\displaystyle (2r)^{d}}$${\displaystyle d}$${\displaystyle d}$

${\displaystyle {\frac {V_{\mathrm {hypersphere} }}{V_{\mathrm {hypercube} }}}={\frac {\pi ^{d/2}}{d2^{d-1}\Gamma (d/2)}}\rightarrow 0}$как .${\displaystyle d\rightarrow \infty }$

Кроме того, расстояние между центром и углами равно , которое неограниченно увеличивается при фиксированном r. В этом смысле почти все многомерное пространство «далеко» от центра. В больших измерениях объем d- мерного единичного гиперкуба (с координатами вершин ) сосредоточен около сферы с радиусом для большой размерности d . Действительно, для каждой координаты среднее значение в кубе равно ${\displaystyle r{\sqrt {d}}}$${\displaystyle \pm 1}$${\displaystyle {\sqrt {d}}/{\sqrt {3}}}$${\displaystyle x_{i}}$${\displaystyle x_{i}^{2}}$

${\displaystyle \langle x_{i}^{2}\rangle ={\frac {1}{2}}\int _{-1}^{1}x^{2}dx={\frac {1}{3}}}$.

Дисперсия для равномерного распределения в кубе равна${\displaystyle x_{i}^{2}}$

${\displaystyle {\frac {1}{2}}\int _{-1}^{1}x^{4}dx-\langle x_{i}^{2}\rangle ^{2}={\frac {4}{45}}}$

Следовательно, квадрат расстояния от начала координат имеет среднее значение d / 3 и дисперсию 4 d / 45. Для больших d распределение близко к нормальному распределению со средним значением 1/3 и стандартным отклонением согласно центральной предельной теореме . Таким образом, в больших измерениях и «середина» гиперкуба, и углы пусты, а весь объем сосредоточен около сферы «промежуточного» радиуса . ${\displaystyle r^{2}=\sum _{i}x_{i}^{2}}$${\displaystyle r^{2}/d}$${\displaystyle {\frac {2}{\sqrt {45d}}}}$${\displaystyle {\sqrt {d/3}}}$

Это также помогает понять распределение хи-квадрат . Действительно, (нецентральное) распределение хи-квадрат, связанное со случайной точкой в ​​интервале [-1, 1], такое же, как распределение квадрата длины случайной точки в d- кубе. По закону больших чисел это распределение концентрируется в узкой полосе примерно в d, умноженной на квадрат стандартного отклонения (σ ² ) исходного вывода. Это освещает распределение хи-квадрат, а также показывает, что большая часть объема d- куба концентрируется около поверхности сферы радиуса .${\displaystyle \sigma {\sqrt {d}}}$

Дальнейшее развитие этого явления состоит в следующем. Любое фиксированное распределение на ℝ индуцирует распределение продуктов по точкам в ℝ ^д . Для любого фиксированного n оказывается, что минимальное и максимальное расстояние между случайной контрольной точкой Q и списком из n случайных точек данных P ₁ , ..., P _n становятся неразличимыми по сравнению с минимальным расстоянием: ^[10]

${\displaystyle \lim _{d\to \infty }E\left({\frac {\operatorname {dist} _{\max }(d)-\operatorname {dist} _{\min }(d)}{\operatorname {dist} _{\min }(d)}}\right)\to 0}$.

Это часто упоминается как функции расстояния, теряющие свою полезность (например, для критерия ближайшего соседа в алгоритмах сравнения функций) в больших измерениях. Однако недавние исследования показали , что это только трюм в искусственном сценарии , когда одномерные распределения ℝ являются независимыми и одинаково распределенными . ^[11] Когда атрибуты коррелированы, данные могут упроститься и обеспечить более высокий контраст на расстоянии, и было обнаружено, что отношение сигнал / шум играет важную роль, поэтому следует использовать выбор характеристик . ^[11]

Поиск ближайшего соседа [ править ]

Эффект усложняет поиск ближайшего соседа в многомерном пространстве. Невозможно быстро отклонить кандидатов, используя разницу в одной координате в качестве нижней границы расстояния, основанного на всех измерениях. ^{[12] [13]}

Однако недавно было замечено, что простое количество измерений не обязательно приводит к трудностям ^[14], поскольку соответствующие дополнительные измерения также могут увеличивать контраст. Кроме того, для итогового ранжирования по-прежнему полезно различать близких и дальних соседей. Однако несоответствующие ("шумовые") размеры уменьшают контраст описанным выше способом. В анализе временных рядов , где данные по своей природе являются многомерными, функции расстояния также работают надежно, пока отношение сигнал / шум достаточно велико. ^[15]

k - классификация ближайшего соседа [ править ]

Другой эффект высокой размерности на функции расстояния касается графиков k- ближайших соседей ( k -NN), построенных из набора данных с использованием функции расстояния. По мере увеличения размерности неравномерное распределение орграфа k -NN становится искаженным с пиком справа из-за появления непропорционального количества узлов , то есть точек данных, которые появляются во многих других списках k -NN других точки данных, чем в среднем. Это явление может существенно повлиять на различные методы классификации (включая k-NN классификатор ), полуобучаемое обучение и кластеризация , ^[16] , и это также влияет на поиск информации . ^[17]

Обнаружение аномалий [ править ]

В обзоре 2012 года Zimek et al. выявили следующие проблемы при поиске аномалий в данных большой размерности: ^[11]

1. Концентрация очков и расстояний: производные значения, такие как расстояния, становятся численно подобными
2. Нерелевантные атрибуты: в данных большой размерности значительное количество атрибутов может быть неактуальным.
3. Определение наборов ссылок: для локальных методов наборы ссылок часто основаны на ближайшем соседе.
4. Несравнимые оценки для разных размерностей: разные подпространства дают несравнимые оценки
5. Интерпретируемость оценок: оценки часто больше не передают смысловое значение
6. Пространство экспоненциального поиска: пространство поиска больше не может систематически сканироваться
7. Предвзятость отслеживания данных : учитывая большое пространство поиска, для любого желаемого значения может быть найдена гипотеза
8. Концентрация: одни объекты чаще встречаются в списках соседей, чем другие.

Многие из проанализированных специализированных методов решают ту или иную из этих проблем, но остается много открытых исследовательских вопросов.

Благословение размерности [ править ]

Удивительно, но несмотря на ожидаемые трудности "проклятия размерности", эвристика здравого смысла, основанная на самых простых методах, "может давать результаты, которые почти наверняка оптимальны" для задач большой размерности. ^[18] Термин «благословение размерности» был введен в конце 1990-х годов. ^[18] Донохо в своем «Манифесте тысячелетия» ясно объяснил, почему «благословение размерности» ляжет в основу будущего интеллектуального анализа данных. ^[19] Эффекты благословения размерности были обнаружены во многих приложениях и нашли свою основу в концентрации явлений меры . ^[20]Одним из примеров благословения феномена размерности является линейная отделимость случайной точки от большого конечного случайного множества с высокой вероятностью, даже если это множество экспоненциально велико: количество элементов в этом случайном множестве может экспоненциально расти вместе с размерностью. Более того, этот линейный функционал можно выбрать в виде простейшего линейного дискриминанта Фишера . Эта теорема отделимости была доказана для широкого класса распределений вероятностей: общих равномерно логарифмически вогнутых распределений, распределений произведений в кубе и многих других семейств (недавно рассмотренных в ^[20] ).

«Благословение размерности и проклятие размерности - две стороны одной медали». ^[21] Например, типичное свойство по существу многомерных распределений вероятностей в многомерном пространстве: квадрат расстояния от случайных точек до выбранной точки с высокой вероятностью близок к среднему (или среднему) квадрату расстояния. . Это свойство значительно упрощает ожидаемую геометрию данных и индексацию данных большой размерности (благословение), ^[22], но, в то же время, делает поиск подобия в больших измерениях трудным и даже бесполезным (проклятие). ^[23]

Zimek et al. ^[11] отметили, что хотя типичные формализации проклятия размерности влияют на данные iid , иметь данные, разделенные по каждому атрибуту, становится проще даже в больших измерениях, и утверждали, что отношение сигнал / шум имеет значение: данные становятся проще с каждым атрибутом. атрибут, который добавляет сигнал, и еще сложнее с атрибутами, которые только добавляют шум (несущественная ошибка) к данным. В частности, для неконтролируемого анализа данных этот эффект известен как заболачивание.

См. Также [ править ]

Ссылки [ править ]