Structured kNN
 | This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. (June 2017) |
Structured k-nearest neighbours (SkNN)[1][2][3] is a machine learning algorithm that generalizes k-nearest neighbors (k-NN). k-NN supports binary classification, multiclass classification, and regression,[4] whereas SkNN allows training of a classifier for general structured output.
For instance, a data sample might be a natural language sentence, and the output could be an annotated parse tree. Training a classifier consists of showing many instances of ground truth sample-output pairs. After training, the SkNN model is able to predict the corresponding output for new, unseen sample instances; that is, given a natural language sentence, the classifier can produce the most likely parse tree.
Training
[edit]As a training set, SkNN accepts sequences of elements with class labels. The type of element does not matter; the only requirement is a defined metric function that gives a distance between each pair of elements of a set.
SkNN is based on idea of creating a graph, with each node representing a class label. There is an edge between a pair of nodes if there is a sequence of two elements in the training set with corresponding classes. The first step of SkNN training is the construction of such a graph from training sequences. There are two special nodes in the graph corresponding to sentence beginnings and ends: if a sequence starts with class C, the edge between node START and node C should be created.
Like regular k-NN, the second part of SkNN training consists of storing the elements of a training sequence in a certain way. Each element of the training sequences is stored in the node related to the class of the previous element in the sequence. Every first element is stored in the START node.
Inference
[edit]Labelling input sequences by SkNN consists of finding the sequence of transitions in the graph, starting from node START. Each transition corresponds to a single element of the input sequence. As a result, the label of each element is determined as the target node label of the transition. The cost of the path is defined as the sum of all transitions, with the cost of transition from node A to node B being the distance from the current input sequence element to the nearest element of class B, stored in node A. Determining an optimal path may be performed using a modified Viterbi algorithm (where the sum of the distances is minimized, unlike the original algorithm which maximizes the product of probabilities).
References
[edit]- ^ Pugelj, Mitja; Džeroski, Sašo (2011). "Predicting Structured Outputs k-Nearest Neighbours Method". Discovery Science. Lecture Notes in Computer Science. Vol. 6926. pp. 262–276. doi:10.1007/978-3-642-24477-3_22. ISBN 978-3-642-24476-6. ISSN 0302-9743.
- ^ Samarev, Roman; Vasnetsov, Andrey (November 2016). "Graph modification of metric classification algorithms". Science & Education of Bauman MSTU/Nauka I Obrazovanie of Bauman MSTU (11): 127–141. doi:10.7463/1116.0850028.
- ^ Samarev, Roman; Vasnetsov, Andrey (2016). "Generalization of metric classification algorithms for sequences classification and labelling". arXiv:1610.04718 [(cs.LG) Learning (cs.LG)].
- ^ Altman, N. S. (1992). "An introduction to kernel and nearest-neighbor nonparametric regression" (PDF). The American Statistician. 46 (3): 175–185. doi:10.1080/00031305.1992.10475879. hdl:1813/31637.