Distancia de Fermat · Parte 6 de 14

Cuando la variedad es desconocida: aprender la distancia

La hipótesis de la variedad nos ofrece un marco teórico en el que abordar la clasificación en alta dimensión, y encontramos en la literatura que la estimación de densidad por núcleos en variedades de Riemann compactas sin frontera está estudiada y tiene buenas garantías de convergencia. Por alentador que resulte, ya notamos una primera dificultad — el cómputo de — y nos resta una segunda: la variedad que soporta las no suele ser conocida. Salvo que los datasets estén generados sintéticamente o el objeto de estudio cuente con un dominio bien entendido y ya formalizado, tendremos problemas tanto para definir adecuadamente la dimensión intrínseca como la distancia en .

La Tierra vista desde el espacio
Secuencia de Hubble de tipos de galaxia
Figura 1: Datos espaciales en variedades bien definidas. (izq.) Los datos geoespaciales están sobre la corteza terrestre, que es aproximadamente la -esfera que representa la frontera de nuestra «canica azul», una -bola. (der.) La clasificación clásica de Hubble distingue literalmente variedades «elípticas», «espirales» e «irregulares» de galaxias de acuerdo con cómo se orientan sus estrellas.1

Considere, por caso, el diagrama de Figura 2, la curva .

Figura 2: La curva de dimensión embebida en . En el espacio ambiente, . Trasladándose sobre , .

A los fines de estimar la densidad de soportada en cierta variedad , hace falta una noción de distancia apropiada en , pues como ya dijimos, raramente bastará con la propia del espacio ambiente.

En el ejemplo de Figura 2, con tan solo observaciones es imposible distinguir , pero con una muestra «suficientemente grande», es de esperar que los propios datos revelen la forma de la variedad. Sobre esta idea se edifica la teoría de «aprendizaje de distancias».

La distancia entre dos puntos es una representación útil de cuán similares son: a menor distancia, mayor similitud. Por ello, la estimación de variedades es fundamental al aprendizaje de representaciones. En una extensa reseña de dicho campo, [1] así lo explican:

La principal tarea del aprendizaje no supervisado se considera entonces como el modelado de la estructura de la variedad que sustenta los datos. La representación asociada que se aprende puede asociarse con un sistema de coordenadas intrínseco en la variedad embebida.

— [1, §8]

El ejemplo canónico: análisis de componentes principales (PCA)

El término «hipótesis de la variedad» es moderno, pero el concepto está presente hace más de un siglo en la teoría estadística2.

El algoritmo arquetípico de modelado de variedades es, como era de esperar, también el algoritmo arquetípico de aprendizaje de representaciones de baja dimensión: el Análisis de Componentes Principales, PCA [2], que dada , devuelve en orden decreciente las «direcciones de mayor variabilidad» en los datos, . Proyectar sobre las primeras direcciones,

(1)

nos devuelve la «mejor»3 representación lineal de dimensión .

Figura 3: y sus componentes principales. Fuente: «On lines and planes of closest fit to systems of points in space.» [2]

Ya se dijo que las variedades que soportan variables aleatorias «silvestres»4 seguramente sean fuertemente no lineales. Sin embargo, todavía hay lugar para PCA en esta aventura: cuando el dataset tiene dimensión verdaderamente muy alta, un proceso razonable consistirá en primero disminuir la dimensión a un subespacio lineal en que las distancias relativas sean casi idénticas a las del espacio original usando PCA, y recién en este subespacio aplicar técnicas más complejas de aprendizaje de distancias.

Aprendizaje del espacio tangente

Aprovechando que al menos las observaciones de entrenamiento son puntos conocidos de la variedad5, y que en la variedad el espacio es localmente euclídeo, P. Vincent y Y. Bengio [3] parten del estimador de densidad por núcleos multivariado (ver tercera parte) pero en lugar de utilizar un núcleo fijo en cada observación , se proponen hacer análisis de componentes principales en un vecindario de cada observación . En lugar de fijar un vecindario «duro» (de observaciones o radio ), definen un «vecindario suave» según , una medida de cercanía en el espacio ambiente tal como la densidad normal multivariada 6:

(2)

