La clasificación del vecino más cercano de margen grande ( LMNN ) [1] es un algoritmo de aprendizaje automático estadístico para el aprendizaje métrico . Se aprende un pseudometric diseñado para la vecina más cercana k- clasificación. 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 k-vecino más cercano asume 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 del voto mayoritario de las k instancias de entrenamiento más cercanas (etiquetadas). La cercanía se mide con una métrica predefinida . Los vecinos más cercanos de margen grande es un algoritmo que aprende esta (pseudo) métrica global de forma supervisada para mejorar la precisión de clasificación de la regla del k vecino más cercano.
Configuración
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 fuera (un caso especial de validación cruzada ). Deje que los datos de entrenamiento consistan en un conjunto de datos, donde el conjunto de posibles categorías de clases es .
El algoritmo aprende una pseudométrica del tipo
- .
Para estar bien definido, la matriz debe ser positivo semi-definido . La métrica euclidiana es un caso especial, dondees la matriz de identidad. Esta generalización es a menudo (falsamente [ cita requerida ] ) referida como métrica de Mahalanobis .
La Figura 1 ilustra el efecto de la métrica en diferentes . 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 .
El algoritmo distingue entre dos tipos de puntos de datos especiales: vecinos objetivo e impostores .
Vecinos objetivo
Los vecinos objetivo se seleccionan antes de aprender. Cada instancia tiene exactamente diferentes vecinos objetivo dentro , 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 .
Impostores
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 el número de impostores para todas las instancias de datos en el conjunto de entrenamiento.
Algoritmo
Los vecinos más cercanos de gran margen optimizan la matriz con la ayuda de 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 entradaestar rodeado de instancias de entrenamiento de la misma clase. Si fuera un punto de prueba, se clasificaría correctamente bajo la regla del vecino más cercano.
El primer objetivo de optimización se logra minimizando la distancia promedio entre las instancias y sus vecinos de destino.
- .
El segundo objetivo se consigue penalizando distancias a impostores que están a menos de una unidad más lejos que los vecinos de destino (y por lo tanto empujarlos fuera del vecindario local de ). El valor resultante a minimizar se puede establecer como:
Con función de pérdida de bisagra, 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.. Cualquier alternativa resultaría en un cambio de escala de por un factor de .
El problema de optimización final se convierte en:
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 costos. Desempeñan 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 asegura quees positivo semi-definido. El problema de optimización es una instancia de programación semidefinida (SDP). Aunque los SDP tienden a sufrir una alta complejidad computacional, esta instancia de SDP en particular 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 es necesario aplicarlas durante el tiempo de ejecución (es decir, el conjunto de variableses escasa). 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.
Extensiones y solucionadores eficientes
LMNN se extendió a múltiples métricas locales en el documento 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 obtienen un solucionador eficiente para el programa semi-definido. Puede aprender una métrica para el conjunto de datos de dígitos manuscritos de 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 y col. [4] extendió el algoritmo para incorporar invariancias locales a transformaciones polinomiales multivariadas y regularización mejorada.
Ver también
- Aprendizaje de similitud
- Análisis discriminante lineal
- Aprendizaje de la cuantificación de vectores
- Espacio pseudométrico
- Búsqueda de vecino más cercano
- Análisis de conglomerados
- Clasificación de datos
- Procesamiento de datos
- Aprendizaje automático
- Reconocimiento de patrones
- Analítica predictiva
- Reducción de dimensión
- Análisis de componentes de vecindario
Referencias
- ^ Weinberger, KQ; Blitzer JC; Saul LK (2006). "Aprendizaje métrico a distancia para clasificación de vecino más cercano de gran margen" . Avances en sistemas de procesamiento de información neuronal . 18 : 1473-1480.
- ^ Weinberger, KQ; Saul LK (2008). "Solucionadores rápidos e implementaciones eficientes para el aprendizaje métrico a distancia" (PDF) . Actas de la Conferencia Internacional sobre Aprendizaje Automático : 1160–1167. Archivado desde el original (PDF) el 24 de julio de 2011 . Consultado el 14 de julio de 2010 .
- ^ Weinberger, KQ; Saul LK (2009). "Aprendizaje métrico a distancia para clasificación de gran margen" (PDF) . Revista de investigación sobre aprendizaje automático . 10 : 207–244.
- ^ Kumar, diputado; Torr PHS; Zisserman A. (2007). "Un clasificador vecino más cercano de margen grande invariante". IEEE 11th International Conference on Computer Vision (ICCV), 2007 : 1–8. doi : 10.1109 / ICCV.2007.4409041 . ISBN 978-1-4244-1630-1.
enlaces externos
- Implementación de Matlab
- Tutorial de ICML 2010 sobre aprendizaje métrico