Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов




Скачать 389.32 Kb.
НазваниеМатематико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов
страница2/6
Дата17.04.2013
Размер389.32 Kb.
ТипЗадача
1   2   3   4   5   6

Глава 1. Рандомизированные алгоритмы стохастической аппроксимации


Развитие методов стохастической аппроксимации (СА) началось в пятидесятые годы ХХ в. с алгоритма Роббинса-Монро [13] и процедуры Кифера-Вольфовица (КВ) [14].

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



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

,

где n} и n} - некоторые заданные убывающие числовые последовательности с определенными свойствами.


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



математическое ожидание при малом β близко к значению производной функции



Поведение последовательности оценок, доставляемых алгоритмом стохастической аппроксимации, зависит от выбора наблюдаемых функций-статистик g(x,β). В ряде практических приложений бывает недостаточно информации относительно статистических свойств ошибок измерения, или они могут просто задаваться неизвестной экспериментатору детерминированной функцией. Это ведет к существенным трудностям в обосновании применимости обычной процедуры Кифера--Вольфовица, и часто ее оценки не сходятся к искомой точке. Hо это не означает, что, решая такие проблемы, надо вообще отказаться от использования достаточно простых в представлении алгоритмов стохастической аппроксимации. Выше в примере уже предлагалось использовать ``другие'' наблюдения. Если удачно заменить статистику g(x,β) на другую, которая ``в среднем'' лучше аппроксимирует производную функции , то можно надеяться на получение лучшего качества поведения последовательности оценок.

Предположим, что функция дважды непрерывно дифференцируема и задана наблюдаемая реализация некоторой бернуллиевской последовательности независимых случайных величин {n}, равных с одинаковой вероятностью плюс/минус единице, некоррелированных с ошибками наблюдения на шаге n. Тогда процедуру Кифера-Вольфовица можно модифицировать, используя рандомизированную статистику



Разложив функцию по формуле Тейлора и, воспользовавшись некоррелированностью n и помех наблюдения, для этой новой статистики имеем



Если значения числовой последовательности {βn} в алгоритме стремятся к нулю, то в пределе эта статистика ``в среднем'' совпадает со значением производной функции .

Такими же свойствами обладает и более простая статистика



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

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


В многомерном случае, когда , для построения последовательности оценок обычная процедура Кифера-Вольфовица, основанная на конечно-разностных аппроксимациях вектора-градиента функции, использует 2q наблюдений на каждой итерации (по два наблюдения для каждой компоненты q-мерного вектора-градиента). Рандомизированные статистики и допускают более простой с вычислительной точки зрения способ обобщения на многомерный случай, использующий всего два или одно измерение функции на каждой итерации. Пусть {n} - бернуллиевский q-мерный случайный процесс. Тогда



а вид формулы для такой же, как и в скалярном случае. Использовать статистику было предложено Дж. Спалом в статье [15]. В его работе, в частности, показано, что для больших n вероятностное распределение соответствующим образом отмасштабированных ошибок оценивания является приблизительно нормальным. Полученная формула для асимптотической дисперсии ошибки вместе с подобной характеристикой обыкновенной процедуры Кифера-Вольфовица была им использована для сравнения двух алгоритмов. Выяснилось, что при прочих равных условиях новый алгоритм имеет ту же скорость сходимости, что и обычная процедура Кифера-Вольфовица, несмотря на то, что в многомерном случае использует существенно меньше наблюдений (в q раз меньше при ). Статистика впервые была предложена в работах [16,17]. В статье [16] она использовалась для построения последовательности оценок, состоятельных при почти произвольных помехах в наблюдении.


Вопрос о скорости сходимости оценок алгоритмов стохастической аппроксимации был, наверное, основным, стимулирующим модификации первоначальных алгоритмов. Свойства оценок обычной процедуры Кифера-Вольфовица и некоторых ее обобщений детально изучены в работах [3,18, 19, 20,21] и во многих других.

Скорость сходимости зависит от гладкости функции. Если она дважды дифференцируема, то среднеквадратичная ошибка обыкновенного алгоритма КВ убывает как O(n-1/2), если трижды дифференцируема - как O(n-2/3)[19]. В. Фабиан [22] модифицировал процедуру Кифера-Вольфовица, предложив использовать кроме аппроксимации первой производной конечно-разностные аппроксимации производных высших порядков с определенными весами. Если функция имеет l непрерывных производных, тогда алгоритм Фабиана обеспечивает среднеквадратичную скорость сходимости порядка O(n-(l-1)/ l) для нечетных l. С вычислительной точки зрения алгоритм Фабиана очень усложнен, число наблюдений на одной итерации быстро увеличивается с ростом гладкости и размерности, кроме этого, на каждом шаге приходится обращать некоторую матрицу.

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

