Хайкин С. - Нейронные сети (778923), страница 87
Текст из файла (страница 87)
Таким образом, дифференцируя,Т(зч, Ь, а) по зч и Ь и приравнивая результат к нулю, получим следующие условия оптимальности. Условие 2: — ~Щ' — '~~ = О. Применяя условие оптимальности 1 к функции Лагранжа (6.11), после перестановки слагаемых получим: 424 Глава 6. Машины опорных векторов решения будет обеспечиваться множителями Лагранжа. В частности, можно сформу- лировать следующую теорему двойственности (дна!)гу 1)геогет) [124). (а) Если прямая задача имеет оптимальное решение, то двойственная задача также имеет оптимальное решение, при этом соответствующие оптимальные решения совпадают.
(б) Для того чтобы зч было оптимальным решением прямой задачи, а и — оптимальным решением двойственной, необходимо и достаточно, чтобы зч было допустимым решением прямой задачи и Ф(чх,) = э(чх„Ь„а,) = ш(п1(хч,Ь„а,). Третье слагаемое в правой части (6.15) равно нулю вследствие условия оптимальности (6.13). Далее, из (6.12) получим: и зч = ,'! а!!1!ххах! =~~! ~~! а,а,г(Атх, х,. !=1 з=! Следовательно, представив целевую функцию как .1(зч,Ь, а) = Я(а), соотношение (6.15) можно переформулировать следующим образом: х !ч !ч Я(а) = ~~) а! — — ,'! ~~! а;а,г(г!(1х, х,, т=! ,=г,=! (6.16) где а! — неотрицательны. Теперь можно сформулировать двойственную задачу.
Для данного обучающего множества ((х!,!1,))н найти мнажшпели Лагранжа (а, ),' г, максимизирующие целевую функцию !ч Ф ж Я(а) = ~> а, — — ~~) ~) гз„а,г(,г(зхъхз 1=! г=! з=! при следующих ограничениях ы Е ',> а,!1, = О, !=1 2, а, ) Одля ! = 1,2,...,)'ч'. Чтобы сформулировать двойственную задачу для рассмотренной прямой, раскроем выражение (6.11): и и н ,1(хч, Ь, а) = -ччтхч — ~~! а!!(гхчгх! — Ь~~ а,г(!+ у 'а,. (6.15) !=! а=! !=! 6.2. Оптимальная гнперплоскость для лннейно-разделимых образов 426 Обратите внимание, что двойственная задача целиком описывается в терминах данных обучения.
Более того, максимизируемая функция фа) зависит только от входных образов, представленных в виде множества скалярных произведений (х~х,)<,, Определив оптимальные множители Лагранжа а,„с помощью соотношения (6.12) можно вычислить оптимальный вектор весовых коэффициентов зг,: (6.17) Для вычисления оптимального значения порога 6, можно использовать полученное значение хч, и выражение (6.7): 8. =1 — ънтхбд для с(" =1. (6.18) Статистические свойства оптимальной гиперплоскости Из описанной в главе 2 теории статистического обучения следует, что ЧС-размерность обучаемой машины определяет способ использования вложенной структуры аппроксимирующих функций. Напомним также, что ЧС-размерность множества разделяющих гиперплоскостей в пространстве размерности т равна т + 1. Тем не менее, чтобы применить метод минимизации структурного риска (см.
главу 2), требуется построить такое множество разделяющих гиперплоскостей переменной ЧС- размерности, которое одновременно минимизирует эмпирический риск (т.е. ошибку классификации на обучающем множестве) и ЧС-размерность. В машине опорных векторов структура множества разделяющих гиперплоскостей определяется Евклидовой нормой вектора весовых коэффициентов хч.
В частности, можно сформулировать следующую теорему (1084), [10851. Пусть Р— диаметр наименьшего шара, содержащего все входные векторы хь хз,..., хн. КС-размерность П множества оптимальных гиперплоскостей, описываемых уравнением зв~~х + (з = 0 ограничена сверху величиной (6.19) п<щш —,т, +1, где символ Ц означает наименьшее целое число, большее или равное заключенному в скобки значению; р — граница разделения, равная 2г0зз,~(г тс — размерность входного пространства. 426 Глава 6.
Машины опорных векторов Из этой теоремы следует, что УС-размерностью (т.е. сложностью) оптимальной гиперплоскости можно управлять независимо от размерности входного пространства с помощью правильного выбора границы разделения р. Предположим, существует некоторая вложенная структура, описываемая в терминах разделяющих гиперплоскостей следующим образом: Яь — — (зк~х+ Ь: ))е'(! < сь), Й = 1,2,...
(6.20) С помощью верхней границы ЧС-размерности и, определяемой неравенством (6.19), вложенную структуру (6.20) можно переписать в эквивалентной форме в терминах границ разделения: (6.21) Яь= — +1:Р >аь, й=1,2,..., где аь и сь — константы. Из главы 2 следует, что для обеспечения хорошей обобщающей способности, в соответствии с принципом минимизации структурного риска, необходимо выбрать структуру с наименьшими ЧС-размерностью и ошибкой обучения.
Из выражений (6.19) и (6.21) видно, что это требование можно удовлетворить с помощью оптимальной гиперплоскости (т.е. с помощью разделяющей гиперплоскости с наибольшей границей разделения р). Либо, в свете выражения (6.9), необходимо использовать оптимальный вектор весовых коэффициентов зк, с минимальной Евклидовой нормой. Таким образом, выбор оптимальной гиперплоскости как поверхности решений для множества линейно-разделимых множеств не только интуитивно удовлетворяет, но и полностью соответствует принципу минимизации структурного риска машины опорных векторов.
6.3. Оптимальная гиперплоскость для неразделимых образов До сих пор в этой главе рассматривались только линейно-разделимые образы. Теперь сконцентрируем внимание на более сложном случае — неразделимых множествах. При таком наборе данных обучения невозможно построить разделяющую гиперплоскость, полностью исключающую ошибки классификации.
Тем не менее мы попытаемся сконструировать оптимальную гиперплоскость, которая сводит к минимуму вероятность таких ошибок на множестве обучающих примеров. 6.3, Оптимальная гиперппоскость для неразделимых образов 427 Граница разделения классов считается мягкой (зой), если некоторая точка (х,, г(,) нарушает следующее условие (см. (6.10)): ~(нтх +5) >1 (=1 2 Я Такое нарушение может иметь две формы. ° Точка (х„а,) попадает в область разделения с нужной стороны поверхности решений (рис. 6.3, а).
° Точка попадает в область разделения с другой стороны поверхности решений (рис. 6.3, 6). Заметим, что в первом случае классификация будет правильной, а во втором— ошибочной. Для того чтобы подготовить почву для формального рассмотрения неразделимых образов, введем в определение разделяющей гиперплоскости (поверхности решений) новое множество неотрицательных скалярных переменных (с,,) ~,: а,(тчтх;+ 6) > 1 — 6н, ( = 1,2,...,Ю. (6.22) Величина г„. называется фиктивной неременной (з1ас1с чапаЫе), определяющей отклонение точек от идеального состояния линейной разделимости.
Если 0 < г„. < 1, то точка попадает в область границы разделения, но с нужной стороны поверхности решений (см. рис. 6.3, а). Если же Г„. > 1, то точка попадает в область с неверной стороны разделяющей гиперплоскости (см. рис. 6.3, 6). Опорные векторы являются теми точками, которые точно удовлетворяют неравенству (6.22) при г„> О.
Заметим, что если образ с Р, > 0 выбросить из обучающего множества, то поверхность решения изменится. Таким образом, опорные векторы определяются одинаково как в случае разделимых, так и в случае неразделимых образов. Задача сводится к поиску разделяющей гиперплоскости, минимизирующей ошибку классификации на множестве обучающих примеров. Это можно обеспечить, минимизируя функционал по вектору весовых коэффициентов и при условии (6.22) и ограничениях на )~тн~(з. Здесь 1(с) — функиия индикатора, определяемая следующим образом: 428 Глава 6. Машины опорных векторов Опорные векторы а) Опорные векторы Рис. 6.3.
Точка х, (принадлежащая классу Сг) попадает внутрь области разделения с нужной стороны от разделяющей гиперппоскости (а). Точка х, (принадлежащая классу Сз) попадает в область разделения с неверной стороны от разделяющей гиперплоскости (б) б) К сожалению, минимизация Ф(с) по и' является невыпуклой )ч)Р-полнойз задачей минимизации. С точки зрения вычислительной сложности алгоритмы можно разделить на два класса. Алгоритмы с полнномивльным временем. Время их выполнения описывается полиномиальиой функцией от размерности задачи. Например, виоритм быстрого преобразования Фурье, используемый в спектральном анализе, являетсв алгоритмом полиномиальной слшкности, так как требует времени выполнения гг)ояп, где и— размерность задачи. Алпгритмы с экспоненциальным временем.
Время их выполнения пропорционально экспоненциальной функции от размерности задачи. Например, выполнение алгоритма экспоненциальной сложности может потребовать времени 2о, где и — размерность задачи. С таких позиций алгоритмы с полиномиальным временем выполнения можно рассмшрнвать как "эффективные", а алгоритмы с экспоненциальным — как "неэффективные".
На практике сушествует множество вычислительных задач, для которых пока не прелложено эффеьтивных алгоритмов. Многие из таких трудноразрешимых задач относят к так называемому классу АГР-лоялых задач О(Р-сошр1ше). Аббревиатура НР означает полбегепп)л)ябс ро!упопца! (недетерминировано полнномиальные). Более полное описание НР-полных задач содержится в [208), [211), [338). 6.3. Оптимальная гиперплоскость для неразделимых образов 429 Чтобы обеспечить математическую трактовку такой задачи минимизации, аппроксимируем функционал Ф(с) следующим образом: Более того, упростим вычисления, записав минимизируемый функционал относительно вектора весов вп Ф(чг, с) = 1 тчг+ С ч'у ~„.. (6.23) 1=1 Как и ранее, минимизация первого слагаемого в (6.23) связана с минимизацией ЧС-размерности машины опорных векторов.
Что же касается второго слагаемого, то оно представляет верхнюю границу количества ошибок тестирования. Таким образом, представление функции стоимости Ф(зч, с) в (6.23) полностью согласуется с принципом минимизации структурного риска. Параметр С обеспечивает компромисс между сложностью машины и количеством неразделимых точек. Его можно рассматривать как некоторую форму "параметра регуляризации".
Параметр С выбирается пользователем. Его можно выбрать двумя способами. ° Экспериментально на основе множества обучения/тестирования. ° Аналитически, оценивая Ъ'С-размерность с помощью (6.19) и используя границы эффективности обобщения машины на основе ЧС-размерности. В любом случае функционал Ф(зч, ~) оптимизируется по зч и (с„) и, при условиях (6.22) и ~, >О. При этом квадрат нормы че трактуется как значение, минимизируемое с учетом неразделимости точек, а не как ограничение, накладываемое на минимизацию количества неразделимых точек.
Сформулированная таким образом задача оптимизации для неразделимых множеств в качестве частного случая включает в себя задачу оптимизации линейно- разделимых множеств. В частности, установив значение 9 равным нулю для всех з, уравнения (6.22) и (6.23) можно свести к виду, соответствующему линейно- разделяемым множествам. Теперь можно формально определить прямую задачу для неразделимых множеств.
Дчя данного обучающего мноясества ((х„д,))и найти оптимальные значения вектора весов зч и порога 6, удовветворяющие ограничениям с((чгтх +6) >1 — с (=1 2 Я Р,. > О для всех (, 430 Глава 6. Машины опорных векторов такие, что вектор лл совместно с с,. минимизируют функционал стоимости и т +С~, а=1 где С вЂ” задаваемый пользователем положительный параметр. Используя метод множителей Лагранжа и выполняя преобразования, аналогичные приведенным в разделе 6.2, можно сформулировать двойственную задачу для неразделимых множеств. Для данного обучающего множества 1(х„д,))н найти множители Лагранжа 1а;)и и максимизиРУющие ЦелевУю фУнкцию и и ю Ч(а) ~~> а '~ '~~~а а И й хтх ~=1 ~=1 з=1 при ограничениях Х ° ,'>„а;4 = О, 1=1 ° О < сс; < С для з' = 1, 2,..., )'ч', где С вЂ” задаваемый пользователем положительный параметр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
