О сервисе WebGround

Ваша тема


Новости сайта

Литература

обложка книгиИнтернетика. Навигация в сложных сетях: модели и алгоритмы
Большакова Е.И., Клышинский Э.С., Ландэ Д.В., Носков А.А., Пескова О.В., Ягунова Е.В. Автоматическая обработка текстов на естественном языке и компьютерная лингвистикаАвтоматическая обработка текстов на естественном языке и компьютерная лингвистика (pdf)
Ягунова Е.В., Макарова О.Е., Антонова А.Ю., Соловьев А.Н. Разные методы компрессии в исследовании понимания новостного текстаРазные методы компрессии в исследовании понимания новостного текста (pdf)
Крылова И.В, Пивоварова Л.М., Савина А.В., Ягунова Е.В. Исследование новостных сегментов российской «снежной революции»: вычислительный эксперимент и интуиция лингвистовИсследование новостных сегментов российской «снежной революции»: вычислительный эксперимент и интуиция лингвистов (pdf)
Ягунова Е.В. Исследование перцептивной устойчивости фонем как элементов речевой цепиИсследование перцептивной устойчивости фонем как элементов речевой цепи (pdf)
Ягунова Е.В. Вариативность структуры нарратива и разнообразие стратегий пониманияВариативность структуры нарратива и разнообразие стратегий понимания (pdf)
Ягунова Е.В., Пивоварова Л.М. Экспериментально-вычислительные исследования художественной прозы Н.В. ГоголяЭкспериментально-вычислительные исследования художественной прозы Н.В. Гоголя (pdf)
Ягунова Е.В. Вариативность стратегий восприятия звучащего текстаВариативность стратегий восприятия звучащего текста (pdf)
Ягунова Е.В. Спонтанный нарратив у детей и у взрослыхСпонтанный нарратив у детей и у взрослых (pdf)
Ягунова Е.В. Исследование избыточности русского звучащего текстаИсследование избыточности русского звучащего текста (pdf)
Ягунова Е.В. Фонетические признаки опорных сегментов и восприятие русского текстаФонетические признаки опорных сегментов и восприятие русского текста (pdf)
Ягунова Е.В. Коммуникативная и смысловая структура текста и его восприятиеКоммуникативная и смысловая структура текста и его восприятие (pdf)
Ягунова Е.В. Где скрывается смысл бессмысленного текста?Где скрывается смысл бессмысленного текста? (pdf)
Ягунова Е.В. Эксперимент в психолингвистике: Конспекты лекций и методические рекомендацииЭксперимент в психолингвистике: Конспекты лекций и методические рекомендации (pdf)
Ягунова Е.В. Теория речевой коммуникацииТеория речевой коммуникации (pdf)
Антонова А.Ю., Клышинский Э.С., Ягунова Е.В. Определение стилевых и жанровых характеристик коллекций текстов на основе частеречной сочетаемостиОпределение стилевых и жанровых характеристик коллекций текстов на основе частеречной сочетаемости (pdf)
Ягунова Е.В. Эксперимент и вычисления в анализе ключевых слов художественного текстаЭксперимент и вычисления в анализе ключевых слов художественного текста (pdf)
Ягунова Е.В. Ключевые слова в исследовании текстов Н.В. ГоголяКлючевые слова в исследовании текстов Н.В. Гоголя (pdf)
Пивоварова Л.М., Ягунова Е.В. Информационная структура научного текста. Текст в контексте коллекцииИнформационная структура научного текста. Текст в контексте коллекции (pdf)
Савина А.Н., Ягунова Е.В. Исследование коллокаций с помощью экспериментов с информантамиИсследование коллокаций с помощью экспериментов с информантами (pdf)
Ягунова Е.В., Пивоварова Л.М. От коллокаций к конструкциямОт коллокаций к конструкциям (pdf)
Пивоварова Л.М., Ягунова Е.В. Извлечение и классификация терминологических коллокаций на материале лингвистических научных текстовИзвлечение и классификация терминологических коллокаций на материале лингвистических научных текстов (pdf)
Julia Kiseleva. Grouping Web Users based on Query LogGrouping Web Users based on Query Log (pdf)
Julia_Kiseleva_Unsupervised_Query_Segmentation_Using_Click_Data_and_Dictionaries_Information.pdfUnsupervised Query Segmentation Using Click Data and Dictionaries Information (pdf)
Четыре лекции о методе
Начала предметного анализа методов (на примере метода Ф.Бэкона)
Вариативность стратегий восприятия звучащего текста
Извлечение и классификация коллокаций на материале научных текстов. Предварительные наблюдения
Природа коллокаций в русском языке. Опыт автоматического извлечения и классификации на материале новостных текстов
Войтишек А. Повторы. Лирические рефреныПовторы. Лирические рефрены (pdf)
Войтишек А. Новое. Лирические рефреныНовое. Лирические рефрены (pdf)
Войтишек А. Всё об одном и том жеВсё об одном и том же. 500 лирических рефренов к 50-летию (pdf)
Войтишек А. Тысяча-часть-1Тысяча-часть-1 (pdf)
Войтишек А. Тысяча-часть-2Тысяча-часть-2 (pdf)
Войтишек А. АлфавитАлфавит (pdf)

