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

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

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

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

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

Метод

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

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

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

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

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

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

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

Р я , дж = 3 × { + 1 с вероятностью  1 6 0 с вероятностью  2 3 − 1 с вероятностью  1 6 {\displaystyle R_{i,j}={\sqrt {3}}\times {\begin{cases}+1&{\text{с вероятностью }}{\frac {1}{6}}\\0&{\text{с вероятностью }}{\frac {2}{3}}\\-1&{\text{с вероятностью }}{\frac {1}{6}}\end{cases}}}

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

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

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

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

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

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

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

Реализации

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

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

Ссылки

  1. ^ Элла, Бингем; Хейкки, Маннила (2001). «Случайная проекция в снижении размерности: приложения к данным изображений и текстов». KDD-2001: Труды Седьмой международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных . Нью-Йорк: Ассоциация вычислительной техники. С. 245–250. CiteSeerX  10.1.1.24.5135 . doi :10.1145/502512.502546.
  2. ^ Джонсон, Уильям Б .; Линденштраус, Джорам (1984). «Расширения липшицевых отображений в гильбертово пространство». Конференция по современному анализу и вероятности (Нью-Хейвен, Коннектикут, 1982) . Contemporary Mathematics. Том 26. Провиденс, Род-Айленд: Американское математическое общество. стр. 189–206. doi :10.1090/conm/026/737400. ISBN 9780821850305. MR  0737400. S2CID  117819162..
  3. ^ Бингем, Элла; Маннила, Хейкки (6 мая 2014 г.). «Случайная проекция в снижении размерности: применение к данным изображений и текста» (PDF) .
  4. ^ Ахлиоптас, Димитрис (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. ^ Ли, Пинг; Хасти, Тревор; Чёрч, Кеннет (2006). «Очень редкие случайные проекции». Труды 12-й международной конференции ACM SIGKDD по обнаружению знаний и добыче данных . стр. 287–296. doi :10.1145/1150402.1150436. ISBN 1595933395. S2CID  7995734.
  6. ^ Кейн, Дэниел М.; Нельсон, Джелани (2014). «Преобразования Спарсера Джонсона-Линденштраусса». Журнал ACM . 61 (1): 1–23. arXiv : 1012.1577 . doi : 10.1145/2559902. MR  3167920. S2CID  7821848.
  7. ^ Чарикар, Моисей (2002). «Методы оценки сходства на основе алгоритмов округления». Труды тридцать четвертого ежегодного симпозиума ACM по теории вычислений . Том 1. С. 380–388. doi :10.1145/509907.509965. ISBN 1581134959. S2CID  4229473.
  8. ^ Фройнд, Йоав; Дасгупта, Санджой; Кабра, Маянк; Верма, Накул (2007). «Изучение структуры многообразий с использованием случайных проекций». 20-я Международная конференция по нейронным системам обработки информации . 1 (1): 473–480.
  9. ^ Буфонос, Петрос; Баранюк, Ричард (2008). «1-битное сжатие данных». 42-я ежегодная конференция по информационным наукам и системам . 1 (1): 16–21. doi :10.1109/CISS.2008.4558487. S2CID  206563812.
  10. ^ Ли, Сяоюнь; Ли, Пин (2019). «Анализ ошибок обобщения квантованного сжатого обучения». 33-я Международная конференция по нейронным системам обработки информации . 1 : 15150–15160.
  11. ^ Kainen, Paul C. ; Kůrková, Věra (1993), «Квазиортогональная размерность евклидовых пространств», Applied Mathematics Letters , 6 (3): 7–10, doi : 10.1016/0893-9659(93)90023-G , MR  1347278
  12. ^ Хехт-Нильсен, Р. (1994). «Контекстные векторы: универсальные приближенные смысловые представления, самоорганизованные из необработанных данных». В Zurada, Jacek M.; Marks, Robert Jackson; Robinson, Charles J. (ред.). Computational Intelligence: Imitating Life . IEEE. стр. 43–56. ISBN 978-0-7803-1104-6.
  13. ^ Горбань, Александр Н .; Тюкин, Иван Ю.; Прохоров, Данил В.; Софейков, Константин И. (2016). «Аппроксимация со случайными базами: 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)». National Academy Science Letters . 43 : 13–21. doi : 10.1007/s40009-018-0771-6. S2CID  91946077.
  15. ^ Сиддхарт, Р.; Агила, Г. (июль 2020 г.). "RandPro - Практическая реализация извлечения случайных проекционных признаков для многомерного анализа многомерных данных в R". SoftwareX . 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 .
Получено с "https://en.wikipedia.org/w/index.php?title=Случайная_проекция&oldid=1215656397"