Структурированный кНН
 | Эта статья включает список литературы , связанную литературу или внешние ссылки , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . ( июнь 2017 г. ) |
Структурированные 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` , хранящегося в узле `. А `. Поиск оптимального пути может осуществляться с использованием модифицированного алгоритма Витерби . В отличие от оригинального, модифицированный алгоритм вместо максимизации произведения вероятностей минимизирует сумму расстояний.
Ссылки
[ редактировать ]- ^ Пугель, Митя; Джероски, Сашо (2011). «Прогнозирование структурированных результатов, метод k-ближайших соседей». Наука открытий . Конспекты лекций по информатике. Том. 6926. стр. 262–276. дои : 10.1007/978-3-642-24477-3_22 . ISBN 978-3-642-24476-6 . ISSN 0302-9743 .
- ^ Самарев Роман; Васнецов, Андрей (ноябрь 2016 г.). «Графовая модификация алгоритмов метрической классификации» . Наука и образование МГТУ им. Баумана/Наука и образование МГТУ им. Баумана (11): 127–141. дои : 10.7463/1116.0850028 .
- ^ Самарев Роман; Васнецов, Андрей (2016). «Обобщение алгоритмов метрической классификации для классификации и маркировки последовательностей». arXiv : 1610.04718 [ (cs.LG) Обучение (cs.LG) ].
- ^ Альтман, Н.С. (1992). «Введение в непараметрическую регрессию ядра и ближайших соседей» (PDF) . Американский статистик . 46 (3): 175–185. дои : 10.1080/00031305.1992.10475879 . hdl : 1813/31637 .