Distancia de Fermat · Parte 8 de 14

La propuesta: clasificadores con distancia de Fermat

En función de lo expuesto hasta ahora, creemos que es posible mejorar un algoritmo de clasificación reemplazando la distancia euclídea por una aprendida de los datos, y en particular que la distancia muestral de Fermat es una buena candidata de reemplazo. Deseamos también comprender si el efecto de la aprendida es independiente del algoritmo de clasificación que la incorpore. Para saldar ambas cuestiones, nos propusimos:

  1. Implementar un clasificador basado en estimación de densidad por núcleos según la definición de KDE en variedades de Riemann [1], al que llamaremos «KDC»1.
  2. Implementar un clasificador de densidad por núcleos basado en la distancia de Fermat, «-KDC», a fin de comparar el rendimiento de KDC con distancia euclídea y con distancia de Fermat.
  3. Implementar un clasificador de vecinos más cercanos según la definición del clasificador de vecinos más cercanos, pero con distancia muestral de Fermat en lugar de euclídea.
  4. Comparar sistemáticamente la capacidad de clasificación de cada algoritmo propuesto — y algunos más de referencia — en datasets de diversas características.
  5. Analizar los resultados e identificar en qué condiciones es que la distancia de Fermat aporta mejoras significativas sobre la tradicional distancia euclídea.

El método de aprendizaje de la distancia muestral de Fermat y los tres algoritmos novedosos componen un repositorio de código abierto que acompaña esta tesis y está a disposición de cualquier investigador que desee corroborar los resultados en GitHub2. En los tres se requirieron desarrollos nuevos al menos parcialmente:

A continuación, mencionamos algunos aspectos salientes sobre los desarrollos de código necesarios así como la metodología de evaluación diseñada, antes de pasar a los resultados.

Estimación de distancia de Fermat out-of-sample

Un proyecto de código preexistente a esta monografía ya implementa el cálculo de la distancia de Fermat microscópica o muestral para un conjunto de observaciones dado: fermat, de Facundo Sapienza. Este paquete fue desarrollado para soportar los experimentos de F. Sapienza, M. Jonckheere, y P. Groisman [2] que exploran los efectos de esta noción de distancia en tareas de clustering. Al ser una tarea no supervisada3, se utilizan todas las observaciones disponibles y solo se requiere calcular la distancia entre dos elementos cualesquiera de la muestra , pero nunca contra otros .

Entrenar un algoritmo supervisado de clasificación requiere apartar una fracción de las observaciones disponibles4 y conformar un conjunto de test en el que evaluar la pérdida objetivo . ¿Cómo calculamos entonces la distancia muestral de Fermat de una nueva observación a los elementos de cada grupo , si no incluimos su nodo en el grafo completo de cada clase durante el entrenamiento?

Sencillamente, para cada una de las clases, definimos el conjunto

resultante de unir la nueva observación al conjunto de entrenamiento correspondiente a la clase , y recomputamos . Aunque sencillo de describir, resultaría absurdamente costoso computacionalmente recomputar la matriz completa de distancias para cada una de las clases por cada nueva observación. En su lugar, implementamos un sencillo algoritmo «incremental», que permite recomputar únicamente las geodésicas que cambian al agregar la nueva observación al grafo completo de la clase en cuestión.5

Elección del ancho de banda para clasificación

Al estimar densidades con distancia de Fermat en una variedad, la elección del ancho de banda se simplifica considerablemente: en lugar de una matriz completa como en el KDE multivariado euclídeo, basta con dos escalares — y . Idealmente, convendría elegir un par óptimo para cada clase , ya que las densidades individuales pueden diferir sustancialmente.

Sin embargo, P. Hall y K.-H. Kang [3] muestran que el óptimo para la estimación de densidad no es necesariamente el óptimo para clasificación: la tarea de clasificar no requiere estimar bien la densidad en todo el soporte, sino distinguir bien en las fronteras entre clases. Teniendo esto en cuenta y para simplificar la configuración, parametrizamos -KDC con un único y globales6. La búsqueda de simplicidad en la configuración no es un deseo, es una necesidad: la elección de hiperparámetros óptimos por validación cruzada en una grilla requiere entrenar el mismo clasificador en una cantidad de configuraciones que crece exponencialmente con la cantidad de hiperparámetros, lo cual prohíbe configuraciones mucho más complejas que unos pocos parámetros.

