Хайкин С. - Нейронные сети (778923), страница 88
Текст из файла (страница 88)
и, лч, = ~ а,,а,х„ (6.24) где Х, — количество опорных векторов. Процедура определения оптимального значения порога также аналогична описанной ранее. В частности, условие Куна — Такера Обратите внимание, что в двойственной задаче ие фигурируют ии фиктивные переменные ~о ии их множители Лагранжа. Таким образом, двойственная задача для неразделимых множеств аналогична более простой задаче для линейно-разделимых образов во всем, за исключением одного, ио крайне важного отличия. В обоих случаях максимизируется одна и та же целевая функция 1ч'1а). Однако в случае неразделимых классов ограничение а, > О заменено более строгим — О< а, < С.
За исключением этого изменения, задача условной оптимизации для неразделимых образов и вычисления оптимальных значений вектора весов и и порога б ие отличается от случая линейно-разделимых множеств. Заметим также, что опорные векторы вычисляются точно таким же способом, как и ранее. Оптимальное значение вектора весовых коэффициентов и определяется по формуле 6.4.
]так создать машину опорных векторов дпя задачи распознавания образов 431 определяется следующим образом: 0!1[4!(зугх, + Ь) — 1+ ~,] = О, г = 1, 2,..., ]У (6.25) ][Я, = 0,8 = 1,2,...,]У. (6.26) Уравнение (6.25) является полным эквивалентом (6.14), в котором единичное слагаемое заменено выражением (1 — ~,.). Как и в (6.14), [1! — множители Лагранжа, которые были введены для обеспечения неотрицательности переменных с! для всех О В седловой точке производная функции Лагранжа по Рм в прямой задаче равна нулю, откуда следует, что а,+]2,=С.
(6.27) Объединяя (6.26) и (6.27), мы видим, что ~,,яеО, еслиат<С. (6.28) Выбирая любую точку (х„т]!) из обучаюшего множества, для которой О< аш! < С, и, таким образом, Р„=О, и используя (6.25), можно вычислить оптимальный порог Ь,. Однако с вычислительной точки зрения порог Ь, лучше выбирать как среднее значение по всем точкам обучающего множества 1165]. 6.4.
Как создать машину опорных векторов для задачи распознавания образов Идея представления ядра в виде скалярного произведения впервые была использована в [11], [12] нри описании метода потенциальных функций, который являлся предтечей сетей на основе радиальных базисных функций. Примерно в то же время в [1089] была предложена идея оптимальных гиперплоскостей. Сочетание этих двух мощных концепций при создании машины опорных векторов впервые было описано в [141, [212], [1086]. Полный мщематический бшис машины опорных векторов был изложен в [1085] и позднее в расширенной форме представлен в [1084]. Ознакомившись со способом нахождения оптимальной гиперплоскости для неразделимых множеств, можно формально описать процесс создания машины опорных векторов для задачи распознавания образов.
Идея машины опорных векторовз базируется на двух математических операциях, приведенных ниже (рис. 6.4). 432 Глава 6. Машины опорных векторов Рис. 6.4. Нелинейное отображение ~р(.) входного пространства в про- странство признаков Входное пространство (ханных) 1. Нелинейное отображение входного вектора в пространство признаков (ГеаШге зрасе) более высокой размерности. 2.
Построение оптимальной гиперплоскости для разделения признаков, полученных в п. 1. Рассмотрим смысл каждой из этих двух операций. Операция 1 выполняется в соответствии с теоремой Ковера (Сечет) о разделимости образов (см. главу 5). Рассмотрим входное пространство, состоящее из нелинейноразделимыт образов (поп!гпеаг!у зерага!ей рапегпз). Согласно теореме Ковера, такое многомерное пространство можно преобразовать в новое пространство признаков, в котором с высокой вероятностью образы станут линейно-разделимыми, если выполняются два условия.
Во-первых, преобразование должно быть нелинейным. Вовторых, размерность пространства признаков должна быть достаточно большой. Эти два условия включены в операцию 1. Однако заметим, что в теореме Ковера ничего не говорится об оптимальности разделяющих гиперплоскостей. Только с помощью оптимальных гиперплоскостей можно минимизировать ЧС-размерность и добиться хорошего обобщения. Этот вопрос и составляет сущность второй операции.
В частности, в этой операции используется идея построения оптимальной разделяющей гиперплоскости в соответствии с теорией, описанной в разделе 6.3, но с одним фундаментальным отличием: разделяющая гиперплоскость теперь определяется как линейная функция от векторов, взятых из пространства признаков, а не из исходного входного пространства. И, что более важно, построение гиперплоскости осуществляется в соответствии с принципом минимизации структурного риска, который вытекает из теории ЧС-размерности.
Стержнем этого построения является оценка ядра скалярного произведения (ншег-ргог!пег 1сегпе!). 6.4. Как создать машину опорных векторов дпя задачи распознавания образов 4ЗЗ Ядро скалярного произведения Пусть х — некоторый вектор из входного пространства, размерность которого равна те. Пусть (ду(х)).', — множество нелинейных преобразований из входного пространства в пространство признаков.
Размерность пространства признаков обозначим через тп Предполагается, что функции уу(х) определены для всех з1 Имея множество нелинейных преобразований, можно определить гиперплоскость, определяющую поверхность решений ~~> ю,~ру(х) + 6 = О, э=1 (6.29) где (ю,), ', — множество весовых коэффициентов, связывающих пространство признаков с выходным пространством; 6 — порог.
Это выражение можно упростить: т~ ,') иуру(х) = О, э=о (6.30) е(х) = [~р (х),~р,(х),...,ф,(х)[~, (6.31) где по определению фо(х) = 1 для всех х. (6.32) В результате вектор признаков (Геашге тес1ог) <р(х) представляет собой "образ", нндуцированный в пространстве признаков при предъявлении вектора входного сигнала х (см. рис. 6.4). Таким образом, в терминах этого образа можно определить поверхность решений в компактной форме: (6.33) считая, что <ре(х) = 1 для всех х.
При этом юс представляет собой порог 6. Уравнение (6.30) определяет поверхность решений, вычисленную в пространстве признаков в терминах линейных весовых коэффициентов машины. Величина ф (х) представляет собой входной сигнал, приходящийся на вес ю, в пространстве признаков. Определим вектор 434 Глава 6. Машины опорных векторов Адаптируя (6.12) к задаче линейного разделения векторов в пространстве признаков, можно записать: и = ~~~ а,4<р(х;), (6.34) где вектор признаков (1еаппе иесгог) е(х,) соответствует входному вектору х, в 1-м примере. Подставляя выражение (6.34) в (6.33), можно определить поверхность решений в пространстве признаков следующим образом: (6.35) Здесь терм Ет(х,)Е(х) представляет собой скалярное произведение двух векторов, индуцированных в пространстве признаков для входного вектора х и примера х,. Исходя из этого, можно ввести понятие ядра скалярного произведения ((ппег-ргодпсг 1сегпе!), обозначаемого как К(х, х,): К(х,х;) =(р~(х)гр(х,) =~~> Е.(х)~р.(х,), (=1,2,...,АГ.
(6.36) К(х, х,) = К(х„х). (6.37) Ядро скалярного произведения К(х, х;) можно использовать для построения оптимальной гиперплоскости в пространстве признаков, не представляя его в явном виде. Это отчетливо видно из подстановки (6.36) в (6.35), в результате которой оптимальную гиперплоскость можно определить следующим образом: ,'~ а,д,К(х,х;) = О. г=1 (6.38) Теорема Мерсера Формула (6.36) для ядра скалярного произведения К(х, х,) является важным част- ным случаем теоремы Мерсера (Мегсег'з 1)зеогеш) из функционального анализа. Эта теорема формулируется следующим образом [217), (728).
Из этого определения видно, что ядро скалярного произведения является симметричной функцией своих аргументов, т.е. для всех 1 выполняется соотношение 6.4. Как создать машину опорных векторов для задачи распознавания образов 436 Пусть К(х, х') — непрерывное симметричное ядро, определенное на закрытом интервале а < к < Ь (это же касается и х').
Ядро может быть представлено в виде ряда К(х, х') = ~~ Х,у,.(х)~рз(х') 1=1 (6.39) с положительными коэффициентами л„> 0 для всех г'. Длл обеспечения корректно- сти этого разложения и его абсолютной и равномерной сходимости необходимо и достаточно выполнение условия / К(х, х')у(х)~р(х')бхбх' > 0 ь дь длн всех ~р( ), для которых в фз(х)с(х < оо. ь ° Для 2, ф! 4-й образ чар,(х), индуцированный в пространстве признаков входным вектором х, является собственной функцией разложения. ° Теоретически размерность пространства признаков (т.е.
количество собственных функций и собственных значений) может быть бесконечно большой. Теорема Мерсера позволяет лишь определить, является ли каро-кандидат ядром скалярного произведения в некотором пространстве, и, таким образом, можно лн его использовать в машине опорных векторов. Однако в ней ничего не говорится о том, как строить функции ~р,(х).
Это необходимо делать самостоятельно. Из соотношения (6.23) видно, что машина опорных векторов в неявном виде включает некоторую форму регуляризации. В частности, использование ядра К(х, х'), определенного в соответствии с теоремой Мерсера, соответствует регуляризации с оператором Р, таким, что зто ядро является функцией Грина оператора РР, где Р— оператор, сопряженный с Р [1004]. Теория регуляризацин рассматривалась в главе 5. Функции !р,(х) называются собственными функциями (е!яепбшспоп) разложения, а числа Х, — ее собственными значениями (е!яепча!пе). Из свойства положительности всех собственных чисел вытекает положительная определенность (роибче беби!!е) ядра К(х, х').
В свете теоремы Мерсера можно сделать следующие наблюдения. 436 Глава 6. Машины опорных векторов Оптимальная архитектура машины опорных векторов Разложение ядра скалярного произведения К(х, х') (6.36) позволяет построить поверхность решений, которая во входном пространстве является нелинейной, однако ее образ в пространстве признаков является линейным. С помощью такого разложения можно определить двойственную задачу условной оптимизации для машины опорных векторов. Дтя данного множества обучаюитих примеров ((х„т(,))н найти множители Лагранжа (Пт)~ т, которые максимизируют целевую функцию и и н Я(а) = ,'т а; — — ~~т у а;а,т1тй,К(хт,х,) и=1 т=т т=т (6.40) при ограничениях ьт 1) ~;аль,=О, т=т 2) О < а, < С для т' = 1,2,..., Х, где С вЂ”.
положительный параметр, задаваемый пользователем. Заметим, что первое ограничение вьпекает из оптимизации Лагранжиана (7(а) по пороговому значению 6 = и~о для тр„(х) = 1. Сформулированная таким образом двойственная задача имеет тот же вид, что и для линейно-неразделимых множеств, рассмотренных в разделе 6.3, за исключением того факта, что используемое там скалярное произведение х~х, заменено ядром скалярного произведения К(х„ х ). Ядро К(хо х,) можно рассматривать как элемент т'т' симметричной матрицы К размерности Х х Ф: К = (К(х„хт))6 7 т. (6.41) Определив оптимальные значения множителей Лагранжа аьл, с помощью адаптированной к нашему случаю формулы (6.17) можно найти соответствующее оптимальное значение вектора тт, весов, связывающего пространство признаков с выходным пространством.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
