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

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

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

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

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

Добавлен: 11.04.2024

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

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

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

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

Далее, нужно взять условный градиент F (х) в точке х к. Но направление полного градиента gk+i в точке x h при­ надлежит гиперплоскости А к. Поэтому условный гради­ ент совпадает с полным. Теперь через точку x k нужно про­ вести прямую

X = xh + Kgh+1

и найти на этой прямой точку хк+1, доставляющую усло­ вный максимум F (х). Наконец, точку х к_г необходимо соединить с хк+1 прямой и на этой прямой найти точку, в ко­

торой

достигается условный максимум F (х).

Эта точка

и есть

жй+1.

 

алгоритма приобретает

Таким образом, общий шаг

следующий вид:

 

 

 

1) в точке x k находится градиент gh+1;

точка хк+1,

2) на прямой X = xk +

'kgu+i

определяется

в которой функция F (ж) достигает условного экстремума

по формуле

^кёк+1

 

 

где

•Tft+l =

 

 

 

 

 

 

 

л ' _

 

.

 

к~ (O c + iH W

3)на прямой X = х к- х + Я (ж^+1 — Хи-і) ищется точка Xk+n доставляющая условный экстремум F (х), по фор­

муле

-Tfe+l ~ -Tfe-l “Г 4

(-Tfc+1

■Tft-l))

где

 

 

_ _____ (fofc+i

хк-д' _____

« 4 + 1 -

1)> A (4 + 1 -

*fc-i)) ’

Эти формулы получены в соответствии с общей формулой (16.16), выведенной в § 2. Отметим, что при точном счете процесс должен закончиться не более чем через п шагов.

Метод параллельных касательных может быть приме­ нен и в случае неквадратичной функции, при этом поиск условного экстремума на прямой должен производиться одним из известных методов одномерного поиска. Однако при этом нет никаких гарантий, что процесс закончится через п шагов. Экспериментально же установлено, что этот метод поиска сходится значительно лучше, чем ме­ тоды наискорейшего спуска или Гаусса-Зайделя.

§ 4. АНАЛИЗ ПОГРЕШНОСТЕЙ МЕТОДА

391

§4. Анализ погрешностей метода

В§ 1 был рассмотрен процесс, в котором строились последовательность вложенных гиперпространств Еъ . . .

..., E k возрастающей размерности и последовательность то­ чек ^, . . x h , доставляющих условный максимум функции F (X), соответственно, на гиперпространствах Е ъ . . ,Èk. При этом оказалось, что векторы ( x k+1 — x h ) являются А-ортогональными.

Покажем сейчас, что справедливо в некотором смысле и обратное утверждение.

Если:

1) векторы z l t . . z k А-ортогональны, т. е.

ZiAzj = 0 при і Ф /,

2) точки х0, х-у, . . ., х к получены из рекуррентного ус­ ловия: х к+1 доставляет условный максимум функции F (х) на прямой

X = x k + K z K х

при произвольной фиксированной точке х0,

то точка х к доставляет условный максимум F (х) на ги­ перпространстве E h, определяемом как совокупность век­ торов вида

 

к

 

 

 

 

х = Х0 + 2

 

 

(16.27)

 

1=1

 

 

 

В самом деле, подставляя формулу (16.26) в выраже­

ние для F (х),

получим

fc

 

 

 

 

F = F ( х 0) — - і - 2 сіс (z»> Azi) +

2

c i

( z u Ф — A x „)).

Положим

i j

i =

i

 

= (Zi, (b — 4ж0)) и

flj =

ZiAzi.

di

Тогда, учитывая ^-ортогональность zt и zj при і Ф j, получим

кк

F = F (х0) ---- 1 - 2

chi + 2 «А-

(16-28)

І=1

І=1

 

Чтобы найти вектор Х опт, доставляющий максимум F (х) ца E h, продифференцируем F по сг и приравняем частные

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

производные к нулю. Тогда

d.

Сіош = ~I

(здесь аьф О из-за полояштельной определенности фор­ мы), откуда

к

d

(16.29)

Хопт (к) = хо + 2

zi ~ •

І=1

і

 

Сопоставляя выражения (16.27) для жопт (к) и жопт (к -f- 1), имеем

аЪпт (1) =

ж0 + zx

,

Жопт {к -)- 1) =

Ж0пт {к)

d. .

-f- Zk+1 - .

 

 

“а+1

Таким образом, точка жопт (к -f 1) лежит на прямой вида

