Análisis de los componentes del barrio

El análisis de componentes de vecindad es un método de aprendizaje supervisado para clasificar datos multivariados en clases distintas según una métrica de distancia dada sobre los datos. Funcionalmente, cumple los mismos propósitos que el algoritmo de los K vecinos más cercanos y hace uso directo de un concepto relacionado denominado vecinos más cercanos estocásticos .

El análisis de componentes de vecindad apunta a "aprender" una métrica de distancia al encontrar una transformación lineal de los datos de entrada de modo que el desempeño promedio de la clasificación de tipo leave-one-out (LOO) se maximice en el espacio transformado. La idea clave del algoritmo es que se puede encontrar una matriz correspondiente a la transformación al definir una función objetivo diferenciable para , seguida 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 como una función de , hasta una constante escalar. Por lo tanto, este uso del algoritmo aborda la cuestión de la selección del modelo . ${\displaystyle A}$${\displaystyle A}$${\displaystyle k}$${\displaystyle A}$

Para definir , definimos una función objetivo que describe la precisión de la clasificación en el espacio transformado y tratamos de determinarla de manera que se maximice esta función objetivo. ${\displaystyle A}$${\displaystyle A^{*}}$

${\displaystyle A^{*}={\mbox{argmax}}_{A}f(A)}$

Considere la predicción de la etiqueta de clase de un único punto de datos por consenso de sus vecinos más cercanos con una métrica de distancia dada. Esto se conoce como clasificación de dejar uno afuera . Sin embargo, el conjunto de vecinos más cercanos puede 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 objetivo basada en los vecinos de un punto será constante por partes y, por lo tanto, no diferenciable . ${\displaystyle k}$${\displaystyle C_{i}}$${\displaystyle A}$${\displaystyle f(\cdot )}$

Podemos resolver esta dificultad utilizando un enfoque inspirado en el descenso de gradiente estocástico . En lugar de considerar a los vecinos más cercanos en cada punto transformado en la clasificación LOO, consideraremos todo el conjunto de datos transformados como vecinos más cercanos estocásticos . Los definimos utilizando una función softmax de la distancia euclidiana al cuadrado entre un punto de clasificación LOO dado y cada uno de los otros puntos en el espacio transformado: ${\displaystyle k}$

${\displaystyle p_{ij}={\begin{cases}{\frac {e^{-||Ax_{i}-Ax_{j}||^{2}}}{\sum _{k\neq i}e^{-||Ax_{i}-Ax_{k}||^{2}}}},&{\mbox{if }}j\neq i\\0,&{\mbox{if }}j=i\end{cases}}}$

La probabilidad de clasificar correctamente un punto de datos es la probabilidad de clasificar los puntos de cada uno de sus vecinos con la misma clase : ${\displaystyle i}$${\displaystyle C_{i}}$

${\displaystyle p_{i}=\sum _{j\in C_{i}}p_{ij}\quad }$donde es la probabilidad de clasificar al vecino del punto . ${\displaystyle p_{ij}}$${\displaystyle j}$${\displaystyle i}$

Defina la función objetivo utilizando la clasificación LOO, esta vez utilizando todo el conjunto de datos como vecinos estocásticos más cercanos:

${\displaystyle f(A)=\sum _{i}\sum _{j\in C_{i}}p_{ij}=\sum _{i}p_{i}}$

Tenga en cuenta que, en el caso de los vecinos más próximos estocásticos, la clase de consenso para un único 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 uno , donde ahora es todo el conjunto de datos transformados. ${\displaystyle i}$${\displaystyle j\in C_{i}}$${\displaystyle P(Class(X_{i})=Class(X_{j}))=p_{ij}}$${\displaystyle j\in C_{j}}$${\displaystyle C_{j}}$

Esta elección de función objetivo es preferible ya que es diferenciable con respecto a (denotar ): ${\displaystyle A}$${\displaystyle x_{ij}=x_{i}-x_{j}}$

${\displaystyle {\frac {\partial f}{\partial A}}=-2A\sum _{i}\sum _{j\in C_{i}}p_{ij}\left(x_{ij}x_{ij}^{T}-\sum _{k}p_{ik}x_{ik}x_{ik}^{T}\right)}$

${\displaystyle =2A\sum _{i}\left(p_{i}\sum _{k}p_{ik}x_{ik}x_{ik}^{T}-\sum _{j\in C_{i}}p_{ij}x_{ij}x_{ij}^{T}\right)}$

Obtener un gradiente para significa 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 da como resultado tiempos de cálculo razonables incluso para grandes conjuntos de datos. ${\displaystyle A}$

"Maximizar es equivalente a minimizar la distancia entre la distribución de clases predicha y la distribución de clases verdadera (es decir: donde los inducidos por son todos iguales a 1). Una alternativa natural es la divergencia KL, que induce la siguiente función objetivo y gradiente:" (Goldberger 2005) ${\displaystyle f(\cdot )}$${\displaystyle L_{1}}$${\displaystyle p_{i}}$${\displaystyle A}$

${\displaystyle g(A)=\sum _{i}\log \left(\sum _{j\in C_{i}}p_{ij}\right)=\sum _{i}\log(p_{i})}$

${\displaystyle {\frac {\partial g}{\partial A}}=2A\sum _{i}\left(\sum _{k}p_{ik}x_{ik}x_{ik}^{T}-{\frac {\sum _{j\in C_{i}}p_{ij}x_{ij}x_{ij}^{T}}{\sum _{j\in C_{i}}p_{ij}}}\right)}$

En la práctica, la optimización del uso de esta función tiende a dar resultados de rendimiento similares a los del original. ${\displaystyle A}$

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.

• Agrupamiento espectral
• Gran margen vecino más cercano

• J. Goldberger, G. Hinton, S. Roweis, R. Salakhutdinov. (2005) Análisis de componentes de vecindad. Avances en sistemas de procesamiento de información neuronal. 17, 513–520, 2005.

• La biblioteca MLPACK contiene una implementación de C++
• nca ( C++ )
• Implementación de "NeighborhoodComponentsAnalysis" de scikit-learn ( Python )