В том случае, когда некоторый обобщенный показатель гладкости функции равен (=l+1, если все частные производные функции порядка до l включительно удовлетворяют условию Липшица), в [17] было предложено использовать статистики вида



и , где - некоторая вектор-функция с конечным носителем (дифференцирующее ядро), определяемая с помощью ортогональных многочленов Лежандра степени меньшей . Два соответствующих рандомизрованных алгоритма дают среднеквадратичную скорость сходимости последовательности оценок, равную O (n-(-1)/ ). В той же работе было показано, что для широкого класса алгоритмов эта скорость сходимости оптимальна в некотором асимптотически минимаксном смысле, т. е. не может быть улучшена ни для какого-либо другого алгоритма, ни для любого другого допустимого правила выбора точек измерения.


Сходимость рандомизированных алгоритмов стохастической аппроксимации в многомерном случае при почти произвольных возмущениях обоснована в работах [23,24] и др. В статье [17] отмечается, что алгоритм с одним измерением в асимптотическом смысле ведет себя хуже, чем алгоритм с двумя измерениями. В [25] показано, что это не совсем так, если при сравнении алгоритмов рассматривать количество итераций, умноженное на количество измерений. Кроме того, во многих практических применениях, в частности, при оптимизации работы систем реального времени, лежащие в основе математической модели динамические процессы могут изменяться слишком быстро, не позволяя успеть получить два последовательных измерения. В некоторых задачах просто невозможно для одного шага алгоритма сделать два измерения таких, чтобы помехи наблюдения в обеих точках и были некоррелированны с . (Это одно из основных условий применимости алгоритма!) Избежать последнего недостатка позволяет предложенный в [26] алгоритм с двумя последовательными наблюдениями в точках и .

Основные предположения. Постановка задачи


Пусть - дифференцируемая по первому аргументу функция, x1,x2,… - выбираемая экспериментатором последовательность точек измерения (план наблюдения), в которых в которых в каждый момент времени n=1,2,… доступно наблюдению с аддитивными помехами vn значение функции

,

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

Постановка задачи. Требуется по наблюдениям y1,y2,… построить последовательность оценок неизвестного вектора , минимизирующего функцию

(1)


типа функционала среднего риска.

Обычно рассматривается задача минимизации функции при более простой модели наблюдений

,

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

,

который входит в общую схему с функцией .

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


Если измерения значений функции фактически делаются с некоторой аддитивной случайной центрированной независимой ошибкой , то, в силу общности поставленной задачи, это усложнение непринципиально. Расширив вектор w дополнительной компонентой v и, обозначив

,

можно рассматривать вместо новую функцию



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

В [27,28,29] описаны результаты, полученные при участии автора, о сходимости и скорости сходимости рекуррентных алгоритмов стохастической оптимизации.
1   2   3   4   5   6

Похожие:

Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов iconПетербургский Государственный Университет Математико-Механический Факультет Кафедра Системного Программирования
Сравнение различных методов хранения xml в реляционных базах данных и в разных системах
Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов iconМатематико-механический факультет Кафедра системного программирования «Мультиагентные платформы и их применение в сетевых задачах»
Мас концентрируют все необходимые для таких технологий свойства с наибольшей выразительностью и полнотой. Результаты внедрения агентных...
Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов iconМатематико-механический факультет Кафедра системного программирования Генерация веб-сервисов C#. net на основе bpel
Задача кодогенерации веб-сервисов возникла в рамках проекта «К700». «К700» — это проект создания рабочих мест оператора и инженера...
Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов iconМатематико-механический факультет Кафедра системного программирования Поддержка структурных изменений в процессах загрузки данных
Исследование необходимости поддержки структурных изменений в источниках данных 35
Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов iconМатематико-механический факультет Кафедра системного программирования Разработка системы сравнения производительности субд
Существует большое количество разнообразных субд (Система управления базами данных), предназначенных для разных задач, однако обычно...
Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов iconМатематико-механический факультет Кафедра системного программирования Разработка jre на ecma cli
Виртуальная машина, включая сборщик мусора и jit компилятор, является наиболее крупным монолитным компонентом среды управляемого...
Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов iconМатематико-механический факультет Кафедра системного программирования Создание режима быстрого прототипирования в case-системе qreal
Использование различных видов диаграмм и сущностей позволяет пользователям наглядно и подробно описать необходимые модули и поведение...
Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов iconМатематико-механический факультет

Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов iconМатематико-механический факультет

Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов iconМатематико-механический факультет

Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница