Распознавание образов: § 4. Условия сходимости рекуррентных алгоритмов

§ 4. Условия сходимости рекуррентных алгоритмов

Итак, пусть задана выпуклая по при любом фиксированном функция потерь и определена процедура получения последовательности :

Рассмотрим несколько более общую, чем в главе IV, процедуру образования последовательности

, (9.13)

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

Будем считать, что величины , образующие бесконечную последовательность неотрицательных чисел, таковы, что

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

Справедлива теорема.

Теорема 9.1. (Б. М. Литваков [441]: Если:

1) функционал ограничен снизу,

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

3) дисперсия помехи ограничена сверху, т. е. , то при любом начальном векторе последовательность с вероятностью 1.

Доказательство теоремы опирается на следующие леммы.

Лемма 1. Для любых и можно подобрать такое , чтобы вероятность того, что вектор окажется внутри гипершара с центром в и радиусом , была больше .

Доказательство. Покажем сначала, что для любого существует ограниченная величина . Согласно процедуре (9.13) справедливо равенство

(9.14)

Увеличим правую часть этого равенства. Согласно условию теоремы

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

оценим величину :

где .

Таким образом, оказывается справедливым неравенство

, (9.15)

где .

Используя неравенство (9.15) и учитывая, что

непосредственно получаем, что

т. е. величина ограничена числом .

Для доказательства леммы воспользуемся неравенством Чебышева для нецентрированных случайных величин

Усилим это неравенство; учитывая, что

получим

Потребуем, чтобы эта вероятность не превосходила . Это произойдет, если величины , , будут связаны соотношением

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

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

Пусть, далее,

Обозначим через область значений :

Лемма 2. Для любых и последовательность с вероятностью 1 хоть раз войдет в область при .

Утверждение леммы 2 эквивалентно такому: вероятность того, что подпоследовательность ни разу не заходит в область стремится к нулю при .

Доказательство. Для доказательства удобно рассмотреть процедуру, отличающуюся от (9.13) только тем, что если последовательность при входит в область , то она там и остается.

Для этого будем считать, что соотношение

выполняется всегда при , а при – лишь для . В случае же, когда при элемент принадлежит , последовательность «залипает», т. е.

Очевидно, что если последовательность , построенная в силу исходного алгоритма, ни разу не заходит в при , то последовательность, построенная по новому правилу, ничем не отличается от исходной и, в частности, не заходит в при . Поэтому достаточно оценить вероятность того, что новая последовательность ни разу не войдет в при .

В области выберем точку , для которой

(это всегда можно сделать), и оценим величину для процедуры

(9.16)

Согласно этой процедуре при

В силу условий теоремы

а также

и .

Поэтому справедливо неравенство

(9.17)

Далее, поскольку функция выпукла, то

и поэтому

. (9.18)

Но точки и выбраны так, что

(поскольку ) и

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

. (9.19)

Объединяя (9.17), (9.18) и (9.19), получаем, что при

Если же при элемент , то

Пусть – вероятность того, что . Тогда, переходя к безусловному математическому ожиданию, получим для

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

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

ограничена, и по условию теоремы ряд сходится. Поэтому

, (9-20)

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

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

Если бы при этом оставалась больше некоторого , то величина

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

а ряд расходится.

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

Остается отметить, что последовательность организована процедурой (9.16) так, что если она хоть раз войдет в при , то она там и останется к моменту . Следовательно, вероятность того, что последовательность ни разу не заходит в , равна и стремится к нулю при .

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

Лемма 3. Для любых и существует такое , что при всех вероятность последовательности выйти из области

при условии , меньше .

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

(9.21)

Очевидно, что величина равна вероятности того, что при условии , если, начиная с , действует процедура (9.21).

Обозначим через точку множества , ближайшую к , и оценим величину

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

Поэтому при в силу процедуры (9.21)

В силу выпуклости справедливо неравенство

Но при элементы и совпадают, а при

Поэтому

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

Если же при , то

Таким образом, всегда

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

(9.22)

поскольку при имеет место

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

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

и для всякой точки – неравенство

то

. (9.23)

Поэтому

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

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

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

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

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

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

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

Далее, в силу леммы 2 последовательность с вероятностью 1 хоть раз войдет в после момента и, следовательно, выйдет из с вероятностью, меньшей . Ввиду произвольности и это означает, что

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

Теорема доказана.