Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 198
Скачиваний: 4
§ 4. ДВОЙСТВЕННАЯ ЗАДАЧА |
305 |
Поэтому |
|
1 - к |
|
VW JpbTW |
|
Отсюда, учитывая, что |
|
W{a, ß ) < W ( a 0, ß0), |
|
получаем (14.14).
Это следствие используется для конструирования кри терия неделе_ния. В самом деле, будем считать, что два мно жества X и X не могут быть разделены с допустимым «за зором» с помощью обобщенного портрета ф (к), (к < 1),
если соответствующая величина П |
меньше заданной |
|
константы р |
0. |
|
Тогда существование такой точки а > 0 , ß>0, что |
||
|
W ( a , ß ) > - ^ ß - , |
(14.15) |
и будет означать, что множества неразделимы с заданным
зазором с помощью обобщенного портретаф (к). |
максимум |
||||
Итак, согласно теоремам |
14.7 и 14.8, |
||||
W (а, |
ß) в положительном квадранте определяет обобщен |
||||
ный |
портрет, |
а, согласно |
следствию, тот факт, что при |
||
W (а, |
ß) = В |
максимум |
еще |
не достигнут, |
означает, |
что множества |
неразделимы с |
зазором, большим, чем |
|||
1 —к |
|
|
|
|
|
V 2 B
Таким образом, проблема построения обобщенного портрета свелась к поиску максимума функции W (а, ß) в положительном квадранте или оценке снизу величины максимума этой функции.
Оказывается, что и другие методы построения разделяющей гиперплоскости в определенном смысле реализуют различные алгоритмы поиска максимума функции W (а, ß) в положительном квадранте. Это об стоятельство дает возможность сравнивать их между
собой: тот алгоритм построения разделяющей гипер |
|
плоскости эффективнее, в основе которого |
лежит бо |
лее эффективная процедура максимизации |
функции |
W(a, ß).
§ 5. АЛГОРИТМЫ ПЕРСЕПТРОННОГО ТИПА |
307 |
и
dF(zx.....zn) |
о > |
если z* = 0. |
|
dz1 |
|||
|
|
2. Применение модифицированного метода Гаусса— Зайделя для максимизации функции W (а, ß) в области
«г > 0, ßj ^ 0 приводит к следующему алгоритму по строения обобщенного портрета. Если на t-м шаге произ водится движение вдоль координаты а*, то
щ (t) = c£j (t — 1) + Ааi.
Аналогично в случае движения вдоль координаты ß^
ß/ (0 = ß/ (t — 1) + Aß;-
Значения остальных координат сохраняются. Приращения Ааг (Aßу), доставляющие максимум по
направлению шага, определяются из условий
= [і_ (ф(f_ 1),а:г)]- IXiI2Ащ = 0
І
( öA ßT |
1 ) ’ ®j) |
I Щ|2 A ßj — , |
где положено
а Ъ
— 1) = 2 аі(^ — і )жі — 2 — i)^i-
3=1
Учитывая, что шаг не должен выводить за пределы огра ничений, получаем
Даг = |
max |
1 — W>(г —1), |
, — Vi{t — 1)) . |
|
|
|
l*t l* |
|
|
Aßj = |
max |
(Ф(*-1), *j)- k |
, - ß H f - i ) ) • |
|
Іг;Іг |
||||
|
|
|
Процесс подъема продолжается до тех пор, пока не бу дет построен обобщенный портрет, либо не будет установ лено, что множества не могут быть разделены с помощью обобщенного портрета ф (А) с допустимым зазором (§ 4).
308 гл. XIV . ПОСТРОЕНИЕ РАЗДЕЛЯЮ Щ ЕЙ ГИПЕРПЛОСКОСТИ
В первом случае останов производится по условию
I 1 — (Хі, |
ф) | < |
е, если |
<хг |
|
0, |
1 — (Xi, |
ф) < |
е, если |
а г |
= |
0 |
Л {Я}, я)?) —к |< е, если ß/ > 0,\
\(xt, ф) — к < е, если ß;- = 0 ) ’
Во втором случае критерием останова служит выпол нение неравенства (14.15)
где р — допустимый зазор.
Алгоритм можно реализовать и в такой форме:
ф (t) = ф (t — 1) + ХіАосі при движении вдоль осг,
ф (t) = ф (t — 1) — г^Дß^ при движении вдоль ßj-.
3. С помощью метода Гаусса — Зайделя удается до стигнуть максимума W (а, ß) и тем самым построить обоб щенный портрет. Однако часто требуется найти просто разделяющую гиперплоскость (х , ф) = с (не обязательно экстремальную) такую, что
X Ф) > ,
(14.16)
(** ф к Ц ± .
Построение такой гиперплоскости обеспечит следую щая огрубленная модификация метода Гаусса — Зай деля:
1) движение вдоль каждой из координат а *(ßj) проис ходит только в сторону от ограничений тогда, когда
(Хі, ф) < |
1 +к |
|
2 |
(xh ф) > |
1 + к |
|
2 |
В случае выполнения этих условий значение вектора ф вычисляется по формулам
ф (0 = Ф (t —- 1) + ДаіХі
(ф (0 = ф (t — 1) — Aßj Xj ) ,
