Проклятие размерности - Curse of dimensionality

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

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

Домены

Комбинаторика

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

Отбор проб

Существует экспоненциальное увеличение объема, связанное с добавлением дополнительных измерений к математическое пространство. Например, 102= 100 равномерно расположенных точек выборки достаточно для выборки единичный интервал («одномерный куб») с не более чем 10−2= 0,01 расстояние между точками; эквивалентная выборка 10-мерного единичный гиперкуб с решеткой, имеющей шаг 10−2= 0,01 между соседними точками потребуется 1020=[(102)10] точки выборки. Как правило, с интервалом 10−n 10-мерный гиперкуб оказывается в 10 раз большеп (10-1)=[(10п)10/(10п)] «больше», чем одномерный гиперкуб, который является единичным интервалом. В приведенном выше примере n = 2: при использовании расстояния выборки 0,01 10-мерный гиперкуб выглядит как 1018 «больше», чем единичный интервал. Этот эффект представляет собой комбинацию задач комбинаторики, описанных выше, и задач функции расстояния, описанных ниже.

Оптимизация

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

Машинное обучение

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

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

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

Функции расстояния

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

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

в качестве .

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

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

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

.

Это часто упоминается как функции расстояния, теряющие свою полезность (например, для критерия ближайшего соседа в алгоритмах сравнения функций) в больших измерениях. Однако недавние исследования показали, что это справедливо только в искусственном сценарии, когда одномерные распределения ℝ находятся независимые и одинаково распределенные.[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] отметил, что хотя типичные формализации проклятия размерности влияют на i.i.d. data, иметь данные, разделенные в каждом атрибуте, становится проще даже в больших измерениях, и утверждал, что соотношение сигнал шум имеет значение: данные становятся проще с каждым атрибутом, который добавляет сигнал, и сложнее с атрибутами, которые только добавляют к данным шум (несущественная ошибка). В частности, для неконтролируемого анализа данных этот эффект известен как заболачивание.

Смотрите также

