kNN estructurado

El algoritmo de k vecinos más cercanos estructurado ( SkNN ) ^{[ 1 ] [ 2 ] [ 3 ]} es un algoritmo de aprendizaje automático que generaliza el algoritmo de k vecinos más cercanos ( k -NN). k -NN admite clasificación binaria , clasificación multiclase y regresión , ^{[ 4 ]} mientras que SkNN permite entrenar un clasificador para una salida estructurada general .

Por ejemplo, una muestra de datos podría ser una oración en lenguaje natural , y la salida podría ser un árbol de análisis sintáctico anotado . El entrenamiento de un clasificador consiste en mostrarle muchos pares de muestras y salidas reales . Tras el entrenamiento, el modelo SkNN es capaz de predecir la salida correspondiente para nuevas muestras desconocidas; es decir, dada una oración en lenguaje natural, el clasificador puede generar el árbol de análisis sintáctico más probable.

Como conjunto de entrenamiento , SkNN acepta secuencias de elementos con etiquetas de clase. El tipo de elemento no importa; el único requisito es una función métrica definida que proporcione una distancia entre cada par de elementos del conjunto.

SkNN se basa en la idea de crear un grafo , donde cada nodo representa una etiqueta de clase. Existe una arista entre un par de nodos si hay una secuencia de dos elementos en el conjunto de entrenamiento con clases correspondientes. El primer paso del entrenamiento de SkNN es la construcción de dicho grafo a partir de las secuencias de entrenamiento. Hay dos nodos especiales en el grafo que corresponden al inicio y al final de las oraciones: si una secuencia comienza con la clase C , se debe crear la arista entre el nodo INICIO y el nodo C.

Al igual que en el algoritmo k -NN convencional , la segunda parte del entrenamiento de SkNN consiste en almacenar los elementos de una secuencia de entrenamiento de una manera específica. Cada elemento de la secuencia se almacena en el nodo correspondiente a la clase del elemento anterior. El primer elemento de cada secuencia se almacena en el nodo START .

El etiquetado de secuencias de entrada mediante SkNN consiste en encontrar la secuencia de transiciones en el grafo, comenzando desde el nodo INICIO . Cada transición corresponde a un único elemento de la secuencia de entrada. Como resultado, la etiqueta de cada elemento se determina como la etiqueta del nodo objetivo de la transición. El coste de la ruta se define como la suma de todas las transiciones, donde el coste de la transición del nodo A al nodo B es la distancia desde el elemento actual de la secuencia de entrada hasta el elemento más cercano de la clase B , almacenado en el nodo A. La determinación de una ruta óptima puede realizarse mediante un algoritmo de Viterbi modificado (donde se minimiza la suma de las distancias , a diferencia del algoritmo original que maximiza el producto de probabilidades).

• Ejemplos de implementación