Aprendizaje Automático en un Espacio No Euclidiano

Machine Learning in a Non-Euclidean Space

Capítulo I. Por qué deberías aprender sobre el ML no euclidiano

“¿Es nuestro cómodo y familiar espacio euclidiano y su estructura lineal siempre el lugar correcto para el aprendizaje automático? Investigaciones recientes argumentan lo contrario: no siempre es necesario y a veces es perjudicial, como demuestra una ola de trabajos interesantes. Empezando por la noción de representaciones hiperbólicas para datos jerárquicos hace dos años, un gran impulso ha resultado en nuevas ideas para representaciones en espacios no euclidianos, nuevos algoritmos y modelos con datos y operaciones no euclidianos, y nuevas perspectivas sobre la funcionalidad subyacente del ML no euclidiano.” por Fred Sala, Ines Chami, Adva Wolf, Albert Gu, Beliz Gunel y Chris Ré, 2019

Lo que aprenderás en este artículo

• La distorsión mide cómo se conserva la distancia al representar los datos en otro espacio.
• Para algunos datos, el espacio euclidiano implica una alta distorsión, por lo que se utilizan espacios no euclidianos como los espacios esféricos o hiperbólicos.
• Se utilizan herramientas de geometría riemanniana como variedades y métrica riemanniana para el aprendizaje automático no euclidiano.
• Las variedades son espacios curvos que son localmente euclidianos.
• Se utilizan mapas exponenciales y logarítmicos para ir de una variedad a su espacio tangente.
• La métrica riemanniana permite calcular las distancias más cortas en la variedad.

Antes de profundizar en esta serie sobre geometría no euclidiana aplicada al aprendizaje automático (ML), tuve que responder una pregunta importante. ¿Vale la pena aprender más sobre el ML no euclidiano?

Para responder a esta pregunta, comencé investigando sobre el ML no euclidiano. Rápidamente encontré un par de recursos. El primero de ellos es de Stanford y la cita anterior se extrajo de él. Los autores argumentan que el aprendizaje automático fue diseñado con una cierta geometría, a saber, la geometría euclidiana, más por tradición o conveniencia que por pensamiento racional.

Hasta ahora, la elección de la geometría euclidiana no parece ser un problema importante. Pero los autores llaman nuestra atención citando a Bronstein et al. en su descripción seminal del paradigma del aprendizaje profundo geométrico.

• Una Guía Completa sobre Redes Neuronales Convolucionales
• Búsqueda de similitud, Parte 4 Hierarchical Navigable Small World (HNSW)
• Búsqueda de similitud, Parte 3 Mezclando el índice de archivo invertido y la cuantificación de productos.

“[m]uchos campos científicos estudian datos con una estructura subyacente que es un espacio no euclidiano.” Bronstein et al.

A medida que continuaba leyendo el artículo, me encontré con un aspecto con el que no estaba familiarizado: la noción de planitud del espacio.

“Hemos elegido trabajar con el espacio euclidiano, con todas sus propiedades inherentes, entre las más críticas de las cuales es su planitud.” Fred Sala, Ines Chami, Adva Wolf, Albert Gu, Beliz Gunel y Chris Ré, 2019

Los autores del artículo de Stanford mencionan el impacto de la planitud. A continuación se presentan los tres puntos planteados y deberías leer nuestra serie para obtener más intuición:

• Mejores representaciones — argumentan que los espacios euclidianos no son adecuados para ciertos conjuntos de datos como los conjuntos de datos jerárquicos que pueden describirse mediante árboles.
• Desbloquear todo el potencial de los modelos — argumentan que para superar las barreras en términos de rendimiento del modelo, podríamos mejorar el espacio en el que se encuentran los datos, pasando de la geometría euclidiana a la geometría no euclidiana.
• Operaciones más flexibles — argumentan que las operaciones en espacios no euclidianos son más flexibles y requieren menos dimensiones. Los autores explican esto más adelante en su artículo, pero intentaremos simplificarlo en nuestra serie de Zepes.

Representar una entidad no plana en un espacio plano

Es importante tener una geometría adecuada, condicional a los datos de entrada. A continuación, mostramos un ejemplo de datos no euclidianos que se “obligan” a encajar en un espacio euclidiano bidimensional. Este es nuestro conocido planeta esférico que se aplana en un plano. Sin embargo, esto se hace con distorsiones no despreciables. Con distorsión nos referimos a que no se conservan las distancias, desde el espacio original [Tierra – esfera] hasta el espacio donde se representa los datos [Mapas – plano].

Por ejemplo, México tiene en realidad casi la misma superficie que Groenlandia ( a la derecha ) pero parece mucho más pequeño en la proyección real ( a la izquierda ).

Hay muchas formas de representar nuestra tierra que implican algún grado de distorsión.

