K-Vecinos más cercanos estructurados [1] [2] [3] es un algoritmo de aprendizaje automático que generaliza el clasificador de k-Vecinos más cercanos (kNN). Mientras que el clasificador kNN admite clasificación binaria , clasificación multiclase y regresión , [4] el kNN estructurado (SkNN) permite el entrenamiento de un clasificador para etiquetas de salida estructuradas generales .
Como ejemplo, una instancia de muestra podría ser una oración en lenguaje natural y la etiqueta de salida es un árbol de análisis anotado . El entrenamiento de un clasificador consiste en mostrar pares de muestras correctas y pares de etiquetas de salida. Después del entrenamiento, el modelo kNN estructurado permite predecir para nuevas instancias de muestra la etiqueta de salida correspondiente; es decir, dada una oración en lenguaje natural, el clasificador puede producir el árbol de análisis sintáctico más probable.
Capacitación
Como conjunto de entrenamiento, SkNN acepta secuencias de elementos con etiquetas de clase definidas. No importa el tipo de elementos, la única condición es la existencia de una función métrica que defina una distancia entre cada par de elementos de un conjunto.
SkNN se basa en la idea de crear un gráfico , cada nodo del cual representa una etiqueta de clase. Hay una ventaja entre un par de nodos si hay una secuencia de dos elementos en el conjunto de entrenamiento con las clases correspondientes. Por lo tanto, el primer paso del entrenamiento SkNN es la construcción del gráfico descrito a partir de secuencias de entrenamiento. Hay dos nodos especiales en el gráfico que corresponden al final y al comienzo de las oraciones. Si la secuencia comienza con la clase " C ", se debe crear el borde entre el nodo " INICIO " y el nodo " C ".
Como un kNN regular, la segunda parte del entrenamiento de SkNN consiste únicamente en almacenar los elementos de la secuencia entrenada de manera especial. Cada elemento de las secuencias de entrenamiento se almacena en un nodo relacionado con la clase del elemento anterior en secuencia. Cada primer elemento se almacena en el nodo " INICIO ".
Inferencia
El etiquetado de las secuencias de entrada en SkNN consiste en encontrar la secuencia de transiciones en el gráfico, comenzando desde el nodo " START ", lo que minimiza el costo total de la ruta. Cada transición corresponde a un solo elemento de la secuencia de entrada y viceversa. Como resultado, la etiqueta del elemento se determina como etiqueta de nodo objetivo de la transición. Coste de la ruta se define como suma de todos sus transiciones, y el costo de la transición desde el nodo ` A ` al nodo ` B ` es una distancia desde actual elemento de la secuencia de entrada al elemento más cercano de clase ` B `, almacenada en el nodo ` A `. La búsqueda de la ruta óptima se puede realizar utilizando el algoritmo de Viterbi modificado . A diferencia del original, el algoritmo modificado en lugar de maximizar el producto de probabilidades minimiza la suma de las distancias.
Referencias
- ^ Pugelj, Mitja; Džeroski, Sašo (2011). "Predicción de salidas estructuradas método k-vecinos más cercanos". Ciencia del descubrimiento . Apuntes de conferencias en Ciencias de la Computación. 6926 . págs. 262-276. doi : 10.1007 / 978-3-642-24477-3_22 . ISBN 978-3-642-24476-6. ISSN 0302-9743 .
- ^ Samarev, Roman; Vasnetsov, Andrey (noviembre de 2016). "Modificación gráfica de algoritmos de clasificación métrica" . Ciencia y educación de Bauman MSTU / Nauka I Obrazovanie de Bauman MSTU (11): 127–141. doi : 10.7463 / 1116.0850028 .
- ^ Samarev, Roman; Vasnetsov, Andrey (2016). "Generalización de algoritmos de clasificación métrica para clasificación y etiquetado de secuencias". arXiv : 1610.04718 [ (cs.LG) Aprendizaje (cs.LG) ].
- ^ Altman, NS (1992). "Una introducción al kernel y la regresión no paramétrica del vecino más cercano" (PDF) . El estadístico estadounidense . 46 (3): 175-185. doi : 10.1080 / 00031305.1992.10475879 . hdl : 1813/31637 .