Случайная проекция

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

Уменьшение размерности

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

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

Метод

Основная идея случайного проецирования выражена в лемме Джонсона-Линденштрауса : ^[2] который гласит, что если точки в векторном пространстве имеют достаточно высокую размерность, то их можно спроецировать в подходящее пространство меньшей размерности таким образом, чтобы с высокой вероятностью приблизительно сохранялись попарные расстояния между точками.

При случайном проецировании исходные d-мерные данные проецируются в k-мерное (k << d) подпространство с использованием случайного $k\times d$ - размерная матрица R, столбцы которой имеют единичную длину. ^{[ нужна ссылка ]} Используя матричную запись: Если $X_{d\times N}$ — исходный набор N d-мерных наблюдений, тогда $X_{k\times N}^{RP}=R_{k\times d}X_{d\times N}$ — это проекция данных на нижнее k-мерное подпространство. Случайное проецирование вычислительно просто: сформируйте случайную матрицу «R» и спроецируйте $d\times N$ матрица данных X на K измерений порядка $O(dkN)$ . Если матрица данных X разрежена и содержит около c ненулевых записей на столбец, то сложность этой операции имеет порядок $O(ckN)$ . ^[3]

Гауссова случайная проекция

Случайная матрица R может быть сгенерирована с использованием распределения Гаусса. Первая строка представляет собой случайный единичный вектор, равномерно выбранный из $S^{d-1}$ . Вторая строка представляет собой случайный единичный вектор из пространства, ортогонального первой строке, третья строка представляет собой случайный единичный вектор из пространства, ортогонального первым двум строкам, и так далее. При таком способе выбора R удовлетворяются следующие свойства:

Сферическая симметрия: для любой ортогональной матрицы. $A\in O(d)$ , RA и R имеют одинаковое распределение.
Ортогональность: строки R ортогональны друг другу.
Нормальность: строки R представляют собой векторы единичной длины.

Более эффективные в вычислительном отношении случайные проекции

Ахлиоптас ^[4] показал, что распределение Гаусса можно заменить гораздо более простым распределением, таким как

R_{i,j}={\sqrt {3}}\times {\begin{cases}+1&{\text{with probability }}{\frac {1}{6}}\\0&{\text{with probability }}{\frac {2}{3}}\\-1&{\text{with probability }}{\frac {1}{6}}\end{cases}}

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

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

Случайная проекция с квантованием

Случайная проекция может быть дополнительно уплотнена путем квантования (дискретизации) с помощью 1-битной (знаковая случайная проекция) или многобитовой. Это строительный блок SimHash, ^[7] дерево РП, ^[8] и другие эффективные методы оценки и обучения памяти. ^[9]^[10]

Большие квазиортогональные базы

Лемма Джонсона -Линденштрауса утверждает, что большие наборы векторов в многомерном пространстве могут быть линейно отображены в пространство гораздо меньшей (но все же высокой) размерности n с приблизительным сохранением расстояний. Одним из объяснений этого эффекта является экспоненциально высокая квазиортогональная размерность n -мерного евклидова пространства . ^[11] –мерном евклидовом пространстве существуют экспоненциально большие (в размерности n ) множества почти ортогональных векторов (с малым значением скалярного произведения ) В n . Это наблюдение полезно при индексировании многомерных данных. ^[12]

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

Реализации

RandPro — пакет R для случайного проецирования. ^[14]^[15]
sklearn.random_projection — модуль случайного проецирования из scikit-learn . библиотеки Python
Реализация Weka [1]

См. также

Ссылки

