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

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(→Смотри также)
(→Описание алгоритма)
 
(4 промежуточные версии не показаны)
Строка 6: Строка 6:
Алгоритм отличается от [[метод сопряженных градиентов|метода сопряженных градиентов]] тем, что использует
Алгоритм отличается от [[метод сопряженных градиентов|метода сопряженных градиентов]] тем, что использует
[[матрица Якоби|матрицу Якоби]] модели, а не [[градиент]] вектора параметров.
[[матрица Якоби|матрицу Якоби]] модели, а не [[градиент]] вектора параметров.
-
От [[алгоритм Гаусса-Ньютона|алгоритма Гаусса-Ньютона]] этот алгоритм отличается тем,
+
От [[Метод Ньютона-Гаусса|алгоритма Гаусса-Ньютона]] этот алгоритм отличается тем,
что использует [[регуляризация|параметр регуляризации]].
что использует [[регуляризация|параметр регуляризации]].
Строка 24: Строка 24:
На каждом шаге итерации этот вектор заменяется на вектор&nbsp;<tex>\mathbf{w}+\Delta\mathbf{w}</tex>.
На каждом шаге итерации этот вектор заменяется на вектор&nbsp;<tex>\mathbf{w}+\Delta\mathbf{w}</tex>.
Для оценки приращения&nbsp;<tex>\Delta\mathbf{w}</tex> используется линейное приближение функции
Для оценки приращения&nbsp;<tex>\Delta\mathbf{w}</tex> используется линейное приближение функции
-
<center><tex>f(\mathbf{w}+\Delta\mathbf{w},\mathbf{x}) \approx f(\mathbf{w},\mathbf{x})+J\Delta\mathbf{w},</tex></center>
+
<center><tex>f(\mathbf{w}+\Delta\mathbf{w},\mathbf{x}) - f(\mathbf{w},\mathbf{x}) \approx J\Delta\mathbf{w},</tex></center>
где&nbsp;<tex>J</tex>&nbsp;— якобиан функции&nbsp;<tex>f(\mathbf{w},\mathbf{x}_n)</tex> в точке&nbsp;<tex>\mathbf{w}</tex>. <tex>(N\times R)</tex>-матрицу&nbsp;<tex>J</tex> наглядно можно представить в виде
где&nbsp;<tex>J</tex>&nbsp;— якобиан функции&nbsp;<tex>f(\mathbf{w},\mathbf{x}_n)</tex> в точке&nbsp;<tex>\mathbf{w}</tex>. <tex>(N\times R)</tex>-матрицу&nbsp;<tex>J</tex> наглядно можно представить в виде
<center><tex>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]. </tex></center>
<center><tex>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]. </tex></center>
Строка 37: Строка 37:
<tex>\mathbf{y}=[y_1,\ldots, y_N]^T</tex> и <tex>\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</tex>.
<tex>\mathbf{y}=[y_1,\ldots, y_N]^T</tex> и <tex>\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</tex>.
Преобразовывая это выражение
Преобразовывая это выражение
-
<center><tex>\|\mathbf{y}-\mathbf{f}(\mathbf{w}+\Delta\mathbf{w})\|^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}) - 2\mathbf{y}^T\mathbf{f}(\mathbf{w}+\Delta\mathbf{w}) + \mathbf{y}^T\mathbf{y} </tex></center>
+
<center><tex>\|\mathbf{y}-\mathbf{f}(\mathbf{w}+\Delta\mathbf{w})\|^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} </tex></center>
и дифференцируя (ср. дифференцирование вектора невязки в статье [[Метод наименьших квадратов]]), получим
и дифференцируя (ср. дифференцирование вектора невязки в статье [[Метод наименьших квадратов]]), получим
<center><tex>\frac{\partial E_D}{\partial\mathbf{w}} =(J^TJ)\Delta\mathbf{w}-J^T\bigl(\mathbf{y}-\mathbf{f}(\mathbf{\mathbf{w}})\bigr) = 0. </tex></center>
<center><tex>\frac{\partial E_D}{\partial\mathbf{w}} =(J^TJ)\Delta\mathbf{w}-J^T\bigl(\mathbf{y}-\mathbf{f}(\mathbf{\mathbf{w}})\bigr) = 0. </tex></center>
Строка 56: Строка 56:
Недостаток алгоритма&nbsp;— значительное увеличение параметра&nbsp;<tex>\lambda</tex> при плохой скорости аппроксимации.
Недостаток алгоритма&nbsp;— значительное увеличение параметра&nbsp;<tex>\lambda</tex> при плохой скорости аппроксимации.
-
При этом обращение матрицы&nbsp;<tex>J^TJ+\lambda I</tex> становиться бессмысленным.
+
При этом обращение матрицы&nbsp;<tex>J^TJ+\lambda I</tex> становится бессмысленным.
-
Этот недостаток можно устранить, используя диагональ матрицы Гессе&nbsp;<tex>J^TJ</tex> в качестве регуляризующего слагаемого:
+
Этот недостаток можно устранить, используя диагональ матрицы&nbsp;<tex>J^TJ</tex> в качестве регуляризующего слагаемого:
<center><tex> \Delta\mathbf{w}=\bigl(J^TJ+\lambda\text{diag}(J^TJ)\bigr)^{-1}J^T\bigl(\mathbf{y}-\mathbf{f}(\mathbf{\mathbf{w}})\bigr). </tex></center>
<center><tex> \Delta\mathbf{w}=\bigl(J^TJ+\lambda\text{diag}(J^TJ)\bigr)^{-1}J^T\bigl(\mathbf{y}-\mathbf{f}(\mathbf{\mathbf{w}})\bigr). </tex></center>

