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

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

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

Домены

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

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

Выборка

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

Оптимизация

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

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

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

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

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

При метрическом обучении более высокие измерения иногда могут позволить модели достичь более высокой производительности. После нормализации встраивания на поверхность гиперсферы FaceNet достигает наилучшей производительности, используя 128 измерений, а не 64, 256 или 512 измерений в одном исследовании абляции. ^[11] Было обнаружено, что функция потерь для унитарно-инвариантного несходства между вложениями слов минимизируется в больших размерностях. ^[12]

Интеллектуальный анализ данных

Генетические мутации в наборе данных отдельных лиц
Индивидуальное имя	Ген 1	Ген 2	...	Джин 2000
Индивидуальный 1	1	0	...	1
...	...	...	...	...
Индивидуальный 200	0	1	...	1

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

Рассмотрим первую таблицу, в которой изображены 200 человек и 2000 генов (особенностей), где 1 или 0 обозначают, есть ли у них генетическая мутация в этом гене. Приложение для интеллектуального анализа этого набора данных может находить корреляцию между конкретными генетическими мутациями и создавать алгоритм классификации, такой как дерево решений, чтобы определить, болен ли человек раком или нет.

Рост перестановок ассоциативных пар по мере увеличения размера пары
Число пар	Расчет на перестановки	Количество перестановок рассчитывается для каждой строки
2	$2000!/(2000-2)!$	3 998 000
3	$2000!/(2000-3)!$	7 988 004 000
4	$2000!/(2000-4)!$	15 952 043 988 000
5	$2000!/(2000-5)!$	31 840 279 800 048 000

Обычной практикой интеллектуального анализа данных в этой области является создание правил ассоциации между генетическими мутациями, которые приводят к развитию рака. Чтобы сделать это, нужно будет просмотреть каждую генетическую мутацию каждого человека и найти другие генетические мутации, которые происходят сверх желаемого порога, и создать пары. Они начнут с пар по два, затем по три, затем по четыре, пока не останется пустой набор пар. Сложность этого алгоритма может привести к вычислению всех перестановок пар генов для каждого человека или строки. Учитывая формулу для расчета перестановок n предметов с размером группы r: ${\frac {n!}{(n-r)!}}$ , вычисление количества трех парных перестановок любого конкретного человека составит 7988004000 различных пар генов, которые необходимо оценить для каждого человека. Число создаваемых пар будет увеличиваться на порядок факториала по мере увеличения размера пар. Рост изображен в таблице перестановок (см. справа).

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

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

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

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

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

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

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

{\frac {V_{\mathrm {hypersphere} }}{V_{\mathrm {hypercube} }}}={\frac {\pi ^{d/2}}{d2^{d-1}\Gamma (d/2)}}\rightarrow 0

как

d\rightarrow \infty

.

Кроме того, расстояние между центром и углами равно $r{\sqrt {d}}$ , которая неограниченно возрастает при фиксированном r.

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

\left\langle x_{i}^{2}\right\rangle ={\frac {1}{2}}\int _{-1}^{1}x^{2}dx={\frac {1}{3}}

.

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

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

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

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

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

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

.

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

Совсем недавно было высказано предположение, что в аргументе о том, что потеря контраста создает проклятие в больших измерениях, может быть концептуальная ошибка. Машинное обучение можно понимать как проблему присвоения экземпляров соответствующему генеративному процессу происхождения, при этом метки классов действуют как символические представления отдельных генеративных процессов. Вывод проклятия предполагает, что все случаи являются независимыми, идентичными результатами единого многомерного порождающего процесса. Если бы существовал только один порождающий процесс, существовал бы только один (естественный) класс, и машинное обучение было бы концептуально плохо определено как в высоких, так и в низких измерениях. Таким образом, традиционный аргумент о том, что потеря контраста создает проклятие, может быть в корне неуместным. Кроме того, было показано, что когда генеративная модель модифицируется для включения нескольких генеративных процессов, потеря контраста может превратиться из проклятия в благословение, поскольку это гарантирует, что ближайший сосед экземпляра почти наверняка будет наиболее близким к нему. связанный экземпляр. С этой точки зрения потеря контраста делает большие расстояния особенно значимыми, а не особенно незначимыми, как часто утверждают. ^[16]

Поиск ближайшего соседа

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

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

k - классификация ближайших соседей

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

Обнаружение аномалий

В исследовании 2012 года Зимек и др. выявил следующие проблемы при поиске аномалий в многомерных данных: ^[15]

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

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

Благословение размерности

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

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

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

См. также

Ссылки

