8. Интуитивные основы стохастической аппроксимации

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

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

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

приближений. При этом последнем значении аргумента функция равна нулю. Предполагается, что алгоритм итерационной процедуры ограничен такими условиями, что в среднем за одну итерацию значение этой функции убывает. Причем соответствующие приращения стремятся к нулю с возрастанием номера итерации, но стремятся не очень быстро. А именно так, что если аргумент остается вне некоторой окрестности точки минимума функции, то ряд из средних величин приращения функции за одну итерацию расходится. Из последнего условия вытекает, что итерационная последовательность, порождаемая алгоритмом, с вероятностью единица не может оставаться все время вне некоторой окрестности минимума функции и, значит, попадает для итераций со сколь угодно большим номером в произвольную окрестность этого минимума. Стремление приращения к нулю приводит к тому, что, оказавшись в достаточно малой окрестности точки минимума, итерационная последовательность с вероятностью, близкой к единице, останется в малой окрестности этой точки. В случае «неединственности» роль, аналогичную роли описанной выше функции, играет функция, равная нулю на требуемом множестве и положительная всюду вне его.

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