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

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

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

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

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

Добавлен: 11.04.2024

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

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

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

§ 2. ПОСТРОЕНИЕ РАЗДЕЛЯЮ Щ ЕЙ ГИПЕРПЛОСКОСТИ 351

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

{х, ф) < 1 + с — е и і б Х ,

или

(X, ф) > — 1 + с -f е и І 6 І ,

где ф и с направляющий вектор и порог разделяющей пло­ скости, построенной на предыдущей итерации.

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

Б л о к ОП-1/3

Блок строит обобщенный портрет либо оптимальную решающую плоскость для выделенной системы векторов путем решения двойственной задачи. Подробнее обе мо­ дификации (ОП-1/За и ОП-1/36) описаны ниже. В резуль­ тате работы блока либо устанавливается неразделимость векторов системы (в этом случае алгоритм прекращает работу, сообщая о неудаче), либо вычисляются направ­ ляющий вектор гиперплоскости ф и его разложение

аЬ

Ф = 2 « л — 2

(15-6)

і=1

;'=1

 

(а. > 0 ,

ß j>

0)

по векторам выделенной группы (а в случае оптимальной гиперплоскости определяется еще и константа с).

Б л о к ОП-1/4

Этот блок исключает из выделенной группы те векторы, которые входят в разложение (15.6) с нулевым весом и передает управление блоку ОП-1/2.

Перейдем к подробному описанию блока ОП-1/3 в двух модификациях.

352 ГЛ. XV. АЛГОРИТМЫ МЕТОДА ОБОБЩЕННОГО ПОРТРЕТА

Б л о к ОГЫ/За

Нахождение обобщенного портрета модифицированным методом сопряженных градиентов (рис. 26).

Рис. 26.

Целью работы этого блока является нахождение в по­ ложительном квадранте максимума функции

аb

w к ß) = 2 ®і —

ft — 4 " ф)>

i= i

j = l

где

 

а

Ъ

Ф = S

— 2 ßj*i»

i=i

;'=i

§ 2. ПОСТРОЕНИЕ РАЗДЕЛЯЮЩЕЙ ГИПЕРПЛОСКОСТИ 353

а —■число векторов первого класса, Ъ— число векторов второго класса в выделенной группе.

Каждому вектору x-t и ставится в соответствие бинар­

ная переменная dt (соответственно dj) *). Кроме того, номер текущего шага обозначен через t.

В этом блоке:

1. Устанавливается ф (0) = 0, яр (0) = 0, t — 0.

2.Полагается для всех і и j dt = 1, d} = 1 (восстанов­ ление размерности пространства).

3.t = t -j- 1.

4. Производится вычисление градиента функции W (а, ß) и квадрата его модуля в соответствующем коорди­ натном подпространстве по формулам

&і (t)

=

[1 — (ф (t — 1),

жг)] di,

ß'j (f)

=

Цф (t — 1), Xj)

— к) dj,

g2 (t)

= Sdt? (t) +

2ß? (0.

5. Проверяется условие: для всех і и j

 

 

ІМ *)

I <

8

 

или &i (t) < e и а г (t — 1)

=

0,

 

(15.7)

 

 

Ißj (t)

I <

8

 

или (г) < е и ßj (t — 1) = 0;

6.Если условия (15.7) выполнены и

аЬ

2 di + 2 äj = а + Ъ,

г=1 І=1

т. е. найден максимум функции в положительном квад­ ранте всего пространства, то блок заканчивает работу, вектор ф (t — 1) принимается за обобщенный портрет ф0 с разложением

а

Ь

Ф(*— 1)= 2 оц(*—

+ S ßi(*-l) xi-

і=і

г=і

*) С помощью этих переменных задаются координатные прост­ ранства, в которых ведется поиск.

12 В. Н . В апник, А. Я. Ч ервонеш ш с

354 ГЛ. XV. АЛГОРИТМЫ МЕТОДА ОБОБЩЕННОГО ПОРТРЕТА

7.Если условия (15.7) выполнены и

аb

2 d t+ 2 dj <^а + b

і = 1

3 = 1

(максимум найден в подпространстве), осуществляется переход к п. 2 (для восстановления размерности).

8. Если условие (15.7) не выполнено, исполняется п. 9.

9. Если ij) (t — 1)

= 0 ,

то

 

 

 

ä i ( t ) = â i ( t ) ,

 

ßj(t)

 

=ßj(t);

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

 

 

 

 

 

 

äi ( t) = dt ( t)

+

8 ( t) äi

(t —

1),

fj (t) =

ß; (t)

+

6 (t) ß, (t -

1),

где

 

 

 

 

 

 

 

<40 =

 

