5.2. ДЕТЕРМИНИРОВАННЫЕ СХОДЯЩИЕСЯ АЛГОРИТМЫ

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

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

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

Пусть минимизируемый критерий ошибки есть

где настраиваемые параметры модели. В гл. 2 упоминались некоторые методы вычисления частных производных по этим параметрам. Эти производные можно использовать по-разному. Приведем обоснование достаточно общего подхода. Функция ошибок (5.19) может рассматриваться как гиперповерхность, определяемая уравнением

где минимальное значение функции ошибок, которое нужно определить:

Функцию ошибок можно разложить в ряд Тейлора в окрестности точки минимума

Члены более высокого порядка. Поскольку имеет минимум в точке то

и величина

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

После подстановки (5.216) уравнение (5.20) описывает гиперпараболоид (фиг. 5.13).

Для исследования сходимости рассматриваемых процедур важно знать поверхности уровня В квадратичном случае эти гиперповерхности представляют

Фиг. 5.13.

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

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

где Модель описывается уравнением

Эти уравнения можно разрешить явно относительно и Когда помехи отсутствуют, в окрестности экстремума ошибка мала. Если достаточно мала, то можно приближенно записать как

Отсюда

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

получаем простые формулы

где

Формулу (5.26) можно также переписать в виде

где

Сравнение уравнений (5.27) и (5.216) показывает, что они

эквивалентны при

Алгоритмы настройки делятся на поисковые и градиентные. В первом случае не требуется явного выражения для градиента функции ошибок или функции потерь, тогда как во втором случае используется допущение о возможности вычисления градиента. О методах оптимизации см. [2, 3, 7, 13, 18, 27].

Поисковые методы можно разбить на два подкласса:

а) Табличные методы. Функция ошибок оценивается в ряде точек пространства параметров, например в узлах регулярной решетки или в случайно выбранных точках.

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

Другой подход связан с использованием методов случайного поиска, когда в каждой точке случайно ищется направление спуска к меньшим значениям функции. Существует много итеративных алгоритмов случайного поиска. Обзор различных методов можно найти в [25]. Случайный поиск особенно удобен, когда число параметров больше 20.

Градиентные методы бывают непрерывными и дискретными. Дискретность может быть связана с измерениями и настройкой.

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

имеет вид

Уравнение касательной к линии уровня в точке запишется как

Вектор

ортогонален к касательной и, следовательно, к линии уровня. В методе наискорейшего спуска настройка параметров производится по формуле

Таким образом, траектория движения в каждой точке ортогональна к линиям уровня (фиг. 5.14). Здесь константа, которая вместе с частными производными определяет скорость изменения параметров. А так как частные производные не измеряются мгновенно, эту скорость

Фиг. 5.14.

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

Дискретные методы делятся на методы, в которых параметры настраиваются поочередно, и методы, в которых все параметры настраиваются одновременно.

а) Циклическая настройка параметров. Допустим, что параметр, который настраивается первым. Одна из возможностей состоит в такой настройке параметра которая обеспечивает равенство нулю Затем эта процедура повторяется для остальных параметров модели. В случае необходимости для удовлетворительной настройки модели циклы настройки повторяются несколько раз. В двумерпом случае плоскость покрывается сеткой линий уровня Как уже отмечалось, в окрестности оптимума линии уровня образуют семейство концентрических эллипсов, главные оси которых могут быть ориентированы произвольно (фиг. 5.14). Таким образом, при настройке параметры модели могут взаимодействовать, поэтому для перевода модели в окрестность оптимума в общем случае требуется несколько циклов. Если система ортогонализована, то достаточно однократной настройки каждого из параметров. Однако проблема состоит в том, что зарапее не известно, какое линейное преобразование ортогонализует систему. Семейство эллипсов характеризуется углом между главными осями, которые являются геометрическим местом точек, удовлетворяющих одному из двух уравнений:

Чем меньше этот угол, тем больше циклов требуется для обеспечения заданной точности. На фиг. 5.14 показана возможная траектория настройки Если линии уровня

представляют собой «овраги», то настройка может прекратиться при В этом недостаток метода.

В дальнейшем будут рассматриваться схемы с одновременной настройкой параметров. Более детальный анализ этих схем содержится в работе [20].

б) Метод наискорейшего спуска. Алгоритм настройки имеет вид

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

в) Наискорейший спуск с минимизацией вдоль направления движения. В этом случае имеем алгоритм

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

Фиг. 5.15.

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

Для попадания в оптимум за один шаг необходимо, чтобы

Равенства приемлемы, если только в противном случае коэффициенты усиления нужно подбирать по

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

где А — диагональная матрица собственных значений, а -матрица состоит из столбцов, образованных ортогональными собственными векторами. Подстановка (5.34) в (5.216) дает

где

Определим

тогда

В пространстве z поверхности уровня являются сферами (фиг. 5.16). Алгоритм наискорейшего спуска в

Фиг. 5.16, (см. скан)

пространстве имеет вид

