§ 4. Условия сходимости процедуры Роббинса — Монро метода стохастической аппроксимации

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

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

Приводимые ниже теоремы VII—XI обобщают и дополняют известные теоремы Дж. Блума [9] и Е. Г. Гладышева [10] метода стохастической аппроксимации.

Теорема VII, так же как и теоремы Блума и Гладышева, требует, чтобы решение уравнений регрессии (86) было единственным. Теоремы VIII—XI не требуют единственности решения уравнений регрессии. Во всех доказываемых ниже теоремах, кроме теоремы XI, предполагается, что фигурирующая в (4) последовательность удовлетворяет обычным для процедуры Роббинса — Монро ограничениям:

Теорема XI позволяет ослабить эти ограничения, заменив их условиями (5), (66):

Введем в рассмотрение неотрицательную дважды непрерывно дифференцируемую функцию векторного

аргумента и рассмотрим также функции

Во всех теоремах настоящего параграфа предполагается, что функции существуют и что выполнено следующее условие.

Условие Б. и при любом

где а, Ь, с — некоторые константы.

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

Обратим внимание на некоторые особенности использования теорем предыдущего параграфа при доказательстве теорем VII—XI.

Роль условия Б в теоремах настоящего параграфа заключается в том, что выполнение этого условия гарантирует, что случайные последовательности

в силу рекуррентной процедуры (4) и условия (87) удовлетворяют условию А (см. § 2) с той лишь несущественной разницей, что неравенства (8) в условии А выполняются, начиная с некоторого вообще говоря,

не обязательно равного единице (см. далее формулу (93) при доказательстве теоремы VIII). При этом

и поэтому в силу (87), кроме того,

В теоремах VII—X соотношения (87) предполагаются выполненными, и поэтому в условиях этих теорем оказывается выполненным условие А, дополненное соотношением (89).

В связи с этим в условиях теорем VII—X выполнено условие 1° теорем I—III из § 3.

В теореме XI, в которой требование (87) заменяется более слабым требованием (88), из условия Б также следует условие А, но для установления этого факта приходится использовать дополнительное ограничение (условие 2° теоремы XI). При этом (см. формулу (99) при доказательстве теоремы XI)

и в силу (88) выполнено условие 1° теоремы V § 3.

Для того, чтобы можно было использовать теоремы § 3, надо еще обеспечить выполнение остальных условий этих теорем. Кроме того, надо гарантиропать, что из факта стремления или к нулю (а этот факт и устанавливается теоремами § 3) следует сходимость случайной последовательности к решению системы уравнений (86). Этим целям и служат остальные условия теорем VII—XI этого параграфа.

Теорема VII. Пусть случайный процесс, определяемый соотношениями (4) и (87), а у — решение уравнений (86). Пусть, далее, функция удовлетворяет условиям:

1°. Условию

2°. для любого

3°. для любого

Тогда при случайный вектор стремится к у почти наверное:

Если функция бесконечно большая, т. е.

то утверждение (90) имеет место и в случае, когда условие 3° заменяется более слабым условием

3а°. для любых

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

