7.4. Оценка медленно меняющихся со временем параметров с помощью динамической стохастической аппроксимации

Задача оценки параметров распределения вероятности трактовалась как последовательная оценка условных распределений с помощью оптимального использования обучающих наблюдений. В §§ 7.1 и 7.2 были приведены алгоритмы стохастической аппроксимации для оценки неизвестных, но неизменных параметров. В случае, когда неизвестные параметры изменяются со временем (непостоянны), эти алгоритмы не могут давать истинные значения параметров. В данном параграфе излагаются алгоритмы для оценки медленно изменяющихся со временем параметров [17], построенные на основе процедуры динамической стохастической аппроксимации, предложенной Дупачем [16]. Краткое введение в процедуру динамической стохастической аппроксимации дано в приложении Этим методом исследуются задачи обучения как с поощрением, так и без поощрения.

В общем случае эти алгоритмы обучения состоят из двухступенной процедуры аппроксимации, выполняемой на каждом шаге процесса обучения. Первая ступень предназначена для коррекции временных изменений оцениваемых параметров; вторая ступень делается, как в обычной процедуре стохастической аппроксимации, на основе наблюдения новых обучающих замеров. Сходимость этих алгоритмов может быть доказана с помощью метода Дворецкого [18].

7.4.1. Обучение с поощрением.

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

неизвестное изменяющееся со временем среднее, дисперсия которого известна. Параметр изменяется медленно со временем следующим образом:

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

вторая ступень:

где последовательность положительных чисел, удовлетворяющих условиям

Применяя метод Дворецкого [18], можно показать, что оценка сходится к в среднеквадратичном с вероятностью единица. Перепишем (7.106) в следующем виде:

где

и

Величина представляет собой шумовую составляющую обучающего замера причем

Уравнение (7.108) можно записать в виде алгоритма стохастической аппроксимации Дворецкого

где

представляет собой детерминированное (без помех) преобразование. Из (7.113) и (7.104) получаем

где

Опуская случайную часть в (7.112) и используя рекурентно (7.114), получим

Таким образом, если (при соответствующем выборе то сходится к при любом конечном значении Пусть теперь Из (7.111) очевидно, что Предположим, что шумовая составляющая величины такова, что ее дисперсия ограничена величиной при всех Следовательно,

Это означает, что сумма дисперсий помех конечна. Наконец, пусть

После возведения в квадрат левой и правой частей выражения (7.108) и определения среднего получаем рекуррентное соотношение для среднеквадратичной ошибки оценок

в котором неравенство получается при подстановке вместо верхней границы дисперсии помехи Обозначая и итерируя выражение (7.119), получим

где

Если то, как легко видеть, правая, а следовательно, и левая части формулы (7.120) становятся равными при Таким образом,

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

Приравнивая первую производную по нулю, получим, что минимум правой части неравенства (7.123) имеет место при

Подставляя (7.124) в (7.123), получим следующее рекуррентное соотношение для сренеквадратичной ошибки:

Пусть начальная оценка имела среднеквадратичную ошибку Введем обозначение Используя (7.124) и (7.125), итерируя попеременно получим оптимальную последовательность и минимизированную среднеквадратичную ошибку

Легко показать, что полученная таким способом оптимальная последовательность удовлетворяет условиям, сформулированным в (7.107), а простая подстановка из (7.126) в Из (7.127) следует, что при значение стремится к нулю как Однако скорость сходимости, выраженная среднеквадратичной ошибкой, несколько меньше, чем у обычного (од-ноступенного) алгоритма стохастической аппроксимации, когда (7.105) и (7.106) можно заменить одним уравнением

Количественное сравнение этих двух алгоритмов может быть произведено путем вычисления среднеквадратичных ошибок оценок, получаемых в обоих случаях. Оптимальное решение для (7.128) было дано в (7.39) и (7.40). Результаты этих вычислений приведены в табл. 7.1. Ясно, что в случае зависимости от времени среднеквадратичная ошибка больше, за исключением предельного случая при когда ошибка обеих оценок равна нулю,

Таблица 7.1 (см. скан)

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

Следует отметить, что если точная природа члена в (7.104) неизвестна и соответственно поправка первой ступени может быть выражена следующим образом:

где в общем случае отличается от то из (7.129) и (7.106) следует, что

Пусть

Согласно (7.131) и (7.104)

Отбрасывая случайную часть в (7.130), образуем следующее выражение:

Если

Вновь можно применить теорему Дворецкого и показать сходимость к

7.4.2. Обучение без поощрения.

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

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

совместной плотности будет

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

что является частным случаем (7.104) при произвольно большом Вычислим первый момент х для из (7.135)

Тогда

Это означает, что изменяется аналогично тип и, следовательно, удовлетворяет частному случаю условия (7.104) при произвольно большом Теперь рассмотрим как зависящий от времени параметр функции совместной плотности и положим, что оценка Применим алгоритм динамической стохастической аппроксимации

где

последовательность, удовлетворяющая условиям (7.107). Используя полученные результаты (например, (7.124)), найдем

Таким образом, и соответственно согласно (7.137), могут быть оценены асимптотически среднеквадратично с вероятностью единица. Из (7.137) следует также, что та же процедура может

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

Пример 2. Используя (7.135) примера 1, рассмотрим случай, когда и известны. Задача заключается в оценке зависящей от времени дисперсии Пусть

Вычислим с помощью (7.135) второй момент для

Далее, используя (7.143) и (7.144), получим

Так как является постоянной, то вновь удовлетворяет условию (7.104) при Чтобы оценить следовательно, а? (согласно (7.144)), можно применить алгоритм динамической стохастической аппроксимации, аналогичный (7.139), для получения оценок, которые сходятся к истинному значению параметра в среднеквадратичном с вероятностью единица.

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

7.4.3. Алгоритм ускоренной динамической стохастической аппроксимации.

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

оценки среднего функции плотности вероятности при произвольно большом когда Перепишем (7.106) в виде

Очевидно, меньшее число перемен знака выражения

указывает, что еще далеко от в то время как более частные перемены знака указывают на близость В соответствии с этим сходимость алгоритма динамической стохастической аппроксимации может быть улучшена с помощью схемы ускорения Кестена [19]. Определим

где

и

где

Это означает, что модифицированный алгоритм использует разные значения каждый раз, когда имеют различные знаки, в противных случаях остается неизменным. Таблица 7.2 показывает, что эта модификация может ускорить процесс обучения. Она дает результат, заключающийся в том, что при очень частых переменах знака (четыре раза в первых десяти шагах) общая поправка для оценки модифицированного алгоритма достигает 3,7 единицы, в то время как поправка для немодифицированного алгоритма равна лишь 2,8 единицы.

Таблица 7.2 (см. скан)