Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 208
Скачиваний: 4
§ 4. УСЛОВИЯ СХОДИМОСТИ |
191 |
условиям
М ( І I а, z) = О,
Будем |
М |
(£2 |
I а, z ) < Z > < оо. |
|
|
|
|
||
|
считать, |
что величины у (г) |
О, образующие |
|
бесконечную последовательность неотрицательных чисел, таковы, что
2 |
Т (0 = |
І—1 |
|
оо |
|
2 |
та(0 < °°- |
і= 1 |
|
Процедура (9.13) для заданного начального условия а = = а нач определяет случайный процесс. Реализации этого случайного процесса индуцируются последователь ностями точек zx, . . ., zn, . . ., которые появляются неза висимо в соответствии с распределением Р (z). Распре деление же Р (z) таково, что для любого а существует
R ( а ) = |
§ (z . а)dP (z ) = |
{<? (2 . а )} |
и |
|
|
D (а) = $ I Ѵо<? (2, а) I2 ^ (2) = |
Мг(| Ѵ0<? (z, а) |®}. |
|
Справедлива |
теорема |
[44]): Если: |
Теорема 9.1. |
(Б. М. Литваков |
|
1)функционал R (а) ограничен снизу,
2)функция D (а) ограничена сверху, т. е. D (а) ^ D,
3)дисперсия помехи % ограничена сверху, т. е. D (%) D , то при любом начальном векторе а н;1Ч последователь
ность R [ а ( і ) ] —> i n f |
R (а) с вероятностью 1 . |
і —*оо а |
теоремы опирается на _ .следующие |
Доказательство |
леммы.
Лемма 1. Для любых N и б > 0 можно подобрать такое г > 0, чтобы вероятность того, что вектор а (N) ока жется внутри гипершара Gn с центром в а нач и радиусом г, была больше 1 — б.
Д о к а з а т е л ь с т в о . Покажем сначала, что для любого і существует ограниченная величина Г (г) =
Ü92 ГЛ. IX . О СХОДИМОСТИ РЕК У РРЕН ТН Ы Х а л г о р и т м о в
*=М{(а (г) — а нач)2} *). Согласно процедуре (9.13) спра ведливо равенство
М {(а (і) — а нач)2} = М {(а (і — 1) — а нач)2} — 2у (і) х
X М {((а (і - 1 ) - |
а Нач ), (Ѵ0 Q (zit |
а (г - |
1 )) + |
5 , ) ) } + |
|
+ V2 (ОМ { |
I Vo Q (z;, |
(i |
1)) + |
U I 2}. |
(9.14) |
Увеличим правую часть этого равенства. Согласно условию |
||||||||||
теоремы |
|
|
|
a |
- |
|
|
|
|
|
М {I I a, |
z } = |
О, |
|
|
|
|
||||
|
|
|
|
|
|
|||||
|
|
М {[Ѵ0<?А, |
а (і — I))]2} < |
D, |
|
|
||||
|
|
М {£2 [ а (г — 1), |
|
|
|
|
|
|||
|
Поэтому у2 (i)M |
{[Ѵ0 Q {zu а (i — 1)) + |
g{]2} < |
2y2 (i) D. |
||||||
Кроме того, |
используя |
то, |
что |
для выпуклой |
функции |
|||||
и любых z, |
а х и а 2 справедливо неравенство |
|
|
|||||||
|
((«і — а 2), Ѵ0 Q (z, |
«!)) > Q (z, |
а х) — Q (z, |
а 2), |
||||||
оценим величину |
М {((а (г — 1) — а нач), |
Ѵ0 Q (z, |
a (i — |
|||||||
|
|
|
|
|
|
|
|
|
- |
1)))}: |
М {((а (г — 1) — а нач), |
Vo Q (z, |
a |
(i — 1)))} > |
|
|
|||||
> М {<? (г, |
а (і — |
1))} — M{Q (z, а нач)} = |
|
|
||||||
|
|
= |
Л (а (і — 1)) —Л (анач) |
А |
Л (аНач), |
|||||
где |
А — inf Л (а). |
|
|
|
|
|
а) |
|||
|
а |
|
|
|
|
|
|
|
|
|
|
Таким образом, оказывается справедливым неравенство |
|||||||||
М {(а (г) — а нач)2} < М {[а (г — 1) — а нач]2} + с (г), |
(9.15) |
|||||||||
где |
с (і) = |
2у (г) (Л (ана,,) — А) |
+ 2Dy2 (і). |
что |
||||||
|
Используя неравенство |
(9.15) и учитывая, |
||||||||
|
|
М {(а (1) — а нач)2} |
= |
с (1), |
|
|
|
|||
непосредственно получаем, |
что |
N |
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
М {(а(7Ѵ )-анач)2} < |
2 |
с (і) = |
Г№, |
|
|
||||
|
|
|
|
|
|
г = і |
|
|
|
|
т. е. величина М {(а (N ) — а нач)2} ограничена числом Tjv.
*) Для сокращения записи здесь и дальше используются обод, начения а2 := (а* в),
§ 4. УСЛОВИЯ СХОДИМОСТИ |
193 |
Для доказательства леммы воспользуемся неравен ством Чебышева для нецентрированных случайных ве личин
Р ( |а ( Л 0 - а нач|> г ) < М {[ а (N) — «нач I2}
г2
Усилим это неравенство; учитывая, что
М {| а (N) — анач I2} < TN,
получим
Р ( |а ( У ) - а нач |> г ) < - ^ - .
Потребуем, чтобы эта вероятность не превосходила б. Это произойдет, если величины г, TN, б будут связаны соотношением
£jv
г2
откуда следует, что с вероятностью, превышающей 1 — б, точка а (N ) будет находиться внутри гипершара G с цен тром в а нач и радиусом
Лемма 1 доказана.
Пусть, далее,
А = inf R (а).
а
Обозначим через Gz область значений а:
Gt = {a: R ( а ) < А + е}.
Лемма 2. |
Для |
любых |
г |
0 и N последовательность |
||
а х, . . ., a N, |
. . |
., |
а г, . . . |
с вероятностью 1 жотгеьраз вой |
||
дет в область |
Gz при і ^ |
N. |
|
|||
Утверждение леммы 2 эквивалентно такому: вероят |
||||||
ность того, |
что |
подпоследовательность а#, . . ., |
a t ни |
|||
разу не заходит в область Gt, стремится к нулю при і |
оо. |
|||||
Д о к а з а т е л ь с т в о . |
Для доказательства |
удоб |
||||
но рассмотреть процедуру, отличающуюся от (9.13)
только |
тем, что |
если |
последовательность при г |
N |
входит |
в область |
Gt, |
то она там и остается. |
|
7 В. Н. Вапник, А. Я. Червонешшс
194 ГЛ. |
IX . |
О СХОДИМОСТИ |
РЕ К У РРЕ Н Т Н Ы Х |
АЛГОРИТМОВ |
|
Для |
этого будем считать, что соотношение |
|
|||
а (г) = а (г — 1) — у |
(і) [Ѵ0 Q (z, а (і — 1)) + У |
|
|||
выполняется всегда при і |
N + 1, а при і !> N + |
1 — |
|||
лишь для |
а (і — 1) ф Gt . В случае же, |
когда при |
і ^ |
||
> N + |
1 |
элемент а (і — 1) принадлежит |
бге, последова |
||
тельность |
«залипает», т. е. |
|
|
||
|
|
а (і) = а (і — 1). |
|
|
|
Очевидно, что если последовательность а (1), ..., а (N), ...
..., а(і), построенная в силу исходного алгоритмами разу не заходит в Gt при і > N , то последовательность, постро енная по новому правилу, ничем не отличается от исход ной и, в частности, не заходит в GEпри і ^ N. Поэтому достаточно оценить вероятность того, что новая последо вательность ни разу не войдет в Gt при і > N.
Вобласти Gt выберем точку а*, для которой і?(а‘) < Л + |
(это всегда можно сделать), и оценим величину М {(а (г)—
— а*)3} для процедуры
а (і) |
'а(і — 1), если |
і > N + 1 и |
а ( і - 1 ) е С і , |
|
||
а (і - |
1) - |
Г (і) [ Ѵ0Q (zu а (і - |
1)) + У |
(9.16) |
||
|
|
|
|
в противном случае. |
|
|
Согласно |
этой |
процедуре при |
а (і — 1) ф. Gt |
|||
М ((а (і) — а*)2 I а (і |
— 1)} =tf(а (г — 1) — а*)2 — |
|||||
—2у |
(і) [М {Ѵ0<2 (z, os |
(i — 1)) I а (i — 1)}, (а (і — 1) — |
||||
— а*)] — 2у (і) [М {It |
I а (і — 1)}, (а (і — 1) — а*)] + |
|||||
|
+ у2 (і) М {І2 -f |
[Ѵ0 Q (z, а (і — I))]31а (і |
— 1)}. |
|||
В |
силу условий теоремы |
|
|
|||
|
|
|
|
М { I t I а} = |
О, |
|
атакже
М{ІѴ0 Q (z, а)]2} < Л и М { ? 2 | а } < 0 .
|
|
|
§ 4. |
УСЛОВИЯ |
СХОДИМОСТИ |
|
|
195 |
|||||
Поэтому |
справедливо |
неравенство |
|
|
|
|
|||||||
М {(а (і) — а*)2 |
I а |
(і — 1)} ^ f( a |
(i — 1) — а*)2— |
|
|||||||||
—2у (t) (М {V0 |
(z, |
а (i — 1))}, |
(а (i |
— 1) — а*)) + |
|||||||||
|
|
|
|
|
|
|
|
|
|
+ |
2у2 (i) D. |
(9.17) |
|
Далее, поскольку функция Q (z, а (і — 1)) выпукла, то |
|||||||||||||
(Vo Q (z, а |
(і — 1)), (а (і — 1) — а*)) > |
Q (z, а (і — 1)) — |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
— Q (z, а*) |
||
и поэтому |
|
|
|
|
|
|
|
|
|
|
|
|
|
(М {Ѵ0 Q (z, |
а (і — 1)) I а ( і— 1)}, |
(а (і — 1 )— |
а*)) > |
||||||||||
|
|
|
|
|
> Л (а (і - |
1)) - |
Л (а*). |
|
(9.18) |
||||
Но точки а (і — 1) и а* |
выбраны так, что |
|
|
||||||||||
|
|
|
Л (а (і — 1)) |
А + |
е |
|
|
|
|||||
(поскольку |
а (і — 1) ф. Gt) |
и |
|
|
|
|
|
|
|||||
|
|
|
|
Л (а*)< Л + |
! |
|
|
|
|
|
|||
и, следовательно, |
|
|
|
|
|
|
|
|
|
|
|||
|
|
Л ( а ( і - 1 ) ) - Л ( а ‘) > |
I |
. |
|
(9.19) |
|||||||
Объединяя (9.17), |
(9.18) |
и (9.19), |
получаем, |
что при |
|||||||||
а (і — 1) |
|
Gt |
|
|
|
|
|
|
|
|
|
|
|
М {(а (і) - |
|
а*)2 |
I а (г - |
1)} |
|
(г - |
1) - а*)2 - |
|
|||||
|
|
|
|
|
|
|
|
|
— У (0 е + 2у2 (і) D. |
||||
Если же |
при і |
|
N |
+ |
1 элемент |
а |
(і |
— 1) ЕЕ Ge, |
то |
||||
М {(а (і) — а*)2 I а (і |
— 1)} = (а (і |
— 1) — а*)2. |
|
||||||||||
Пусть |
бг — вероятность |
того, |
что |
а (і — 1) ф Gz. |
|||||||||
Тогда, переходя к безусловному математическому ожида нию, получим для і > N + 1
М{(а (і) — а*)2} ^ М {(а (і — 1) — а*)2} — s8,y (і) +
+2Т2 (і) D.
7*
