Градиентный поиск методом наискорейшего спуска

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

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

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

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

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

Напомним по (4.4) представляет собой одномерный варициз соотношения (4.36). Для определения характера процесса, возникающего при использовании этого алгоритма для поиска оптимума квадратичной рабочей функции, подставим в (4.36) соотношение для градиента (4.29) и затем (4.28). При этом

После преобразований

Решение этого уравнения усложняется тем, что различные компоненты вектора взаимосвязаны между собой. Матрица R в общем случае не диагональная, а поскольку матрица W в (4.38) содержит член , то она также является не диагональной.

Для понимания отличия этого случая от предыдущего можно сравнить (4.38) с уравнением (4.34), соответствующим методу Ньютона. Однако решить уравнение (4.38) можно, если привести его к системе координат, образованной главными осями. Для этого сначала, как и в (3.37), введем смещение . Тогда (4.38) принимает вид

Затем, используя соотношения (3.13) и (3.38), приведем уравнение к главным осям, т. е. учитывая , получаем

Умножив обе части этого уравнения слева на найдем

Теперь, как и в (3.4), матрица собственных значений А является диагональной, поэтому (4.41) представляет собой множество уравнений вида (4.7). Отсюда ясно, что в системе координат, образованной главными осями, компоненты вектора не являются взаимосвязанными. Более того, методом индукции находим решение (4.41):

Из (4.42) следует, что алгоритм наискорейшего спуска является устойчивым и сходящимся, если

Поскольку произведение двух диагональных матриц равно матрице, составленной из произведений соответствующих элементов, (4.43) можно записать в виде

Такая запись показывает, что условие сходимости выполняется, если параметр выбран так, чтобы

где — максимальное собственное значение матрицы R. Соотношение (4.45) является необходимым и достаточным условием сходимости алгоритма наискорейшего спуска для квадратичной рабочей функции. Если это условие выполняется, то

Подставляя в (4.46) и осуществляя обратное преобразование к исходной системе координат, находим

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

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

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

Рис. 4.8. Применение алгоритма наискорейшего спуска в системе с двумя весовыми коэффициентами. В соответствии с (4.48) по осям знаменатели геометрических прогрессий являются постоянными

Итеративный процесс в исходной системе координат можно описать, выразив (4.42) через вектор . Умножим сначала обе части уравнения (4.42) слева на Q:

Используя подстановку , получаем

Далее воспользуемся следующим соотношением:

где А — любая матрица, для которой существуют эти произведения. Подставляя в (4.50) и выражение (3.5), имеем

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

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