§ 7.2. Стохастическая аппроксимация

Алгоритм последовательного оценивания, описанный в § 7.1, не всегда сходится, если векторы наблюдений не являются линейно разделимыми (пример 7.2). Этот факт выдвигает задачу построения алгоритма оценивания, сходимость которого гарантирована.

Метод стохастической аппроксимации был первоначально разработан как метод оптимизации при наличии случайных помех [Вайлд, 1964; Мендел, 1970]. Этот метод, сходимость которого гарантирована при очень общих условиях, можпо применить и для оценивания параметров в задаче распознавания образов. Однако оценить скорость сходимости метода стохастической аппроксимации обычно довольно трудно.

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

Это соотношение можно переписать следующим образом:

Другими словами, при добавлении нового объекта X для вычисления оценки достаточно помнить только, предыдущую оценку и число наблюдений Кроме того, по мере увеличения влияние нового объекта на вектор выборочного среднего значения уменьшается следующим образом:

Последовательность коэффициентов называется гармонической последовательностью.

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

1. Когда имеется математическое выражение для оценки, можно построить процедуру последовательного оценивания путем разбиения этого выражения на два слагаемых: оценку, рассчитанную по объектам, и вклад объекта.

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

Рис. 7.3. Задача нахождения корня.