^ Элла, Бингхэм; Хейкки, Маннила (2001). «Случайная проекция при уменьшении размерности: приложения к изображениям и текстовым данным». KDD-2001: Материалы седьмой Международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных . Нью-Йорк: Ассоциация вычислительной техники. стр. 245–250. CiteSeerX 10.1.1.24.5135 . дои : 10.1145/502512.502546 .
^ Джонсон, Уильям Б .; Линденштраусс, Йорам (1984). «Расширения липшицевых отображений в гильбертово пространство». Конференция по современному анализу и теории вероятностей (Нью-Хейвен, Коннектикут, 1982) . Современная математика. Том. 26. Провиденс, Род-Айленд: Американское математическое общество. стр. 189–206 . дои : 10.1090/conm/026/737400 . ISBN 9780821850305 . МР 0737400 . S2CID 117819162 . .
^ Бингхэм, Элла; Маннила, Хейкки (6 мая 2014 г.). «Случайная проекция при уменьшении размерности: приложения к изображениям и текстовым данным» (PDF) .
^ Ахлиоптас, Димитрис (2001). «Случайные прогнозы, удобные для базы данных». Материалы двадцатого симпозиума ACM SIGMOD-SIGACT-SIGART по принципам систем баз данных - PODS '01 . стр. 274–281. CiteSeerX 10.1.1.28.6652 . дои : 10.1145/375551.375608 . ISBN 978-1581133615 . S2CID 2640788 .
^ Ли, Пин; Хасти, Тревор; Черч, Кеннет (2006). «Очень редкие случайные прогнозы». Материалы 12-й международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных . стр. 287–296. дои : 10.1145/1150402.1150436 . ISBN 1595933395 . S2CID 7995734 .
^ Кейн, Дэниел М.; Нельсон, Джелани (2014). «Преобразования Спарсера Джонсона-Линденштрауса». Журнал АКМ . 61 (1): 1–23. arXiv : 1012.1577 . дои : 10.1145/2559902 . МР 3167920 . S2CID 7821848 .
^ Чарикар, Моисей (2002). «Методы оценки сходства на основе алгоритмов округления». Материалы тридцать четвертого ежегодного симпозиума ACM по теории вычислений . Том. 1. С. 380–388. дои : 10.1145/509907.509965 . ISBN 1581134959 . S2CID 4229473 .
^ Фройнд, Йоав; Дасгупта, Санджой; Кабра, Маянк; Верма, Накул (2007). «Изучение структуры многообразий с помощью случайных проекций». 20-я Международная конференция по нейронным системам обработки информации . 1 (1): 473–480.
^ Буфунос, Петрос; Баранюк, Ричард (2008). «1-битное сжатие». 42-я ежегодная конференция по информационным наукам и системам . 1 (1): 16–21. дои : 10.1109/СНПЧ.2008.4558487 . S2CID 206563812 .
^ Ли, Сяоюнь; Ли, Пин (2019). «Анализ ошибок обобщения квантового компрессионного обучения». 33-я Международная конференция по нейронным системам обработки информации . 1 : 15150–15160.
^ Кайнен, Пол С .; Куркова, Вера (1993), «Квазиортогональная размерность евклидовых пространств», Письма по прикладной математике , 6 (3): 7–10, doi : 10.1016/0893-9659(93)90023-G , MR 1347278
^ Хехт-Нильсен, Р. (1994). «Векторы контекста: приблизительные представления общего назначения, самоорганизующиеся на основе необработанных данных». В Зураде Яцек М.; Маркс, Роберт Джексон; Робинсон, Чарльз Дж. (ред.). Вычислительный интеллект: имитация жизни . IEEE. стр. 43–56. ISBN 978-0-7803-1104-6 .
^ Gorban, Alexander N. ; Tyukin, Ivan Y.; Prokhorov, Danil V.; Sofeikov, Konstantin I. (2016). "Approximation with Random Bases: Pro et Contra". Information Sciences . 364–365: 129–145. arXiv : 1506.04631 . doi : 10.1016/j.ins.2015.09.021 . S2CID 2239376 .
^ Равиндран, Сиддхарт (2020). «Методика независимого от данных многоразового проецирования (DIRP) для уменьшения размерности при классификации больших данных с использованием k-ближайшего соседа (k-NN)». Письма Национальной академии наук . 43 : 13–21. дои : 10.1007/s40009-018-0771-6 . S2CID 91946077 .
^ Сиддхарт, Р.; Агила, Г. (июль 2020 г.). «RandPro — практическая реализация случайного извлечения признаков на основе проекций для многомерного анализа многомерных данных в R» . Программное обеспечениеX . 12 : 100629. Бибкод : 2020SoftX..1200629S . дои : 10.1016/j.softx.2020.100629 .

Дальнейшее чтение

Фодор, Имола К (2002). Обзор методов уменьшения размерности (Отчет). CiteSeerX 10.1.1.8.5098 .
Менон, Адитья Кришна (2007). Случайные проекции и приложения к уменьшению размерности (Диссертация). CiteSeerX 10.1.1.164.640 .
Рамдас, Адитья. Случайное введение в случайные прогнозы (отчет). CiteSeerX 10.1.1.377.2593 .

[1] Элла, Бингхэм; Хейкки, Маннила (2001). «Случайная проекция при уменьшении размерности: приложения к изображениям и текстовым данным». KDD-2001: Материалы седьмой Международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных . Нью-Йорк: Ассоциация вычислительной техники. стр. 245–250. CiteSeerX 10.1.1.24.5135 . дои : 10.1145/502512.502546 .

