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

Эта статья поднимает множество проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны )

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален.
Найти источники: «Случайная проекция» - новости · газеты · книги · ученый · JSTOR ( ноябрь 2014 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

‹Приведенный ниже шаблон ( необходим эксперт ) рассматривается на предмет удаления. См. Шаблоны для обсуждения, чтобы помочь достичь консенсуса. ›

Эта статья требует внимания специалиста по математике . Пожалуйста , добавьте причину в или разговоре параметр для этого шаблона , чтобы объяснить проблему с статьей. WikiProject Mathematics может помочь нанять эксперта. ( Ноябрь 2014 г. )

( Узнайте, как и когда удалить этот шаблон сообщения )

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

Снижение размерности [ править ]

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

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

Метод [ править ]

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

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

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

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

Сферическая симметрия: для любой ортогональной матрицы RA и R имеют одинаковое распределение. $A\in O(d)$
Ортогональность: строки 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}}

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

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

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

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

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

Реализации [ править ]

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

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

Хеширование с учетом местоположения
Случайное отображение
Лемма Джонсона-Линденштрауса

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

^ Элла, Бингем; Хейкки, Маннила (2001). «Случайная проекция при уменьшении размерности: приложения к изображениям и текстовым данным». KDD-2001: Материалы седьмой Международной конференции ACM SIGKDD по открытию знаний и интеллектуальному анализу данных . Нью-Йорк: Ассоциация вычислительной техники. С. 245–250. CiteSeerX 10.1.1.24.5135 . DOI : 10.1145 / 502512.502546 .
^ Джонсон, Уильям Б .; Линденштраус, Иорам (1984). «Расширения липшицевых отображений в гильбертово пространство». Конференция по современному анализу и теории вероятностей (Нью-Хейвен, штат Коннектикут, 1982) . Современная математика. 26 . Провиденс, Род-Айленд: Американское математическое общество. С. 189–206 . DOI : 10.1090 / conm / 026/737400 . ISBN 9780821850305. Руководство по ремонту 0737400 ..
^ Бингхэм, Элла; Маннила, Хейкки (6 мая 2014 г.). «Случайная проекция при уменьшении размерности: приложения к изображениям и текстовым данным» (PDF) .
^ Achlioptas, Димитрис (2001). «Удобные для базы данных случайные прогнозы». Материалы двадцатого симпозиума ACM SIGMOD-SIGACT-SIGART по принципам систем баз данных - PODS '01 . С. 274–281. CiteSeerX 10.1.1.28.6652 . DOI : 10.1145 / 375551.375608 . ISBN 978-1581133615. S2CID 2640788 .
^ Кейн, Дэниел М .; Нельсон, Джелани (2014). «Преобразования Спарсера Джонсона-Линденштрауса». Журнал ACM . 61 (1): 1-23. arXiv : 1012.1577 . DOI : 10.1145 / 2559902 . Руководство по ремонту 3167920 . S2CID 7821848 .
^ Кайнен, Пол С .; Куркова, Věra (1993), "квазиортогональная размерность евклидовых пространств", Прикладная Математика Письмо , 6 (3): 7-10, DOI : 10.1016 / 0893-9659 (93) 90023-G , МР 1347278
Перейти ↑ Hecht-Nielsen, R. (1994). «Векторы контекста: общие представления приблизительного значения, самоорганизующиеся из необработанных данных». В Зураде, Jacek M .; Маркс, Роберт Джексон; Робинсон, Чарльз Дж. (Ред.). Вычислительный интеллект: подражание жизни . IEEE. С. 43–56. ISBN 978-0-7803-1104-6.
^ Горбань, Александр Н .; Тюкин, Иван Юрьевич; Прохоров, Данил В .; Софейков, Константин И. (2016). «Аппроксимация со случайным основанием: Pro et Contra». Информационные науки . 364–365: 129–145. arXiv : 1506.04631 . DOI : 10.1016 / j.ins.2015.09.021 . S2CID 2239376 .
^ Ravindran, Сиддхартха (2020). «Метод независимой от данных многоразовой проекции (DIRP) для уменьшения размерности в классификации больших данных с использованием k-ближайшего соседа (k-NN)». Письма Национальной Академии Наук . 43 : 13–21. DOI : 10.1007 / s40009-018-0771-6 . S2CID 91946077 .
^ Siddharth, R .; Агила, Г. (июль 2020 г.). «RandPro - практическая реализация извлечения признаков на основе случайной проекции для многомерного многомерного анализа данных в R» . Программное обеспечениеX . 12 : 100629. Bibcode : 2020SoftX..1200629S . DOI : 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 . DOI : 10.1145 / 502512.502546 .

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

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

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

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

[6] Кайнен, Пол С .; Куркова, Věra (1993), "квазиортогональная размерность евклидовых пространств", Прикладная Математика Письмо , 6 (3): 7-10, DOI : 10.1016 / 0893-9659 (93) 90023-G , МР 1347278

[7] Перейти ↑ Hecht-Nielsen, R. (1994). «Векторы контекста: общие представления приблизительного значения, самоорганизующиеся из необработанных данных». В Зураде, Jacek M .; Маркс, Роберт Джексон; Робинсон, Чарльз Дж. (Ред.). Вычислительный интеллект: подражание жизни . IEEE. С. 43–56. ISBN 978-0-7803-1104-6.

[GorbanTyukin2016-8] Горбань, Александр Н .; Тюкин, Иван Юрьевич; Прохоров, Данил В .; Софейков, Константин И. (2016). «Аппроксимация со случайным основанием: Pro et Contra». Информационные науки . 364–365: 129–145. arXiv : 1506.04631 . DOI : 10.1016 / j.ins.2015.09.021 . S2CID 2239376 .

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

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

[1]