Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 11.04.2024

Просмотров: 194

Скачиваний: 4

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

314 ГЛ. X IV . ПОСТРОЕНИЕ РАЗДЕЛЯЮ Щ ЕЙ ГИПЕРПЛОСКОСТИ

Максимизируемая функция W (а, ß) имеет вид

W{a, ß )= S

ai - Ä S ß j - - T

S ßj *i | •

i — 1

j — 1

i = l

Квадратичная часть этой функции есть

а

b

 

2

 

 

 

Q(a, ß) =

2 a&i — 2

h xi

 

 

 

 

 

 

 

i=i

j=i

 

 

Обозначим

составляющие условного

градиента через

 

 

г dW_

=

1 — te. Ф).

если

аг> 0

или (1 — (Xi, ф) >

О,

Öi =

даг

 

о

 

в противном случае,

 

 

 

 

 

 

ß; =

( dW

= (%

 

если

ßj > 0 или (Sj, ф) — к >

О,

Ѣ

 

0

 

 

в противном случае,

 

 

 

 

 

 

 

 

 

 

 

 

о

Ь

 

 

 

где положено ф =

2 аіхі — 2 ßi^r Обозначим составляю-

щиѳ вектора z

(t),

І= 1

3=1

направление движения

на

t-м шаге,

 

 

 

задающего

через

ссг, ßj.

 

 

 

 

При вычислении величины шага по формуле (14.18) необходимо вычислять величину (z (t), Az (У)), т. e. значе­ ние квадратичной функции F (х) при подстановке в нее вектора г. В нашем случае

а

 

 

 

 

(z, Az) = 2

аіхі

2

Ря

іф р

і=і

 

3=1

 

 

где обозначено

2 äjXi

 

 

ф =

-

SМу-

 

Таким образом, заменяя формулы (14.17), (14.18) и (14.19) в соответствии с введенными обозначениями, при­ ходим к следующему алгоритму.

Находится условный градиент в точке а (У), ß (У):

аі (£ + 1) =

 

если а (У)> 0 или 1 — (зГіф (У)) > О,

Г 1 — (ж{ф (У)),

(

0

в противном случае,

 

 

 

§ 6.

ГРАДИЕНТНЫЕ

МЕТОДЫ

315

$j ( t + 1)=

 

 

 

 

 

 

 

 

 

 

О,

_

l(xj>Ф (t)) — к, если ß; (t) > 0 или (ж/ф (t)) —к >

~

{

0

 

 

в противном

случае.

 

Определяется направление

движения:

 

 

<хг (t

+

1) =

âi

(t

+

1)

+

б (t

+

1) ät (t),

 

где

ßj (t

+

1) =

h

(t

+

1)

+

6 (t

+

1) fr, (t),

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2

*?(* + !)+

2

ßy^+ '1)

 

 

H t +

l ) = = 4 r ------

 

y=1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2

i?w +

2

ß?(f)

 

Далее вычисляется

 

i=x

 

 

J=1

 

 

 

 

 

 

 

 

b

 

 

 

 

 

 

o

 

 

 

 

 

 

 

^(* +

i)

= 2

 

 

+

 

 

2

ßj(< + i) ^ .

 

 

 

 

j=i

 

 

 

 

j=i

 

 

 

Новое значение а* и ß; находится по формулам

at (t + 1) = at (t) + &t (t + 1) h (t + 1),

ßi (* + 1) = ß^ (t) + ßj (t + 1) h (t + 1).

Здесь h (t + 1) — величина шага, определяемая из усло­ вия достижения максимума по направлению или выхода на ограничение:

h (t +

1) = min (Го (t +

1), Ti (t +

1), Tj (t + 1)),

где

 

i,]

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2 «f (* + i)+ 2

ß| c*+ 1 )

 

To (*•+ 1) =

i=l

 

 

 

 

 

 

 

№(* + 1). *(* + !))

 

 

 

 

 

“i (0

если

äi(t +

i) < 0 ,

Ti(« +

1) =

a^t + i)

 

 

 

 

+

oo,

если

â i(t -f- 1) >

0,

 

 

 

 

 

В. It)

 

ßj {t +

1) <

0,

 

 

- ^r-1------, если

Ti(* +

1) =

РД* + 1)

 

;

^

 

+

оо,

если

ß;-(f +

1 )> 0 .

 

 

316 гл. XIV . ПОСТРОЕНИЕ РАЗДЕЛЯЮ Щ ЕЙ ГИПЕРПЛОСКОСТИ

Наконец,

ф (t + 1) = ф (t) + ф (t + 1) h (t + 1).

Первый шаг (t = 0) отличается от общего лишь тем, что значения ссг (1), ß7- (1) задаются следующим образоом

