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

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

Снижение размерности

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

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

Метод

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализации

RandPro - Пакет R для случайной проекции ^[9]
sklearn.random_projection - Модуль 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..
^ Бингхэм, Элла; Маннила, Хейкки (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.
^ Кейн, Дэниел М .; Нельсон, Джелани (2014). "Преобразования Спарсера Джонсона-Линденштрауса". Журнал ACM. 61 (1): 1–23. arXiv:1012.1577. Дои:10.1145/2559902. МИСТЕР 3167920.
^ Кайнен, Пол К.; Куркова, Вера (1993), "Квазиортогональная размерность евклидовых пространств", Письма по прикладной математике, 6 (3): 7–10, Дои:10.1016 / 0893-9659 (93) 90023-Г, МИСТЕР 1347278
^ Р. Хехт-Нильсен, Векторы контекста: самоорганизация приближенных смысловых представлений общего назначения из необработанных данных, в: Дж. Зурада, Р. Маркс, К. Робинсон (ред.), Computational Intelligence: Imitating Life, IEEE Press, 1994. С. 43–56.
^ Горбань Александр Николаевич; Тюкин, Иван Юрьевич; Прохоров, Данил В .; Софейков, Константин И. (2016). «Аппроксимация со случайным основанием: Pro et Contra». Информационные науки. 364-365: 129–145. arXiv:1506.04631. Дои:10.1016 / j.ins.2015.09.021.
^ Равиндран, Сиддхарт (2020). «Метод независимой от данных многоразовой проекции (DIRP) для уменьшения размерности в классификации больших данных с использованием k-ближайшего соседа (k-NN)». Письма Национальной Академии Наук. 43: 13–21. Дои:10.1007 / s40009-018-0771-6.

Фодор И. (2002) «Обзор методов уменьшения размерности». Центр прикладных научных вычислений, Национальный университет Лоуренса Ливермора, технический отчет UCRL-ID-148494
АДИТЯ КРИШНА МЕНОН (2007) «Случайные проекции и приложения к снижению размерности». Школа информационных технологий Сиднейского университета, Австралия
Адитья Рамдас «Случайное введение в случайные проекции». Университет Карнеги Меллон

[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..

[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.

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

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

[7] Р. Хехт-Нильсен, Векторы контекста: самоорганизация приближенных смысловых представлений общего назначения из необработанных данных, в: Дж. Зурада, Р. Маркс, К. Робинсон (ред.), Computational Intelligence: Imitating Life, IEEE Press, 1994. С. 43–56.

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]