ММО3 (1185328), страница 2

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

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

Интуи Рис. 1 Иллюстрируются разделение классов и .с помощью линейных границ с испо льзованием концепции максимального «зазора».

Напомним, что пара параллельных гиперплоскостей и в многомерном пространстве описывается с помощью уравнений:

( ) , (1)

( ) ,

где является направляющим вектором для гиперплоскостей.

Пусть , где - некоторое вещественное число. Нетрудно таким образом подобрать и , чтобы система

( ) , (2)

( ) ,

Описывала те же самые гиперплоскости, что и система (1). Пусть точки и принадлежат плоскостям и соответственно. Расстояние (величина зазора) между гиперплоскостями и равно проекции разности на направление , Данная проекция по определению равна . Однако согласно системе (2) . Следовательно задача поиска двух максимально удалённых друг от друга параллельных гиперплоскостей, каждая из которых отделяет объекты одного из классов, может быть сведена к оптимизационной задаче с ограничениями.

(3)

при

при , .

При этом оптимизация производится по компонентам направляющего вектора и параметру сдвига .

Введём обозначение: при и . Учитывая, функция монотонно возрастает с уменьшением , переходим от задачи (3) к задаче

(4)

, .

Задача (4) относится к хорошо изученному классу задач квадратичного программирования.

Решение задачи квадратичного программирования. Важным инструментом исследования экстремальных значений оптимизируемых функций при ограничениях является функция Лагранжа или лагранжиан, который для задачи (4) записывается в виде

,

где являются неотрицательными вещественными, которые называются множителями Лагранжа.

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

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

,

Условия стационарности заключаются в выполнении равенств

, (5)

В векторной форме система (5) принимает вид

.

Из условия стационарности также следует выполнение равенства

(6)

Условия стационарности (5,6) для лагранжиана являются необходимыми условиями экстремума при ограничениях задачи (4).

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

Нетрудно показать, воспользовавшись уравнениями (5,6), что лагранжиан в точке может быть записан в виде .

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

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

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

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

(7)

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

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

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

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

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

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

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

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

при

при , .

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

, ,

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

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

;

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

, ;

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

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

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

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

,

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

(7)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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