4.7. Метод опорных векторов

 

Метод опорных векторов (Support Vector Mashine, SVM), предложенный В.Н. Вапником [146, 84], относится к группе граничных методов классификации. Он определяет принадлежность объектов к классам с помощью границ областей. Будем рассматривать только бинарную классификацию, т.е. классификацию только по двум категориям  и , принимая во внимание то, что этот подход может быть расширен на любое конечное количество категорий. Предположим, что каждый объект классификации является вектором в N-мерном пространстве. Каждая координата вектора - это некоторый признак, количественно тем больший, чем больше этот признак выражен в данном объекте.

В.Н. Вапник

 

Предполагается, что существует учебная коллекция - это множество векторов  и чисел  Число  равно 1 в случае принадлежности соответствующего вектора  категории , и -1 - в противном случае. Как было показано выше, линейный классификатор - это один из простейших способов решения  задачи классификации. В этом случае ищется прямая (гиперплоскость в N-мерном пространстве), отделяющая все точки одного класса от точек другого класса.  Если удается найти такую прямую (рис. 16), то задача классификации сводится к определению взаимного расположения точки и прямой: если новая точка лежит с одной стороны прямой (гиперплоскости), то она принадлежит классу , если с другой   классу  .

Формализуем эту классификацию: необходимо найти вектор  такой, что для некоторого  значения   и новой точки  выполняется:

form3

где  - скалярное произведение векторов  и :

.

 - уравнение гиперплоскости, которая разделяет классы. То есть, если  скалярное произведение вектора  на  не меньше значения , то новая точка принадлежит первому классу, если меньше – ко второму. Вектор  перпендикулярен искомой разделяющей гиперплоскости, а значение  зависит от кратчайшего расстояния между этой гиперплоскостью и началом координат. Возникает вопрос, какая из гиперплоскостей разделяет классы лучше всего?

 

ris16

 

Рис. 16. Разделение классов прямой

 

Метод SVM базируется на таком постулате: наилучшая разделяющая прямая – это та, которая максимально далеко отстоит от ближайших до нее точек обоих классов.  То есть задача метода SVM состоит в том, чтобы найти такие вектор  и число , чтобы для некоторого  (половина ширины разделяющей поверхности) выполнялось:

Умножим после этого обе части неравенства на   и, не ограничивая общности, выберем  равным единице. Таким образом, для всех векторов  из учебной коллекции будет справедливо:

form4 

Условие  задает полосу, которая разделяет классы (рис. 17). Границами полосы являются две параллельные гиперплоскости с направляющим вектором . Точки, ближайшие к разделяющей гиперплоскости, расположены точно на границах полосы.

 

ris17-1

Рис. 17. Разделяющая полоса

 

Чем шире полоса, тем увереннее можно классифицировать документы, соответственно, в методе SVM считается, что самая широкая полоса является наилучшей.

Сформулируем условия задачи оптимальной разделяющей полосы, определяемой неравенством:  (так переписывается система уравнений, исходя из того, что ). Ни одна из точек обучающей выборки не может лежать внутри этой разделяющей полосы. При этих ограничениях  и  - постоянные как элементы учебной коллекции, а  и  - переменные.

Легко видеть, что ширина разделяющей полосы равна . Поэтому необходимо найти такие значения  и , чтобы выполнялись приведенные линейные ограничения, и при этом как можно меньше была норма вектора , то есть необходимо минимизировать:

