Gran margen vecino más cercano

La clasificación de vecino más cercano de margen grande ( LMNN ) ^[1] es un algoritmo de aprendizaje automático estadístico para el aprendizaje métrico . Aprende una pseudométrica diseñada para la clasificación de k vecinos más cercanos . El algoritmo se basa en la programación semidefinida , una subclase de optimización convexa .

El objetivo del aprendizaje supervisado (más específicamente, la clasificación) es aprender una regla de decisión que pueda categorizar instancias de datos en clases predefinidas. La regla de los k vecinos más cercanos supone un conjunto de datos de entrenamiento de instancias etiquetadas (es decir, las clases son conocidas). Clasifica una nueva instancia de datos con la clase obtenida a partir del voto mayoritario de las k instancias de entrenamiento (etiquetadas) más cercanas. La cercanía se mide con una métrica predefinida . Los vecinos más cercanos con margen grande es un algoritmo que aprende esta (pseudo)métrica global de manera supervisada para mejorar la precisión de clasificación de la regla de los k vecinos más cercanos.

La intuición principal detrás de LMNN es aprender una pseudométrica bajo la cual todas las instancias de datos en el conjunto de entrenamiento están rodeadas por al menos k instancias que comparten la misma etiqueta de clase. Si esto se logra, se minimiza el error de dejar uno afuera (un caso especial de validación cruzada ). Dejemos que los datos de entrenamiento consistan en un conjunto de datos , donde el conjunto de posibles categorías de clase es . ${\displaystyle D=\{({\vec {x}}_{1},y_{1}),\puntos ,({\vec {x}}_{n},y_{n})\}\subconjunto R^{d}\times C}$${\displaystyle C=\{1,\puntos ,c\}}$

El algoritmo aprende una pseudométrica del tipo

${\displaystyle d({\vec {x}}_{i},{\vec {x}}_{j})=({\vec {x}}_{i}-{\vec {x}}_{j})^{\top }\mathbf {M} ({\vec {x}}_{i}-{\vec {x}}_{j})}$.

Para que la matriz esté bien definida, debe ser semidefinida positiva . La métrica euclidiana es un caso especial, donde es la matriz identidad. Esta generalización se conoce a menudo (falsamente ^{[ cita requerida ] ) como} métrica de Mahalanobis . ${\displaystyle d(\cdot ,\cdot )}$${\displaystyle \mathbf {M}}$${\displaystyle \mathbf {M}}$

La figura 1 ilustra el efecto de la métrica al variar . Los dos círculos muestran el conjunto de puntos con la misma distancia al centro . En el caso euclidiano, este conjunto es un círculo, mientras que bajo la métrica modificada (Mahalanobis) se convierte en un elipsoide . ${\displaystyle \mathbf {M}}$${\displaystyle {\vec {x}}_{i}}$

El algoritmo distingue entre dos tipos de puntos de datos especiales: vecinos objetivo e impostores .

Los vecinos de destino se seleccionan antes del aprendizaje. Cada instancia tiene exactamente diferentes vecinos de destino dentro de , que comparten la misma etiqueta de clase . Los vecinos de destino son los puntos de datos que deberían convertirse en vecinos más cercanos según la métrica aprendida . Denotemos el conjunto de vecinos de destino para un punto de datos como . ${\displaystyle {\vec {x}}_{i}}$${\estilo de visualización k}$${\displaystyle D}$${\displaystyle y_{i}}$${\displaystyle {\vec {x}}_{i}}$${\displaystyle N_{i}}$

Un impostor de un punto de datos es otro punto de datos con una etiqueta de clase diferente (es decir , ) que es uno de los vecinos más cercanos de . Durante el aprendizaje, el algoritmo intenta minimizar la cantidad de impostores para todas las instancias de datos en el conjunto de entrenamiento. ${\displaystyle {\vec {x}}_{i}}$${\displaystyle {\vec {x}}_{j}}$${\displaystyle y_{i}\neq y_{j}}$${\displaystyle {\vec {x}}_{i}}$

Los vecinos más próximos con un margen grande optimizan la matriz con la ayuda de la programación semidefinida . El objetivo es doble: para cada punto de datos , los vecinos objetivo deben estar cerca y los impostores deben estar lejos . La figura 1 muestra el efecto de dicha optimización en un ejemplo ilustrativo. La métrica aprendida hace que el vector de entrada esté rodeado de instancias de entrenamiento de la misma clase. Si fuera un punto de prueba, se clasificaría correctamente según la regla del vecino más próximo. ${\displaystyle \mathbf {M} }$${\displaystyle {\vec {x}}_{i}}$${\displaystyle {\vec {x}}_{i}}$${\displaystyle k=3}$

