Лемма Джонсона–Линденштрауса

Математический результат

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

Лемма имеет приложения в сжатом считывании , многообразном обучении , уменьшении размерности , встраивании графов и обработке естественного языка . Большая часть данных, хранящихся и обрабатываемых на компьютерах, включая текст и изображения, может быть представлена ​​в виде точек в многомерном пространстве (см. модель векторного пространства для случая текста). Однако основные алгоритмы для работы с такими данными, как правило, очень быстро становятся неэффективными по мере увеличения размерности. ^[1] Поэтому желательно уменьшать размерность данных таким образом, чтобы сохранить их соответствующую структуру.

Лемма, вероятно, объясняет, как большие языковые модели (LLM), такие как трансформаторы, способны представлять очень тонкие значения слов и контекст в относительно низкоразмерных вложениях. ^[2]

Лемма

При наличии , набора точек в и целого числа , ^[3] существует линейное отображение такое, что ${\displaystyle 0<\varepsilon <1}$ ${\displaystyle X}$ ${\displaystyle m}$ ${\displaystyle \mathbb {R} ^{N}}$ ${\displaystyle n>8(\ln m)/\varepsilon ^{2}}$ ${\displaystyle f:\mathbb {R} ^{N}\rightarrow \mathbb {R} ^{n}}$

${\displaystyle (1-\varepsilon )\|u-v\|^{2}\leq \|f(u)-f(v)\|^{2}\leq (1+\varepsilon )\|u-v\|^{2}}$

для всех . ${\displaystyle u,v\in X}$

Формулу можно переписать: $${\displaystyle (1+\varepsilon )^{-1}\|f(u)-f(v)\|^{2}\leq \|u-v\|^{2}\leq (1-\varepsilon )^{-1}\|f(u)-f(v)\|^{2}}$$

В качестве альтернативы, для любого и любого целого числа ^{[Примечание 1]} существует линейная функция , такая что ограничение является - билипшицевым . ^{[Примечание 2]} ${\displaystyle \epsilon \in (0,1)}$ ${\displaystyle n\geq 15(\ln m)/\varepsilon ^{2}}$ ${\displaystyle f:\mathbb {R} ^{N}\rightarrow \mathbb {R} ^{n}}$ ${\displaystyle f|_{X}}$ ${\displaystyle (1+\varepsilon )}$

Кроме того, лемма точна с точностью до постоянного множителя, т.е. существует множество точек размера m, требующее размерности

${\displaystyle \Omega \left({\frac {\log(m)}{\varepsilon ^{2}}}\right)}$

для того, чтобы сохранить расстояния между всеми парами точек с точностью до . ^{[4] [5]} ${\displaystyle (1\pm \varepsilon )}$

Классическое доказательство леммы берет скалярное кратное ортогональной проекции на случайное подпространство размерности в . Ортогональная проекция схлопывает некоторые измерения пространства, к которому она применяется, что уменьшает длину всех векторов, а также расстояние между векторами в пространстве. В условиях леммы концентрация меры гарантирует, что существует ненулевой шанс того, что случайная ортогональная проекция уменьшит попарные расстояния между всеми точками в примерно на постоянный множитель . Поскольку шанс ненулевой, такие проекции должны существовать, поэтому мы можем выбрать одну и установить . ${\displaystyle f}$ ${\displaystyle P}$ ${\displaystyle n}$ ${\displaystyle \mathbb {R} ^{N}}$ ${\displaystyle X}$ ${\displaystyle c}$ ${\displaystyle P}$ ${\displaystyle f(v)=Pv/c}$

Чтобы получить проекцию алгоритмически, достаточно с высокой вероятностью многократно выбирать ортогональные матрицы проекции случайным образом. Если вы продолжите бросать кости, вы в конечном итоге получите одну за полиномиальное случайное время.

Альтернативное заявление

Связанная лемма — это распределительная лемма JL. Эта лемма утверждает, что для любого и положительного целого числа существует распределение по , из которого выводится матрица , такая, что для и для любого вектора единичной длины справедливо следующее утверждение. ^[6] ${\displaystyle 0<\varepsilon ,\delta <1/2}$ ${\displaystyle d}$ ${\displaystyle \mathbb {R} ^{k\times d}}$ ${\displaystyle A}$ ${\displaystyle k=O(\varepsilon ^{-2}\log(1/\delta ))}$ ${\displaystyle x\in \mathbb {R} ^{d}}$

