3.4.4. Алгоритм Левенберга-Марквардта

Другим приложением ньютоновской стратегии оптимизации является алгоритм Левенберга-Марквардта [39]. При его использовании точное значение гессиана в формуле (3.34) заменяется аппроксимированным значением которое рассчитывается на основе содержащейся в градиенте информации с учетом некоторого регуляризационного фактора.

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

где . При использовании обозначений

вектор градиента и аппроксимированная матрица гессиана, соответствующие целевой функции (3.37), определяются в виде

где обозначены компоненты гессиана содержащие высшие

производные относительно Сущность подхода Левенберга-Марквардта состоит в аппроксимации с помощью регуляризационного фактора в котором переменная называемая параметром Левенберга-Марквардта, является скалярной величиной, изменяющейся в процессе оптимизации. Таким образом, аппроксимированная матрица гессиана на шаге алгоритма приобретает вид:

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

а направление минимизации выбирается по методу наискорейшего спуска:

По мере уменьшения погрешности и приближения к искомому решению величина параметра понижается и первое слагаемое в формуле (3.40) начинает играть все более важную роль.

На эффективность алгоритма влияет грамотный подбор величины Слишком большое начальное значение по мере прогресса оптимизации должно уменьшаться вплоть до нуля при достижении фактического решения, близкого к искомому. Известны различные способы подбора этого значения, но мы ограничимся описанием только одной оригинальной методики, предложенной Д. Марквардтом [95]. Пусть значения целевой функции на шагах итерации обозначаются соответственно а значения параметра на этих же шагах - и Коэффициент уменьшения значения обозначим причем . В соответствии с классическим алгоритмом Левенберга-Марквардта значение изменяется по следующей схеме:

• если то принять

• если то принять

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

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

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