Análisis de componentes del barrio.

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

Definición

El análisis de componentes del vecindario tiene como objetivo "aprender" una métrica de distancia al encontrar una transformación lineal de los datos de entrada de modo que el rendimiento promedio de la clasificación de dejar uno fuera (LOO) se maximice en el espacio transformado. La idea clave del algoritmo es que se puede encontrar una matriz correspondiente a la transformación definiendo 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 en función de , hasta una constante escalar. Este uso del algoritmo, por lo tanto, aborda la cuestión de la selección del modelo . ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle k}$ ${\displaystyle A}$

Explicación

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

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

Clasificación de dejar uno fuera (LOO)

Considere predecir la etiqueta de clase de un único punto de datos por consenso de sus 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 cercanos puede ser bastante diferente después de pasar todos los puntos por una transformación lineal. Específicamente, el conjunto de vecinos de 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 )}$

Solución

Podemos resolver esta dificultad utilizando un enfoque inspirado en el descenso de gradiente estocástico . En lugar de considerar 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 usando una función softmax de la distancia euclidiana al cuadrado entre un punto de clasificación LOO dado y cada uno de los demás 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 }$¿Dónde está la probabilidad de clasificar al vecino del punto ? ${\displaystyle p_{ij}}$ ${\displaystyle j}$ ${\displaystyle i}$

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:

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

Tenga en cuenta que bajo 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 uno de los cuales 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 se evalúan como contribuciones insignificantes debido a la contribución rápidamente decreciente de 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}$

Formulación alternativa

"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}$

Historia y antecedentes

El análisis de componentes de 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

• Agrupación espectral
• Vecino más cercano de gran margen

Referencias

• J. Goldberger, G. Hinton, S. Roweis, R. Salakhutdinov. (2005) Análisis de componentes barriales. Avances en los 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 "NeighborhoodComponentsAnalysis" de scikit-learn ( Python )