Por ejemplo, la distorsión se observa naturalmente en la famosa proyección de Mercator. El problema de Groenlandia muestra la pérdida de información al pasar de una representación esférica a una representación plana con dicha proyección. Esta proyección no es preservadora del área, una propiedad fundamental esperada en este caso. De hecho, Groenlandia, con un área de alrededor de 2.2 millones de kilómetros cuadrados, parece más grande que Sudamérica, con un área de alrededor de 17.8 millones de kilómetros cuadrados. Esta proyección de Mercator preserva los ángulos pero no las áreas, por lo tanto, no es perfecta.

Ahora, otros conjuntos de datos también se ven obligados a estar en un espacio euclidiano en el que observamos distorsiones. Este es el caso de los grafos: en un espacio euclidiano, no podemos incrustar grandes clases de grafos sin baja distorsión o sin pérdida de información.

La distorsión tiene varias definiciones matemáticas más rigurosas. Esencialmente, queremos que la distorsión mida la calidad de la incrustación evaluando cuán bien se preservan las distancias. Aquí, lo definimos de la siguiente manera:

Distorsión ~ AVG {Distancia del grafo / Distancia de la incrustación}

Ejemplo.

En la figura a continuación, podemos demostrar a través de las desigualdades de tipo Poincare que no podemos incrustar los dos ciclos (cuadrado, círculo) en un espacio euclidiano sin distorsión. Tenga en cuenta que una distorsión de 1 es una distorsión perfecta: las distancias del grafo coinciden exactamente con las distancias del espacio de incrustación. Cualquier distorsión diferente de 1 significa que no estamos preservando las distancias del grafo.

En el cuadrado de arriba, los dos nodos opuestos en la diagonal tienen una distancia de 2 en términos de distancia del grafo. Sin embargo, la ruta más corta en la incrustación euclidiana tiene una distancia de √2.

Este concepto de distorsión es realmente importante ya que la geometría euclidiana no permite tener la proyección ideal de los datos del grafo. En particular, para los datos de grafo jerárquicos, para minimizar la distorsión, una solución es usar un espacio hiperbólico.

Nota. Aprenderemos más sobre este ejemplo de espacio no euclidiano en el siguiente capítulo.

Representar datos en un espacio no euclidiano

Es difícil entender cómo podemos representar datos de otra manera que no sea con vectores en Rn. Además, ¿cómo podemos alejarnos de la distancia euclidiana que conocemos tan bien para comparar dos representaciones vectoriales?

En la geometría de Riemann, una solución se describe por medio de variedades. Las variedades son objetos que se parecen a Rn pero solo localmente. Eso significa que podemos usar vectores localmente para representar nuestros puntos de datos. ¡Pero solo localmente!

La noción de similitud o distancias es clave en el aprendizaje automático. Si estamos construyendo, por ejemplo, un modelo de procesamiento del lenguaje natural, queremos preservar la noción de similitud en la semántica dentro del espacio de incrustación que representa la entrada textual. En otras palabras, queremos que dos palabras que sean similares en significado también sean similares en el espacio euclidiano, es decir, con una baja distancia euclidiana. De manera similar, dos palabras que sean diferentes en significado deberían estar lejos en el espacio euclidiano, es decir, con una alta distancia euclidiana.

Por lo tanto, necesita haber un enfoque equivalente cuando se escapa de la geometría euclidiana. Este enfoque se describe mediante una métrica de Riemann. La métrica de Riemann nos permite comparar dos entidades en el espacio no euclidiano y preservar esta noción intuitiva de distancia.

👀 Recuerdo.

Ahora, necesitamos recordar que en este marco no euclidiano podemos realizar operaciones localmente en nuestras representaciones de datos y tenemos una métrica para medir distancias. Por lo tanto, estamos equipados para hacer aprendizaje automático en espacios no euclidianos.

🙌🏻 ¿Por qué debería aprender más sobre el aprendizaje automático en un espacio no euclidiano?

Hasta ahora, sabemos que el aprendizaje automático sin el genio Euclides es algo real. Existen proyectos reales que abordan nuestros problemas de aprendizaje automático tradicionales con un marco de geometría diferente.

Ahora, naturalmente surge una pregunta: ¿vale la pena nuestro tiempo aprender más que la existencia de este campo?

Es un espacio bastante aterrador que involucra matemáticas no triviales. Pero mi amigo, Aniss Medbouhi, Investigador de Doctorado en Aprendizaje Automático en KTH, nos ayudará a superar la complejidad inherente de este espacio.

La otra razón por la que no estaba convencido de este espacio es que leí que era más adecuado para datos jerárquicos que pueden describirse mediante árboles. A primera vista, no involucra los datos con los que trabajo a diario.

Sin embargo, los resúmenes a continuación nos dan una idea de los conjuntos de datos relevantes de interés:

“Sin embargo, el trabajo reciente ha demostrado que el espacio isométrico apropiado para incrustar redes complejas no es el espacio euclidiano plano, sino el espacio hiperbólico de curvatura negativa. Presentamos un nuevo concepto que explota estas ideas recientes y proponemos aprender incrustaciones neuronales de grafos en el espacio hiperbólico. Proporcionamos evidencia experimental de que la incrustación de grafos en su geometría natural mejora significativamente el rendimiento en tareas posteriores para varios conjuntos de datos públicos del mundo real.” Chamberlain et al.