${\displaystyle P(|\Vert Ax\Vert _{2}^{2}-1|>\varepsilon )<\delta }$

Можно получить лемму JL из распределительной версии, установив и для некоторой пары u , v оба в X. Тогда лемма JL следует из объединения, ограниченного по всем таким парам. ${\displaystyle x=(u-v)/\|u-v\|_{2}}$ ${\displaystyle \delta <1/n^{2}}$

Ускорение преобразования JL

При наличии A вычисление произведения матрицы-вектора занимает время. Была проведена некоторая работа по получению распределений, для которых произведение матрицы-вектора можно вычислить за меньшее время. ${\displaystyle O(kd)}$ ${\displaystyle O(kd)}$

Существует два основных направления работы. Первое, быстрое преобразование Джонсона-Линденштрауса (FJLT), ^[7] было введено Эйлоном и Шазеллом в 2006 году. Этот метод позволяет вычислять произведение матрицы-вектора всего за для любой константы . ${\displaystyle d\log d+k^{2+\gamma }}$ ${\displaystyle \gamma >0}$

Другой подход заключается в построении распределения, поддерживаемого разреженными матрицами. ^[8] Этот метод позволяет сохранить только часть записей в матрице, что означает, что вычисление может быть выполнено за короткое время. Кроме того, если вектор имеет только ненулевые записи, разреженный JL занимает время , которое может быть намного меньше времени, используемого быстрым JL. ${\displaystyle \varepsilon }$ ${\displaystyle kd\varepsilon }$ ${\displaystyle b}$ ${\displaystyle kb\varepsilon }$ ${\displaystyle d\log d}$

Тензорные случайные проекции

Можно объединить две матрицы JL, взяв так называемое произведение граней , которое определяется как тензорное произведение строк (было предложено В. Слюсарем ^[9] в 1996 г. ^{[10] [11] [12] [ 13] [14]} для приложений радаров и цифровых антенных решеток ). Более конкретно, пусть и будут двумя матрицами. Тогда произведение граней будет ^{[10] [11] [12] [13] [14]} ${\displaystyle {C}\in \mathbb {R} ^{3\times 3}}$ ${\displaystyle {D}\in \mathbb {R} ^{3\times 3}}$ ${\displaystyle {C}\bullet {D}}$

${\displaystyle {C}\bullet {D}=\left[{\begin{array}{c }{C}_{1}\otimes {D}_{1}\\\hline {C}_{2}\otimes {D}_{2}\\\hline {C}_{3}\otimes {D}_{3}\\\end{array}}\right].}$

Эта идея тензоризации была использована Касивисванатаном и др. для дифференциальной конфиденциальности . ^[15]

Матрицы JL, определенные таким образом, используют меньше случайных битов и могут быть быстро применены к векторам, имеющим тензорную структуру, благодаря следующему тождеству: ^[12]

${\displaystyle (\mathbf {C} \bullet \mathbf {D} )(x\otimes y)=\mathbf {C} x\circ \mathbf {D} y=\left[{\begin{array}{c }(\mathbf {C} x)_{1}(\mathbf {D} y)_{1}\\(\mathbf {C} x)_{2}(\mathbf {D} y)_{2}\\\vdots \end{array}}\right]}$,

где — поэлементное ( Адамара ) произведение. Такие вычисления использовались для эффективного вычисления полиномиальных ядер и многих других алгоритмов линейной алгебры ^{[ необходимо разъяснение ]} . ^[16] ${\displaystyle \circ }$

В 2020 году ^[17] было показано, что если матрицы являются независимыми или гауссовыми, то объединенная матрица удовлетворяет распределительной лемме JL, если число строк не менее ${\displaystyle C_{1},C_{2},\dots ,C_{c}}$ ${\displaystyle \pm 1}$ ${\displaystyle C_{1}\bullet \dots \bullet C_{c}}$

${\displaystyle O(\epsilon ^{-2}\log 1/\delta +\epsilon ^{-1}({\tfrac {1}{c}}\log 1/\delta )^{c})}$.

Для больших это так же хорошо, как полностью случайный Джонсон-Линденштраус, но соответствующая нижняя граница в той же статье показывает, что эта экспоненциальная зависимость от необходима. Предлагаются альтернативные конструкции JL, чтобы обойти это. ${\displaystyle \epsilon }$ ${\displaystyle (\log 1/\delta )^{c}}$

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

