§ 5. Процедура Роббинса — Монро метода стохастической аппроксимации и процедура метода потенциальных функций

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

в которой неизвестными являются компоненты вектора с. Если функции и распределение вероятностей случайной величины х известны, то в системе (38) левые части полностью определены.

Предположим теперь, что распределение вероятности случайной величины х заранее не известно, и, следовательно, левые части уравнений (38) не могут быть явно вычислены. Пусть, однако, в последовательные моменты времени появляются точки в соответствии с этим распределением вероятностей, и при любом с могут быть вычислены величины Для этого случая Г. Роббинс и С. Монро [4] предложили следующую рекуррентную процедуру последовательных приближений, позволяющую шаг за шагом приближаться к решению системы уравнений (38):

Роббинс и Монро предполагали, что в процедуре последовательность неотрицательных чисел, удовлетворяющих условию (13) и

Было показано, что при некоторых ограничениях, накладываемых на вид функций процедура (39), (40) сходится, т. е. в вероятностном смысле сходятся к корням системы уравнений (38). Вопрос о сходимости процедуры вида (39) будет подробно рассмотрен в главе IV. В настоящем же параграфе мы не будем оговаривать тех ограничений, которым должны удовлетворять функции и не будем стеснять себя условием (40), а обсудим соотношение процедуры (39) и процедуры (!), (!!) метода потенциальных функций.

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

зависит (и притом специальным образом) лишь «стягивающий множитель» Поэтому далее с процедурой Роббинсам-Монро сравнивается не общая процедура а специальный вид (11), (12) этой процедуры.

Если ограничиться случаем, когда размерность вектора с конечна, то непосредственно видно, что процедура (12) может быть рассмотрена как процедура Роббинса-Монро (39), приспособленная для решения следующей системы уравнений регрессии

Если считать, что математическое ожидание помехи равно нулю при каждом фиксированном х, система (41) принимает вид

Обратим внимание на то, что искомые параметры входят в уравнения регрессии (41) и (42) весьма специальным образом. Тем самым процедура (12) метода потенциальных функций выделяет специфический подкласс (41) и (42) уравнений регрессии и соответствующий специфический подкласс процедур Роббинса-Монро. Такие процедуры обладают рядом специальных свойств, благодаря которым они могут быть изучены более подробно, нежели процедуры Роббинса-Монро общего вида. Рассмотрим некоторые из этих свойств.

1. Возможность машинной реализации процедуры. В § 2 процедура (12) была получена из (11) в предположении, что выстраиваемые процедурой (11) функции могут быть представлены рядом (9). Разумеется, всегда возможен и обратный переход от соотношения (12) к соотношению (11). В этом смысле можно сказать, что процедуры Роббинса-Монро вида (12) допускают машинную реализацию (см. § 3). Это

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

Рис. 9.

2. Существование экстремизируемого функционала. Как было указано в § 4, для процедур вида (12) может быть выписан функционал (37), (33), экстремизируемый этой процедурой. В предположении, что вектор конечномерный, процедура (12) может быть представлена в виде стохастической градиентной процедуры (35), а уравнение регрессии (42) приобретает вид

где функция и функционал определяются формулами (34) и (36) соответственно. Разумеется, в общем случае уравнения регрессии (38) не имеют градиентного вида (43). Существование экстремизируемого функционала для процедуры (12) позволяет придать точный смысл решаемой экстраполяционной задаче.

3. Возможность использования функционала для определения понятия сходимости процедуры. Наличие экстремизируемого процедурой (12) функционала позволяет определить для нее понятие сходимости даже в тех случаях, когда уравнения регрессии (43) вообще не имеют решений. Чтобы разъяснить это обстоятельство, рассмотрим случаи, когда в точке минимума функционала производная не

существует (рис. 9, а) и когда имеет точную нижнюю грань, но не имеет точки минимума (рис. 9, б). В случаях подобного рода уравнения регрессии (43) заведомо не имеют решений и поэтому бессмысленно говорить о сходимости процесса Роббинса — Монро к решению уравнений регрессии. Вместе с тем для процедур Роббинса — Монро типа (12) само понятие сходимости может быть определено как стремление при значения функционала к его точной нижней грани. Условия, при которых сходимость в этом смысле имеет место, устанавливаются в § 5 главы IV. Устанавливаемые там критерии исходят лишь из предположения, что функции в уравнениях регрессии (38) и в процедуре Роббинса—Монро (39) имеют «градиентный вид», т. е.

что, вообще говоря, имеет место не только для процедуры (12), но и для процедур Роббинса-Монро более общего вида.