g 2 ( 0

•

 

 

 

g 2 (t — 1)

 

 

10.Находится вектор

аЬ

 

 

* (0 = 2

аА — 2

Pä -

 

 

 

І = 1

І = 1

 

11.

Вычисляется пробная величина шага

 

 

 

г.

й2(0

 

 

 

 

йпи 0' ( Ж ? й ) -

 

12.

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

 

 

 

h = min ( Änpoe, Д - ., З -А ,

 

 

 

V

Г і і

| ß y | /

 

где минимум берется лишь по тем і и) , для которых

< 0

или

<С 0.

минимум достигается

при h = hnр0б, то

ис­

13.

Если

полняется п.

14, если же минимум достигается при

 

то устанавливается dt = 0 (dj = 0) и ip (t) = 0 и далее исполняется л. 14.

§ 2. ПОСТРОЕНИЕ РАЗДЕЛЯЮЩЕЙ ГИПЕРПЛОСКОСТИ 355

14. Находятся новые значения коэффициентов а и ß:

at (t) = a-i (t — 1) + h ät (t),

ßjf (t) = ßj (f — 1) + Щ>і (t).

15. Находится новый вектор

 

Ф (it — 1) +

Щ (t),

если

h = /гДроб,

ф(0 =

а

Ь

 

 

' i = l

ßj (t) щ,

если

h 4=йдроб-

 

 

3=1

 

 

16. Осуществляется проверка на неразделимость груп­ пы векторов. Для этого вычисляется значение функции

 

а

b

W (а (f), ß (t)) =

S «i (t) - к 2 ßj (t) ---- !~(ф (t), ф (0).

 

i = l

3=1

Если W (a, ß)

В,

осуществляется переход к п. 3),

в противном случае принимается решение о неразделимости группы векторов и блок заканчивает работу.

М о д и ф и к а ц и я ОП-1/36

Эта модификация предназначена для отыскания опти­ мальной разделяющей гиперплоскости путем решения двойственной задачи модифицированным методом сопря­ женных градиентов (рис. 27).

От ОП-1/За отличаются только первые пункты. 1. Устанавливается

ф (0) = 0, ф (0) = 0 , t = 0.

2. Полагается для всех і и /

di = 1, dj = 1 •

Кроме того, вводится бинарная переменная q и устанав­ ливается

д = 1

(указатель работы во всем пространстве или в гиперпро­ странстве).

3. t =r-t+ 1.

12*

356 ГЛ. XV. АЛГОРИТМЫ МЕТОДА ОБОБЩ ЕННОГО ПОРТРЕТА

Рис. 27,

§ 2. ПОСТРОЕНИЕ РАЗДЕЛЯЮЩЕЙ ГИПЕРПЛОСКОСТИ 357

4.1. Находится градиент функции W (а, ß):

 

« і

 

(l)

=

1

—

f a ,

 

ф (t — 1 ) ) ,

4.2. Если q = 1

=

(zj’

Ф

{t

— 1)) +

1.

 

ßi

U)

 

 

 

 

чае 4.4.

 

 

исполняется 4.3, в противном слу­

 

 

 

 

 

 

 

 

 

 

 

4.3. а) Определяются функции от аргумента р

 

“і (р) =

а і(0 + Р.

 

 

если

a-iit — 1 )> 0 ,

 

F(a,i(t)-\-p)

если

аД і— 1 )< 0 ,

 

 

 

ß; (р) =

 

 

ß, (1) — р,

 

если

ßj (t — 1) О,

 

F (ß?\t) — P),

 

если

ßj

— 1 )< 0 ,

где

 

 

 

р /_\

 

 

 

ПРИ ж >

О,

 

 

=

\0

 

и функция

* w

 

при ж <

О,

 

 

 

а

 

 

 

 

Ь

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Ь { р ) =

2 і «г ( р ) — S ßi ( р ) -

 

 

 

 

 

г = 1

 

 

 

 

3=1

 

 

б)

Вычисляются

числа

 

 

 

 

 

 

 

L i

=

L

(

-

a - ) ,

 

 

L j = L

(ßj).

в)

Если все Li

и Lj <

0, то устанавливается

 

 

 

 

 

dj

= 0

 

 

 

 

для всех /, при которых ßj = 0. Осуществляется переход

к 4.4.

Если не все L;, Lj < 0, то находится

 

г)

 

 

 

 

L0= min (Lj, Lj),

 

 

 

 

 

г,І

 

 

где минимум берется лишь по

тем і и / ,

для которых

L , 0

и Lj > 0.

 

 

 

 

 

д)

Устанавливается

 

 

 

 

dj

=

0,

если а г

= 0 и Lj >

L 0,

 

dj

=

0,

если ßj

= 0 и Lj <

L 0.

Далее исполняется 4.4.

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