Análisis de los componentes del vecindario

Consideremos predecir la etiqueta de clase de un único punto de datos por consenso de su${\displaystyle k}$-vecinos más cercanos con una métrica de distancia dada. Esto se conoce como clasificación de dejar uno fuera . Sin embargo, el conjunto de vecinos más cercanos${\displaystyle C_{i}}$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 de un punto puede sufrir cambios discretos en respuesta a cambios suaves en los elementos de${\displaystyle A}$, lo que implica que cualquier función objetivo${\displaystyle f(\cdot )}$basado en los vecinos de un punto será constante por partes y, por lo tanto, no diferenciable .

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

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

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

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

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

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

Tenga en cuenta que bajo vecinos más cercanos estocásticos, la clase de consenso para un solo punto${\displaystyle i}$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.${\displaystyle j\in C_{i}}$es decir:${\displaystyle P(Clase(X_{i})=Clase(X_{j}))=p_{ij}}$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.${\displaystyle j\in C_{j}}$dónde${\displaystyle C_{j}}$ahora es el conjunto de datos transformado completo.

Esta elección de función objetivo es preferible ya que es diferenciable con respecto a${\displaystyle A}$(denotar${\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)}$

Obtención de un gradiente para${\displaystyle A}$Esto significa que se puede encontrar con un método iterativo como el descenso de gradiente conjugado . Cabe destacar que, en la práctica, la mayoría de los términos internos del gradiente resultan en contribuciones insignificantes debido a la rápida disminución de la contribución de los puntos distantes del punto de interés. Esto implica que la suma interna del gradiente se puede truncar, lo que permite obtener tiempos de cálculo razonables incluso para conjuntos de datos grandes.

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

${\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 de${\displaystyle A}$El uso de esta función suele ofrecer resultados de rendimiento similares a los de la original.

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