Главная > Теория распознавания образов (статистические проблемы обучения)
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
След.
Макеты страниц

Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше

Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике

ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO

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

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

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

Алгоритм получается таким (модификация I):

А. Начальный шаг.

1) Находится градиент  функции  в произвольной точке ;

2) полагается ;

3) находится точка , доставляющая максимум функции  на прямой  ( – параметр).

Б. Общий шаг. Пусть уже найдены точки .

1) находится градиент  функции  в точке .

2) полагается

,

где

;

3) находится точка , доставляющая условный максимум  на прямой

.

В. Останов алгоритма. Процесс обрывается в тот момент, когда градиент  обратится в нуль, т. е. достигается максимум  на всем пространстве .

При абсолютно точном вычислении алгоритм должен привести к максимуму не более чем за  шагов, так как при этом точки  вычисляемые методом сопряженных градиентов, совпадают с точками , получающимися в процессе, описанном в предыдущем пункте: как было показано, этот процесс выводит на абсолютный максимум не более чем за  шагов.

В реальных условиях, при ограниченной точности вычислений, процесс поиска максимума следует остановить не при точном обращении в нуль градиента, а в тот момент, когда градиент станет достаточно мал. При этом на самом деле может потребоваться более  шагов. Более подробно эти вопросы будут рассмотрены ниже.

Чтобы придать алгоритму более «конструктивную» форму, найдем формулу, определяющую точку максимума квадратичной формы на прямой .

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

,

где  – градиент  в точке . Максимизируя по , получим

и соответственно

.                   (16.16)

Таким образом, вычисление в пункте 3) алгоритма может быть осуществлено по формуле

.

2. Более известна модификация метода, при которой для вычисления очередного направления  используются векторы  и  вместо  и .

Рассмотрим систему векторов , коллинеарных соответственно векторам  (т. е.  при некоторых действительных ). Для векторов  и  сохраняется условие -ортогональности

 при .                    (16.17)

Кроме того, из (16.11) следует, что

 при .                 (16.18)

Наконец, остается в силе соотношение типа (16.9)

.                      (16.19)

Умножая правую и левую части (16.19) на  и учитывая (16.17) и (16.18), получим при

,

откуда  при . При  получим

,

откуда

.                (16.20)

Соотношение (16.20) определяет  с точностью до произвольного множителя через  и ц. При выводе (16.20) использовались лишь соотношения (16.17), (16.18), (16.19). Поэтому процесс построения векторов  может рассматриваться как процесс -ортогонализации векторов .

Полагая в (16.20)  и , получим конкретную систему векторов , коллинеарных . Каждый вектор  задает направление прямой, исходящей из , на которой лежит . Алгоритм, таким образом, примет следующий вид (модификация II).

А. Начальный шаг, такой же как и в модификации I.

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

1) Находится градиент  функции  в точке ;

2) полагается

,

где

;                       (16.21)

3) находится точка , доставляющая условный максимум  на прямой

по формуле

.                     (16.22)

Формулы (16.21) и (16.22) могут быть преобразованы. Так, полагая

,

имеем из (16.22)

,

откуда получаем, применяя (16.12),

.                (16.23)

С другой стороны, поскольку

,

из (16.21) имеем

и, таким образом,

.                     (16.24)

Наконец, из (16.21), (16.23) и (16.24) получаем

.

Таким образом, формулы (16.21) и (16.22) могут быть записаны в виде

,

где

                       (16.25)

и

.                     (16.26)

Совпадение результатов действия по формулам (16.21) и (16.22), с одной стороны, и (16.25), (16.26), с другой, может служить критерием правильности вычислений.

3. Метод сопряженных градиентов может быть применен и для максимизации функций , не являющихся квадратичными. Известно, однако, что вблизи максимума достаточно гладкие функции, как правило, хорошо аппроксимируются квадратичной функцией, например, с помощью разложения в ряд Тейлора. При этом обычно предполагается, что коэффициенты аппроксимирующей квадратичной функции неизвестны, но для любой точки можно найти градиент  функции .

При этом пункт 1) алгоритма может быть выполнен без изменений, пункт 2) должен выполняться по формуле (16.25), поскольку в эту формулу не входит явно матрица , а пункт 3), нахождение условного максимума на прямой, может быть выполнен одним из известных способов, например, методом Фибоначчи. Применение метода сопряженных градиентов дает обычно значительно более быструю сходимость к максимуму по сравнению с методами наискорейшего спуска, Гаусса – Зайделя и др.

4. Что будет, если применить метод сопряженных градиентов для максимизации квадратичной формы с положительно полуопределенной формой ?

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

,

где все  и некоторые из . При этом функция имеет максимум, если выполнено условие: когда , то и . Легко видеть, что максимум в этом случае достигается на целом гиперпространстве. А именно, пусть, например, при , меняющемся от 1 до , , а при , меняющемся от  до ,  и . Тогда максимум достигается в точках с координатами  при  и с произвольными значениями  при . Они образуют гиперпространство размерности .

Если же при некоторых  , a , то функция не имеет максимума и возрастает неограниченно. В самом деле, пусть, например,  и ; тогда, если положить  при  и устремить  к , то, очевидно, и  будет возрастать до бесконечности.

Оказывается, что метод сопряженных градиентов (при точном счете) позволяет в первом случае достигнуть максимума не более чем за  шагов, где  – число  не равных нулю, а во втором случае не более чем через  шагов выводит на направление, по которому функция  возрастает неограниченно.

В исходной системе координат функция  имеет вид

,

причем матрица  вырождена и имеет ранг . При этом, как и раньше, обращение градиента в нуль есть критерий достижения максимума, а ортогональность градиента гиперпространству – критерий условного экстремума на гиперпространстве.

Рассмотрим применение метода сопряженных градиентов в форме II в этом случае. Здесь приходится изменить условие остановки, т. е. теперь возможно, что при вычислении длины шага

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

Таким образом, условие останова будет таким. Процесс останавливается, если:

на очередном шаге

или

на очередном шаге оказывается, что

.

В первом случае алгоритм, естественно, приводит в точку максимума. Во втором случае направление  будет направлением неограниченного возрастания функции . В самом деле, на прямой

при  функция  имеет вид

,

причем

,

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

Нам остается убедиться, что останов произойдет не более чем через  шагов, где  – ранг матрицы . В самом деле пусть при  выполнено условие . Тогда остаются в силе соотношения

 при  

(при выводе этих соотношений положительно-определенность не использовалась).

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

,

причем

,

так что в точке  достигается условный максимум функции  на . Далее, на гиперпространстве  функция  имеет вид

,

где

,

и так как , то квадратичная часть  положительно определена. Но, как известно из линейной алгебры, это возможно только в том случае, когда размерность пространства  меньше или равна рангу  матрицы .

Следовательно, останов обязательно произойдет при .

 

1
Оглавление
email@scask.ru