“Sin embargo, aunque los conjuntos de datos simbólicos complejos a menudo exhiben una estructura jerárquica latente, los métodos más avanzados típicamente aprenden incrustaciones en espacios vectoriales euclidianos, que no tienen en cuenta esta propiedad. Para este propósito, presentamos un nuevo enfoque para aprender representaciones jerárquicas de datos simbólicos mediante su incrustación en el espacio hiperbólico, o más precisamente, en una bola de Poincaré de n dimensiones.” Nickel y Kiela

Los conjuntos de datos mencionados anteriormente se enumeran a continuación, según Chamberlain et al.:

(1) Karate: el club de karate de Zachary contiene 34 vértices divididos en dos facciones. [4]

(2) Polbooks: una red de libros sobre la política estadounidense publicados alrededor de la época de la elección presidencial de 2004 y vendidos por el vendedor de libros en línea Amazon.com. Las aristas entre los libros representan compras frecuentes de libros por los mismos compradores.

(3) Fútbol: una red de partidos de fútbol americano entre universidades de la División IA durante la temporada regular de otoño de 2000. [2]

(4) Adjnoun: red de adyacencia de adjetivos y sustantivos comunes en la novela David Coppereld de Charles Dickens. [3]

(5) Polblogs: una red de hipervínculos entre blogs sobre política estadounidense, registrados en 2005. [1]

Además, en biología, encontramos este conjunto de datos de referencia:

• Biología: datos evolutivos como proteínas. [5]

Finalmente, los datos de PNL, es decir, los datos textuales, son otro tipo de datos jerárquicos. Como resultado, muchos dominios pueden beneficiarse de la comprensión de los avances en el aprendizaje automático no euclidiano.

Ahora que sabemos cómo representar mejor ciertos conjuntos de datos, es clave relacionarlo con el aprendizaje automático. Cualquier tarea de aprendizaje automático requiere primero la ingestión de datos. Se dedica mucho tiempo a limpiar nuestros datos subyacentes y representarlo con precisión. La calidad de la representación de los datos es esencial ya que afecta directamente el rendimiento de nuestros modelos. Por ejemplo, en PNL, aconsejo a mis estudiantes que se centren en arquitecturas que proporcionen buenos embeddings, como embeddings contextuales. Ha habido una extensa investigación en la mejora de los embeddings, pasando de las redes neuronales superficiales (fasttext, word2vec) a las redes neuronales profundas y transformadores (sentence-transformers, BERT, RoBERTa, XLM). Sin embargo, también vale la pena señalar que la representación de datos está muy relacionada con la tarea en cuestión, y la investigación muestra que ciertas redes neuronales superficiales proporcionan mejores resultados que las redes neuronales profundas, para ciertas tareas.

Conclusión

En este artículo, vimos que podemos aprovechar la geometría no euclidiana para abordar problemas existentes específicos de datos esféricos y conjuntos de datos jerárquicos como gráficos. Al incrustar dichos conjuntos de datos en un espacio euclidiano, el precio a pagar es una distorsión que no permite preservar las distancias desde el espacio original hasta el espacio de incrustación. Esta distorsión es intuitiva en nuestra representación de la Tierra, donde tenemos muchas formas de representar nuestro globo, algunas de las cuales no preservan las propiedades fundamentales esperadas, como la conservación del área. De manera similar para los gráficos, es necesario preservar las propiedades fundamentales y distorsionar el espacio subyacente puede resultar en un peor rendimiento para las tareas de aprendizaje automático posteriores.

En el siguiente capítulo, aprenderemos más sobre las geometrías esférica e hiperbólica. Nos centraremos más en esta última y daremos una idea de cómo los modelos en dicho espacio pueden incrustar mejor los datos jerárquicos.

Conéctese con los contribuyentes.

Investigador doctoral en ML en el Real Instituto de Tecnología de KTH.

Linkedin . https://www.linkedin.com/in/aniss-medbouhi/

Científico de datos en Microsoft y profesor en EPITA Paris.

Linkedin . https://www.linkedin.com/in/mastafa-foufa/

[1] Lada A. Adamic y Natalie Glance. The political blogosphere and the 2004 U.S. election. Proceedings of the 3rd international workshop on Link discovery — LinkKDD ’05, pages 36–43, 2005.

[2] Michelle Girvan y Mark E. J. Newman. Community structure in social and biological networks. In Proceedings of the national academy of sciences, 99:7821–7826, 2002.

[3] Mark E. J. Newman. Finding community structure in networks using the eigenvectors of matrices. Physical Review E — Statistical, Nonlinear, and Soft Matter Physics, 74(3):1–19, 2006.

[4] Wayne W. Zachary. An information ow model for conict and ssion in small groups. Journal of anthropological research, 33:452–473, 1977.

[5] AlQuraishi, Mohammed. “ProteinNet: un conjunto de datos estandarizado para el aprendizaje automático de la estructura de proteínas”. BMC bioinformatics 20.1 (2019): 1-10.

We will continue to update Zepes; if you have any questions or suggestions, please contact us!