5.3. ВЕРОЯТНОСТНЫЕ АЛГОРИТМЫ; СТОХАСТИЧЕСКАЯ АППРОКСИМАЦИЯ

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

Фиг. 5.30.

быть использована для решения различных задач, связанных с оптимизацией, адаптацией, настройкой моделей и обучением при наличии шумов [24].

В 1951 г. Роббинс и Монро [19] предложили подход к решению задачи об отыскании корня уравнения регрессии. Рассматривается условная плотность вероятности или условная функция распределения и предполагается, что:

а) существует функция регрессии

б) уравнение имеет единственное решение Последнее условие означает, что монотонная функция.

Корень уравнения предлагается искать с помощью следующего рекуррентного алгоритма:

где оценка на шаге, наблюдение искажено аддитивным случайпьш шумом (фиг. 5.30), а последовательность действительных чисел, свойства которой будут определены ниже. Эта последовательность должна быть выбрана так, чтобы сходились по вероятности к 6, т. е. для всех

Из этого условия вытекают следующие ограничения. Рассмотрим выражение совместно с уравнением (5.50). Вычислим математическое ожидание

или

где

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

или

При условии, что конечна и

находим, что

Если выбрано так, что

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

Разлагая в ряд в окрестности находим, что

или

Подстановка в уравнение (5.57) дает

или

Условиям (5.55), (5.55а) и (5.56) удовлетворяет, например, последовательность при

Как уже отмечалось, первоначально этот метод был предложен для решения уравпений с монотонной функцией в левой части. Затем Кифер и Вольфовиц [12] применили этот метод для отыскания экстремума функции регрессии. Так как функция регрессии не известна, ее производная оценивается по формуле

При этом преобразовании четная функция заменяется на нечетную (см. гл. 2). Алгоритм определения точки минимума имеет вид

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

следующим образом. Необходимо максимизировать (минимизировать) по функцию

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

В этом случае алгоритм вычисления х имеет вид

Выбор определяет итеративный метод. Если выполнены условия сходимости, то

Если не известпа, то градиент можно оцепить по формуле

базис, небольшое вещественное число, которое может зависеть от номера итерации и от компонент вектора

Если, кроме того, случайная и задана функция распределения где случайный вектор, то лучшее, чего можно в этом случае добиться, — это максимизировать (минимизировать) математическое ожидание

Тогда есть корень уравнения

который определяется по следующему алгоритму:

Если заранее не известны, то, используя вместо градиента его оценку, получаем

Здесь т. е.

если

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

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

Для нижнего уровня шума сходимость к истинному значению показана на фиг. 5.31. Выбор приводит к истинному значению за один шаг; при имеет место движение осцилляторного типа; выбор обеспечивает сходимость за два шага. На фиг. для верхнего уровня шума при соответственно показаны итерации при оценке х для двух разных последовательностей (сплошная и

(кликните для просмотра скана)

(кликните для просмотра скана)

(кликните для просмотра скана)

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

Некоторые из этих алгоритмов могут быть сделаны непрерывными. Детерминированный вариант:

В стохастическом случае алгоритм имеет вид

Более обширную информацию о теории и приложениях стохастической аппроксимации можно почерпнуть из нескольких хороших обзоров (см., например, [1, 24]), а приложения описаны в работах [6, 10, 17, 21—23].

ЛИТЕРАТУРА

(см. скан)

(см. скан)

ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА

(см. скан)

(см. скан)

(см. скан)