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

196 ГЛ. IX. О СХОДИМОСТИ РЕКУРРЕНТНЫХ АЛГОРИТМОВ

Из этого рекуррентного соотношения, очевидно, сле­

Всилу леммы 1 величина

М( а (N ) — а * )2

где с — константа, не зависящая от г.

Далее, поскольку процедура (9.16) организована так, что, попав в Ge, последовательность «залипает», вероят­ ность 6і не возрастает с ростом і.

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

неравенства (9.20) становилась бы отрицательной при достаточно больших £, тогда как левая часть положитель­

менту і. Следовательно, вероятность того, что последо­

при условии а (N ) 6= Gt, меньше б.

Д о к а з а т е л ь с т в о . Оценим вероятность б* того, что в последовательности aN, . . ., а, хотя бы один эле­

Очевидно, что величина б* равна вероятности того, что ссі ZjÉ G2s при условии ajy £Е Ge, если, начиная с i = = N + 1, действует процедура (9.21).

Обозначим через а£ (£) точку множества Ge, ближай­ шую к а (г), и оценим величину

М {(а (і) — а е (і))2}.

Очевидно, справедливо неравенство

(а (і) — а е (г))2 < [а (г) — а е (г — I)]2.

Поэтому при а (г — 1) е G2e в силу процедуры (9.21)

198 гл . IX . О СХОДИМОСТИ РЕ К У РРЕ Н Т Н Ы Х АЛГОРИТМОВ

(а (N) - а £ (ІѴ))2 = 0.

Далее, оценим расстояние Л между произвольным эле­ ментом а ф С2е и множеством G£, т. е. ширину зоны, которую должна пройти точка а (£), чтобы из Gt уйти за пределы G2£. Так как функция R (а) выпукла,

Ѵ0Я ( а) = М (I Ѵ0 Q(z, а) |} < / Я ,

для всякой точки a g C j выполняется неравенство

R (а) А + е

и для всякой точки а ф Ga — неравенство

R (а) > А + 2в,

Воспользуемся неравенством Чебышева

^{|« (0 — « е (0|> Л |а (ЛГ )еС ,> <

М{(а(0-«е(і))*|а(Л0еСІ}

Ч---------------- Л2----------------

Учитывая далее (9.22) и (9.23), получаем

2 Т- (О-

i = N + l

Правая часть неравенства не зависит от і, поэтому, выбрав N достаточно большим, можно добиться, чтобы бг было меньше б при всех і N, а это и значит, что последова­ тельность выходит из бг2е с вероятностью, меньшей б.

Лемма доказана.

Докажем теперь теорему 9.1.

Для заданных е и б подберем N x так, чтобы для всякого N N-l вероятность последовательности выйти за пре­ делы области

G2t = {а: R (а) < А + 2е}

при условии, что а (N ) ge Gz, была меньше б. Это можно сделать в силу леммы 3.

Далее, в силу леммы 2 последовательность а (1),...

. . ., а (N), . . . с вероятностью 1 хоть раз войдет в G, после момента N x и, следовательно, выйдет из G2t с ве­ роятностью, меньшей б. Ввиду произвольности б и е это означает, что

R (а (і)) — ^ inf R (а)

І-КЯ а

свероятностью единица.

Теорема доказаңа,