Рекомендации

  1. ^ Беллман, Ричард Эрнест; Rand Corporation (1957). Динамическое программирование. Издательство Принстонского университета. п. ix. ISBN  978-0-691-07951-6.,
    Переиздано: Беллман, Ричард Эрнест (2003). Динамическое программирование. Courier Dover Publications. ISBN  978-0-486-42809-3.
  2. ^ Беллман, Ричард Эрнест (1961). Процессы адаптивного управления: экскурсия. Издательство Принстонского университета.
  3. ^ Тейлор, К. Роберт (1993). «Динамическое программирование и проклятия размерности». Приложения динамического программирования к проблемам принятия решений в сельском хозяйстве. Westview Press. С. 1–10. ISBN  0-8133-8641-1.
  4. ^ а б Кутроумбас, Константинос; Теодоридис, Сергиос (2008). Распознавание образов (4-е изд.). Берлингтон. ISBN  978-1-59749-272-0. Получено 8 января 2018.
  5. ^ Хьюз, Г.Ф. (Январь 1968 г.). «О средней точности статистических распознавателей образов». IEEE Transactions по теории информации. 14 (1): 55–63. Дои:10.1109 / TIT.1968.1054102. S2CID  206729491.
  6. ^ Туловище, Г. В. (июль 1979 г.). «Проблема размерности: простой пример». IEEE Transactions по анализу шаблонов и машинному анализу. ПАМИ-1 (3): 306–307. Дои:10.1109 / TPAMI.1979.4766926. PMID  21868861.
  7. ^ Б. Чандрасекаран; А. К. Джайн (1974). «Сложность квантования и независимые измерения». Транзакции IEEE на компьютерах. 23 (8): 102–106. Дои:10.1109 / T-C.1974.223789.
  8. ^ Маклахлан, Дж. Дж. (2004). Дискриминантный анализ и статистическое распознавание образов. Wiley Interscience. ISBN  978-0-471-69115-0. МИСТЕР  1190469.
  9. ^ А. Золланвари; А. П. Джеймс; Р. Самени (2020). «Теоретический анализ явления пика в классификации». Журнал классификации. 37: 421–434. Дои:10.1007 / s00357-019-09327-3.
  10. ^ Бейер, К .; Goldstein, J .; Ramakrishnan, R .; Вал, У. (1999). Когда имеет значение «ближайший сосед»?. Proc. 7-я Международная конференция по теории баз данных - ICDT'99. LNCS. 1540. С. 217–235. Дои:10.1007/3-540-49257-7_15. ISBN  978-3-540-65452-0.
  11. ^ а б c d Зимек, А .; Schubert, E .; Кригель, Х.-П. (2012). «Обзор неконтролируемого обнаружения выбросов в многомерных числовых данных». Статистический анализ и интеллектуальный анализ данных. 5 (5): 363–387. Дои:10.1002 / sam.11161.
  12. ^ Marimont, R.B .; Шапиро, М. (1979). «Поиск ближайшего соседа и проклятие размерности». IMA J Appl Math. 24 (1): 59–70. Дои:10.1093 / imamat / 24.1.59.
  13. ^ Чавес, Эдгар; Наварро, Гонсало; Баеза-Йейтс, Рикардо; Маррокин, Хосе Луис (2001). «Поиск в метрических пространствах». Опросы ACM Computing. 33 (3): 273–321. CiteSeerX  10.1.1.100.7845. Дои:10.1145/502807.502808.
  14. ^ Houle, M.E .; Кригель, Х.; Kröger, P .; Schubert, E .; Зимек, А. (2010). Могут ли расстояния между общими соседями победить проклятие размерности? (PDF). Управление научно-статистической базой данных. Конспект лекций по информатике. 6187. п. 482. Дои:10.1007/978-3-642-13818-8_34. ISBN  978-3-642-13817-1.
  15. ^ Bernecker, T .; Houle, M.E .; Кригель, Х.; Kröger, P .; Ренц, М .; Schubert, E .; Зимек, А. (2011). Качество рейтингов сходства во временных рядах. Симпозиум по пространственным и временным базам данных. Конспект лекций по информатике. 6849. п. 422. Дои:10.1007/978-3-642-22922-0_25. ISBN  978-3-642-22921-3.
  16. ^ Радованович, Милош; Нанопулос, Александрос; Иванович, Мирьяна (2010). «Хабы в космосе: популярные ближайшие соседи в данных большой размерности» (PDF). Журнал исследований в области машинного обучения. 11: 2487–2531.
  17. ^ Радованович, М .; Nanopoulos, A .; Иванович, М. (2010). О существовании упорных результатов в моделях векторных пространств. 33-я международная конференция ACM SIGIR по исследованиям и разработкам в области информационного поиска - SIGIR '10. п. 186. Дои:10.1145/1835449.1835482. ISBN  9781450301534.
  18. ^ а б Кайнен, Пол К. (1997), «Использование геометрических аномалий большой размерности: когда сложность упрощает вычисления», в Kárný, M .; Уорвик, К. (ред.), Компьютерные интенсивные методы управления и обработки сигналов, стр. 283–294, Дои:10.1007/978-1-4612-1996-5_18
  19. ^ Донохо, Дэвид Л. (2000), «Анализ многомерных данных: проклятия и благословения размерности», Приглашенная лекция на конференции «Математические задачи 21 века», Национальное собрание AMS, Лос-Анджелес, Калифорния, США, 6-12 августа 2000 г., CiteSeerX  10.1.1.329.3392
  20. ^ а б Горбань Александр Николаевич; Макаров Валерий А .; Тюкин, Иван Юрьевич (2020). «Многомерный мозг в многомерном мире: благословение многомерности». Энтропия. 22 (1): 82. arXiv:2001.04959. Bibcode:2020Entrp..22 ... 82G. Дои:10.3390 / e22010082.
  21. ^ Горбань, Александр Н .; Тюкин, Иван Юрьевич (2018). «Благо размерности: математические основы статистической физики данных». Фил. Пер. R. Soc. А. 376 (2118): 20170237. arXiv:1801.03421. Bibcode:2018RSPTA.37670237G. Дои:10.1098 / rsta.2017.0237. ЧВК  5869543. PMID  29555807.
  22. ^ Хехт-Нильсен, Роберт (1994), «Контекстные векторы: самоорганизующиеся из необработанных данных представления приблизительного значения общего назначения», в Zurada, J.M .; Marks, R.J .; Робинсон, С.Дж. (ред.), Вычислительный интеллект: имитация жизни; Труды Всемирного конгресса по вычислительному интеллекту, нейронным сетям; 1994; Орландо; FL, Пискатауэй, Нью-Джерси: IEEE Press, стр. 43–56, ISBN  0780311043
  23. ^ Пестов, Владимир (2013). "Подвержено ли проклятие размерности k-NN классификатору в больших измерениях?". Comput. Математика. Приложение. 65 (10): 43–56. Дои:10.1016 / j.camwa.2012.09.011.