Случайная проекция
В этой статье есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения )
|
В математике и статистике случайная проекция — это метод, используемый для уменьшения размерности набора точек, лежащих в евклидовом пространстве . Согласно теоретическим результатам, случайная проекция хорошо сохраняет расстояния, но эмпирические результаты скудны. [1] Они применялись ко многим задачам естественного языка под названием « случайное индексирование» .
Уменьшение размерности
[ редактировать ]Снижение размерности, как следует из названия, означает уменьшение количества случайных величин с использованием различных математических методов статистики и машинного обучения. Снижение размерности часто используется для решения проблем управления и манипулирования большими наборами данных. Методы уменьшения размерности обычно используют линейные преобразования для определения внутренней размерности многообразия, а также для определения его основных направлений. Для этой цели существуют различные сопутствующие методы, в том числе: анализ главных компонент , линейный дискриминантный анализ , канонический корреляционный анализ , дискретное косинусное преобразование , случайное проецирование и т. д.
Случайное проецирование — это простой и эффективный в вычислительном отношении способ уменьшить размерность данных за счет обмена контролируемого количества ошибок на более быстрое время обработки и меньшие размеры модели. Размеры и распределение случайных матриц проекций контролируются таким образом, чтобы приблизительно сохранить попарные расстояния между любыми двумя выборками набора данных.
Метод
[ редактировать ]Основная идея случайного проецирования выражена в лемме Джонсона-Линденштрауса : [2] который гласит, что если точки в векторном пространстве имеют достаточно высокую размерность, то их можно спроецировать в подходящее пространство меньшей размерности таким образом, чтобы с высокой вероятностью приблизительно сохранялись попарные расстояния между точками.
При случайном проецировании исходные d-мерные данные проецируются в k-мерное (k << d) подпространство с использованием случайного - размерная матрица R, столбцы которой имеют единичную длину. [ нужна ссылка ] Используя матричную запись: Если — исходный набор N d-мерных наблюдений, тогда — это проекция данных на нижнее k-мерное подпространство. Случайное проецирование вычислительно просто: сформируйте случайную матрицу «R» и спроецируйте матрица данных X на K измерений порядка . Если матрица данных X разрежена и содержит около c ненулевых записей на столбец, то сложность этой операции имеет порядок . [3]
Гауссова случайная проекция
[ редактировать ]Случайная матрица R может быть сгенерирована с использованием распределения Гаусса. Первая строка представляет собой случайный единичный вектор, равномерно выбранный из . Вторая строка представляет собой случайный единичный вектор из пространства, ортогонального первой строке, третья строка представляет собой случайный единичный вектор из пространства, ортогонального первым двум строкам, и так далее. При таком способе выбора R удовлетворяются следующие свойства:
- Сферическая симметрия: для любой ортогональной матрицы. , RA и R имеют одинаковое распределение.
- Ортогональность: строки R ортогональны друг другу.
- Нормальность: строки R представляют собой векторы единичной длины.
Более эффективные в вычислительном отношении случайные проекции
[ редактировать ]Ахлиоптас [4] показал, что распределение Гаусса можно заменить гораздо более простым распределением, таким как
Это эффективно для приложений баз данных, поскольку вычисления могут выполняться с использованием целочисленной арифметики. Более соответствующее исследование проводится в. [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 .