Структурированный k-ближайших соседей [1] [2] [3] — это алгоритм машинного обучения , который обобщает классификатор k-ближайших соседей (kNN). В то время как классификатор kNN поддерживает бинарную классификацию , многоклассовую классификацию и регрессию , [4] структурированный kNN (SkNN) позволяет обучать классификатор для общих структурированных выходных меток .
Например, экземпляром образца может быть предложение на естественном языке, а выходной меткой — аннотированное дерево разбора . Обучение классификатора состоит из показа пар правильных образцов и выходных меток. После обучения структурированная модель kNN позволяет предсказать для новых экземпляров образца соответствующую выходную метку; то есть, учитывая предложение на естественном языке, классификатор может создать наиболее вероятное дерево разбора.
В качестве обучающего набора SkNN принимает последовательности элементов с определенными метками классов. Тип элементов не имеет значения, единственным условием является существование метрической функции, определяющей расстояние между каждой парой элементов набора.
SkNN основана на идее создания графа , каждый узел которого представляет метку класса. Между парой узлов есть ребро тогда и только тогда, когда в обучающем наборе есть последовательность из двух элементов с соответствующими классами. Таким образом, первым шагом обучения SkNN является построение описанного графа из обучающих последовательностей. В графе есть два специальных узла, соответствующих концу и началу предложений. Если последовательность начинается с класса ` C `, должно быть создано ребро между узлом ` START ` и узлом ` C `.
Как и в обычной kNN, вторая часть обучения SkNN состоит только из сохранения элементов обучаемой последовательности особым образом. Каждый элемент обучающей последовательности сохраняется в узле, связанном с классом предыдущего элемента в последовательности. Каждый первый элемент сохраняется в узле ` START `.
Маркировка входных последовательностей в SkNN заключается в нахождении последовательности переходов в графе, начиная с узла ` START `, которая минимизирует общую стоимость пути. Каждый переход соответствует одному элементу входной последовательности и наоборот. В результате метка элемента определяется как метка целевого узла перехода. Стоимость пути определяется как сумма всех его переходов, а стоимость перехода из узла ` A ` в узел ` B ` - это расстояние от текущего элемента входной последовательности до ближайшего элемента класса ` B `, хранящегося в узле ` A `. Поиск оптимального пути может быть выполнен с использованием модифицированного алгоритма Витерби . В отличие от оригинального, модифицированный алгоритм вместо максимизации произведения вероятностей минимизирует сумму расстояний.