ä; (1) = ±і (1),

ßl (1) = ßj (1).

Критерий останова: | â* j <; е и | ßy | < e или

W(a, ß ) > Д.

Вглаве XV будет подробно рассмотрена структура ал­ горитма построения обобщенного портрета на основе ме­ тода сопряженных градиентов в первой модификации.

§7. Теория оптимальной разделяющей гиперплоскости

Напомним, что оптимальной разделяющей гиперпло­ скостью была названа плоскость

где Фопт — единичныя вектор, доставляющий максимум функции

П (ер) = Сі (ф ) —

с2 (ф ) = min (х,

фопт) — max (Я, ф ),

 

х

 

X

І-О П Т

г 1 (Фопт)

'

(Фопт)

-----

9

•

Рассмотрим теперь минимальный по модулю вектор ф (доставляющий минимум функции (ф, ф)), удовлетворяю­ щий неравенствам

(ян Ф) > 1 + с,

(14.20)

(®і, Ф) < —1 + с.

Параметр с считается допустимым, если неравенства (14.20) совместны. Нетрудно убедиться, что если множества X и I разделимы гиперплоскостью, то множество допу­ стимых с не пусто. Будем искать минимум функции (ф, ф)

§ 7 ОПТИМАЛЬНАЯ РАЗДЕЛЯЮ Щ АЯ ГИПЕРПЛОСКОСТЬ 317

при ограничениях (14.20), считая переменными как век­ тор т|7, так и параметр с. Оказывается, что решение этой задачи равносильно отысканию оптимальной разделяющей гиперплоскости.

Теорема 14.9. Если множества X и X разделимы ги­ перплоскостью, то минимум функции (т|), ф) при ограни­ чениях (14.20) существует, единственен и достигается при

,ф

_

_____ 2(Ропт_____

 

 

Сі ('Ропт) С2 (Топт)

£

_

Сі (фрпт) ~Ь С2 (фрпт)

 

 

Сі ОРопт) ~ ’ Сг ОРопМ

где фонт — направляющий

вектор оптимальной

разде­

ляющей гиперплоскости.

Покажем,

что для

любого

Д о к а з а т е л ь с т в о .

вектора ф, удовлетворяющего (14.20),

справедливо не­

равенство

 

 

 

П Ф

>

 

(14.21)

Действительно, поскольку нуль не удовлетворяет (14.20), знаменатель в нуль не обращается. Далее, в силу (14.20)

Г_ Ф \

^

с + і

МФІ / ="'

Ж ’

/

Ф

\

е — і

с2 \

I Ф I

/ 5=5

ІФІ

и, значит,

п_Ф_

к-1

причем равенство достигается только в том случае, когда

 

 

С+І

и

 

іфі

 

 

. ( ф \

_

g - 1

'2ІІФІ j

“

H M •

Теперь, учитывая, что

 

 

Г І ( ф о п х ) > п ( 7 | т ) ,

(14.22)

318 ГЛ. XXV. ХІОСТРОЕНИЕ р а з д е л я ю щ е й г и п е р п л о с к о с т и

получаем для любого вектора ф, удовлетворяющего (14.20),

>

2

(14.23)

І [ (Фопт)

 

‘

В силу единственности оптимальной разделяющей гиперплоскости (теорема 14.1) неравенства (14.21) и (14.22) переходят в равенство для векторов, удовлетворяющих (14.20), только при

Ф

 

7 7 7

— Фот,

(14.24)

Сі _Ф_

g+*

r ( j t .

с — 1

ІФІ

 

 

ж ’

2 l m

ж •

Только при этих условиях, очевидно, достигается равен­ ство и в (14.23).

Разрешая эти равенства относительно і|)ис, получаем что минимум (ф, ф) при ограничениях (14.20) достигается только в точке

_____ ^Фопт_____

Фо =

 

(Фонт)

(Фонт)

 

(Фонт) ~Ь

(Фопт)

 

Сі (Фопт) Сі (Фопт)

Теорема доказана.

 

Таким

образом, вектор тр0, доставляющий максимум

(ір, ф) при

ограничениях (14.20),

всегда коллинеареп <г0пт

и оптимальная разделяющая гиперплоскость может быть задана в виде

< * , « =

§ 8. Двойственная задача

Точно так же как при нахождении обобщенного порт­ рета, здесь оказывается удобным перейти к двойственной задаче. Воспользуемся условиями Куна — Таккера. Согласно теореме 14.4, для того чтобы величина (ф, ф), рассматриваемая как функция ф и с, достигала минимума при ограничениях (14.20) в точке ф0, с0, необходимо и до­ статочно, чтобы

Смотрите также файлы