¿Por qué las proyecciones aleatorias son probablemente tan efectivas como las diseñadas cuidadosamente?
Esta pregunta que ha hecho en la sección “detalles” es la pregunta clave del lema JL. Y la desafortunada verdad es que no lo son . O más bien, lo son, pero solo cuando sus datos están por todas partes.
Para ver por qué, considere este ejemplo de juguete que dibujé. (Tenga en cuenta que este ejemplo se eligió porque podemos visualizar 3 dimensiones, y no porque la matemática del lema JL sea útil aquí. Es solo para intuición). 
Esto nos lleva a nuestro primer punto: para entender una versión “simplificada” del lema JL, debemos entender:
- ¿Cuál es la diferencia entre el aprendizaje inductivo y transductivo?
- ¿Funciona el aprendizaje profundo si las entradas están en un espacio dimensional relativamente bajo?
- ¿Qué se entiende exactamente por pesos compartidos en una red neuronal convolucional?
- ¿Cómo funcionan las capas de incrustación en TensorFlow?
- ¿Cuáles son los algoritmos estándar para la inferencia en redes bayesianas?
¿Qué dice realmente el lema de JL sobre las proyecciones?
Intuitivamente, el lema de JL dice que es esto: si elige un subespacio aleatorio y proyecta en él, las distancias por pares escaladas entre puntos probablemente se conservarán .
Esto será cierto independientemente del conjunto de puntos que tenga. Pero notará que en el ejemplo de la derecha, algunos aviones parecen ser “mejores” que otros. En el conjunto de puntos a la izquierda, probablemente podría proyectarse en cualquier plano, y seguramente sería igualmente malo. Pero los datos de la derecha parecen estar cerca de un plano, por lo que intuitivamente, los planos “cercanos” a los datos parecen ser “menos malos”.
Por un lado, el lema JL nos dice que las distancias por pares probablemente no estén distorsionadas. Pero, por otro lado, la geometría nos dice que algunas proyecciones son “mejores” que otras. Y este desajuste nos dice algo interesante sobre las proyecciones aleatorias:
- La distancia por pares no nos dice todo lo que hay que saber sobre la reducción de dimensionalidad . El lema JL por sí solo no puede decirnos por qué algunas proyecciones son peores que otras en el conjunto de datos de la derecha. Todo lo que nos dice es que la distancia por pares escalada no se distorsiona demasiado.
- Pero sigue siendo bastante útil . Por ejemplo, si estaba ejecutando vecinos más cercanos aproximados o algo así, podría elegir una proyección aleatoria y reducir la dimensión de manera significativa, pero aún así sería principalmente correcta.
Entonces, en cierto sentido, el lema JL parece funcionar porque las distancias por pares no son tan importantes para la reducción de la dimensionalidad como podríamos haber esperado. Aún así, es interesante que sean tan resistentes a la proyección aleatoria, y parece que vale la pena preguntarse por qué.
Una definición más formal del lema JL
Primero expondré el lema JL, y luego demostraré la intuición usando una caricatura de una prueba, lo que debería darle una buena idea de por qué es cierto.
Proposición 1 (el lema JL): Para algunos [math] k \ ge O (\ log m / \ varepsilon ^ 2) [/ math] (donde [math] \ varepsilon [/ math] es nuestra tolerancia de error elegida), con alta probabilidad, el mapa [matemática] f: \ mathbb {R} ^ d \ rightarrow \ mathbb {R} ^ k [/ math] no cambia la distancia por pares entre dos puntos más que un factor de [math] (1 \ pm \ varepsilon) [/ math], después de escalar en [math] \ sqrt {n / k} [/ math]).
Hay un par de cosas que es bueno notar sobre el lema JL que podrían ayudarlo a saber cuándo es aplicable a sus problemas.
- Hace declaraciones para la reducción del espacio alto al espacio “medio”. Realmente no funciona de la misma manera para espacios extremadamente pequeños, como [math] \ mathbb {R} ^ 1 [/ math].
- De acuerdo con el lema JL, nuestra elección de [math] k [/ math] (recuerde que estamos mapeando de [math] \ mathbb {R} ^ d [/ math] a [math] \ mathbb {R} ^ k [ / math]) debería depender solo del número de puntos [math] m [/ math] y nuestra tolerancia al error [math] \ varepsilon [/ math].
Una caricatura de una prueba
[ Nota: creo que esta “caricatura” se debe a Avrim Blum, pero no puedo encontrarla, por lo que no puedo estar seguro.]
La esencia de la prueba es esta: el lema JL se deduce del hecho de que la longitud al cuadrado de un vector se concentra bruscamente alrededor de su media cuando se proyecta en un subespacio aleatorio [matemático] k [/ matemático]. Lo que pretendemos mostrar en esta sección es por qué esto incluso sería cierto o útil para probar el lema JL.
Comenzaremos como algo que realmente no se parece al lema de JL, pero al final con suerte quedará claro cuál es la relación.
Primero, digamos que muestreamos aleatoriamente [matemática] m [/ matemática] puntos que se encuentran en la superficie de una esfera dimensional [matemática] d [/ matemática]. Estos puntos también pueden verse como vectores aleatorios de longitud unitaria. 
Nos gustaría ver cómo se comportan las coordenadas individuales. Entonces simplificaremos un poco la imagen.
Dado que se encuentran en una [dimensión matemática] d [/ matemática], son puntos en [matemática] \ mathbb {R} ^ d [/ matemática]. Pero tenga en cuenta que, independientemente del tamaño de [math] d [/ math], podemos decir que estos puntos se encuentran en un subespacio dimensional [math] m [/ math], porque solo hay [math] m [/ matemáticas] puntos. Entonces diremos que se encuentran en [math] \ mathbb {R} ^ m [/ math].
Comencemos mirando la primera coordenada. Según la teoría de probabilidad estándar, sabemos que [math] \ mathbb {E} [x ^ 2_1] = 1 / m [/ math]. Tenga en cuenta que a medida que [math] m [/ math] aumenta, la concentración aumenta precipitadamente, lo que significa que los valores reales de las coordenadas se concentrarán fuertemente alrededor de este valor.
Ahora nos gustaría extender esta intuición para observar todas las coordenadas. Dado que el valor de estas coordenadas se concentrará fuertemente alrededor de [matemática] 1 / m [/ matemática] para grandes [matemática] m [/ matemática], podemos ver que el tipo de coordenadas parece un poco iid. En realidad no lo son, porque si una coordenada es grande, las otras son necesariamente pequeñas, pero esta “nitidez” significa que son “casi” iid. Esto no es una prueba real, ¿verdad? Entonces, digamos que son iid con fines ilustrativos.
Si son iid, entonces podemos aplicar nuestro Chernoff / Hoeffding favorito para decir que, con una probabilidad realmente alta, todas las coordenadas estarán realmente muy cerca de ser [matemáticas] 1 / m [/ matemáticas] en tamaño. Por ejemplo, [matemáticas] p (| (x_1 ^ 2 + \ ldots + x_k ^ 2) – k / n | \ ge \ varepsilon k / n] \ le 1 / (e ^ {O (k \ varepsilon ^ 2) }) [/ math]. Recuerde, esto es si son iid, que por supuesto no lo son, pero se ven como si fueran. Esto es intuición.
En este punto, estamos listos para mirar proyecciones aleatorias. La idea básica es que tomaremos un plano aleatorio y proyectaremos nuestros vectores unitarios en él. Aquí hay una serie de ejemplos “aleatorios” que inventé (tenga en cuenta que el plano de proyección se traduce al origen). 
Pero resulta que podemos ver las proyecciones vectoriales de una manera más interesante. Proyectar desde [math] \ mathbb {R} ^ m [/ math] a [math] \ mathbb {R} ^ k [/ math] es básicamente lo mismo que rotar aleatoriamente el vector, y luego leer el primero [math ] k [/ math] coordenadas.
Ahora llegamos al lema JL: para que el lema JL sea básicamente verdadero, la distancia entre los dos vectores debe ser casi la misma después de escalarla en consecuencia. En la imagen de arriba, los vectores proyectados tienen una línea punteada que representa la distancia. En otras palabras, ese vector debe tener casi la misma longitud escalada que en el ejemplo original.
Como era de esperar, resulta que esto es cierto. Aquí están las matemáticas que lo justifican.
Usando el límite de Chernoff-Hoeffding anterior, vemos que en [matemáticas] k = O (\ frac {1} {\ varepsilon ^ 2} \ log n) [/ matemáticas], entonces con probabilidad [matemáticas] 1 – O (n ^ p) [/ math] (para casi cualquier elección entera positiva de [math] p [/ math] que desee), la proyección a las primeras coordenadas [math] k [/ math] tiene una longitud [math] \ sqrt {k / n} \ cdot (1 \ pm \ varepsilon) [/ math].
Ahora, veamos la distancia entre un par de vectores. Digamos que nuestros vectores regulares no proyectados se llaman [math] \ vec {v} _1 [/ math] y [math] \ vec {v} _2 [/ math]. Entonces el vector que representa la línea punteada entre los vectores originales sería [math] \ vec {d} = \ vec {v} _2 – \ vec {v} _1 [/ math].
Y aquí está la línea de golpe. Podemos tomar ese “vector de distancia” que va entre nuestros vectores originales, y usar el mismo argumento de proyección que el anterior. Por lo tanto, con alta probabilidad (por el límite de la unión), la longitud de todos estos “vectores de distancia” [matemática] \ vec {d} [/ matemática] se proyecta a la longitud [matemática] \ sqrt {\ frac {k} {n} } \ cdot (1 \ pm \ varepsilon) || \ vec {d} || _2 [/ math].
Hacia argumentos más generales.
Así que esa es la intuición de por qué el lema JL es cierto. Como dijimos antes, el lema JL se deduce del hecho de que la longitud al cuadrado de un vector se concentra bruscamente alrededor de su media cuando se proyecta en un subespacio dimensional [matemático] k [/ matemático] aleatorio. Espero que esta última sección explique aproximadamente por qué esto nos ayudaría a probar el lema JL, y es un comienzo de por qué es cierto de manera más general.
Si quieres saber más, espero que esto te ayude a descubrir las pruebas que flotan por ahí. Diría que la respuesta de Alexandre Passos es un comienzo razonable. Existe un excelente tratamiento en Fundamentos del aprendizaje automático, de Mohri et al . Es un libro excelente de todos modos, y deberías leerlo solo porque sí.
