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

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

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

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

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

Добавлен: 11.04.2024

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

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

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

 

§ 1.

ИДЕЯ МЕТОДА

377

тО

Система векторов

ух, . .

y k линейно

независи­

ма, т.

е. не существует чисел А,х, . .

kh, не все из которых

равны нулю, таких, что

к

2 hVi = 0.

І=1

В самом деле, предположим противное, и пусть, например, к$ Ф 0. Тогда

Уі = 2 ТіУи ІФЗ

где положено

Умножая справа и слева это равенство на Аух, получим в силу (16.6)

ІУЬ А Уі) = о,

но это невозможно, поскольку yj ф 0 (утверждение а)) и квадратичная форма положительно определена.

г) Утверждения б) и в) устанавливают, что векторы Ук . • ., Уи образуют Л-ортогональный базис. В силу известных теорем линейной алгебры отсюда следует, что всякий вектор пространства E k представим в виде

к

 

X = Х0+ 2 TiJ/i-

(16.7)

І=1

 

Это утверждение можно доказать и непосредственно по индукции. Для Е х утверждение очевидно, так как всякая точка прямой х 0 + kgx может быть представлена и в виде

х 0 + к (х0 — хх), если

учесть, что хх,

так

же как и х 0,

лежит на этой прямой

и х 0 — хх Ф 0.

В

общем случае

предположим, что (16.7) верно для E h^x, т. е. всякий вектор X вида

 

к—X

X =

k\gI Xq

представим и в виде

i=l

к-1

 

X "

ТіУі “К

 

І=1

378 ГЛ. XVI. МЕТОД СОПРЯЖЕННЫХ НАПРАВЛЕНИЙ

Положим поэтому

К-1

ж/с-1= 2 а іУі +хо,

і= 1

кк—і

х к = 2

+

^ 0 =

2 Уі + ^këk + х 0-

i=l

 

i—1

Здесь Xk Ф- 0,

потому

что

х к ф E h- V Вычитая первое

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

Ä - I

У к = 2

І=1

откуда

6Ä 2 i=l

Ф і — а і ) Уі + b k g k i

Уі -Ь

Ѵк

(16.8)

К

 

Наконец, каждый вектор х из E h представим в виде

к

 

 

Х “

XlfëI

{" Xqi

г=1

 

 

а следовательно, и в виде

 

 

к—1

 

 

* = 2 ßi2/i -1-

+ ^0-

г=1

 

 

Подставляя сюда выражение (16.8) для gk, получим пред­ ставление произвольного вектора из E k в виде (16.7).

д)

Найдем

теперь, как

выражается вектор у к+і чере

Уі,- ■

Уи и gh+i-

Для точки х к <= Ек в силу (16.7) су­

ществует представление вида

 

 

 

к

 

 

 

х к = 2 а іУі "Ь х о,

 

 

і=і

 

для x h+1 — представление вида

 

 

 

к

 

 

х к + 1 — 2 & іУ і +

X g i i f i - ( - Х 3 .

i—1

§ 1.

ИДЕЯ МЕТОДА

379

Следовательно,

к

 

 

 

У т =

сіУі + Xgk+1-

(16.9)

 

i=l

 

Убедимся теперь, что в этом разложении отлично от нуля только одно с, а именно ск. Умножим скалярію выражение (16.9) на вектор Ayj:

к

(У т, Ay,) = 2 сі (Ун Ayj) + X (gk+1, AyД. i=l

При / силу (16.6) отсюда следует

 

 

CJ (Ул A y j )

+

Ä, (g h+1, Ayj) =

0.

(16.10)

Далее возможны

преобразования

 

 

 

Ayj — А (Xj

 

 

— (Axj

&)

• [Axj_^ — Ь) —

 

 

 

 

 

=

g j

1g j + i 1

 

 

 

откуда при j <. к в силу (16.3) справедливо

 

 

(gh+i, А Уі) =

gh+1

 

- gj+i) =

0,

(16.11)

а при j — к имеет место

 

 

 

 

 

 

(gfe+i,

A y h) =

gk+1 (gk — gft+1) = — Igk+1|a

(16.12)

Возвращаясь к (16.10), получим,

что при / < к коэффици­

енты с; = 0, в то время как при j — к

 

 

 

 

_

X

 

 

Ayk) _

 

1gte+il2

 

 

поскольку (ук, Аук) Ф 0.

 

 

 

 

 

 

Окончательно (16.9)

примет вид

 

 

 

 

 

» » =

*■ ( « - ■

+ т

а

'*)

■

(16.13)

Тем самым

 

 

 

устанавливаем,

что

 

 

 

 

x h + l = ^ g k + l + с к У к + x h

380 ГЛ. XVI. МЕТОД СОПРЯЖЕННЫХ НАПРАВЛЕНИЙ

или, иначе,

 

 

= Хі + Я

У*) ■

 

Таким образом, точка x k+1 заведомо лежит на

двумерной

плоскости

hgh+1+ cyh

(16.14)

„х = x k +

(Я и с — параметры) и даже на одномерной

прямой вида

* = ^ + я ( ^ +І + (^ ^ у к)

(16.15)

(Я — параметр), и поиск максимума в пространстве размер­ ности к может быть заменен поиском максимума на плос­ кости или на прямой.

§ 2. Метод сопряженных градиентов

Метод сопряженных градиентов для нахождения макси­ мума квадратичной формы имеет несколько модификаций.

1. Одна из них получается непосредственно из рас­ смотренного выше процесса, если заменить максимизацию функции F (х) на гиперпространстве Е к отысканием макси­ мума на прямой вида (16.15). Как было показано в преды­ дущем пункте результат от этого не изменится, так как эти максимумы совпадают.

Алгоритм получается таким (модификация I): А. Начальный шаг.

1)

Находится градиент

 

функции F (х) в произволь­

ной точке х0;

= gx;

 

 

 

 

2)

полагается

 

 

 

 

3) находится точка хъ доставляющая максимум функ­

ции F (х) на прямой X = х 0 -J-

(Я — параметр).

Б.

Общий шаг.

Пусть уже найдены точки х 0, хъ . . .

. . . , x k - li x h*

 

 

функции F (х) в точке x h;

1)

находится градиент gft+1

2)

полагается

 

 

 

 

 

где

z k + l =

g k + l +

а к + 1 (x k — x k- i) ,

 

 

 

 

 

 

 

ttfc+1 —

( K - i - * t ). А Уц+і)

 

 

_____________ 4 + 1 _______________ .

A (Xk - W

)

 

((** -

A (Xä - Xk-x)) ’

 

 

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