Когда использовать лемму Джонсона-Линденштраусса над СВД?

Лемма Джонсона-Линденштраусса позволяет представлять точки в многомерном пространстве в точки в более низком измерении. При нахождении низкоразмерных пространств наилучшего соответствия стандартная методика заключается в том, чтобы найти разложение по сингулярному значению и затем взять подпространство, порожденное наибольшим сингулярным значением. Когда интересно использовать Джонсона-Линденштраусса над СВД?

machine-learning user09128323
источник

Ответы:

Два подхода предоставляют очень разные гарантии.

Лемма Дж.Л. по существу говорит: «Вы даете мне ошибку, которую хотите, и я дам вам пространство с малым размером, которое фиксирует расстояния до этой ошибки». Это также парная гарантия в худшем случае : для каждой пары точек и т. Д.

По сути, SVD обещает «вы скажете мне, в каком измерении вы хотите жить, и я дам вам наилучшее из возможных вложений», где «наилучшее» определяется как среднее : общая ошибка истинного сходства и прогнозируемого сходства минимальна.

Так что с теоретической точки зрения они решают самые разные проблемы. На практике, какой из них вам нужен, зависит от вашей модели проблемы, какие параметры более важны (ошибка или размерность) и какие гарантии вам нужны.

Суреш Венкат
источник

f (\cdot)

$f(\cdot)$

A

$A$

f (x)

$f(x)$

A x

$Ax$

f

$f$

ℓ_{1}

$\ell_1$

SVD и JL также экстраполируют на будущие точки также по-разному.

То есть, если вы предполагаете, что ваши данные поступают из некоторого базового распределения, в принципе SVD должен оставаться «хорошим» для любых будущих точек, пока они отбираются из одного и того же распределения. С другой стороны, целевое измерение JL зависит от количества точек, а это означает, что применение преобразования JL к дополнительным точкам может увеличить вероятность ошибки.

Это становится актуальным, если, например, если вы используете уменьшение размерности в качестве шага предварительной обработки для какого-либо другого алгоритма. Границы SVD для тренировочных данных могут сохраняться на тестовых данных, но JL не будет.

Frumple
источник

Это очень хороший момент.

Пол Сигел

Это продолжение ответа Суреша - я немного погуглил после прочтения его ответа и пришел к следующему пониманию. Первоначально я собирался опубликовать это как комментарий к его ответу, но он продолжал расти.

Пожалуйста, укажите на ошибки в ответе, я не специалист в этой области.

В некотором смысле, JL и SVD похожи на яблоки и апельсины.

1) Проблемы, которые они решают, совершенно разные. Один касается парных расстояний, другой - с наилучшим представлением. Один наихудший случай, другой средний случай.

\begin{matrix} (1) & \arg min_{P} {sup_{u, v} (| 1 - \frac{| | P u - P v | |_{2}}{| | u - v | |_{2}} |)} \end{matrix}

$\arg\min\limits_{P} \left\{\sup\limits_{u,v} \left(\Biggl\lvert 1- \frac{||Pu-Pv||_2}{||u-v||_2} \Biggl\rvert \right) \right\} \tag{1}$

(Это не точно, я прокомментирую это позже)

Проблема, которую решает SVD: (задано измерение ) $k$

\arg min_{P of dim k} {Avg (| | u - P u | |_{2})}

$\arg\min\limits_{P\text{ of dim k}} \left\{\text{Avg}\left(||u-Pu||_2\right)\right\}$

2) Входные данные: хотя оба алгоритма выводят подпространства, необходимые им входные данные различны. Для JL требуется допуск (какова максимальная ошибка, которую вы готовы допустить между фактическими расстояниями и расстояниями в подпространстве), в то время как SVD требует количества измерений. $\epsilon$

3) JL неконструктивен, SVD конструктивен - этот момент немного расплывчатый, так как термин конструктивный точно не определен. Существуют детерминированные алгоритмы для вычисления SVD, но алгоритм поиска пространства JL является рандомизированным - делайте случайные проекции, если не получится, попробуйте еще раз.

4) SVD является уникальным (подпространство может быть не уникальным, но целевое значение будет одинаковым для всех подпространств). Уравнение (1) выше, не является точным в том смысле , что JL не на самом деле говорить о минимизации расхождения в попарных расстояниях - это дает гарантию о существовании меньшего подпространства , где расстояние будет atmost отличается от их фактического ценности. Таких подпространств может быть много, некоторые лучше, чем другие. $\epsilon$

(См. Комментарии для объяснения по поводу вычеркнутых частей ответа).

Изменить: @ john-myles-white написал сообщение о JL, чтобы проверить свои претензии и показать, как можно построить проекцию: http://www.johnmyleswhite.com/notebook/2014/03/24/a-note- на-джонсон-Линденштраусс-лемма /

elexhobby
источник

В вашем ответе есть ряд ошибок. (1) JL чрезвычайно конструктивен: есть все виды алгоритмов для построения отображения (2) оно не сохраняет разницы, но относительное различие (отношение) (3) лемма JL была дерандомизирована (4) работы JL для любого набора векторов: конструкция не зависит от фактического ввода. единственная необходимая информация - это число векторов.

Суреш Венкат

Спасибо Суреш. Я включил все, кроме вашего последнего предложения. Не стесняйтесь редактировать ответ дальше. В последнем пункте я запутался. Вы говорите, что одна и та же карта будет работать независимо от того, какой набор векторов я вам дам?

elexhobby

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

Сашо Николов

Стоит проверить реализацию

научного труда

Я хотел бы добавить, что не только не существует детерминированного алгоритма для построения JL-встраивания в целом, но и в вычислительном отношении запрещена проверка того, что матрица, случайно сгенерированная в соответствии с алгоритмом JL, действительно обладает свойством «почти изометрии» (хотя это с очень высокой вероятностью). Поэтому я считаю разумным сказать, что теорема JL не конструктивна. Сравните с алгоритмом «выберите случайное действительное число от до »; это дает трансцендентное число с вероятностью , но я бы не назвал его конструктивным.

0

$0$

1

$1$

1

$1$

Пол Сигел