Материал из MachineLearning.
Алгоритм Левенберга-Марквардта предназначен для оптимизации параметров нелинейных регрессионных моделей.
Предполагается, что в качестве критерия оптимизации используется среднеквадратичная ошибка модели на
обучающей выборке. Алгоритм заключается в последовательном приближении заданных начальных значений параметров к
искомому локальному оптимуму.
Алгоритм отличается от метода сопряженных градиентов тем, что использует
матрицу Якоби модели, а не градиент вектора параметров.
От алгоритма Гаусса-Ньютона этот алгоритм отличается тем,
что использует параметр регуляризации.
Постановка задачи
Задана регрессионная выборка — множество пар \}_{n=1}^N)
свободной переменной 
и зависимой переменной 
.
Задана регрессионная модель — функция )
непрерывно дифференцируемая в области 
.
Требуется найти такое значение вектора параметров 
, которое бы доставляло локальный минимум
функции ошибки
\bigr)^2. (*))
Описание алгоритма
Перед началом работы алгоритма задается начальный вектор параметров .
На каждом шаге итерации этот вектор заменяется на вектор 
.
Для оценки приращения 
используется линейное приближение функции
 \approx f(\mathbf{w},\mathbf{x})+J\Delta\mathbf{w},)
где 
— якобиан функции в точке . )
-матрицу наглядно можно представить в виде
![J=\left[\begin{array}{ccc} \frac{\partial f(\mathbf{w},\mathbf{x}_1)}{\partial w_1} & \dots & \frac{\partial f(\mathbf{w},\mathbf{x}_1)}{\partial w_R} \\ \vdots & \ddots & \vdots \\ \frac{\partial f(\mathbf{w},\mathbf{x}_N)}{\partial w_1} & \dots & \frac{\partial f(\mathbf{w},\mathbf{x}_N)}{\partial w_R} \\ \end{array} \right].](../mimetex/?J=\left[\begin{array}{ccc} \frac{\partial f(\mathbf{w},\mathbf{x}_1)}{\partial w_1} & \dots & \frac{\partial f(\mathbf{w},\mathbf{x}_1)}{\partial w_R} \\ \vdots & \ddots & \vdots \\ \frac{\partial f(\mathbf{w},\mathbf{x}_N)}{\partial w_1} & \dots & \frac{\partial f(\mathbf{w},\mathbf{x}_N)}{\partial w_R} \\ \end{array} \right]. )
Здесь вектор параметров ![\mathbf{w}=[w_1,\ldots, w_R]^T](../mimetex/?\mathbf{w}=[w_1,\ldots, w_R]^T)
.
Приращение в точке , доставляющий минимум 
равно нулю
(ср. приближение функции рядом Тейлора в статье Оптимальная хирургия мозга).
Поэтому для нахождения последующего значения приращения приравняем нулю
вектор частных производных по . Для этого )
представим в виде
\|^2,)
где
![\mathbf{y}=[y_1,\ldots, y_N]^T](../mimetex/?\mathbf{y}=[y_1,\ldots, y_N]^T)
и ![\mathbf{f}(\mathbf{w}+\Delta\mathbf{w})=[f(\mathbf{w}+\Delta\mathbf{w},\mathbf{x}_1),\ldots, f(\mathbf{w}+\Delta\mathbf{w},\mathbf{x}_N))]^T](../mimetex/?\mathbf{f}(\mathbf{w}+\Delta\mathbf{w})=[f(\mathbf{w}+\Delta\mathbf{w},\mathbf{x}_1),\ldots, f(\mathbf{w}+\Delta\mathbf{w},\mathbf{x}_N))]^T)
.
Преобразовывая это выражение
\|^2 = \bigl(\mathbf{y}-\mathbf{f}(\mathbf{w}+\Delta\mathbf{w})\bigr)^T\bigl(\mathbf{y}-\mathbf{f}(\mathbf{w}+\Delta\mathbf{w})\bigr) = \mathbf{f}^T(\mathbf{w}+\Delta\mathbf{w})\mathbf{f}(\mathbf{w}+\Delta\mathbf{w}) - 2\mathbf{y}^T\mathbf{f}(\mathbf{w}+\Delta\mathbf{w}) + \mathbf{y}^T\mathbf{y} )
и дифференцируя (ср. дифференцирование вектора невязки в статье Метод наименьших квадратов), получим
\Delta\mathbf{w}-J^T\bigl(\mathbf{y}-\mathbf{f}(\mathbf{\mathbf{w}})\bigr) = 0. )
Таким образом, чтобы найти значение нужно решить систему линейных уравнений
^{-1}J^T\bigl(\mathbf{y}-\mathbf{f}(\mathbf{\mathbf{w}})\bigr). )
Так как число обусловленности матрицы 
есть квадрат числа обусловленности матрицы
(см. соотв. раздел в статье Сингулярное разложение),
то матрица может оказаться существенно вырожденной. Поэтому Марквардт предложил ввести
параметр регуляризации 
,
^{-1}J^T\bigl(\mathbf{y}-\mathbf{f}(\mathbf{\mathbf{w}})\bigr), )
где 
— единичная матрица. Этот параметр назначается на каждой итерации алгоритма.
Если значение ошибки убывает быстро, малое значение 
сводит этот алгоритм к алгоритму Гаусса-Ньютона.
Алгоритм останавливается, в том случае, если приращение в последующей итерации меньше заданного значения,
либо если параметры доставляют ошибку меньшую заданной величины.
Значение вектора на последней итерации считается искомым.
Недостаток алгоритма — значительное увеличение параметра при плохой скорости аппроксимации.
При этом обращение матрицы 
становится бессмысленным.
Этот недостаток можно устранить, используя диагональ матрицы в качестве регуляризующего слагаемого:
\bigr)^{-1}J^T\bigl(\mathbf{y}-\mathbf{f}(\mathbf{\mathbf{w}})\bigr). )
Смотри также
Литература
- Levenberg, K. A Method for the Solution of Certain Problems in Last Squares. Quart. Appl. Math. 1944. Vol. 2. P. 164—168.
- Демиденко Е. З. Оптимизация и регрессия. М. Наука. 1989.
Внешние ссылки