La estimación de densidad asociada resulta:

(3)

Ahora bien, computar una para cada una de las observaciones, más su inversa y la «raíz cuadrada» de esta última es muy costoso, por lo que los autores agregan un refinamiento: si la variedad en cuestión es de dimensión , es de esperar que las direcciones principales a partir de la -ésima sean «negligibles»7. En lugar de computar las componentes principales de ,

  1. fijan de antemano la dimensión esperada para la variedad,
  2. se quedan con las direcciones principales8,
  3. «ponen en cero» el resto y
  4. «completan» la aproximación con un poco de «ruido» .

La aproximación resultante — con los primeros autovectores y autovalores de — es mucho menos costosa de invertir, y tiene una interpretación geométrica bastante intuitiva en cada punto. Usando el mismo clasificador basado en la regla de Bayes que ya mencionamos en la segunda parte, obtienen así resultados superadores a los del KDE multivariado con . El método es intuitivo e ingenioso, pero todavía consta de dos dificultades:

En un trabajo contemporáneo a [3], «Charting a Manifold» [8], el autor aborda dificultades análogas en el contexto de la reducción de dimensionalidad, en tres etapas:

  1. estimar la dimensión intrínseca de la variedad ; luego
  2. definir un conjunto de cartas centradas en cada observación que minimicen una divergencia global, y finalmente
  3. «coser» las cartas a través de una conexión global sobre la variedad.

El procedimiento para estimar es tanto ingenioso como costoso de computar. Sean observaciones -dimensionales muestreadas de una distribución en con con algo de ruido isotrópico10 -dimensional. Dada una bola centrada en un punto cualquiera , consideremos la tasa a la que incorpora observaciones vecinas a medida que crece . Cuando está en la escala del ruido isotrópico, la bola incorpora puntos rápidamente, pues los hay en todas las direcciones. A medida que alcanza la escala en la que la variedad es localmente análoga a , la incorporación de nuevos puntos disminuye, pues solo habrá nuevas observaciones en las direcciones tangentes a . Si sigue creciendo, la bola eventualmente alcanzará la escala de la curvatura de la variedad, momento en el que comenzará a acelerarse nuevamente la incorporación de puntos. El que minimiza identifica la escala localmente lineal, y la tasa de crecimiento en esa escala, la dimensión intrínseca: allí la cantidad de puntos en la bola crece como .11

Figura 4: Una bola de radio creciente centrada en un punto de una -variedad muestreada con ruido en minimiza la tasa a la que incorpora observaciones cuando está en la escala «localmente lineal» de la variedad. Fuente: [8, Fig. 1]

Estimada , los pasos siguientes no son menos complejos. Por un lado, se plantea un sistema de ecuaciones para obtener simultáneamente todos los entornos coordenados centrados en cada observación minimizando una medida de divergencia entre vecinos12. Finalmente, han de encontrar una conexión entre los entornos coordenados de cada observación, de manera que se puedan definir coordenadas para cualquier punto de la variedad y con ellas formar un atlas diferenciable.

Una conexión [9] es otro término de significado muy preciso en geometría riemanniana que aquí usamos coloquialmente. Es un objeto geométrico que conecta espacios tangentes cercanos, describiendo precisamente cómo estos varían a medida que uno se desplaza sobre la variedad. La «conexión» de Brand es más modesta: un conjunto de transformaciones afines que llevan las coordenadas locales de cada carta a un único sistema de coordenadas global en , resuelto en forma cerrada por mínimos cuadrados. El resultado es una representación de baja dimensión con mapas de ida y vuelta, del mismo tipo que las de Isomap o LLE13, pero no una métrica ni una densidad de volumen . Si se dispusiera de un atlas diferenciable con su conexión en sentido estricto, sería posible en principio computar y ; pero a esta altura, hemos reemplazado el de por sí difícil problema original — encontrar una buena representación de baja dimensión — por uno tal vez aún más difícil: encontrar la dimensión intrínseca, un atlas diferenciable y su conexión global para una variedad desconocida. El proceso es sumamente interesante, pero complejiza en lugar de simplificar nuestro desafío inicial.

Isomap

