Диссертация (1137507), страница 11
Текст из файла (страница 11)
Поскольку данноеисследование не имеет своей целью детальный анализ работы алгоритмовмашинного обучения применительно к задаче автоматической классификацииактантов, мы ограничимся лишь полуформальным описанием принциповработы выбранного алгоритма. Метод опорных векторов хорошо исследован иописан в литературе, более формальное описание используемых алгоритмовсодержится, например, в [Cortes, Vapnik, 1995].Ранее в разделе, посвящённойм спецификации поставленной задачи иметодовеерешения,былприведенпримерболееобщейзадачиклассификации, в котором точки в признаковом пространстве координатразделялись на два класса и было необходимо построить решающую функцию,которая позволила бы для новых экземпляров определить, к какому классу ониотносятся.Мывновьиспользуемэтотпримердлятого,чтобыпродемонстрировать проблему, которую решает выбранный нами методопорных векторов, и принцип его работы.Итак, пусть наши экземпляры – это набор точек в двухмерномпространстве, и задача классификатора состоит в том, чтобы построить прямую,66по одну сторону от которой находятся точки одного класса, а по другую – точкидругого класса.Рисунок 8: Решающая функция в двумерном пространствеМожно заметить, что прямая, приведённая на Рис.
8, далеко неединственная из возможных, и исходя из тренировочных данных можнопостроитьбесконечноеколичествопрямых,которыеудовлетворяютприведённому выше условию.Рисунок 9: Альтернативные варианты построения решающей функции67Какая из прямых наилучшим образом разделяет наше признаковоепространство? С точки зрения способностей классификатора к генерализации,предпочтительной кажется прямая, которая разделяла бы пространствомаксимально надёжно, т.е. максимально удалённая от обеих множеств.Формализация этого требования и приводит нас к методу опорных векторов,суть которого заключается в следующем: требуется на основе тренировочныхданных построить оптимальную разделяющую гиперплоскость (в нашемпримере – прямую), которая максимально удалена от экземпляров, наиболееблизких к границе класса.
Проиллюстрируем эту идею примером:Рисунок 10: Решающая функция с максимальной границейВ данном примере прямая разделяет признаковое пространство на дваподпространства, причем построена она таким образом, что расстояние отпрямой до ближайших к ней точек каждого класса максимизировано.Опишем вышесказанное более формально. Пусть нам дан наборэкземпляров, принадлежащих к одному из двух классов.
Любая гиперплоскостьв признаковом пространстве из признаков может быть описана формулойвида ∙ + = 0, где – вектор, перпендикулярный гиперплоскости, а –68константа, задающая расстояние от гиперплоскости до центра координат.Гиперплоскость, которая разделяет экземпляры на два класса, может бытьиспользована в целевой функции () = ( ∙ + ) : если функцияпринимает положительное значение, экземпляр получает метку первогокласса, если значение отрицательное – приписывается метка второго класса.Поскольку, как мы уже продемонстрировали, таких гиперплоскостей можнопостроить бесконечно много, мы накладываем дополнительное ограничение:наша гиперплоскость должна быть максимально удалена от ближайших к нейэкземпляров обоих классов.
Расстояние от гиперплоскости до экземпляра выражаетсяформулой ((, ), ) =( ∙+)‖‖1≥ ‖‖ инашазадача–максимизировать это расстояние. Как мы можем видеть, в данном случаедостаточно будет максимизировать величину 1/‖‖ , что эквивалентноминимизации ‖‖ . При этом необходимо, чтобы все экземпляры изобучающей выборки были классифицированы корректно. Формально этоограничение выглядит как ( ∙ + ) ≤ 1 (∀ ) . Если объект принадлежит кпервому классу ( > 0), то данное неравенство будет соблюдаться только вслучае когда > 0 и ∙ + > 0, аналогичное верно для второго класса.Эта задача может быть переформулирована как задача оптимизации ирешенаспомощьюметодовквадратическогопрограммирования.Традиционно (для удобства вычислений) минимизации подвергается ненепосредственно ‖‖ , а12∗ ‖‖2 .
В этом случае задача оптимизациипринимает следующий вид:Минимизировать12∑‖‖2При условии ( ∙ + ) − 1 ≥ 0Для всех экземпляров = 1. . 69Обратим внимание, что целевая функция выпуклая, а это значит, чтонайденноерешение(вданномслучае,минимум),будетглобальнооптимальным, т.е. решающая функция, созданная методом опорных векторов,будет единственной.Метод опорных векторов в озвученной выше формулировке имеет рядсвойств, которые делают его интересным в рамках стоящей перед нами задачи.Обратим внимание, что положение разделяющей гиперплоскости зависиттолько от опорных векторов. Это позволяет значительно уменьшить объёмданных, используемых для построения решающей функции, и выгодноотличает метод опорных векторов от, например, линейной регрессии ибайесовских методов классификации, особенно в контексте, когда признаковоепространство имеет большую размерность.Однако в данной формулировке метод опорных векторов восприимчив кшуму в исходных данных.
Представим себе, что наши данные содержатнесколько "ошибочных" экземпляров, расположенных в непосредственнойблизости от решающей гиперплоскости:Рисунок 11: Проблемы решающих функций с жёсткой границей70Использование метода опорных векторов с жёсткой границей, которыймы только что рассмотрели, может привести к построению неоптимальнойгиперплоскости, т.к. учитывает только опорные, т.е. "проблемные" точки.Решением в данном случае является модификация метода опорныхвекторов, которая разрешает неправильную классификацию некоторыхэкземпляров в тренировочных данных – классификаторы с мягкой границей.Этот подход позволяет повысить способность алгоритма к построениюклассификаторов, менее восприимчивых к ошибкам во входных данных.
Взадачу вводится дополнительный параметр , который определяет стоимостьошибочной классификации на тренировочных данных.Теперь задача оптимизации выглядит следующим образом:Минимизировать ½ ∑‖‖2 + ∑ εiПри условии ( ∙ + ) − 1 + ≥ 0Здесь – вспомогательная переменная, которая равна расстоянию догиперплоскости в случае, если экземпляр классифицирован неправильно, и 0 вслучае правильной классификации. При высоких значениях параметра поведение такого алгоритма приближается к стандартному методу опорныхвекторов, т.к. повышается стоимость ошибочной классификации.
В целом,классификаторы на основе метода опорных векторов с мягкой границей менеевосприимчивы к ошибкам в тренировочных данных и лучше подходят длярешения нашей задачи с учётом того, что наши входные данные, несмотря нафильтрацию, содержат неточности.Наш краткий обзор будет неполным без упоминания функций ядра,которыепозволяютметодуопорныхвекторовработатьслинейнонеразделимыми данными. Представим себе следующий набор данных:71Рисунок 12: Линейно неразделимые классыВ данном случае найти прямую, которая разделяла бы точки, более непредставляетсявозможным.Решениемвданнойситуацииявляетсяиспользование функции, которая переводит признаковое пространство вдругое пространство, в котором точки оказываются разделимы с помощьюгиперплоскости.
Так, в приведённом выше примере мы можем использоватьрадиальную функцию преобразования, в результате применения которой точкиоказываются разделимы:Рисунок 13: Разделение классов с помощью радиального ядра72В представленном исследовании мы не использовали преобразованийпространства, т.к. их семантика в нашем случае непрозрачна. В силу того, чтометод опорных векторов может работать только с числовыми свойствами, анаши атрибуты имеют номинальные значения, мы вынуждены передклассификацией произвести бинаризацию признаков. Суть этой процедурыможет быть прояснена с помощью следующего примера. Рассмотрим признак"Лемма".
Этот признак для каждого экземпляра принимает одно значение,например, “машина”, “дом”, “красный” и т.д. В процессе бинаризации мызаменяем признак "Лемма" на бинарных признаков "Лемма=машина","Лемма=дом" и т.д., где – размер словаря значений выбранного признака. Врезультате каждый экземпляр оказывается описан в терминах наборабинарных признаков и может быть проинтерпретирован классификатором ииспользован для построения оптимальной гиперплоскости. Это признаковоепространство очень трудно визуализировать и интерпретировать, и мы неимеем возможности определить, требуется ли какое-либо преобразование внашем случае, и если да, то какое.
В связи с этим мы остановили выбор налинейном методе опорных векторов: в этом методе преобразованийпризнакового пространства не производится, кроме того, он отличаетсявысокой вычислительной эффективностью.Метод опорных векторов в классической формулировке подходит толькодля решения задач бинарной классификации, однако наша задача в общемслучае состоит в приписании одного класса-семантической роли из наборанеопределённого размера (различные конструкции имеют разное числоролей). Для того, чтобы мы могли использовать SVM, мы должныинтерпретировать задачу присвоения ролей из ролевого набора длявыбранной конструкции в терминах бинарной классификации. Существуетнесколько способов сделать это, и мы рассмотрим два наиболее популярных изних.73Первый способ носит название "один против всех", и состоит вследующем: для каждого класса в тренировочном наборе данных мы строимклассификатор, принимающий решение о том, принадлежит ли экземпляр кэтому классу или нет.
Затем каждый из натренированных классификаторовприменяется к новому экземпляру, и выбирается класс, получившийнаибольший вес.Рисунок 14: Классификация методом "один против всех"Альтернативныйспособприведениязадачимультиклассовойклассификации к задаче бинарной классификации – "каждый против каждого".В этом случае для каждой пары классов строится отдельный классификатор (всумме ( − 1)/2 классификаторов для классов), и результаты работы этихклассификаторов используются для ранжирования меток классов для каждоговходного экземпляра. Несмотря на то, что в данном случае требуется построитьбольше классификаторов, для обучения каждого из них используется меньшеданных, а решающие функции зачастую оказываются более надёжными. Крометого, данный метод позволяет получить информацию о ранжировании.74Рисунок 15: Классификация методом "каждый против каждого"На практике выбор того или иного метода зависит от параметров задачии от технических возможностей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
