Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

7.2. Методы стохастической аппроксимации. Специфика условий сходимости

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

Процедура Роббинса-Монро

Пусть априори известно, что zи<0 при x<x*, zи>0 при x>x*, zи = 0 при х = х* (рис. 7.1). Характеристики ошибок, искажающих результаты определения z при тех

или иных xi, предполагаются следующими:

- математическое ожидание δzi равно нулю для любого i (i = 1, 2, .. .);

- дисперсия δzi конечна и постоянна при различных i;

- величины δzi, присутствующие в разных экспериментах, независимы и носят аддитивный характер.

Предлагается схема переходов. Xi+1=xi-aizi, где zi - значение z в точке хи найденное экспериментально; аi - член последовательности корректирующих коэффициентов. Требуется дать оценку сходимости процесса, реализуемого в соответствии с этой схемой.

Поскольку zi = zиizi, можно представить Xi+1 как Хi+1 = (xi-aizиi)-aiδzi, откуда следует Yi = xi-aizиi, Ri = -aiδzi. Обращаясь к условиям сходимости процесса в средне-квадратическом, рассмотрим две группы соотношений для Ri и Yi.

Анализ случайной составляющей: из выражения Ri и исходных предпосылок получаем М [Ri] = - aМ [δzi] = 0, D[Ri] = M[Ri2] = a2iD[δzi], где D[δzi] есть дисперсия ошибки, не меняющаяся с изменениями i. Ясно, что требование


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


или


где а0 - некоторая константа; р - показатель степени, выбираемый как p≥0,5.

В рамках этих условий нетрудно получить и


таким образом, проблема фильтрации ошибок решается здесь в принципе просто.

Рис. 7.1
Рис. 7.1

Анализ регулярной составляющей удобно провести применительно к случаям а), б), рассмотренным в § 7.1. 15 8

Модуль разности Yi-х̂ = хi-aizиi-x̂ может быть представлен здесь как

(7.1)

Если сделать те или иные предположения о характере

зависимости zиi от xi (или, что то же, от г), то формула (7.1) позволит оценить, насколько реально выполнение

условия


Пусть, например, существует возможность указать для очередного хi нижнюю границу значений |zиi| т. е. принять |zиi|>ρi. Это значит |Yi-x̂|<|xi-х̂|-аiρi [см. верхнюю строку (7.1)]; слагаемое -aiρi может рассматриваться как поправка -γi (см. 7.1), если только последовательность {аiρi} обладает свойством


Точно так же, допуская |zиi|≤A|хi-х̂|+В, где А и В - некоторые константы, получаем |Yi-x̂|<аiВ+(aiA-1)|xi-x̂| [см. нижнюю строку (7.1)]. Начиная с некоторого номера i, разность

aiA-1 станет отрицательной (с каждым шагом коэффициент ai уменьшается), и тогда последнее неравенство

примет вид |Yi-х̂|<aiB; очевидно,


и величина Yi сходится к x̂.

Таким образом, процедура Роббинса - Монро обеспечивает выполнение условий сходимости, хотя и предъявляет определенные требования к уровню информированности исследователя о свойствах функции zи = f(x).

Все сказанное выше основывается на результатах теоремы Дворецкого (16), приводимой здесь без доказательства: пусть {αi}, {βi}, {γi} - последовательности неотрицательных действительных чисел, такие, что


пусть х̂ - действительное число, a Yi- измеримые преобразования, удовлетворяющие условию |Yi-x̂|≤max{αi, (1 + βi)|xi-х̂|-γi} для всех действительных xi (i = 1,2,...); пусть далее Xi+1 = Yi+Ri, где Ri - действительные случайные величины, причем M[Ri] = 0,


В этих предположениях схема Роббинса-Монро обеспечивает сходимость процесса оптимизации в среднеквадратическом (и по вероятности) к х̂.

Обратимся теперь к анализу еще одного метода стохастической апппроксимации, предназначенного специально для поиска максимума f(x).

Процедура Кифера - Вольфовица

Допустим априори, что функция zи = f(x) унимодальна и имеет экстремум (максимум) в точке х*. Ошибки, искажающие результаты экспериментов, имеют следующие особенности:

- они аддитивны;

- математическое ожидание δzi = 0 для всех i (i = 1, 2, ...);

- дисперсия δzi конечна и постоянна (t = 1, 2, ...);

- случайные величины δzi и δzk (i = k) независимы.

Предлагается схема переходов: Xi+1 = Xi+ai[z(xii) - z (хi-ci)/сi, где z(xi+ci) и z(x+ci)-значения z в точках xi-соответственно; ai и ci-члены последовательностей неотрицательных действительных чисел. Требуется дать анализ сходимости предложенной схемы.

Геометрическая интерпретация рассматриваемых условий дана на рис. 7.2; величина [z(xii) - z(xi-ci)](2ci)-1 определяет приближенно тангенс угла наклона кривой zи = f(x) в точке хi (для этого на каждом шаге проводятся два эксперимента). Таким образом, идея метода заключается в последовательных оценках величин θi с целью выбора направления дальнейшего "движения". Учитывая, что z(xi±ci) = zи(xi±ci) + δz(xi±ci) получаем


Puc. 7.2
Puc. 7.2

Анализ случайной, составляющей: из выражения Ri и исходных предпосылок следует М [Ri] = 0, D [Ri] = 2(ai/ci)2D[δz], где D [δz] - дисперсия ошибки, не зависящая от i. Требование


удовлетворяется при условии


или


где а0, с0 - некоторые константы, p≥0,5; если p≥0,5, то


в случае необходимости можно требовать


не нарушая рассматриваемых соотношений.

Анализ регулярной составляющей: обозначим разность zи(xi+ci)-zи(xi-ci) через (-Δzиi); тогда Yi = -xi-aiΔzиi/ci, следовательно,

(7.2)

Формула (7.2) не отличается по своей структуре от (7.1), поэтому все замечания, сделанные ранее применительно к (7.1) и касающиеся выполнения условия


могут быть перенесены на (7.2) Так, положив


(в верхней строке 7.2) и


(в нижней строке 7.2), приходим к выводу о достаточности всего этого для обеспечения сходимости Yi к х̂.

Закончив исследование условий сходимости конкретных методов стохастической аппроксимации, естественно поставить вопрос: в каком отношении находятся х и х*? Очевидно, ответ может быть один: если все те сведения, которые нужны исследователю для доказательства сходимости, относятся действительно к х*, то х̂ ≡ х*; следовательно, начинать поиск рассматриваемыми методами имеет смысл тогда, когда об х* уже что-то известно.

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"