• Случайная проекция
• Ограниченное свойство изометрии
• Вложения слов

Примечания

1. Или любое целое число ${\displaystyle n>128(\ln m)/(9\varepsilon ^{2}).}$
2. Этот результат следует из результата выше. Эскиз доказательства: Обратите внимание и для всех . Проведите работу для 1= m и 1< m , применяя результат выше в последнем случае, отметив ${\displaystyle 1/(1+\varepsilon )<{\sqrt {1-3\varepsilon /4}}}$ ${\displaystyle {\sqrt {1+3\varepsilon /4}}<{\sqrt {1+\varepsilon }}<1+\varepsilon }$ ${\displaystyle \varepsilon \in (0,1)}$ ${\displaystyle 3\varepsilon /4}$ ${\displaystyle 128/9<15.}$

Ссылки

1. Например, говоря о поиске ближайшего соседа в многомерных наборах данных, Джон Клейнберг пишет: «Более сложные алгоритмы обычно достигают времени запроса, логарифмического по n, за счет экспоненциальной зависимости от размерности d ; действительно, даже анализ среднего случая эвристик, таких как деревья kd, выявляет экспоненциальную зависимость от d во времени запроса». Клейнберг, Джон М. (1997), «Два алгоритма поиска ближайшего соседа в многомерных наборах данных», Труды двадцать девятого ежегодного симпозиума ACM по теории вычислений , STOC '97, Нью-Йорк, США: ACM, стр. 599–608, doi : 10.1145/258533.258653 , ISBN 0-89791-888-6.
2. Хардт, Мориц. "Вложения слов: объяснение их свойств". Вне выпуклого пути . Получено 10 октября 2024 г.
3. Фернандес-Гранда, Карлос. «Конспекты лекций 5: Случайные прогнозы» (PDF) . п. 6. Лемма 2.6 (лемма Джонсона-Линденштрауса)
4. Ларсен, Каспер Грин; Нельсон, Джелани (2017), «Оптимальность леммы Джонсона-Линденштрауса», Труды 58-го ежегодного симпозиума IEEE по основам компьютерной науки (FOCS) , стр. 633–638, arXiv : 1609.02094 , doi : 10.1109/FOCS.2017.64, ISBN 978-1-5386-3464-6, S2CID  16745
5. Нильсен, Франк (2016), «10. Быстрая приближенная оптимизация в больших размерностях с наборами ядер и быстрым сокращением размерности», Введение в HPC с MPI для науки о данных, Springer, стр. 259–272, ISBN 978-3-319-21903-5
6. Джонсон, Уильям Б .; Линденштраус, Джорам (1984), «Расширения липшицевых отображений в гильбертово пространство», в Beals, Ричард; Бек, Анатоль; Беллоу, Александра; и др. (ред.), Конференция по современному анализу и вероятности (Нью-Хейвен, Коннектикут, 1982) , Contemporary Mathematics, т. 26, Провиденс, Род-Айленд: Американское математическое общество, стр. 189–206, doi :10.1090/conm/026/737400, ISBN 0-8218-5030-X, MR  0737400, S2CID  117819162
7. Ailon, Nir; Chazelle, Bernard (2006), «Приблизительные ближайшие соседи и быстрое преобразование Джонсона–Линденштрауса», Труды 38-го ежегодного симпозиума ACM по теории вычислений , Нью-Йорк: ACM Press, стр. 557–563, doi :10.1145/1132516.1132597, ISBN 1-59593-134-1, MR  2277181, S2CID  490517
8. Кейн, Дэниел М.; Нельсон, Джелани (2014), «Преобразования Спарсера Джонсона-Линденштрауса», Журнал ACM , 61 (1): 1, arXiv : 1012.1577 , doi : 10.1145/2559902, MR  3167920, S2CID  7821848. Предварительная версия этой статьи была опубликована в Трудах Двадцать третьего ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , 2012.
9. Эстеве, Анна; Бой, Ева; Фортиана, Хосеп (2009), «Условия взаимодействия в регрессии на основе расстояния», Communications in Statistics , 38 (18–20): 3498–3509, doi :10.1080/03610920802592860, MR  2589790, S2CID  122303508
10. Слюсарь, VI (27 декабря 1996 г.), "Конечные продукты в матрицах в радиолокационных приложениях". (PDF) , Радиоэлектроника и системы связи , 41 (3): 50–53
11. Слюсарь, В.И. (1997-05-20), "Аналитическая модель цифровой антенной решетки на основе произведений матриц гранеразделения". (PDF) , Труды ICATT-97, Киев : 108–109
12. Слюсар, В.И. (1997-09-15), "Новые операции произведения матриц для приложений радаров" (PDF) , Труды Прямые и обратные задачи теории электромагнитных и акустических волн (ДИПЭД-97), Львов. : 73–74
13. Слюсарь, В.И. (13 марта 1998 г.), "Семейство граневых произведений матриц и его свойства" (PDF) , Кибернетика и системный анализ Ц/К Кибернетика и системный анализ.- 1999. , 35 (3): 379–384, doi :10.1007/BF02733426, S2CID  119661450
14. Слюсарь, В.И. (2003), "Обобщенные фейс-произведения матриц в моделях цифровых антенных решеток с неидентичными каналами" (PDF) , Радиоэлектроника и системы связи , 46 (10): 9–17
15. Касивисванатан, Шива Прасад; Рудельсон, Марк; Смит, Адам Д.; Ульман, Джонатан Р. (2010), «Цена частного выпуска таблиц сопряженности и спектры случайных матриц с коррелированными строками», в Шульман, Леонард Дж. (ред.), Труды 42-го симпозиума ACM по теории вычислений, STOC 2010, Кембридж, Массачусетс, США, 5–8 июня 2010 г. , Ассоциация вычислительной техники, стр. 775–784, doi :10.1145/1806689.1806795, ISBN 978-1-4503-0050-6, ОСТИ  990798, S2CID  5714334
16. Вудрафф, Дэвид П. (2014), Эскиз как инструмент для численной линейной алгебры , Основы и тенденции в теоретической информатике, т. 10, arXiv : 1411.4357 , doi : 10.1561/0400000060, MR  3285427, S2CID  51783444
17. Ахле, Томас; Капралов, Майкл; Кнудсен, Якоб; Паг, Расмус ; Велинкер, Амейя; Вудрафф, Дэвид; Занди, Амир (2020), «Забывчивое рисование многочленных ядер высокой степени», Симпозиум ACM-SIAM по дискретным алгоритмам , Ассоциация вычислительной техники, стр. 141–160, arXiv : 1909.01410 , doi : 10.1137/1.9781611975994.9 , ISBN 978-1-61197-599-4

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

