§ 8. ДВОЙСТВЕННАЯ ЗАДАЧА |
319 |
а) точка ф0, с0 удовлетворяла (14.20) и б) градиент функции в этой точке раскладывался с по
ложительными коэффициентами по градиентам ограни чений, которые достигаются в точке ф0, с0.
Иными словами, необходимо и достаточно, чтобы су ществовали такие числа а* 0 и ß7- 0, что
Фо •— 2 i=i
и, кроме того,
д (гр, гр)
причем
«г (1 + со — (Фо- х і)) = 0,
(14.26)
ßl ((Фо- + 1 — c0) = 0.
Рассмотрим теперь функцию
|
b |
W (а, ß) = 2 аі + |
2 ßj — 4 " |
i=l |
3=1 |
где положено
аЪ
Будем искать максимум этой функции при ограниче ниях
С&г ^ и,
аb
2 «і = |
2 ßi- |
(14-2V) |
i = l |
3=1 |
|
Согласно условиям Куна — Таккера, для того чтобы мак симум функции W (ос, ß) при ограничениях (14.27) до стигался в точке а0, ß°, необходимо и достаточно, чтобы:
а) точка ос0, ß° удовлетворяла условиям (14.27) и
320 ГЛ. XIV. ПОСТРОЕНИЕ РАЗДЕЛЯЮЩЕЙ ГИПЕРПЛОСКОСТИ
|
б) существовали числа qx <1 0, |
. . ., qa |
0, qx |
0, . . . |
. . qb ^ |
0; с *) такие, |
что |
|
|
|
|
|
|
dW |
(1 — (ф0, Жі)) ■= q{ — с, |
dW |
— (1 + ('Фоі Xj)) — <7j + |
c |
да. |
"^ß“ |
|
|
|
|
|
|
|
|
|
и g;aj = 0, q $ j — 0, где положено ф0 = |
2 |
а&і + |
2 ßp®r |
|
Ввиду |
|
|
|
|
i=l |
i—1 |
|
|
произвольности положительных |
чисел |
q h |
qj |
условие б) равносильно |
существованию числа с такого, |
что |
|
(Хі, |
'фо) > |
с + 1, |
|
|
|
|
|
|
|
|
(14.28) |
|
|
№> Ф«) < с — 1 |
|
|
и |
|
|
|
|
|
|
(1 + С — (ф0, Т ;) ) а°і |
|
|
|
|
|
|
0 , |
|
(14.29) |
|
|
(1 — с + (ф0, |
2ß) ßj = |
0. |
|
|
|
|
|
|
Сопоставляя условия Куна — Танкера для минимума функции (ф,ф) при ограничениях (14.20) и для максимума функции W (а, ß) при ограничениях (14.27), получаем следующую теорему.
Теорема 14.10. Точка а 0, ß°, в которой достигается мак симум функции W (а, ß) при ограничениях (14.27), и век тор фо, доставляющий минимум функции (ф, ф) при огра ничениях (14.20), связаны соотношением
а |
Ь |
|
Фо = 2 а°х* - |
2 |
(14.30) |
i=l |
3=1 |
|
Таким образом, для нахождения оптимальной разде ляющей гиперплоскости достаточно найти максимум функции W (а , ß) при ограничениях (14.27), определить ф0 из (14.30) и задать гиперплоскость уравнением
(х, |
|
min (хр фо) + max (x-, фо) |
фо) = -! |
----------- ----------------• |
а |
|
Ь |
|
*) Условие 2 |
а. = |
2 |
можно рассматривать как два нера- |
і = |
1 |
3 = 1 |
|
веиства 2оц — 2ß,- 0 и 2сц — 2ßj <J0.
равно В, то «зазор» не превосходит
§ 8. ДВОЙСТВЕННАЯ ЗАДАЧА |
321 |
Отметим, что функция W (а, ß) имеет, вообще говоря, не единственный максимум. Ио все точки а 0, ß°, достав ляющие максимум этой функции при ограничениях (14.27), соответствуют одному и тому же вектору ф0.
Значение максимума функции W (а, ß) позволяет су дить о расстоянии между выпуклыми оболочками мно жеств X и X, которое равно
П(фопт) = Ш " |
Действительно, |
|
(Фо. Фо) = (Фо. S a ? Xi + 2 ß ? Xj ) . |
Напомним, что значения a° и ß° отличны от нуля толь |
ко для тех векторов x t (Xj), |
для которых |
( * г , Фо) = с + 1, |
( x h фо) = с — 1. |
Поэтому с учетом (14.27) |
|
(Фо. Фо) = 2 ai "Ь 2 ßy |
+ с (2 ai |
—2 ß?)= 2 a* |
i = l |
J = 1 |
Vi= l |
j = l ' |
i —l |
;'=1 |
Следовательно, |
|
|
|
|
|
|
|
a |
b |
|
|
|
|
W (a0i ßo) = |
2 |
2 ß?--------------------грСФо? 'Фо) = 'фо). |
Наконец, |
г— 1 |
J=1 |
|
|
|
|
|
|
|
VW (et», |
|
|
|
|
2 |
|
|
|
П (фонт) |
— ІФоІ |
|
ß») • |
|
Последнее соотношение позволяет в ходе практиче ского вычисления оптимальной разделяющей гиперпло скости оценивать зазор между разделяемыми множествами. А именно, если найдена точка а, ß, удовлетворяющая ус ловиям (14.27), и значение функции W (a, ß) з этой точке
2
в •
Для множеств, не разделимых гиперплоскостью, т. е. таких, выпуклые оболочки которых пересекаются, функ ция W (a, ß) в области, определяемой соотношениями (14.27), возрастает неограниченно.
11 В. Н. Вапник, А- Я. Червонеикис
322 гл . XIV. ПОСТРОЕНИЕ РАЗДЕЛЯЮЩЕЙ ГИПЕРПЛОСКОСТИ
§ 9. Методы вычисления оптимальной разделяющей гиперплоскости
Вычислять оптимальную разделяющую гиперплоскость на ЦВМ не многим сложнее, чем находить обобщенный портрет.
Для этого достаточно в градиентных методах макси мизации функции W (а, ß) заменить условный градиент функции W (а, ß) в положительном квадранте на условный градиент функции при ограничениях
« і > 0, ßj > 0 (і = 1, 2, |
а) (J = 1,2, . . ., Ъ), |
аЬ
и в качестве начальной точки выбрать точку, удовлетво ряющую (14.27). В соответствии с теоремой П. 4, дока занной в приложении, условный градиент функции W (а, ß) на многообразии, задаваемом условиями (14.27), однозначно определяется формулой
|
1 — (Xi, ф) + |
d, если 1 — (xh ф)4- |
Ѵусл W (а, ß) = |
|
+ d 0, oCj 0, |
|
0 |
|
в противном случае, |
|
1 + (Xj, ф) — d, |
(14 ЗЦ |
|
если 1 +(Xj, ф) — v |
V U |
W (а, ß) = |
|
- d > 0,ß, > 0 , |
|
0 |
|
в противном случае |
при |
условии |
|
|
2ѴуСЛW - 2Ѵусл w = 0 .
Теперь остается подобрать величину d так, чтобы это
условие выполнялось. Будем рассматривать VyCn, ѴуСЛ в (14.31) как функции d и обозначим
L(d) = ЗѴуол (d) - 2ѴуСП(d)*
Очевидно, что для нахождения условного градиента до статочно найти корень уравнения
L (d) = 0,