^ Беллман, Ричард Эрнест; Рэнд Корпорейшн (1957). Динамическое программирование . Издательство Принстонского университета. п. ix. ISBN 978-0-691-07951-6 . ,
Переиздано: Беллман, Ричард Эрнест (2003). Динамическое программирование . Публикации Курьера Дувра. ISBN 978-0-486-42809-3 .
^ Беллман, Ричард Эрнест (1961). Процессы адаптивного управления: экскурсия . Издательство Принстонского университета. ISBN 9780691079011 .
^ Тейлор, К. Роберт (1993). «Динамическое программирование и проклятия размерности» . Применение динамического программирования к задачам принятия решений в сельском хозяйстве . Вествью Пресс. стр. 1–10. ISBN 0-8133-8641-1 .
^ Udacity (23 февраля 2015 г.). «Проклятие размерности – Технологический институт Джорджии – Машинное обучение» . Ютуб . Проверено 29 июня 2022 г.
^ Перейти обратно: ^а ^б Кутрумбас, Константинос; Теодоридис, Сергиос (2008). Распознавание образов (4-е изд.). Берлингтон. ISBN 978-1-59749-272-0 . Проверено 8 января 2018 г. {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
^ Хьюз, Г.Ф. (январь 1968 г.). «О средней точности статистических распознавателей образов». Транзакции IEEE по теории информации . 14 (1): 55–63. дои : 10.1109/TIT.1968.1054102 . S2CID 206729491 .
^ Транк, Г.В. (июль 1979 г.). «Проблема размерности: простой пример». Транзакции IEEE по анализу шаблонов и машинному интеллекту . ПАМИ-1 (3): 306–307. дои : 10.1109/TPAMI.1979.4766926 . ПМИД 21868861 . S2CID 13086902 .
^ Б. Чандрасекаран; А. К. Джайн (1974). «Сложность квантования и независимые измерения». Транзакции IEEE на компьютерах . 23 (8): 102–106. дои : 10.1109/TC.1974.223789 . S2CID 35360973 .
^ Маклахлан, Дж.Дж. (2004). Дискриминантный анализ и статистическое распознавание образов . Уайли Интерсайенс. ISBN 978-0-471-69115-0 . МР 1190469 .
^ Золланвари, А.; Джеймс, AP; Самени, Р. (2020). «Теоретический анализ феномена пика в классификации». Журнал классификации . 37 (2): 421–434. дои : 10.1007/s00357-019-09327-3 . S2CID 253851666 .
^ Шрофф, Флориан; Калениченко Дмитрий; Филбин, Джеймс (июнь 2015 г.). «FaceNet: унифицированное внедрение для распознавания лиц и кластеризации» (PDF) . Конференция IEEE 2015 по компьютерному зрению и распознаванию образов (CVPR) . стр. 815–823. arXiv : 1503.03832 . дои : 10.1109/CVPR.2015.7298682 . ISBN 978-1-4673-6964-0 . S2CID 206592766 .
^ Инь, Цзы; Шен, Юаньюань (2018). «О размерности встраивания слов» (PDF) . Достижения в области нейронных систем обработки информации . 31 . Карран Ассошиэйтс, Инк.
^ Бейли, Д.Х.; Борвейн, Дж. М.; Крэндалл, Р.Э. (2006), «Боксовые интегралы», Журнал вычислительной и прикладной математики , 206 : 196–208, doi : 10.1016/j.cam.2006.06.010 , S2CID 2763194
^ Бейер, К.; Гольдштейн, Дж.; Рамакришнан, Р.; Шафт, У. (1999). «Когда имеет смысл слово «ближайший сосед»?». Теория баз данных — ICDT'99 . ЛНКС. Том. 1540. стр. 217–235. дои : 10.1007/3-540-49257-7_15 . ISBN 978-3-540-65452-0 . S2CID 206634099 .
^ Перейти обратно: ^а ^б ^с ^д Зимек, А.; Шуберт, Э.; Кригель, Х.-П. (2012). «Опрос по неконтролируемому обнаружению выбросов в многомерных числовых данных». Статистический анализ и интеллектуальный анализ данных . 5 (5): 363–387. дои : 10.1002/sam.11161 . S2CID 6724536 .
^ Линь, Вэнь-Янь; Лю, Сыин; Рен, Чанхао; Чунг, Нгай-Ман; Ли, Гонконг; Мацусита, Ясуюки (2021). «Теория оболочек: статистическая модель реальности» . Транзакции IEEE по анализу шаблонов и машинному интеллекту . 44 (10): 6438–6453. дои : 10.1109/TPAMI.2021.3084598 . ISSN 1939-3539 . ПМИД 34048335 . S2CID 235242104 .
^ Маримонт, РБ; Шапиро, МБ (1979). «Поиски ближайших соседей и проклятие размерности». IMA J Appl Math . 24 (1): 59–70. дои : 10.1093/имамат/24.1.59 .
^ Чавес, Эдгар; Наварро, Гонсало; Баеза-Йейтс, Рикардо; Маррокин, Хосе Луис (2001). «Поиск в метрических пространствах». Обзоры вычислительной техники ACM . 33 (3): 273–321. CiteSeerX 10.1.1.100.7845 . дои : 10.1145/502807.502808 . S2CID 3201604 .
^ Хоул, Мэн; Кригель, HP ; Крегер, П.; Шуберт, Э.; Зимек, А. (2010). Могут ли расстояния между общими соседями победить проклятие размерности? (PDF) . Управление научными и статистическими базами данных. Конспекты лекций по информатике. Том. 6187. с. 482. дои : 10.1007/978-3-642-13818-8_34 . ISBN 978-3-642-13817-1 .
^ Бернекер, Т.; Хоул, Мэн; Кригель, HP ; Крегер, П.; Ренц, М.; Шуберт, Э.; Зимек, А. (2011). Качество ранжирования сходства во временных рядах . Симпозиум по пространственным и временным базам данных. Конспекты лекций по информатике. Том. 6849. с. 422. дои : 10.1007/978-3-642-22922-0_25 . ISBN 978-3-642-22921-3 .
^ Радованович, Милош; Нанопулос, Александрос; Иванович, Мирьяна (2010). «Хабы в космосе: популярные ближайшие соседи в многомерных данных» (PDF) . Журнал исследований машинного обучения . 11 : 2487–2531.
^ Радованович, М.; Нанопулос, А.; Иванович, М. (2010). О существовании упрямых результатов в моделях векторного пространства . 33-я международная конференция ACM SIGIR по исследованиям и разработкам в области информационного поиска - SIGIR '10. п. 186. дои : 10.1145/1835449.1835482 . ISBN 9781450301534 .
^ Перейти обратно: ^а ^б Кайнен, Пол К. (1997), «Использование геометрических аномалий большой размерности: когда сложность упрощает вычисления», в Карни, М.; Уорвик, К. (ред.), Интенсивные компьютерные методы управления и обработки сигналов , стр. 283–294, doi : 10.1007/978-1-4612-1996-5_18 , ISBN 978-1-4612-7373-8
^ Донохо, Дэвид Л. (2000), «Анализ многомерных данных: проклятия и благословения размерности», приглашенная лекция на тему «Математические проблемы 21 века», Национальное собрание AMS, Лос-Анджелес, Калифорния, США, 6–12 августа, 2000 , CiteSeerX 10.1.1.329.3392.
^ Перейти обратно: ^а ^б Горбань, Александр Н. ; Макаров Валерий А.; Тюкин, Иван Юрьевич (2020). «Многомерный мозг в многомерном мире: благословение размерности» . Энтропия . 22 (1): 82. arXiv : 2001.04959 . Бибкод : 2020Entrp..22...82G . дои : 10.3390/e22010082 . ПМЦ 7516518 . PMID 33285855 .
^ Горбань, Александр Н.; Тюкин, Иван Юрьевич (2018). «Благословение размерности: математические основы статистической физики данных» . Фил. Пер. Р. Сок. А. 376 (2118): 20170237.arXiv : 1801.03421 . Бибкод : 2018RSPTA.37670237G . дои : 10.1098/rsta.2017.0237 . ПМК 5869543 . ПМИД 29555807 .
^ Хехт-Нильсен, Роберт (1994), «Векторы контекста: приблизительные представления значения общего назначения, самоорганизующиеся на основе необработанных данных», в Зураде, Дж. М.; Маркс, Р.Дж.; Робинсон, CJ (ред.), Вычислительный интеллект: имитация жизни; Труды Всемирного конгресса по вычислительному интеллекту, нейронным сетям; 1994 год; Орландо; Флорида , Пискатауэй, Нью-Джерси: IEEE Press, стр. 43–56, ISBN. 0780311043
^ Пестов, Владимир (2013). «Влияет ли на классификатор k-NN в больших измерениях проклятие размерности?» . Вычислить. Математика. Приложение . 65 (10): 43–56. дои : 10.1016/j.camwa.2012.09.011 .

[1] Беллман, Ричард Эрнест; Рэнд Корпорейшн (1957). Динамическое программирование . Издательство Принстонского университета. п. ix. ISBN 978-0-691-07951-6 . ,
Переиздано: Беллман, Ричард Эрнест (2003). Динамическое программирование . Публикации Курьера Дувра. ISBN 978-0-486-42809-3 .

[2] Беллман, Ричард Эрнест (1961). Процессы адаптивного управления: экскурсия . Издательство Принстонского университета. ISBN 9780691079011 .

[3] Тейлор, К. Роберт (1993). «Динамическое программирование и проклятия размерности» . Применение динамического программирования к задачам принятия решений в сельском хозяйстве . Вествью Пресс. стр. 1–10. ISBN 0-8133-8641-1 .

[4] Udacity (23 февраля 2015 г.). «Проклятие размерности – Технологический институт Джорджии – Машинное обучение» . Ютуб . Проверено 29 июня 2022 г.

[Pattern_recog-5] Перейти обратно: ^а ^б Кутрумбас, Константинос; Теодоридис, Сергиос (2008). Распознавание образов (4-е изд.). Берлингтон. ISBN 978-1-59749-272-0 . Проверено 8 января 2018 г. {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

[6] Хьюз, Г.Ф. (январь 1968 г.). «О средней точности статистических распознавателей образов». Транзакции IEEE по теории информации . 14 (1): 55–63. дои : 10.1109/TIT.1968.1054102 . S2CID 206729491 .

[7] Транк, Г.В. (июль 1979 г.). «Проблема размерности: простой пример». Транзакции IEEE по анализу шаблонов и машинному интеллекту . ПАМИ-1 (3): 306–307. дои : 10.1109/TPAMI.1979.4766926 . ПМИД 21868861 . S2CID 13086902 .

[8] Б. Чандрасекаран; А. К. Джайн (1974). «Сложность квантования и независимые измерения». Транзакции IEEE на компьютерах . 23 (8): 102–106. дои : 10.1109/TC.1974.223789 . S2CID 35360973 .

[McLachlan:2004-9] Маклахлан, Дж.Дж. (2004). Дискриминантный анализ и статистическое распознавание образов . Уайли Интерсайенс. ISBN 978-0-471-69115-0 . МР 1190469 .

[zollanvari-10] Золланвари, А.; Джеймс, AP; Самени, Р. (2020). «Теоретический анализ феномена пика в классификации». Журнал классификации . 37 (2): 421–434. дои : 10.1007/s00357-019-09327-3 . S2CID 253851666 .

[11] Шрофф, Флориан; Калениченко Дмитрий; Филбин, Джеймс (июнь 2015 г.). «FaceNet: унифицированное внедрение для распознавания лиц и кластеризации» (PDF) . Конференция IEEE 2015 по компьютерному зрению и распознаванию образов (CVPR) . стр. 815–823. arXiv : 1503.03832 . дои : 10.1109/CVPR.2015.7298682 . ISBN 978-1-4673-6964-0 . S2CID 206592766 .

[12] Инь, Цзы; Шен, Юаньюань (2018). «О размерности встраивания слов» (PDF) . Достижения в области нейронных систем обработки информации . 31 . Карран Ассошиэйтс, Инк.

[Bailey2006-13] Бейли, Д.Х.; Борвейн, Дж. М.; Крэндалл, Р.Э. (2006), «Боксовые интегралы», Журнал вычислительной и прикладной математики , 206 : 196–208, doi : 10.1016/j.cam.2006.06.010 , S2CID 2763194

[14] Бейер, К.; Гольдштейн, Дж.; Рамакришнан, Р.; Шафт, У. (1999). «Когда имеет смысл слово «ближайший сосед»?». Теория баз данных — ICDT'99 . ЛНКС. Том. 1540. стр. 217–235. дои : 10.1007/3-540-49257-7_15 . ISBN 978-3-540-65452-0 . S2CID 206634099 .

[survey-15] Перейти обратно: ^а ^б ^с ^д Зимек, А.; Шуберт, Э.; Кригель, Х.-П. (2012). «Опрос по неконтролируемому обнаружению выбросов в многомерных числовых данных». Статистический анализ и интеллектуальный анализ данных . 5 (5): 363–387. дои : 10.1002/sam.11161 . S2CID 6724536 .

[16] Линь, Вэнь-Янь; Лю, Сыин; Рен, Чанхао; Чунг, Нгай-Ман; Ли, Гонконг; Мацусита, Ясуюки (2021). «Теория оболочек: статистическая модель реальности» . Транзакции IEEE по анализу шаблонов и машинному интеллекту . 44 (10): 6438–6453. дои : 10.1109/TPAMI.2021.3084598 . ISSN 1939-3539 . ПМИД 34048335 . S2CID 235242104 .

[17] Маримонт, РБ; Шапиро, МБ (1979). «Поиски ближайших соседей и проклятие размерности». IMA J Appl Math . 24 (1): 59–70. дои : 10.1093/имамат/24.1.59 .

[18] Чавес, Эдгар; Наварро, Гонсало; Баеза-Йейтс, Рикардо; Маррокин, Хосе Луис (2001). «Поиск в метрических пространствах». Обзоры вычислительной техники ACM . 33 (3): 273–321. CiteSeerX 10.1.1.100.7845 . дои : 10.1145/502807.502808 . S2CID 3201604 .

[houle-ssdbm10-19] Хоул, Мэн; Кригель, HP ; Крегер, П.; Шуберт, Э.; Зимек, А. (2010). Могут ли расстояния между общими соседями победить проклятие размерности? (PDF) . Управление научными и статистическими базами данных. Конспекты лекций по информатике. Том. 6187. с. 482. дои : 10.1007/978-3-642-13818-8_34 . ISBN 978-3-642-13817-1 .

[houle-sstd11-20] Бернекер, Т.; Хоул, Мэн; Кригель, HP ; Крегер, П.; Ренц, М.; Шуберт, Э.; Зимек, А. (2011). Качество ранжирования сходства во временных рядах . Симпозиум по пространственным и временным базам данных. Конспекты лекций по информатике. Том. 6849. с. 422. дои : 10.1007/978-3-642-22922-0_25 . ISBN 978-3-642-22921-3 .

[21] Радованович, Милош; Нанопулос, Александрос; Иванович, Мирьяна (2010). «Хабы в космосе: популярные ближайшие соседи в многомерных данных» (PDF) . Журнал исследований машинного обучения . 11 : 2487–2531.

[22] Радованович, М.; Нанопулос, А.; Иванович, М. (2010). О существовании упрямых результатов в моделях векторного пространства . 33-я международная конференция ACM SIGIR по исследованиям и разработкам в области информационного поиска - SIGIR '10. п. 186. дои : 10.1145/1835449.1835482 . ISBN 9781450301534 .

[Kainen1997-23] Перейти обратно: ^а ^б Кайнен, Пол К. (1997), «Использование геометрических аномалий большой размерности: когда сложность упрощает вычисления», в Карни, М.; Уорвик, К. (ред.), Интенсивные компьютерные методы управления и обработки сигналов , стр. 283–294, doi : 10.1007/978-1-4612-1996-5_18 , ISBN 978-1-4612-7373-8

[Donoho2000-24] Донохо, Дэвид Л. (2000), «Анализ многомерных данных: проклятия и благословения размерности», приглашенная лекция на тему «Математические проблемы 21 века», Национальное собрание AMS, Лос-Анджелес, Калифорния, США, 6–12 августа, 2000 , CiteSeerX 10.1.1.329.3392.

[GorbanEntr2020-25] Перейти обратно: ^а ^б Горбань, Александр Н. ; Макаров Валерий А.; Тюкин, Иван Юрьевич (2020). «Многомерный мозг в многомерном мире: благословение размерности» . Энтропия . 22 (1): 82. arXiv : 2001.04959 . Бибкод : 2020Entrp..22...82G . дои : 10.3390/e22010082 . ПМЦ 7516518 . PMID 33285855 .

[GorTyukPhTranRS2018-26] Горбань, Александр Н.; Тюкин, Иван Юрьевич (2018). «Благословение размерности: математические основы статистической физики данных» . Фил. Пер. Р. Сок. А. 376 (2118): 20170237.arXiv : 1801.03421 . Бибкод : 2018RSPTA.37670237G . дои : 10.1098/rsta.2017.0237 . ПМК 5869543 . ПМИД 29555807 .

[Hecht1994-27] Хехт-Нильсен, Роберт (1994), «Векторы контекста: приблизительные представления значения общего назначения, самоорганизующиеся на основе необработанных данных», в Зураде, Дж. М.; Маркс, Р.Дж.; Робинсон, CJ (ред.), Вычислительный интеллект: имитация жизни; Труды Всемирного конгресса по вычислительному интеллекту, нейронным сетям; 1994 год; Орландо; Флорида , Пискатауэй, Нью-Джерси: IEEE Press, стр. 43–56, ISBN. 0780311043

[PestovCamwa2013-28] Пестов, Владимир (2013). «Влияет ли на классификатор k-NN в больших измерениях проклятие размерности?» . Вычислить. Математика. Приложение . 65 (10): 43–56. дои : 10.1016/j.camwa.2012.09.011 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]