Gran margen vecino más cercano

La clasificación de vecinos más cercanos de margen amplio ( 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 la optimización convexa .

El objetivo del aprendizaje supervisado (más específicamente, la clasificación) es aprender una regla de decisión que permita categorizar instancias de datos en clases predefinidas. La regla de los k vecinos más cercanos presupone un conjunto de datos de entrenamiento con instancias etiquetadas (es decir, se conocen las clases). Clasifica una nueva instancia de datos con la clase obtenida mediante el voto mayoritario de las k instancias de entrenamiento (etiquetadas) más cercanas. La proximidad se mide con una métrica predefinida . El algoritmo Large Margen Nearest Neighbors aprende esta (pseudo)métrica global de forma supervisada para mejorar la precisión de clasificación de la regla de los k vecinos más cercanos.

La idea 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 compartan la misma etiqueta de clase. Si esto se logra, el error de dejar uno fuera (un caso especial de validación cruzada ) se minimiza. Sea que los datos de entrenamiento consisten en un conjunto de datos.${\displaystyle D=\{({\vec {x}}_{1},y_{1}),\dots ,({\vec {x}}_{n},y_{n})\}\subset R^{d}\times C}$, donde el conjunto de posibles categorías de clase es${\displaystyle C=\{1,\dots ,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${\displaystyle d(\cdot ,\cdot )}$para estar bien definida, la matriz${\displaystyle \mathbf {M} }$necesita ser semidefinida positiva . La métrica euclidiana es un caso especial, donde ${\displaystyle \mathbf {M} }$es la matriz identidad . Esta generalización a menudo se denomina (erróneamente ) métrica de Mahalanobis .

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

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

Los vecinos más cercanos de gran margen optimizan la matriz.${\displaystyle \mathbf {M} }$con la ayuda de la programación semidefinida . El objetivo es doble: para cada punto de datos${\displaystyle {\vec {x}}_{i}}$, 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${\displaystyle {\vec {x}}_{i}}$estar rodeado de instancias de entrenamiento de la misma clase. Si fuera un punto de prueba, se clasificaría correctamente bajo la${\displaystyle k=3}$regla del vecino más cercano.

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.${\displaystyle {\vec {x}}_{l}}$que estén a menos de una unidad de distancia que los vecinos objetivo${\displaystyle {\vec {x}}_{j}}$(y por lo tanto, expulsándolos del vecindario local de${\displaystyle {\vec {x}}_{i}}$). El valor resultante que se debe minimizar se puede expresar como:

${\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${\textstyle [\cdot ]_{+}=\max(\cdot ,0)}$, lo 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.${\displaystyle M}$Cualquier opción alternativa${\displaystyle c>0}$daría como resultado un reescalado de${\displaystyle M}$por un factor de${\displaystyle 1/c}$.

El problema de optimización final queda así:

${\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${\textstyle \lambda >0}$es alguna constante positiva (normalmente establecida mediante validación cruzada). Aquí las variables${\displaystyle \xi _{ijl}}$(junto con dos tipos de restricciones) reemplazan el término en la función de costo. Juegan un papel similar al de las variables de holgura para absorber el alcance de las violaciones de las restricciones del impostor. La última restricción garantiza que${\displaystyle \mathbf {M} }$es semidefinida positiva. El problema de optimización es una instancia de programación semidefinida (PSE). Aunque las PSE tienden a sufrir de una alta complejidad computacional, esta instancia particular de PSE se puede resolver de manera muy eficiente debido a las propiedades geométricas subyacentes del problema. En particular, la mayoría de las restricciones de impostor se satisfacen naturalmente y no necesitan ser impuestas durante el tiempo de ejecución (es decir, el conjunto de variables${\displaystyle \xi _{ijl}}$es escaso). 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 supervisa las restricciones restantes (probablemente satisfechas) solo ocasionalmente para garantizar la corrección.

LMNN se extendió a múltiples métricas locales en el artículo de 2008. ^{[ 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 manuscritos MNIST en varias horas, involucrando miles de millones de restricciones por pares. Una implementación de código abierto en Matlab está disponible gratuitamente en la página web de los autores .

Kumal et al. ^{[ 4 ]} extendieron el algoritmo para incorporar invariantes locales a transformaciones polinómicas multivariadas y mejoraron la regularización.

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