El análisis de componentes de vecindad es un método de aprendizaje supervisado para clasificar datos multivariados en clases distintas de acuerdo con una métrica de distancia dada sobre los datos. Funcionalmente, cumple los mismos propósitos que el algoritmo de K vecinos más cercanos y hace uso directo de un concepto relacionado denominado vecinos estocásticos más cercanos .
Definición
El análisis de componentes de vecindad tiene como objetivo "aprender" una métrica de distancia mediante la búsqueda de una transformación lineal de los datos de entrada de manera que el rendimiento promedio de clasificación de dejar uno fuera (LOO) se maximice en el espacio transformado. La idea clave del algoritmo es que una matriz correspondiente a la transformación se puede encontrar definiendo una función objetivo diferenciable para , seguido del uso de un solucionador iterativo como el descenso de gradiente conjugado . Uno de los beneficios de este algoritmo es que el número de clases se puede determinar en función de , hasta una constante escalar. Por lo tanto, este uso del algoritmo aborda la cuestión de la selección del modelo .
Explicación
Para definir , definimos una función objetivo que describe la precisión de clasificación en el espacio transformado y tratamos de determinar de modo que esta función objetivo se maximice.
Clasificación de dejar uno fuera (LOO)
Considere la posibilidad de predecir la etiqueta de clase de un solo punto de datos por consenso de su -vecinos más cercanos con una métrica de distancia determinada. Esto se conoce como clasificación de dejar uno fuera . Sin embargo, el conjunto de vecinos más cercanospuede ser bastante diferente después de pasar todos los puntos a través de una transformación lineal. Específicamente, el conjunto de vecinos para un punto puede sufrir cambios discretos en respuesta a cambios suaves en los elementos de, lo que implica que cualquier función objetiva basado en los vecinos de un punto será constante a trozos y , por tanto, no diferenciable .
Solución
Podemos resolver esta dificultad utilizando un enfoque inspirado en el descenso de gradiente estocástico . En lugar de considerar el-vecinos más cercanos en cada punto transformado en la clasificación LOO, consideraremos todo el conjunto de datos transformados como vecinos estocásticos más cercanos . Los definimos usando una función softmax de la distancia euclidiana al cuadrado entre un punto de clasificación LOO dado y cada otro punto en el espacio transformado:
La probabilidad de clasificar correctamente el punto de datos. es la probabilidad de clasificar los puntos de cada uno de sus vecinos con la misma clase :
dónde es la probabilidad de clasificar vecino de punto .
Defina la función objetivo usando la clasificación LOO, esta vez usando todo el conjunto de datos como vecinos estocásticos más cercanos:
Tenga en cuenta que en los vecinos estocásticos más cercanos, la clase de consenso para un solo punto es el valor esperado de la clase de un punto en el límite de un número infinito de muestras extraídas de la distribución sobre sus vecinos es decir: . Por lo tanto, la clase predicha es una combinación afín de las clases de todos los demás puntos, ponderada por la función softmax para cada dónde es ahora todo el conjunto de datos transformados.
Esta elección de función objetivo es preferible ya que es diferenciable con respecto a (denotar ):
Obteniendo un gradiente parasignifica que se puede encontrar con un solucionador iterativo como el descenso de gradiente conjugado . Tenga en cuenta que, en la práctica, la mayoría de los términos más internos del gradiente evalúan contribuciones insignificantes debido a la contribución rápidamente decreciente de los puntos distantes del punto de interés. Esto significa que la suma interna del gradiente se puede truncar, lo que resulta en tiempos de cálculo razonables incluso para grandes conjuntos de datos.
Formulación alternativa
"Maximizando es equivalente a minimizar el -distancia entre la distribución de clases predicha y la verdadera distribución de clases (es decir, donde el Inducido por son todos iguales a 1). Una alternativa natural es la divergencia KL, que induce la siguiente función objetivo y gradiente: "(Goldberger 2005)
En la práctica, la optimización de el uso de esta función tiende a dar resultados de rendimiento similares a los del original.
Historia y antecedentes
El análisis de componentes del vecindario fue desarrollado por Jacob Goldberger, Sam Roweis, Ruslan Salakhudinov y Geoff Hinton en el departamento de informática de la Universidad de Toronto en 2004.
Ver también
Referencias
- J. Goldberger, G. Hinton, S. Roweis, R. Salakhutdinov. (2005) Análisis de componentes de vecindario . Avances en sistemas de procesamiento de información neuronal. 17, 513-520, 2005.
enlaces externos
Software
- La biblioteca MLPACK contiene una implementación de C ++
- nca ( C ++ )
- implementación de sklearn ( Python )