ГЛАВА 7. ОБУЧЕНИЕ В СИСТЕМАХ ПОСЛЕДОВАТЕЛЬНОГО РАСПОЗНАВАНИЯ НА ОСНОВЕ СТОХАСТИЧЕСКОЙ АППРОКСИМАЦИИ

7.1. Обучение с поощрением с помощью стохастической аппроксимации

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

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

Так как то всегда выполняются условия

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

то последовательные оценки стремятся к величине в смысле среднего квадрата с вероятностью единица. В случае оценки неизвестной функции плотности вероятности по наблюдениям представим аппроксимирующей конечной суммой [1]

где система ортонормированных функций, т. е.

Для оценки коэффициентов предложен следующий алгоритм стохастической аппроксимации:

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

Приведем здесь иное рассмотрение, преследуя две цели: во-первых, иллюстрировать применение стохастической аппроксимации к оценке параметра, и, во-вторых, чтобы показать связь метода байесовой оценки, описанного в § 6.1, с процедурой стохастической аппроксимации [2].

А. Оценка среднего вектора М при гауссовом распределении.

Напомним формулы (6.7) и (6.8):

Добавляя и отнимая в уравнении (6.7), получим

Отметим, что (7.7) также является частным видом алгоритма стохастической аппроксимации. Сущность этого алгоритма легко можно увидеть в случае, когда Тогда (7.7) принимает вид

Пусть где есть -мерный вектор помехи

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

что удовлетворяет условиям (7.3). Тогда уравнение (7.8) принимает вид

Пусть теперь

тогда

где удовлетворяет условиям

Так как для начальной опенки ограничена сверху величиной В, т. е.

то

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

Это просто означает, что (7.8) является частным случаем стохастической аппроксимации при сходимости оценок к истинному среднему вектору в среднеквадратичном с вероятностью единица.

В. Оценка ковариационной матрицы К гауссова распределения.

Перепишем уравнение оценки (6.14) в виде

Так как

то (7.17) принимает вид

Пусть

что удовлетворяет условиям (7.3). Можно показать, что (7.18) также является частным видом алгоритма процедуры стохастической аппроксимации Дворецкого [2]. Оценки, полученные из (7.18), сходятся к истинной ковариационной матрице (для каждого элемента) в среднеквадратичном с верятностью единица.

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

С. Оценка параметра биномиального распределения.

Уравнение (6.29) можно переписать в следующем виде:

Введем величину

которая удовлетворяет условиям (7.3), и пусть

причем

Определим

Тогда (7.20) примет вид

где

При этом

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

Условие Дворецкого (Приложение ) может быть легко проверено, так как

Наконец,

справедливо в силу предположений (7.23) относительно и поэтому дает условие Таким образом, согласно теореме Дворецкого,

Уравнения (7.28) и (7.29) вновь приводят к заключению о том, что сходимость оценок к истинному значению параметра в среднеквадратичном и с вероятностью единица является прямым следствием приведения метода байесовой оценки к общей схеме стохастической аппроксимации.

D. Среднеквадратичная ошибка и оптимальная обучающая последовательность.

На практике часто оказывается необходимым определять скорость сходимости алгоритма обучения, выраженную через среднеквадратичную ошибку оценки. В качестве примера рассмотрим алгоритм (7.10)

Пусть

Тогда, согласно (7.30),

где В — верхняя граница Итерируя выражение (7.32), получим

где есть среднеквадратичная ошибка начальной оценки Так как

то (7.33) принимает вид

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

Таким образом,

или

где

а помехи предполагаются стационарными, так что

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

Пусть начальная среднеквадратичная ошибка равна Используя (7.37) и (7.38), попеременно итерируем для получения соответственно оптимальной последовательности у и минимальной среднеквадратичной

ошибки в следующем виде:

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