En rigor, no es necesario conocer para estimar densidades en ella; bastaría con conocer una aproximación a la distancia geodésica en que sirva de sustituto a la distancia euclídea en el espacio ambiente. Probablemente el algoritmo más conocido a tal fin sea Isomap — por «mapeo isométrico de features».

Desarrollado a fines del siglo XX por Joshua Tenenbaum et al. [10], [11], el algoritmo consta de tres pasos:

Definición (algoritmo Isomap). Sean observaciones -dimensionales. El mapeo isométrico de features es el resultado de:

  1. Construir el grafo pesado de vecinos más cercanos , donde cada observación es un vértice y la arista14 que une con está presente con peso si y solo si

    • (-Isomap): la distancia euclídea entre y en el espacio ambiente es menor o igual a , , o
    • (-Isomap): es uno de los vecinos más cercanos de 15.
  2. Computar la distancia geodésica en el grafo — el «costo» de los caminos mínimos — entre todo par de observaciones, 16.
  3. Construir la representación -dimensional utilizando MDS17 en el espacio euclídeo que minimice una métrica de discrepancia denominada «estrés», entre las distancias de (2) y la norma euclídea en la representación. Para elegir el valor óptimo de , búsquese el «codo» en el gráfico de estrés en función de la dimensión de MDS18.

Figura 5: Isomap aplicado a 1.000 dígitos «2» manuscritos del dataset MNIST con . Nótese que las dos direcciones se corresponden fuertemente con características de los dígitos: el rulo inferior en el eje , y el arco superior en el eje . Fuente: [11].

La pieza clave del algoritmo es la estimación de la distancia geodésica en a través de su aproximación por la distancia en el grafo de vecinos más cercanos. Si la muestra disponible es «suficientemente grande» y el espacio está «densamente muestreado», es razonable esperar que en el entorno de una observación las distancias euclídeas aproximen bien las distancias geodésicas, y por ende un «paseo» por el grafo debería describir una curva prácticamente contenida en . Isomap fue — y aún es — un algoritmo sumamente efectivo que avivó el interés por el aprendizaje de distancias, pero cuenta con un talón de Aquiles: la elección del parámetro de cercanía, o :