Жж0пт (&) -(-

и, очевидно, доставляет функции Е (ж) условный макси­ мум на этой прямой, поскольку в этой точке достигается условный максимум на всем гиперпространстве E k+1, включающем прямую.

Поэтому при точном счете последовательности ж0, хъ . . .

. . ., x k и ж0, ж (1), . . ., ж (&) совпадут. Если же при вы­ числении допускаются ошибки, то ошибки на каждом шаге будут просто складываться (векторно). В самом деле, пусть в результате первых к шагов процесс приводит в не­ которую точку х*к, отличную от жопх (к). Положим

хк

■ жопт (А;) Ажд.

Будем считать, что х\

ЕЕ E h. Тогда коэффициенты ct для

х\ при і ф к в представлении

(16.27) равны нулю. Поиск

максимума на прямой

 

 

X = хі +

Xzk+1

равносилен поиску максимума выражения (16.28) по пе­ ременной с&+1 при фиксированных остальных перемен­ ных сг. Осуществляя эту операцию, убеждаемся, что ch+l0llT,

§ 4. АНАЛИЗ ПОГРЕШНОСТЕЙ МЕТОДА

393

как и раньше, равно — - . Таким образом, (к +

1)-й шаг

а к + і

»

возмущенного процесса совпадает с соответствующим шагом невозмущенного, откуда следует, что ошибки про­ сто складываются. Если суммарная накопившаяся ошиб­ ка после п шагов заведомо мала по сравнению с переме-. щением от начальной точки к точке оптимума (это усло­ вие выполняется при работе на ЭВМ), то во всяком слу­ чае после двух-трех повторных применений алгоритма максимум будет найден с очень высокой точностью.

Все эти рассуждения верны в предположении, что си­ стема И-ортогональных векторов zt получена заранее и с достаточно высокой точностью. Но в действительности метод сопряженных градиентов строит эти векторы, ис­ пользуя рекурсивную процедуру. Оказывается, что при этом дело может обстоять значительно хуже, а именно: однажды возникшая малая ошибка может привести к ла­ винообразному нарастанию ошибок в ходе дальнейших вычислений.

В самом деле, рассмотрим метод сопряженных гради­

ентов

в форме II: х0 — произвольно и при к ;> 1

1)

ShA 1

Sh

А. (Xh

’

(16.30')

2)

z k+l

= ëh+l a / £ + l z

f t )

(16.30")

3)

&k+1

 

"h Уh+X^h+Ъ

(16.30"')

где

 

 

 

 

 

 

 

 

tefc+i, A z k)

 

 

 

*+1

(Zb A z k)

’

 

 

 

 

 

(16.31)

 

 

 

z/c+i)

 

 

Гк+1 ~

A z k+d

'

Выведем рекуррентные соотношения для величин (g k , zt)

и (zk, Azi). Из (16.30")

имеем

 

x h

x h -l

J h z k-

Подставляя это выражение в (16.30') и умножая скалярно обе части равенства на zh получим

(ëh+li Zi) — i.ëhi zi)

Ук (Zh: -Azi)

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

(в

последнем

члене

использовано равенство {Azk, zt) =

=

(zk, Azi)).

Далее,

чтобы получить рекуррентное выра­

жение для (zk+1, Azi), заменим zk+1 по формуле

(16.30");

получим

 

 

 

 

(z?t+i! Azi) = a h+1 (zh, Azt) -f- (gk+i, Azj).

(16.32)

Теперь воспользуемся снова соотношением, вытекающим из (16.30') и (16.30"),

 

A z i =

Ч г

(^+1 — Si)

 

 

 

Ч

 

 

 

и

подставив его в (16.32)

получим

 

 

(Zk+i, Azi) = аk+1(zk, Azi) — у - ((gui — gt), gk+1).

 

 

 

 

4

 

Наконец, из формулы (16.30")

 

 

 

gi+l =

z i+1

a i+lz i,

 

и

окончательно рекуррентное

соотношение

примет вид

(г/с+і, Az) = a;t+1 (zk, Az{) — —

[{zi+1,gk+1) —

 

 

 

ч

 

 

 

 

—

(1

+ а г+і) (zb Ski-1) +

* i (Zi-u gfc+i)l-

Перепишем рекуррентные соотношения в новых обозна­ чениях, полагая (gh, zt) = ahii, (zh, A zt) — ck,t. При i > 1

получаем

^h+l, i

&k, i

Tk

^h,

i

(16.33)

1

 

 

 

 

 

cfc+l,i = а к+1ск,г-----Z~ l aJc+l,i+l

(1 4" a i+l) a k+l,i

ai<Z/c+1Д-1 ]*

•i

 

 

 

 

 

При i = 1 получаем

 

 

 

 

 

ck+i, 1 = a k + ick, 1 -------ГГ” [ ß /c+i, 2 ~

(1

a i )

a k+1, l l -

 

Ti

 

 

 

 

Нетрудно убедиться, что коэффициенты y k и a k подоб­ раны в алгоритме именно так, чтобы ah+lt h и ch+ljh обра­ тились точно в нуль. Поэтому можно рассматривать си­ стему (16.33) при к ;> і + 1 с граничным условием akih-i — о, ck,h_x = 0. Так как система (16.31) является линейной и однородной, то при этих начальных условиях она имеет единственное решение

ац,і = 0 , cifi = 0 при к > і.

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