и в силу того, что с положительно определенными Обратное преобразование к пространству дает

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

г) Метод Ньютона — Рафсона. Алгоритм имеет вид

Из этой формулы вытекает, что в методе Ныотона — Рафсона движение происходит по направлению к центру гиперэллипсоида, так как используется матрица вторых производных в точке Это движение можно также интерпретировать как движение к минимуму гиперпараболоида, который является аппроксимацией второго порядка гиперповерхности, определяемой уравнением (5.20) (фиг. 5.17).

Разлагая критерий в ряд Тейлора в окрестности получим

Минимум достигается в точке в которой Следовательно,

что приводит к уравнению (5.38).

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

Фиг. 5.17.

квадратов (5.18). В этом случае

Вблизи минимума и вторым членом можно пренебречь. Подстановка в (5.38) приводит к следующему методу.

д) Метод Гаусса — Ньютона. Алгоритм имеет вид

Легко проверить, что это обычная оценка метода наименьших квадратов, если линейна по

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

е) Метод Маркуардта. Пусть центр гиперсферы в пространстве параметров. Воспользуемся методом множителей Лагранжа для решения задачи поиска минимума на гиперсфере при ограничении

Тогда

Так как поверхность уровня не является идеальной гиперсферой, разложим в ряд Тейлора

Следовательно, уравнение (5.41) запишется как

Отсюда следует, что

Дальнейший анализ этой формулы показывает, что при имеем метод Гаусса — Ньютона, а при метод наискорейшего спуска с нулевым шагом (фиг. 5.18). Изменяя можно управлять сходимостью алгоритма. Недостаток состоит в необходимости приблияенной оценки матрицы вторых производных и последующего ее

Фиг. 5.18.

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

ж) Метод сопряженных градиентов. Заметим, что для удобства сначала формулу (5.216) можно записать как

где

поэтому

Направления и у называются сопряженными по отношению к положительно определенной матрице А, если

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

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

Модификация метода наискорейшего спуска заменой градиентного направления движения на сопряженное, как мы увидим, обеспечивает достижение минимума за шагов для -мерной квадратичной функции ошибок. Формула для вычисления итераций имеет вид

где определяется положением локального минимума вдоль направления что означает

Так как

справедливо также равенство

поскольку

и

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

Подстановкой эту гипотезу легко проверить, что дает

Начиная на первом шаге с направления, определяемого градиентом, после итераций имеем независимых сопряженных направлений. На последнем шаге градиент в соответствии с (5.456) должен быть ортогонален ко всем этим независимым направлениям, но в га-мерном пространстве это невозможно. Следовательно, градиент равен нулю и минимум достигнут. Этот алгоритм получен в работе [9].

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

или

Можно доказать, что

и

где

На шаге что в случае квадратичного критерия означает достижение минимума. Недостаток зтого метода состоит в том, что на каждом шаге нужно решать задачу минимизации по направлению. В работе [4] предложен подобный метод, но без минимизации. Этот алгоритм приводит в точку минимума за столько же шагов, но на каждом шаге используется одна функция и один градиент.

Все перечисленные методы хорошо применимы для случая почти квадратичных поверхностей, а также, по-видимому, и для многих других гладких поверхностей, в том числе на наборах однородных функций:

где

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

з) Метод Якобсона — Оксмана [11]. Идея метода удивительно проста. Предположим, что в точках известны значения функции и ее градиента и в этих точках выражение (5.49) можно записать в виде

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

Одним из паиболее серьезных тестов для проверки градиентных алгоритмов является так называемый «овраг» Розенброка, определяемый формулой (см. [20])

Фиг. 5.19 (см. скан) (из работы [20]).

Эта поверхность изображена на фиг. 5.19. В работе [20] проведено сравнение нескольких алгоритмов, проверенных на ряде разных «оврагов».

Примеры.

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

и «овраг» Розенброка. Для каждого алгоритма проводилось по 20 итераций. На фиг. 5.20-5.29 представлены результаты, пол ученные при рассмотрении квадратичной функции и «оврага» Розенброка

Поисковые итеративные методы

Метод Хука — Дживса [13].

Начальная точка:

Симплекс-метод [3].

Начальная точка:

Фиг. 5.20.

Фиг. 5.21.

Фиг. 5.22.

Фиг. 5.23.

Случайный поиск [25].

Начальная точка:

Адаптивный случайный поиск [25].

Начальная точка:

Градиентные методы с дискретной настройкой

Наискорейший спуск.

Начальная точка:

Фиг. 5.24.

Фиг. 5.25.

Наискорейший спуск с минимизацией вдоль направления движения.

Начальная точка:

Метод Маркуардта.

Начальная точка:

Фиг. 5.26.

Фиг. 5.27.

Метод Флетчера — Пауэлла (см. [18]).

Начальная точка:

Метод Дэвидона (см. [4]).

Начальная точка:

Фиг. 5.28.

Фиг. 5.29.

Метод Якобсона — Оксмана (см. [11]).

Начальная точка:

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