Jump to content

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

В математике и статистике случайная проекция — это метод, используемый для уменьшения размерности набора точек, лежащих в евклидовом пространстве . Согласно теоретическим результатам, случайная проекция хорошо сохраняет расстояния, но эмпирические результаты скудны. [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] Это означает, что для представления элемента такого многомерного пространства линейными комбинациями случайно и независимо выбранных векторов часто может потребоваться генерировать выборки экспоненциально большой длины, если мы используем ограниченные коэффициенты в линейных комбинациях. С другой стороны, если допускаются коэффициенты со сколь угодно большими значениями, количество случайно сгенерированных элементов, достаточных для аппроксимации, даже меньше размерности пространства данных.

Реализации

[ редактировать ]

См. также

[ редактировать ]
  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 .
  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 .

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

[ редактировать ]
  • Фодор, Имола К (2002). Обзор методов уменьшения размерности (Отчет). CiteSeerX   10.1.1.8.5098 .
  • Менон, Адитья Кришна (2007). Случайные проекции и приложения к уменьшению размерности (Диссертация). CiteSeerX   10.1.1.164.640 .
  • Рамдас, Адитья. Случайное введение в случайные прогнозы (отчет). CiteSeerX   10.1.1.377.2593 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 4129e8c8cb936fd87d7469433bbae509__1711444560
URL1:https://arc.ask3.ru/arc/aa/41/09/4129e8c8cb936fd87d7469433bbae509.html
Заголовок, (Title) документа по адресу, URL1:
Random projection - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)