Теорема VII позволяет устанавливать сходимость процедуры Роббинса — Монро лишь в том случае, когда решение системы уравнений (86) единственно. Требование единственности решения системы уравнений регрессии отражено в условиях 2° и 3° (или теоремы VII.

Для того чтобы сформулировать теорему VIII, обозначим через У множество решений системы уравнений (86) и будем говорить, что стремится к У при по вероятности (или почти наверное)

если

Теорема VIII. Пусть -случайный процесс, определяемый соотношениями (4) и (87). Пусть, далее, функция удовлетворяет условиям:

1°. Условию Б.

2°. для любого

3°. Для каждой последовательности на которой одновременно и

Тогда при случайный вектор стремится к почти наверное:

Если же функция бесконечно большая, то условия 2° и 3° могут быть заменены более слабыми условиями:

2а°. Функция может обращаться в нуль лишь в точках из У.

За°. Для каждой ограниченной последовательности, на которой одновременно й

Прежде чём перейти к доказательству теоремы VIII, сформулируем и докажем лемму III, которая нам понадобится также для доказательства теорем IX и

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

то

Доказательство леммы III. Докажем, например, что из следует Соответствующее доказательство для случая проводится совершенно аналогично.

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

Выберем последовательность такую что и рассмотрим последовательность точек Поскольку эта последовательность ограничена, из

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

Эти соотношения противоречат определению множества У: в силу этого определения у должно принадлежать У и, следовательно, должно быть выполненным соотношение Тем самым доказано существование функции Для завершения доказательства покажем, что утверждение леммы III следует из существования функции и из факта ограниченности почти всех реализаций случайного процесса

Утверждение леммы означает, что для любых найдется такой номер что вероятность множества реализаций, для которых при всех

больше, чем Чтобы найти и тем самым доказать лемму, поступим следующим образом. Для заданного найдем такое С (6/2), что на множестве реализаций вероятности большей, чем выполнено условие

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

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

имеет вероятность, не меньшую, чем В силу произвольности это означает, что

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

Доказательство теоремы VIII. Доказательство этой теоремы опирается на теоремы III и § 3. Покажем сначала, что при выполнении условий 1° и 3° теоремы VIII функции

удовлетворяют условиям теоремы III § 3, а в случае, если бесконечно большая функция и выполнены условия 1° и удовлетворяют условиям теоремы § 3.

Действительно, в силу рекуррентной процедуры (4) имеем

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

где Переходя к математическому ожиданию по получим

и поэтому в силу условия Б

В силу условий (87) соотношение (93) влечет за собой выполнение условия 1° теоремы III § 3, начиная с такого

что при пп. Условие же 2° теоремы III выполнено, поскольку оно совпадает с условием 3° теоремы VIII. Поэтому при выполнении условий 1° и 3° теоремы VIII в силу теоремы III § 3 при

Условие 2° гарантирует при этом, что

Таким образом, первая часть теоремы VIII доказана. Если же бесконечно большая функция, то условие 1° теоремы § 3 также выполнено в силу (93), а условие теоремы VIII гарантирует выполнение условия 2° теоремы § 3. Условие 3° теоремы следует из того, что последовательность бесконечно большая, поскольку функция бесконечно большая. Тем самым в силу теоремы устанавливается справедливость (94) и в этом случае. Кроме того, при доказательстве теоремы было установлено, что в условиях этой теоремы почти все реализации случайного процесса ограничены. Этот факт, соотношение (94) и условие 2а° теоремы VIII составляют в совокупности условия леммы III, если отождествить с функцией фигурирующей в лемме III. Поэтому из утверждения леммы III следует утверждение теоремы VIII. Теорема доказана полностью.

Покажем, каким образом из теоремы VIII может быть получена теорема VII. Из условия 2° теоремы VII. непосредственно следует условие 2° теоремы VIII. Выполнение, условия 3° теоремы VIII гарантируется тем, что при выполнении условия 3° теоремы VII из следует а следовательно, в силу непрерывности и в силу условия 2° теоремы VII имеет место Условия же 1° теорем VII и VIII совпадают. Тем самым первая часть теоремы VII доказана. Аналогичными рассуждениями устанавливается вторая часть теоремы VII, когда функция бесконечно большая.

В случае неединственности решения системы уравнений (86) могут оказаться полезными следующие

теоремы IX и Теорема IX устанавливает условия сходимости по вероятности, а теорема X — условия сходимости почти наверное.

Теорема IX. Пусть случайный процесс, определяемый соотношениями (4) и (87), Пусть, далее, функции удовлетворяют условиям

1°. Условию Б.

2°. бесконечно большая функция.

3°. Функция непрерывно дифференцируема и может обращаться в нуль лишь в точках из У.

4°. Функция

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

Тогда при случайный вектор стремится к У по вероятности:

Доказательство теоремы IX. Докажем сначала, что воспользовавшись с этой целью теоремой 1а § 3.

Заметим, что, как показано при доказательстве теоремы VIII (см. формулу (93) и следующий за ней текст), условие 1° теоремы III § 3 следует лишь из условия Б и соотношений (4) и (87). Но условие Б и соотношения (4) и (87) выполнены и в теореме IX, а первые условия теорем III и 1а совпадают. Поэтому условие 1° теоремы 1а выполнено.

Проверим выполнение условия 2° теоремы 1а. Для этого, воспользовавшись соотношением (4), применим формулу Тейлора к функции

Переходя в (95) к математическому ожиданию по и воспользовавшись условием 4° теоремы IX, убеждаемся, что условие 2° теоремы 1а выполнено, если положить

Наконец, условие 3° теоремы 1а следует из условия 2° теоремы IX. Тем самым все условия теоремы 1а выполнены, и поэтому

Кроме того, заметим, что, как было показано при доказательстве теоремы 1а, реализации случайного процесса ограничены почти наверное. Условие (96), ограниченность почти всех реализаций случайного процесса и условие 3° теоремы IX составляют в совокупности условия леммы III, если положить В силу утверждения леммы III имеет место

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

Теорема X, устанавливающая условия сходимости почти наверное, отличается от теоремы IX лишь условием 4°. Это условие 4° и позволяет доказать сходимость процедуры (4) не только по вероятности, но и почти наверное.

Теорема Пусть случайный процесс, определяемый соотношениями (4) и (87). Пусть, далее, функции удовлетворяют условиям теоремы IX и, кроме того, условию

4°. Функции

существуют и ограничены в любой ограниченной области изменения переменной

Тогда при случайный вектор стремится к почти наверное:

Доказательство теоремы Доказательство теоремы X совершенно аналогично доказательству теоремы IX с тем лишь отличием, что всюду вместо

сходимости по вероятности устанавливается сходимость почти наверное, и с этой целью используется не теорема 1а, а теорема На из § 3.

Для доказательства того факта, что

нужно проверить выполнение условий теоремы IIа. Условие 1° теоремы На совпадает с уже проверенным при доказательстве теоремы VIII соответствующим условием теоремы III (это устанавливается лишь с использованием условия 1° теоремы VIII, которое совпадает с условием 1° доказываемой теоремы). Условие 2° теоремы IIа следует из (95) и из условия 4° теоремы Действительно, из (95) следует

где

Функция ограничена при любых ограниченны у в силу условия 4° теоремы X и непрерывности частных производных Поэтому соотношение (98) гарантирует выполнение условия 2° теоремы IIа. Условие же 3° теоремы На следует из того, что функция бесконечно большая.

Поскольку все три условия теоремы IIа выполнены, в силу утверждения этой теоремы справедливо соотношение (97). Кроме того, как было доказано при доказательстве теоремы IIа, почти все реализации случайного процесса ограничены. Условие (97), ограниченность почти всех реализаций случайного процесса и условие 3° доказываемой теоремы составляют в совокупности условия леммы III, если положить В силу утверждения леммы III

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

Условие 4° теоремы X является в приложениях весьма ограничительным. Например, если пытаться использовать эту теорему для доказательства сходимости процедуры восстановления неизвестной функции (см. гл. VI), то это условие означало бы, что ошибка измерения значения функции должна быть ограничена. В следующем параграфе будет приведена приспособленная к особенностям метода потенциальных функций теорема, не обладающая этим недостатком.

Докажем теперь теорему XI, которая отличается от других теорем этого параграфа тем, что вместо условия (87) на выбор последовательности в ней фигурирует условие (88).

Теорема XI. Пусть случайный процесс, определяемый соотношениями (4) и (88). Пусть, далее, функции удовлетворяют условиям:

1°. Условию Б.

2°. Условию 2° теоремы где некоторая константа.

Тогда при случайный вектор стремится к У по вероятности: .

Условие 3° теоремы XI, очевидно, является существенно более сильным, нежели соответствующее условие теоремы VIII. Именно благодаря усилению этого условия оказывается возможным отказаться от требования (87), заменив его более слабым требованием (88). Однако при этом сходимость случайного процесса доказывается не почти наверное, а лишь по вероятности.

Несмотря на то, что условие 3° теоремы XI является жестким, в приложениях это условие часто выполняется. В качестве примера можно привести процедуру Роббинса—Монро для определения среднего значения случайной величины х. При этом

И, положив

имеем и из теоремы XI заключаем, что если последовательность удовлетворяет требованиям (88).

Условие 3° теоремы XI выполняется также при использовании метода потенциальных функций в некоторых задачах обучения (см. гл. VI и VII).

В случае единственности решения системы уравнений (86) условие 2° теоремы XI может быть заменено более просто проверяемым условием 2° теоремы VII, поскольку в случае единственности из условия 2° теоремы VII следует условие 2° теоремы VIII (см. текст, следующий за доказательством теоремы VIII).

Доказательство теоремы XI. Докажем, что воспользовавшись с этой целью теоремой V § 3.

Заметим, что формула (93) получена лишь с помощью условия Б и поэтому имеет место и в условиях теоремы XI. В силу условия 3° теоремы XI из (93) следует

В силу условий (88) соотношение (99) влечет за собой выполнение условия 1° теоремы V, начиная с такого что при имеет место Условие же 2° теоремы V совпадает с условием 3° теоремы XI. Поэтому в силу теоремы V

Утверждение теоремы XI следует из условия 2° и соотношения (100). Теорема XI доказана.