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[1][2][3] is a machine learning algorithm that generalizes the k-Nearest Neighbors (kNN) classifier. Whereas the kNN classifier supports binary classification, multiclass classification and regression,[4] the Structured kNN (SkNN) allows training of a classifier for general structured output labels.
As an example, a sample instance might be a natural language sentence, and the output label is an annotated parse tree. Training a classifier consists of showing pairs of correct sample and output label pairs. After training, the structured kNN model allows one to predict for new sample instances the corresponding output label; 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 defined class labels. Type of elements does not matter, the only condition is the existence of metric function that defines a distance between each pair of elements of a set.
SkNN is based on idea of creating a graph, each node of which represents class label. There is an edge between a pair of nodes iff there is a sequence of two elements in training set with corresponding classes. Thereby the first step of SkNN training is the construction of described graph from training sequences. There are two special nodes in the graph corresponding to an end and a beginning of sentences. If sequence starts with class `C`, the edge between node `START` and node `C` should be created.
Like a regular kNN, the second part of the training of SkNN consists only of storing the elements of trained sequence in special way. Each element of training sequences is stored in node related to the class of previous element in sequence. Every first element is stored in node `START`.
Inference
[edit]Labelling of input sequences in SkNN consists in finding sequence of transitions in graph, starting from node `START`, which minimises overall cost of path. Each transition corresponds to a single element of input sequence and vice versa. As a result, label of element is determined as target node label of the transition. Cost of the path is defined as sum of all its transitions, and the cost of transition from node `A` to node `B` is a distance from current input sequence element to the nearest element of class `B`, stored in node `A`. Searching of optimal path may be performed using modified Viterbi algorithm. Unlike the original one, the modified algorithm instead of maximizing the product of probabilities minimizes the sum of the distances.
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.