Текущая версия

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

Алгоритм отличается от метода сопряженных градиентов тем, что использует матрицу Якоби модели, а не градиент вектора параметров. От алгоритма Гаусса-Ньютона этот алгоритм отличается тем, что использует параметр регуляризации.

Содержание

Постановка задачи

Задана регрессионная выборка — множество пар D = \{(\mathbf{x}_n, y_n)\}_{n=1}^N свободной переменной \mathbf{x}\in\mathbb{R}^M и зависимой переменной y\in\mathbb{R}. Задана регрессионная модель — функция f(\mathbf{w},\mathbf{x}_n) непрерывно дифференцируемая в области W\times X.

Требуется найти такое значение вектора параметров \mathbf{w}, которое бы доставляло локальный минимум функции ошибки

E_D = \sum_{n=1}^{N} \bigl(y_n-f(\mathbf{w},\mathbf{x}_n)\bigr)^2. (*)

Описание алгоритма

Перед началом работы алгоритма задается начальный вектор параметров \mathbf{w}. На каждом шаге итерации этот вектор заменяется на вектор \mathbf{w}+\Delta\mathbf{w}. Для оценки приращения \Delta\mathbf{w} используется линейное приближение функции

f(\mathbf{w}+\Delta\mathbf{w},\mathbf{x}) - f(\mathbf{w},\mathbf{x}) \approx J\Delta\mathbf{w},

где J — якобиан функции f(\mathbf{w},\mathbf{x}_n) в точке \mathbf{w}. (N\times R)-матрицу J наглядно можно представить в виде

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.

Приращение \Delta\mathbf{w} в точке \mathbf{w}, доставляющий минимум E_D равно нулю (ср. приближение функции E_D рядом Тейлора в статье Оптимальная хирургия мозга). Поэтому для нахождения последующего значения приращения \Delta\mathbf{w} приравняем нулю вектор частных производных E_D по \mathbf{w}. Для этого (*) представим в виде

E_D = \|\mathbf{y}-\mathbf{f}(\mathbf{w}+\Delta\mathbf{w})\|^2,

где \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. Преобразовывая это выражение

\|\mathbf{y}-\mathbf{f}(\mathbf{w}+\Delta\mathbf{w})\|^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}

и дифференцируя (ср. дифференцирование вектора невязки в статье Метод наименьших квадратов), получим

\frac{\partial E_D}{\partial\mathbf{w}} =(J^TJ)\Delta\mathbf{w}-J^T\bigl(\mathbf{y}-\mathbf{f}(\mathbf{\mathbf{w}})\bigr) = 0.

Таким образом, чтобы найти значение \Delta\mathbf{w} нужно решить систему линейных уравнений

\Delta\mathbf{w}=(J^TJ)^{-1}J^T\bigl(\mathbf{y}-\mathbf{f}(\mathbf{\mathbf{w}})\bigr).

Так как число обусловленности матрицы J^TJ есть квадрат числа обусловленности матрицы J (см. соотв. раздел в статье Сингулярное разложение), то матрица J^TJ может оказаться существенно вырожденной. Поэтому Марквардт предложил ввести параметр регуляризации \lambda\geq 0,

\Delta\mathbf{w}=(J^TJ+\lambda I)^{-1}J^T\bigl(\mathbf{y}-\mathbf{f}(\mathbf{\mathbf{w}})\bigr),

где I — единичная матрица. Этот параметр назначается на каждой итерации алгоритма. Если значение ошибки E_D убывает быстро, малое значение \lambda сводит этот алгоритм к алгоритму Гаусса-Ньютона.

Алгоритм останавливается, в том случае, если приращение \Delta\mathbf{w} в последующей итерации меньше заданного значения, либо если параметры \mathbf{w} доставляют ошибку E_D меньшую заданной величины. Значение вектора \mathbf{w} на последней итерации считается искомым.

Недостаток алгоритма — значительное увеличение параметра \lambda при плохой скорости аппроксимации. При этом обращение матрицы J^TJ+\lambda I становится бессмысленным. Этот недостаток можно устранить, используя диагональ матрицы J^TJ в качестве регуляризующего слагаемого:

\Delta\mathbf{w}=\bigl(J^TJ+\lambda\text{diag}(J^TJ)\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.

Внешние ссылки

Источник — «http://www.recognition.su/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B5%D0%BD%D0%B1%D0%B5%D1%80%D0%B3%D0%B0-%D0%9C%D0%B0%D1%80%D0%BA%D0%B2%D0%B0%D1%80%D0%B4%D1%82%D0%B0»