[2] Джонсон, Уильям Б .; Линденштраусс, Йорам (1984). «Расширения липшицевых отображений в гильбертово пространство». Конференция по современному анализу и теории вероятностей (Нью-Хейвен, Коннектикут, 1982) . Современная математика. Том. 26. Провиденс, Род-Айленд: Американское математическое общество. стр. 189–206 . дои : 10.1090/conm/026/737400 . ISBN 9780821850305 . МР 0737400 . S2CID 117819162 . .

[3] Бингхэм, Элла; Маннила, Хейкки (6 мая 2014 г.). «Случайная проекция при уменьшении размерности: приложения к изображениям и текстовым данным» (PDF) .

[4] Ахлиоптас, Димитрис (2001). «Случайные прогнозы, удобные для базы данных». Материалы двадцатого симпозиума ACM SIGMOD-SIGACT-SIGART по принципам систем баз данных - PODS '01 . стр. 274–281. CiteSeerX 10.1.1.28.6652 . дои : 10.1145/375551.375608 . ISBN 978-1581133615 . S2CID 2640788 .

[5] Ли, Пин; Хасти, Тревор; Черч, Кеннет (2006). «Очень редкие случайные прогнозы». Материалы 12-й международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных . стр. 287–296. дои : 10.1145/1150402.1150436 . ISBN 1595933395 . S2CID 7995734 .

[6] Кейн, Дэниел М.; Нельсон, Джелани (2014). «Преобразования Спарсера Джонсона-Линденштрауса». Журнал АКМ . 61 (1): 1–23. arXiv : 1012.1577 . дои : 10.1145/2559902 . МР 3167920 . S2CID 7821848 .

[7] Чарикар, Моисей (2002). «Методы оценки сходства на основе алгоритмов округления». Материалы тридцать четвертого ежегодного симпозиума ACM по теории вычислений . Том. 1. С. 380–388. дои : 10.1145/509907.509965 . ISBN 1581134959 . S2CID 4229473 .

[8] Фройнд, Йоав; Дасгупта, Санджой; Кабра, Маянк; Верма, Накул (2007). «Изучение структуры многообразий с помощью случайных проекций». 20-я Международная конференция по нейронным системам обработки информации . 1 (1): 473–480.

[9] Буфунос, Петрос; Баранюк, Ричард (2008). «1-битное сжатие». 42-я ежегодная конференция по информационным наукам и системам . 1 (1): 16–21. дои : 10.1109/СНПЧ.2008.4558487 . S2CID 206563812 .

[10] Ли, Сяоюнь; Ли, Пин (2019). «Анализ ошибок обобщения квантового компрессионного обучения». 33-я Международная конференция по нейронным системам обработки информации . 1 : 15150–15160.

[11] Кайнен, Пол С .; Куркова, Вера (1993), «Квазиортогональная размерность евклидовых пространств», Письма по прикладной математике , 6 (3): 7–10, doi : 10.1016/0893-9659(93)90023-G , MR 1347278

[12] Хехт-Нильсен, Р. (1994). «Векторы контекста: приблизительные представления общего назначения, самоорганизующиеся на основе необработанных данных». В Зураде Яцек М.; Маркс, Роберт Джексон; Робинсон, Чарльз Дж. (ред.). Вычислительный интеллект: имитация жизни . IEEE. стр. 43–56. ISBN 978-0-7803-1104-6 .

[GorbanTyukin2016-13] Gorban, Alexander N. ; Tyukin, Ivan Y.; Prokhorov, Danil V.; Sofeikov, Konstantin I. (2016). "Approximation with Random Bases: Pro et Contra". Information Sciences . 364–365: 129–145. arXiv : 1506.04631 . doi : 10.1016/j.ins.2015.09.021 . S2CID 2239376 .

[14] Равиндран, Сиддхарт (2020). «Методика независимого от данных многоразового проецирования (DIRP) для уменьшения размерности при классификации больших данных с использованием k-ближайшего соседа (k-NN)». Письма Национальной академии наук . 43 : 13–21. дои : 10.1007/s40009-018-0771-6 . S2CID 91946077 .

[15] Сиддхарт, Р.; Агила, Г. (июль 2020 г.). «RandPro — практическая реализация случайного извлечения признаков на основе проекций для многомерного анализа многомерных данных в R» . Программное обеспечениеX . 12 : 100629. Бибкод : 2020SoftX..1200629S . дои : 10.1016/j.softx.2020.100629 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]