Referencias

  • [1] Y. Bengio, A. Courville, y P. Vincent, «Representation Learning: A Review and New Perspectives», IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 35, n.º 8, pp. 1798-1828, ago. 2013, doi: 10.1109/TPAMI.2013.50.
  • [2] K. Pearson, «LIII. On Lines and Planes of Closest Fit to Systems of Points in Space», nov. 1901, doi: 10.1080/14786440109462720.
  • [3] P. Vincent y Y. Bengio, «Manifold Parzen Windows», en Advances in Neural Information Processing Systems, MIT Press, 2002.
  • [4] T. Hastie, R. Tibshirani, y J. Friedman, Elements of Statistical Learning Data Mining, Inference, and Prediction. Springer London, Limited, 2009.
  • [5] Y. Bengio, H. Larochelle, y P. Vincent, «Non-Local Manifold Parzen Windows», en Advances in Neural Information Processing Systems, MIT Press, 2005.
  • [6] S. Rifai, Y. N. Dauphin, P. Vincent, Y. Bengio, y X. Muller, «The Manifold Tangent Classifier», en Advances in Neural Information Processing Systems, Curran Associates, Inc., 2011.
  • [7] P. Simard, B. Victorri, Y. LeCun, y J. Denker, «Tangent Prop - A Formalism for Specifying Selected Invariances in an Adaptive Network», en Advances in Neural Information Processing Systems, Morgan-Kaufmann, 1991.
  • [8] M. Brand, «Charting a Manifold», en Advances in Neural Information Processing Systems, MIT Press, 2002.
  • [9] M. P. do Carmo, Riemannian Geometry. Birkhäuser Boston, 1992.
  • [10] J. Tenenbaum, «Mapping a Manifold of Perceptual Observations», en Advances in Neural Information Processing Systems, MIT Press, 1997.
  • [11] J. B. Tenenbaum, V. de Silva, y J. C. Langford, «A Global Geometric Framework for Nonlinear Dimensionality Reduction», Science, vol. 290, n.º 5500, pp. 2319-2323, dic. 2000, doi: 10.1126/science.290.5500.2319.
  • [12] R. W. Floyd, «Algorithm 97: Shortest Path», Communications of the ACM, vol. 5, n.º 6, p. 345, jun. 1962, doi: 10.1145/367766.368168.
  • [13] E. W. Dijkstra, «A Note on Two Problems in Connexion with Graphs», Numerische Mathematik, vol. 1, n.º 1, pp. 269-271, dic. 1959, doi: 10.1007/BF01386390.
  • [14] J. B. Kruskal, «Multidimensional Scaling by Optimizing Goodness of Fit to a Nonmetric Hypothesis», Psychometrika, vol. 29, n.º 1, pp. 1-27, mar. 1964, doi: 10.1007/BF02289565.
  1. 1La categorización completa es más compleja, con outliers cuando distintas galaxias interactúan entre sí, como las Antennae. La topología del espacio-tiempo es un tópico de estudio clave en la relatividad general.
  2. 2Estas referencias vienen del mismo Bengio comentando en Reddit sobre el origen del término.
  3. 3Cuya definición precisa obviamos.
  4. 4Es decir, medidas «en el campo», por contraposición a aquellas definidas y generadas digitalmente según leyes conocidas.
  5. 5″Módulo« el error de medición, claro está.
  6. 6En los experimentos del trabajo, no obstante, usan el vecindario duro de los vecinos más cercanos.
  7. 7La sugerente metáfora que usan en el trabajo es que en lugar de ubicar una «bola» de densidad alrededor de cada observación , quieren ubicar un «panqueque» tangente a la variedad.
  8. 8En la práctica, las obtienen usando SVD — descomposición en valores singulares [4, §3, Eq. 45, p. 64].
  9. 9El grupo de Bengio, Vincent y Rifai continuó con estos estimadores, con énfasis en aprender una geometría global de la variedad, pero a partir de aquí su camino se desvía del de esta monografía: Y. Bengio, H. Larochelle, y P. Vincent [5] agregan restricciones globales a los núcleos punto a punto y los computan con redes neuronales, y S. Rifai, Y. N. Dauphin, P. Vincent, Y. Bengio, y X. Muller [6] aprenden explícitamente un atlas para clasificar con TangentProp [7].
  10. 10Del griego iso-, «igual», y -tropos, «dirección»: «igual en todas las direcciones».
  11. 11Más precisamente, el autor sigue , con la cantidad de puntos en la bola, que vale aproximadamente en la escala del ruido, es menor a en la escala de la curvatura, y alcanza su máximo en la escala localmente lineal. El máximo de da así tanto la escala como la dimensión. Además, evalúa las bondades y dificultades de estimar tanto punto a punto como globalmente en toda la variedad.
  12. 12 A tal fin, modela la muestra como una «mezcla de gaussianas» — gaussian mixture modelling o «GMM» por sus siglas en inglés —, con , y resuelve simultáneamente maximizando la verosimilitud de la mezcla — que «aplasta» cada componente sobre los datos — penalizada por una a priori que castiga la divergencia entre gaussianas vecinas. Intuitivamente, la divergencia representa el «costo» o «error» que resulta de querer representar un punto del vecindario de en las coordenadas correspondientes a un vecindario de : es la divergencia de Kullback-Leibler entre y , que el autor llama entropía cruzada. Nótese que solo exige que los subespacios principales de vecinos sean casi el mismo, no que sus ejes estén alineados, lo que vuelve convexo el problema.
  13. 13Locally linear embeddings en inglés. Sobre Isomap ampliaremos en la siguiente sección.
  14. 14Edge en inglés.
  15. 15O viceversa: el grafo se toma no dirigido, así que basta con que uno de los dos sea vecino más cercano del otro.
  16. 16A tal fin, se puede utilizar según convenga el algoritmo de Floyd-Warshall [12] o el de Dijkstra [13].
  17. 17Multidimensional scaling, o «escalamiento multidimensional», un algoritmo de reducción de dimensionalidad [14].
  18. 18Valor que debería coincidir con la dimensión intrínseca de los datos.