§ 1.5. Алгоритмы идентификации

Оптимальное решение с является решением уравнения (1.4.4), представляющего собой условие оптимальности

Это векторное уравнение эквивалентно системе, вообще говоря, нелинейных уравнений относительно компонент вектора с. В общем случае, когда вектор с входит нелинейно в (1.5.1), явное аналитическое выражение для оптимального вектора найти невозможно даже при наличии полной априорной информации. Поэтому приходится довольствоваться различными приближенными методами решения уравнения (1.5.1). Большинство из них относится к методам последовательных приближений. Физический смысл этих методов состоит в замене статического уравнения, коим является условие оптимальности, «динамическим» — разностным уравнением, решение которого с течением времени стремится к оптимальному вектору с. Такое разностное уравнение и определяет собой алгоритм идентификации.

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

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

Выбор матрицы усиления определяет тот или иной конкретный метод. Так, скалярная матрица усиления

где единичная матрица, соответствует градиентному методу. Диагональная матрица усиления

соответствует псевдоградиентному методу. Матрица, равная обратной матрице Гессе вида

соответствует методу Ньютона, а матрица вида

где — начальное значение отвечает модифицированному методу Ньютона,

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

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

Рис. 1.14

Если средние потери квадратичны по с, то их градиент будет линейной функцией с, а матрица усиления определяемая обратной матрицей Гессе (1.5.5) или (1.5.6), не будет зависеть от или В этом случае алгоритм (1.5.2), соответствующий методу Ньютона — Рафсона, приводит к

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

Особенность дискретной системы (рис. 1.14), соответствующей итеративному алгоритму (1.5.2), состоит в том, что она автономна. Это естественно, поскольку этот алгоритм использует полную априорную информацию и не требует какой-либо дополнительной информации. Итеративный алгоритм (1.5.2) непосредственно не может быть использован для определения оптимального решения с если градиент средних потерь не полностью определен, что бывает в часто возникающем на практике случае, когда нам не известна полностью плотность распределения помех и наблюдений. Поэтому широкое распространение получили рекуррентные алгоритмы, не требующие знания градиента средних потерь а использующие текущую информацию, содержащуюся в наблюдениях. Эти рекуррентные алгоритмы тесно связаны с методом стохастической аппроксимации, который является фундаментом адаптивного подхода. Их особенность состоит в том, что вместо градиента средних потерь в них фигурирует градиент функций потерь который непосредственно зависит от наблюдений Рекуррентные алгоритмы можно представить в виде

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

Скалярная матрица усиления

соответствует градиентному методу стохастической аппроксимации. Диагональная матрица

Рис. 1.15

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

в частности, при

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

Скалярные множители в (1.5.8), (1.5.10), а также в (1.5.9) должны удовлетворять условиям вида

которые обеспечивают сходимость рекуррентных алгоритмов (1.5.7) (т. е. сходимость в вероятностном смысле порождаемых ими оценок к оптимальному решению с для широкого класса функций потерь и плотностей распределения помех Условия (1.5.12) имеют ясный физический смысл. Они обеспечивают изменение оценки порождаемой рекуррентным алгоритмом, в среднем в сторону антиградиента (условие ); уменьшение шага алгоритма не настолько быстрое, чтобы оценка перестала изменяться при достижении некоторой произвольной точки (условие б), и не настолько медленное, чтобы оценка достигнув оптимальной точки с не смогла остановиться в ней (условие в). Этим условиям удовлетворяет, например,

Блок-схема рекуррентного алгоритма (1.5.7), приведенная на рис. 1-15, отличается от блок-схемы итеративного алгоритма (рис. 1.14)

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

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

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