KNN estructurat

Structured k-Nearest Neighbors és un algorisme d'aprenentatge automàtic que generalitza el classificador k-Nearest Neighbors (kNN). Mentre que el classificador kNN admet classificació binària, classificació multiclasse i regressió, el kNN estructurat (SkNN) permet entrenar un classificador per a etiquetes de sortida estructurades generals.

Com a exemple, una instància de mostra pot ser una frase en llenguatge natural i l'etiqueta de sortida és un arbre d'anàlisi anotat. L'entrenament d'un classificador consisteix a mostrar parells de mostres correctes i parells d'etiquetes de sortida. Després de l'entrenament, el model kNN estructurat permet predir per a noves instàncies de mostra l'etiqueta de sortida corresponent; és a dir, donada una oració en llenguatge natural, el classificador pot produir l'arbre d'anàlisi més probable.

Entrenament

Com a conjunt d'entrenament, SkNN accepta seqüències d'elements amb etiquetes de classe definides. El tipus d'elements no importa, l'única condició és l'existència d'una funció mètrica que defineix una distància entre cada parell d'elements d'un conjunt.

SkNN es basa en la idea de crear un gràfic, cada node del qual representa l'etiqueta de classe. Hi ha una vora entre un parell de nodes si hi ha una seqüència de dos elements en el conjunt d'entrenament amb les classes corresponents. Per tant, el primer pas de l'entrenament SkNN és la construcció del gràfic descrit a partir de seqüències d'entrenament. Hi ha dos nodes especials al gràfic corresponents a un final i un principi de frases. Si la seqüència comença amb la classe `C`, s'ha de crear la vora entre el node `START` i el node `C`.

Inferència

L'etiquetatge de seqüències d'entrada en SkNN consisteix a trobar seqüències de transicions en el gràfic, a partir del node `START`, que minimitza el cost global del camí. Cada transició correspon a un sol element de la seqüència d'entrada i viceversa. Com a resultat, l'etiqueta de l'element es determina com a etiqueta de node objectiu de la transició. El cost del camí es defineix com la suma de totes les seves transicions, i el cost de la transició del node `A` al node `B` és una distància des de l'element de la seqüència d'entrada actual fins a l'element més proper de la classe `B`, emmagatzemat al node `A`. La cerca del camí òptim es pot realitzar mitjançant l'algorisme de Viterbi modificat. A diferència de l'original, l'algoritme modificat en lloc de maximitzar el producte de probabilitats minimitza la suma de les distàncies.