Omisión de la densidad de volumen

El estimador de la definición de KDE en variedades de Riemann incluye un factor que KDC y -KDC omiten: es decir, tomamos . Sin conocer no hay forma de evaluar , como se discutió en la definición de función de densidad de volumen y sus observaciones. Lo único que sabemos de es lo que allí se dijo: vale exactamente en variedades planas, vale en el propio punto y tiende a a medida que se acerca a . Como el núcleo solo pesa observaciones a distancia comparable a , y la construcción de B. Pelletier [4] exige , el factor omitido es cercano a justamente en la región que importa, y tanto más cuanto menor sea respecto de la curvatura de . Para clasificación, conjeturamos7 que el efecto podría ser todavía menor, porque el mismo factor afecta a todas las clases alrededor de y en buena medida se cancela en el cociente de la regla de Bayes. Es un supuesto que no verificamos, que falla en variedades muy curvas respecto de , y que retomamos como debilidad en Trabajo futuro. Por ahora diremos que no es necesariamente un callejón sin salida: en variedades conocidas podemos calcularlo explícitamente [5], y en variedades desconocidas podríamos estimar su efecto. A. L. Besse [6, §6.3] expresa mediante campos de Jacobi a lo largo de las geodésicas que irradian de — es decir, en función de cómo se separan o se juntan las geodésicas vecinas; esa información local es del mismo tipo que la que captura el análisis de componentes principales alrededor de cada observación de P. Vincent y Y. Bengio [7]: cómo cambia el espacio tangente estimado de una observación a sus vecinas.

Referencias

  • [1] J.-M. Loubes y B. Pelletier, «A Kernel-Based Classifier on a Riemannian Manifold», Statistics & Decisions, vol. 26, n.º 1, pp. 35-51, mar. 2008, doi: 10.1524/stnd.2008.0911.
  • [2] F. Sapienza, M. Jonckheere, y P. Groisman, «Weighted Geodesic Distance Following Fermat's Principle», 2018.
  • [3] P. Hall y K.-H. Kang, «Bandwidth Choice for Nonparametric Classification», The Annals of Statistics, vol. 33, n.º 1, feb. 2005, doi: 10.1214/009053604000000959.
  • [4] B. Pelletier, «Kernel Density Estimation on Riemannian Manifolds», Statistics & Probability Letters, vol. 73, n.º 3, pp. 297-304, jul. 2005, doi: 10.1016/j.spl.2005.04.004.
  • [5] G. Henry y D. Rodriguez, «Kernel Density Estimation on Riemannian Manifolds: Asymptotic Results», Journal of Mathematical Imaging and Vision, vol. 34, n.º 3, pp. 235-239, jul. 2009, doi: 10.1007/s10851-009-0145-2.
  • [6] A. L. Besse, Manifolds All of Whose Geodesics Are Closed. Berlin, Heidelberg: Springer Berlin Heidelberg, 1978. doi: 10.1007/978-3-642-61876-5.
  • [7] P. Vincent y Y. Bengio, «Manifold Parzen Windows», en Advances in Neural Information Processing Systems, MIT Press, 2002.
  1. 1Kernel Density Classifier, por sus siglas en inglés.
  2. 2https://github.com/capitantoto/fermat.
  3. 3Una tarea supervisada de aprendizaje es aquella en que se entrena el algoritmo con un conjunto de observaciones para el que ya se sabe el valor correcto de respuesta. Una tarea «no supervisada» no cuenta con una «respuesta correcta» de antemano. Clustering — identificar grupos en la muestra — es una tarea no supervisada; clasificación — asignar elementos a clases conocidas de antemano — es una tarea supervisada.
  4. 4De no hacerlo y evaluar al clasificador sobre los mismos datos de entrenamiento, se corre el riesgo de sobreajustar el clasificador a los datos. De entrenar -NN con toda la muestra, se puede tomar incondicionalmente. Durante el entrenamiento se acertará la clase correcta siempre, ya que cada observación es su propia vecina con distancia cero, pero el clasificador resultante generalizará muy mal a nuevas observaciones.
  5. 5Para más detalles al respecto, léase el método SampleFermatDistance._distancia en el módulo fkdc/fermat.py.
  6. 6Y KDC con un único , elegido sobre una grilla mucho más fina que la de -KDC.
  7. 7Siguiendo un argumento alla P. Hall y K.-H. Kang [3].