.

Это известная задача  квадратичной оптимизации  при линейных ограничениях.

Если предположить, что на учебных документах возможно были допущены ошибки экспертами при классификации, то необходимо ввести набор дополнительных переменных  характеризующих величину ошибок на объектах  Это позволяет смягчить ограничения:

Предполагается, что если  то на документе  ошибки нет. Если  то на документе  допускается ошибка. Если  то объект попадает внутрь разделяющей полосы, но относится алгоритмом к своему классу.

Задачу поиска оптимальной разделяющей полосы можно в этом случае переформулировать следующим образом минимизировать сумму:

при ограничениях , где  коэффициент C -  параметр настройки метода, который позволяет регулировать соотношение между максимизацией ширины разделяющей полосы и минимизацией суммарной ошибки. Приведенная задача является задачей квадратичного программирования, которую можно переписать в следующем виде:

По известной теореме Куна-Такера такая задача эквивалентна двойственной задаче поиска седловой точки функции Лагранжа:

Необходимым условием метода Лагранжа является равенство нулю производных лагранжиана по переменным  и , откуда получаем:

т.е. искомый вектор – это линейная комбинация учебных векторов, для которых . Если , то документ обучающей коллекции называется опорным вектором.

Таким образом, уравнение разделяющей плоскости имеет вид:

.

Приравняв производную лагранжиана по  нулю, получим:

Подставляя последнее выражение и выражение для  в лагранжиан получим эквивалентную задачу квадратичного программирования, содержащую только двойственные переменные:

При этом существенно, что целевая функция зависит не от конкретных значений , а от скалярных произведений между ними. Следует заметить, что целевая функция является выпуклой, поэтому любой ее локальный минимум является глобальным.

Метод классификации разделяющей полосой имеет два недостатка:

-         при поиске разделяющей полосы важное значение имеют только пограничные точки;

-         во многих случаях найти оптимальную разделяющую полосу невозможно.

Для улучшения метода применяется идея расширенного пространства, для чего:

1.     Выбирается отображение  векторов  в новое, расширенное пространство.

2.     Автоматически применяется новая функция скалярного произведения, которая применяется при решении задачи квадратичного программирования, так называемую  функцию ядра (kernel function):  На практике обычно выбирают не отображение , а сразу функцию , которая могла бы быть скалярным произведением при некотором отображении . Функция ядра - главный параметр настраивания машины опорных векторов.

3.     Определяется разделяющая гиперплоскость в новом пространстве: с помощью функции  устанавливается новая матрица коэффициентов для задачи оптимизации. При этом вместо скалярного произведения  берется значение , и решается новая  задача оптимизации.

4.     Найдя  и , получаем поверхность, которая классифицирует,  в новом, расширенном пространстве.

Ядром может быть не всякая функция, однако класс допустимых ядер достаточно широк. Например, в системе классификации новостного контента с применением известного пакета LibSVM (http://www.csie.ntu.edu.tw/~cjlin/libsvm) [124] в качестве функции ядра рекомендуется использовать радиальную базисную функцию:

где   - настраиваемый параметр.

Рассмотрим наглядный пример перехода к расширенному пространству, изображенный на рис. 18. Как видно,  круглые и квадратные фигуры не разделяются линейной полосой. Если же «изогнуть» пространство, перейдя к третьему измерению, то эти фигуры можно разделить  плоскостью, которая отрезает часть поверхности с квадратными точками. Таким образом, выгнув пространство с помощью отображения , можно найти разделяющую гиперплоскость.

Метод SVM обладает определенными преимуществами:

-         на тестах с документальными массивами превосходит другие методы;

-         при выборах  разных ядер позволяет реализовать другие подходы. Например, большой класс нейронных сетей можно представить с помощью SVM со специальными ядрами;

-         итоговое правило выбирается не с помощью экспертных эвристик, а путем оптимизации некоторой целевой функции.

ris18

Рис. 18. Пример перехода к расширенному пространству

 

К недостаткам метода можно отнести:

-         иногда слишком малое количество параметров для настройки: после того как фиксируется ядро, единственным изменяемым параметром остается коэффициент ошибки ;

-         нет четких критериев выбора ядра;

-         медленное обучение системы классификации.