El primer objetivo de optimización se logra minimizando la distancia promedio entre las instancias y sus vecinos objetivo.

${\displaystyle \sum _{i,j\in N_{i}}d({\vec {x}}_{i},{\vec {x}}_{j})}$.

El segundo objetivo se logra penalizando las distancias a los impostores que están a menos de una unidad de distancia de los vecinos objetivo (y, por lo tanto, los expulsan del vecindario local de ). El valor resultante que se debe minimizar se puede expresar como: ${\displaystyle {\vec {x}}_{l}}$${\displaystyle {\vec {x}}_{j}}$${\displaystyle {\vec {x}}_{i}}$

${\displaystyle \sum _{i,j\in N_{i},l,y_{l}\neq y_{i}}[d({\vec {x}}_{i},{\vec {x}}_{j})+1-d({\vec {x}}_{i},{\vec {x}}_{l})]_{+}}$

Con una función de pérdida de bisagra , que garantiza que la proximidad del impostor no se penalice cuando está fuera del margen. El margen de exactamente una unidad fija la escala de la matriz . Cualquier elección alternativa daría como resultado un reescalado de por un factor de . ${\textstyle [\cdot ]_{+}=\max(\cdot ,0)}$${\displaystyle M}$${\displaystyle c>0}$${\displaystyle M}$${\displaystyle 1/c}$

El problema de optimización final se convierte en:

${\displaystyle \min _{\mathbf {M} }\sum _{i,j\in N_{i}}d({\vec {x}}_{i},{\vec {x}}_{j})+\lambda \sum _{i,j,l}\xi _{ijl}}$

${\displaystyle \forall _{i,j\in N_{i},l,y_{l}\neq y_{i}}}$

${\displaystyle d({\vec {x}}_{i},{\vec {x}}_{j})+1-d({\vec {x}}_{i},{\vec {x}}_{l})\leq \xi _{ijl}}$

${\displaystyle \xi _{ijl}\geq 0}$

${\displaystyle \mathbf {M} \succeq 0}$

El hiperparámetro es una constante positiva (normalmente establecida mediante validación cruzada). Aquí las variables (junto con dos tipos de restricciones) reemplazan el término en la función de costo. Desempeñan un papel similar a las variables de holgura para absorber el alcance de las violaciones de las restricciones del impostor. La última restricción garantiza que sea semidefinida positiva. El problema de optimización es una instancia de programación semidefinida (SDP). Aunque las SDP tienden a sufrir de una alta complejidad computacional, esta instancia particular de SDP se puede resolver de manera muy eficiente debido a las propiedades geométricas subyacentes del problema. En particular, la mayoría de las restricciones del impostor se satisfacen naturalmente y no necesitan ser aplicadas durante el tiempo de ejecución (es decir, el conjunto de variables es disperso). Una técnica de resolución particularmente adecuada es el método del conjunto de trabajo , que mantiene un pequeño conjunto de restricciones que se aplican activamente y monitorea las restricciones restantes (probablemente satisfechas) solo ocasionalmente para garantizar la corrección. ${\textstyle \lambda >0}$${\displaystyle \xi _{ijl}}$${\displaystyle \mathbf {M} }$${\displaystyle \xi _{ijl}}$

En el artículo de 2008, la LMNN se amplió a múltiples métricas locales. ^[2] Esta extensión mejora significativamente el error de clasificación, pero implica un problema de optimización más costoso. En su publicación de 2009 en el Journal of Machine Learning Research, ^[3] Weinberger y Saul derivan un solucionador eficiente para el programa semidefinido. Puede aprender una métrica para el conjunto de datos de dígitos escritos a mano MNIST en varias horas, lo que implica miles de millones de restricciones por pares. Una implementación de Matlab de código abierto está disponible gratuitamente en la página web de los autores.

Kumal et al. ^[4] ampliaron el algoritmo para incorporar invariancias locales a las transformaciones polinomiales multivariadas y mejoraron la regularización.

• Implementación de Matlab
• Tutorial de ICML 2010 sobre aprendizaje de métricas