Хайкин С. - Нейронные сети (778923), страница 86
Текст из файла (страница 86)
Таким образом, мы сможем произвести сравнительную оценку машин опорных векторов с многослойными персептронами, обучаемыми по методу обратного распространения, а также с сетями на основе радиальных базисных функций. В последней части главы рассматривается задача нелинейной регрессии. В разделе 6.7 описывается функция потерь (!оья бтпсттоп), которая лучше всего подходит для данной задачи. В разделе 6.8 обсуждается создание машины опорных векторов для решения задачи нелинейной регрессии. В разделе 6.9 приводятся выводы и некоторые заключительные замечания. 6.2. Оптимальная гнлерллоскость для лннейно-разделимых образов 419 6.2.
Оптимальная гиперплоскость для линейно-разделимых образов Рассмотрим множество обучающих примеров ((хг, 4)),'~ „где х, — входной образ для примера г; г!г — соответствующий ему желаемый отклик (целевой выход). Для начала предположим, что класс, представленный подмножеством г(г =41, и класс, представленный подмножеством г(, = — 1, лииейио-разделимы. Уравнение поверхности решений в форме гиперплоскости, выполняющей это разделение, записывается следующим образом: ягтх+ 6 = О, (6.1) где х — входной вектор; и — настраиваемый вектор весов; 6 — порог.
Таким образом, можно записать: и~х,+6>Одляг1, =+1, (6.2) тттхг + Ь ( О д А = — 1. Допущение о линейной разделимости образов введено для того, чтобы доступно объяснить основную идею, положенную в основу машин опорных векторов. Далее, в разделе 6.3, это допущение будет ослаблено. Для данного вектора весов и и порога о расстояние между гиперплоскостью, задаваемой уравнением (6.1), и ближайшей точкой из набора данных называется границей разделении (шаги!и оГ зерзгабоп) и обозначается символом р. Основной целью машины опорных векторов является поиск конкретной гиперплоскости, для которой граница разделения будет максимальной. При этом условии поверхность решения называется олглимальной гилерллоскослгью (орйша! Ьурегр!апе). На рис. 6.1 показано геометрическое представление оптимальной гиперплоскости в двумерном пространстве входных сигналов.
Пусть и, и 6, — оптимальные значения вектора весов и порога соответственно. Исходя из этого, оптимальную гилерллоскослгь, представляющую многомерную линейную поверхность решений в пространстве входных сигналов, можно описать уравнением язвах + гь = О. (6.3) Оио является аналогом уравнения (6.1). При этом дискриминаитиая функция д(х) = этих+ 6, (6.4) определяет алгебраическую меру расстояния от точки х до оптимальной гиперплос- кости (269).
420 Глава 6. Машины опорных векторов Опорные векторы Рис. 6.1. Оптимальная гиперплоскость для линейно-разделимых образов Это легко увидеть, если выразить х следующим образом: тто х = яр+и 1! .11' где хр — нормальная проекция точки х на оптимальную гиперплоскость; т — желаемое алгебраическое расстояние. Величина г является положительной, если х находится с положительной стороны оптимальной гиперплоскости, и отрицательным в противном случае. Так как по определению д(х„) =О, следовательно, д(х) = итх+ 6, = и ))тко)) или (6.5) В частности, расстояние от начала координат (т.е.
х = О) до оптимальной гиперплоскости равно 6,/!~тт,!1 Если 6, > О, то начало координат находится с положительной стороны оптимальной гиперплосюсти, если же 6, ( Π— то с отрицательной. Геометрическая интерпретация зтих алгебраических результатов представлена на рис. 6.2. Требуется найти параметры тт, и 6, оптимальной гиперплосюсти на основе данного множества примеров Т=((х,, г(г)). В свете результатов, показанных на рис. 6.2, видно, что пара (и„Ь,) должна удовлетворять следующим ограничениям: тттхг + 6, > 1 дла г(г = +1, (6.6) 6.2. Оптимальная гиперплоскость для линейно-разделимых образов 421 ааьнаа оскость Рис.
6.2. Геометрическая интерпретация алшб- раических расстояний от точек до оптимальной паперплоскости (двумерный случай) д(х')) = тктх" + Ь. = + 1 для с(" = + 1. (6.7) Исходя из выражения (6.5), алгебраическое расстояние (а)йеопйс о)з1апсе) от опорного вектора хбе до оптимальной гиперплоскости равно )!н, )Р д(хбд) а — „', если с(('~ = +1, //зг,!! ~ — —,„',, если с(('1 = — 1, (6.8) где знак "плюс" означает расположение точки х~') с положительной стороны от опти- мальной гиперплоскости, а знак "минус'* — с отрицательной.
Пусть р — оптимальное значение границы разделения между двумя классами, составляющими множество примеров Т. Тогда из уравнения (6.8) следует, что 2 р = 2г = !! .!!' (6.9) Заметим, что если выполняется уравнение (6.2), то множества являются линейно- разделимыми. В этом случае значения ч, и б, можно масштабировать так, чтобы выполнялось условие (6.6). Такая операция масштабирования не влияет на соотношение (6.3). Конкретные точки (х„с(,), для которых первое и второе ограничения выполняются со знаком равенства, называются опорными векторами (зцррогт чессог).
Отсюда и получили свое название машины опорных векторов. Эти векторы играют решающую роль в работе обучаемых машин. А именно, опорные векторы являются теми точками данных, которые лежат ближе всего к поверхности решений, и, таким образом, являются самыми сложными для классификации. Как таковые они лучше всего указывают иа оптимальное размещение поверхности решений. Рассмотрим опорный вектор х<'), для которого с(('~ = +1. Тогда, по определению, 422 Глава 6. Машины опорных векторов Соотношение 16.9) означает„что максимизация границы разделения между классами эквивалентна минимизации Евклидовой нормы вектора чу.
Подводя итог, отметим, что оптимальная гиперплоскость, определяемая уравнением 16.3), является единственной (нпзйпе) в том смысле, что оптимальный вектор весов но обеспечивает максимально возможное разделение между положительными и отрицательными примерами. Такое оптимальное состояние достигается с помощью минимизации Евклидовой нормы вектора весов зе. Квадратичная оптимизация и поиск оптимальной гиперплоскости Нашей целью является разработка вычислительно эффективной процедуры исполь- ювания обучающего множества Т=1(хе, 111))~" з для поиска оптимальной гиперплос- кости, удовлетворяющей следующему ограничению: с)1(зч~х, + Ь) > 1 для 1 = 1, 2,..., Х.
(6.10) Для данного обучающего мнодсества Цх„111))н найти оптимальные значения вектора весовых коэффициентов т и порога 6, удовлетворяющие условию 11 1зчтх + 6) > 1 для 1 = 1 2 )'ч и минимизирующие функцию стоимости Ф(зч) = 1 2 Масштабирующий множитель 1/2 включен для удобства выкладок. Такая задача условной оптимизации называется прямой задачей и удовлетворяет следующим условиям. ° Функция стоимости Ф1зч) является выпуклой'. ° Ограничения линейны по е'. ' Пусть С вЂ” некоторое подмножество М . Это подмножество нюыввется еылукяым, если ах+ 11 — а)у 0 С для всех (х,у) Е С и а Е )0,1). Функция З: С Я называется еылукзой, если Пах+ (1 — а)у) < адх) + (1 — а)лу) для всех (х, у) е С и а е )О, 1,'. Это ограничение объединяет оба неравенства 16.6), если вместо чг, используется и. Задачу условной оптимизации, которую необходимо решить, можно описать следующим образом, 6.2.
Оптимальная гиперппоскость дпя линейно-разделимых образов 423 Следовательно, эту задачу можно решить с помощью метода мнозюителей Лагранлса (Мег(зод оГ Ьайтапяе ппййр!(егз) [124). Построим сначала функцию Лагранжа: .Х(чг, Ь, а) = — чг~зч — ,'> а;(а,(зябях, + Ь) — Ц, в=1 (6.11) зч = 1) а,г(,хо 1=1 Применяя условие оптимальности 2 к функции Лагранжа (6.11), получим; (6.12) а,д, = О. з=! (6.13) Вектор решения чг определяется в терминах расширения, включающего Х примеров обучения.
Это решение является единственным благодаря выпуклости Лагранжиана, чего нельзя сказать о коэффициентах Лагранжа а,. Важно также заметить, что в седловой точке для каждого множителя Лагранжа а, произведение этого множителя на соответствующее ограничение сходится к нулю, т.е. оц [й;(зч~х, + Ь) — 1) = О для з = 1, 2,..., Х. (6.14) Таким образом, ненулевые значения могут иметь только те множители, которые в точности удовлетворяют условию (6.14).
Это свойство следует из условия Куна-Такера (Кп)ш-Тпс)гег сопд)боп), сформулированного в теории оптимизации [124), [298). Как уже отмечалось, решение прямой задачи предполагает выпуклость функции стоимости и линейность ограничений. Для такой задачи условной оптимизации можно сформулировать так называемую двойственную задачу (дпа! ргоЫеш), которая будет иметь то же оптимальное решение, что и прямая, однако оптимальность ее где дополнительные неотрицательные переменные оь — это так называемые множители Лагранжа (Ьаягапяе пщ1бр1(ег). Решение задачи условной оптимизации определяется седловой точкой (задд!е ро[пг) функции Лагранжа,У(чг, Ь, а), которую необходимо минимизировать по зч и Ь, одновременно максимизируя по а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