• Ахлиоптас, Димитрис (2003), «Случайные проекции, удобные для баз данных: Джонсон–Линденштраус с бинарными монетами», Журнал компьютерных и системных наук , 66 (4): 671–687, doi : 10.1016/S0022-0000(03)00025-4 , MR  2005771. Журнальная версия статьи, ранее опубликованной на PODC 2001.
• Баранюк, Ричард ; Дэвенпорт, Марк; ДеВоре, Рональд ; Уэйкин, Майкл (2008), «Простое доказательство свойства ограниченной изометрии для случайных матриц», Constructive Approximation , 28 (3): 253–263, doi :10.1007/s00365-007-9003-x, hdl : 1911/21683 , MR  2453366, S2CID  15911073.
• Дасгупта, Санджой; Гупта, Анупам (2003), «Элементарное доказательство теоремы Джонсона и Линденштрауса» (PDF) , Случайные структуры и алгоритмы , 22 (1): 60–65, doi :10.1002/rsa.10073, MR  1943859, S2CID  10327785.
• Ландвебер, Питер ; Лазар, Эмануэль А.; Патель, Нил (2016), «О диаметрах волокон непрерывных отображений», American Mathematical Monthly , 123 (4): 392–397, arXiv : 1503.07597 , doi : 10.4169/amer.math.monthly.123.4.392, S2CID  51751732
• Слюсар, В.И. (1997-05-20), "Аналитическая модель цифровой антенной решетки на основе произведений матриц гранеразделения". (PDF) , Труды ICATT-97, Киев : 108–109
• Слюсарь, В.И. (13 марта 1998 г.), "Семейство граневых произведений матриц и его свойства" (PDF) , Кибернетика и системный анализ Ц/К Кибернетика и системный анализ.- 1999. , 35 (3): 379–384, doi :10.1007/BF02733426, S2CID  119661450.
• Современный алгоритмический инструментарий. Лекция №4: Снижение размерности (PDF) , 2023 г.