¿Cuándo usar el lema de Johnson-Lindenstrauss sobre SVD?

El lema de Johnson-Lindenstrauss permite representar puntos en un espacio de alta dimensión en puntos en una dimensión inferior. Al encontrar espacios dimensionales más bajos de mejor ajuste, una técnica estándar es encontrar la descomposición del valor singular y luego tomar el subespacio generado por los valores singulares más grandes. ¿Cuándo es interesante usar Johnson-Lindenstrauss sobre la SVD?

machine-learning user09128323
fuente

Respuestas:

Los dos enfoques ofrecen garantías muy diferentes.

El JL Lemma dice esencialmente "me das el error que deseas, y te daré un espacio dimensional bajo que captura las distancias hasta ese error". También es una garantía por pares en el peor de los casos : para cada par de puntos , etc., etc.

La SVD esencialmente promete "dime en qué dimensión quieres vivir, y te daré la mejor integración posible", donde "mejor" se define como en promedio : el error total de similitud real versus similitud proyectada es mínimo.

Entonces, desde una perspectiva teórica, resuelven problemas muy diferentes. En la práctica, cuál desea depende de su modelo para el problema, qué parámetros son más importantes (error o dimensión) y qué tipo de garantías necesita.

Suresh Venkat
fuente

¿Podría alguien decirme cómo se obtiene exactamente

en (1-eps) | uv | ^ 2 <= | f (u) -f (v) | ^ 2 <= (1 + eps) | uv | ^ 2 (de en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma )?

f (\cdot)

$f(\cdot)$

T ....

Esa es otra pregunta. Pero en (muy) breve, si toma una matriz

y la llena con entradas extraídas de una normal estándar, entonces

se define como

A

$A$

f (x)

$f(x)$

A x

$Ax$

Suresh Venkat

¿Existe también un esquema JL para campos finitos donde la distorsión está en la métrica de Hamming? Si es así, ¿qué sería

aquí?

f

$f$

T ....

No puede hacer la reducción de dimensionalidad de manera efectiva para la métrica de Hamming. La estructura

es muy diferente. En un sentido muy práctico, admitir reducciones de estilo JL está vinculado a vivir en un espacio de Hilbert.

ℓ_{1}

$\ell_1$

Suresh Venkat

SVD y JL también se extrapola a puntos futuros de manera diferente también.

Es decir, si asume que sus datos provienen de alguna distribución subyacente, en principio, la SVD debe permanecer "buena" para cualquier punto futuro siempre que se muestreen de la misma distribución. Por otro lado, la dimensión objetivo de JL depende del número de puntos, lo que significa que la aplicación de una transformación JL a puntos adicionales puede aumentar la probabilidad de error.

Esto se vuelve relevante si, por ejemplo, si está utilizando la reducción de dimensionalidad como un paso de preprocesamiento para algún otro algoritmo. Los límites de SVD para los datos de entrenamiento pueden mantenerse en los datos de prueba, pero los JL no.

Frumple
fuente

Este es un muy buen punto.

Paul Siegel

Este es un seguimiento de la respuesta de Suresh: busqué en Google un poco después de leer su respuesta y obtuve el siguiente entendimiento. Originalmente iba a publicar esto como un comentario a su respuesta, pero siguió aumentando.

Señale errores en la respuesta, no soy un experto en este campo.

En cierto sentido, JL y SVD son como manzanas y naranjas.

1) Los problemas que resuelven son completamente diferentes. Uno tiene que ver con distancias por pares, el otro con la mejor representación. Uno es el peor de los casos, el otro es el caso promedio.

\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}$

(Esto no es preciso, comentaré más sobre esto más adelante)

El problema que SVD está resolviendo es (dada una dimensión $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) Entradas: aunque ambos algoritmos generan subespacios, las entradas que necesitan son diferentes. JL requiere una tolerancia (cuál es el error máximo que está dispuesto a tolerar entre distancias reales y distancias en el subespacio), mientras que SVD requiere varias dimensiones. $\epsilon$

3) JL no es constructivo, SVD es constructivo: este punto es un poco vago, ya que el término constructivo no está definido con precisión. Existen algoritmos deterministas para calcular la SVD, pero el algoritmo para encontrar un espacio JL es aleatorio: haga proyecciones aleatorias, si falla, intente nuevamente.

4) SVD es único (el subespacio puede no ser único, pero el valor objetivo será el mismo para todos los subespacios). La ecuación (1) anterior no es precisa en el sentido de que JL en realidad no habla de minimizar la discrepancia en las distancias por pares, sino que garantiza la existencia de un subespacio más pequeño donde las distancias serán casi $\epsilon$ diferentes de su actual valores. Podría haber muchos de estos subespacios, algunos mejores que otros.

(Consulte los comentarios para obtener una explicación sobre las partes marcadas de la respuesta).

Editar: @ john-myles-white ha escrito una publicación sobre JL para verificar sus afirmaciones y mostrar cómo se puede construir una proyección: http://www.johnmyleswhite.com/notebook/2014/03/24/a-note- on-the-johnson-lindenstrauss-lemma /

elexhobby
fuente

Hay una serie de errores en su respuesta. (1) JL es extremadamente constructivo: hay todo tipo de algoritmos para construir el mapeo (2) no conserva la diferencia pero la diferencia relativa (la relación) (3) el lema JL se ha desrandomizado (4) JL funciona para cualquier conjunto de vectores: la construcción es independiente de la entrada real. La única información necesaria es el número de vectores.

Suresh Venkat

Gracias Suresh He incorporado todo excepto tu sugerencia final. Siéntase libre de editar aún más la respuesta. Sobre el último punto, estoy confundido. ¿Estás diciendo que el mismo mapa funcionará sin importar qué conjunto de vectores te dé?

elexhobby

Ese es un punto ligeramente sutil. Una vez que arregla el error y el número de vectores, hay una distribución de probabilidad fija en los mapas que funcionará con alta probabilidad para cualquier conjunto de vectores. Por supuesto, no hay un mapa lineal fijo determinista que satisfaga esta propiedad.

Sasho Nikolov

Vale la pena echarle un vistazo a la implementación scikit-learn de

KLDavenport

Me gustaría agregar que no solo no existe un algoritmo determinista para construir una incrustación JL en general, es típicamente computacionalmente prohibitivo verificar que una matriz generada aleatoriamente de acuerdo con el algoritmo JL realmente tenga la propiedad "casi isometría" (aunque lo hace con muy alta probabilidad). Entonces creo que es razonable decir que el teorema de JL no es constructivo. Compare con el algoritmo "elija un número real aleatorio entre y "; esto da un número trascendental con probabilidad , pero no lo llamaría constructivo.

0

$0$

1

$1$

1

$1$

Paul Siegel