ММО и поиск достоверных закономерностей в данных. Учебное пособие. Сенько (1185322), страница 11

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

Из условий дополняющей нежёсткости следует, что в точке справедливо равенство

Таким образом максимум равен и достигается при .

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

(7)

Пусть - решение задачи (7) Направляющий вектор оптимальной разделяющей гиперплоскости находится по формуле .

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

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

Распознавание новых объектов. Классификация нового распознаваемого объекта с описанием вычисляется согласно знаку выражения

Объект относится к классу , если и объект относится к классу в противном случае.

4.7.2 Случай отсутствия линейной разделимости

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

Требования об отделимости классов из задачи (3) заменяются более мягкими требованиями:

при

при , .

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

, ,

Положительная константа является открытым параметром алгоритма. Иными словами оптимальное значение подбирается пользователем.

Пусть - вектор множителей Лагранжа, соответствующих ограничениям

;

- вектор множителей Лагранжа, соответствующих ограничениям

, ;

Из теоремы ККТ следует, что для точки , в которой функция достигает своего минимума при ограничениях задачи (4), и некоторых векторов значений неотрицательных множителей Лагранжа и соблюдаются условия стационарности лагранжиана

по переменным .

Данные условия записываются в виде

Также из теоремы ККТ следует необходимость выполнения равенств, которые носят название условий дополняющей нежёсткости

,

Оптимальные значения множителей могут быть найдены как решение двойственной задачи квадратичного программирования.

(7)

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

Также как и в случае существования линейной разделимости параметра сдвига находится из ограничения, соответствующего произвольному опорному вектору . Действительно, из условий дополняющей нежёсткости и и следующего из них равенства следует выполнение равенства , эквивалентного равенству .

Распознавание нового объекта производится по его описанию также как и в случае линейно разделимых классов с помощью решающего правила (8) по величине распознающей функции .

4.7.3 Построение оптимальных нелинейных разделяющих поверхностей с помощью метода опорных векторов.

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

Линейная разделимость означает существование решения аналога задачи квадратичного программирования (4) для пространства , которое сводится к решению двойственной задачи

Отметим, что необходимость полного восстановления преобразования для поиска всех коэффициентов задачи квадратичного программирования (13) отсутствует. Достаточно найти функцию, связывающую скалярное произведение c векторами и , где и .

Такую функцию мы далее будем называть потенциальной и обозначать

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

\Существование преобразования , для которого выполняется равенство (15), было показано для неотрицательных симметричных потенциальных функций вида

где -целое число, -вещественная константа.

Существование преобразования с выполнением равенство (15) доказано также для ядровых функции типа гауссианы

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

оказаться нелинейная поверхность.

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

Прототипом метода опорных векторов явился метод «Обобщенный портрет», разработанный В.Н.Вапником и А.Я.Червоненкисом [1] . В современном варианте метод был предложен в работе [21]. Подробное описание метода появилось в работе [18] в 1998 году. .В настоящее время метод опорных векторов является одним из наиболее распространённым в мире средством решения задач распознавания, высокая эффективность которого подтверждается практикой. В связи с этим были предложены подходы, использующие основные принципы метода опорных векторов для решения задач регрессионного анализа.

Литература

[1] Вапник В.Н., Червоненкис А.Я. Теория распознавания образов (статистические проблемы обучения). М.: Наука. 1974. - 416 с.

[3] Воронцов К.В. (Курс лекций). www.machinelearning.ru

[4] Докукин А.А., Сенько О.В.Оптимальные выпуклые корректирующие процедуры в задачах высокой размерности Журнал вычислительной математики и математической физики. 2011. Т. 51. № 9. С. 1751-1760.

[5] А.М. Дубров, В.С.Мхитарян, Л.И.Трошин Многомерные статистические методы: Учебник, - М.: Финансы и статистика, 2000, - 352с.

[6] Дмитриев А.Н., Журавлев Ю.И., Кренделев Ф.П., О математических принципах классификации предметов и явлений. Сб. "Дискретный анализ". Вып. 7. Новосибирск, ИМ СО АН СССР. 1966. C. 3-11.

[7] Донской В.И. Алгоритмические модели обучения классификации: обоснование, сравнение, выбор. –Симферополь, «ДИАЙПИ», 2014,-227 с.

[8] Дюкова Е.В. Алгоритмы распознавания типа “Кора”: сложность реализации и метрические свойства// Распознавание, классификация, прогноз (матем. методы и их применение). М.: Наука, 1989. Вып.2. С. 99-125.

[9] Журавлев Ю.И., Никифоров В.В. Алгоритмы распознавания, основанные на вычислении оценок // Кибернетика. 1971. №3. С. 1-11.

Характеристики

Список файлов книги