Алгоритм Левенберга-Марквардта
Материал из MachineLearning.
(Новая: '''Алгоритм Левенберга-Марквардта''' предназначен для оптимизации параметров нелинейных [[регрессионн...) |
(→Описание алгоритма) |
||
(6 промежуточных версий не показаны.) | |||
Строка 1: | Строка 1: | ||
'''Алгоритм Левенберга-Марквардта''' предназначен для оптимизации параметров нелинейных [[регрессионная модель|регрессионных моделей]]. | '''Алгоритм Левенберга-Марквардта''' предназначен для оптимизации параметров нелинейных [[регрессионная модель|регрессионных моделей]]. | ||
Предполагается, что в качестве критерия оптимизации используется [[среднеквадратичная ошибка]] модели на | Предполагается, что в качестве критерия оптимизации используется [[среднеквадратичная ошибка]] модели на | ||
- | [[выборка|обучающей выборке]]. Алгоритм заключается в последовательном приближении заданных начальных значений параметров к | + | [[выборка|обучающей выборке]]. [[Алгоритм]] заключается в последовательном приближении заданных начальных значений параметров к |
искомому локальному оптимуму. | искомому локальному оптимуму. | ||
Алгоритм отличается от [[метод сопряженных градиентов|метода сопряженных градиентов]] тем, что использует | Алгоритм отличается от [[метод сопряженных градиентов|метода сопряженных градиентов]] тем, что использует | ||
[[матрица Якоби|матрицу Якоби]] модели, а не [[градиент]] вектора параметров. | [[матрица Якоби|матрицу Якоби]] модели, а не [[градиент]] вектора параметров. | ||
- | От [[ | + | От [[Метод Ньютона-Гаусса|алгоритма Гаусса-Ньютона]] этот алгоритм отличается тем, |
что использует [[регуляризация|параметр регуляризации]]. | что использует [[регуляризация|параметр регуляризации]]. | ||
Строка 24: | Строка 24: | ||
На каждом шаге итерации этот вектор заменяется на вектор <tex>\mathbf{w}+\Delta\mathbf{w}</tex>. | На каждом шаге итерации этот вектор заменяется на вектор <tex>\mathbf{w}+\Delta\mathbf{w}</tex>. | ||
Для оценки приращения <tex>\Delta\mathbf{w}</tex> используется линейное приближение функции | Для оценки приращения <tex>\Delta\mathbf{w}</tex> используется линейное приближение функции | ||
- | <center><tex>f(\mathbf{w}+\Delta\mathbf{w},\mathbf{x}) | + | <center><tex>f(\mathbf{w}+\Delta\mathbf{w},\mathbf{x}) - f(\mathbf{w},\mathbf{x}) \approx J\Delta\mathbf{w},</tex></center> |
где <tex>J</tex> — якобиан функции <tex>f(\mathbf{w},\mathbf{x}_n)</tex> в точке <tex>\mathbf{w}</tex>. <tex>(N\times R)</tex>-матрицу <tex>J</tex> наглядно можно представить в виде | где <tex>J</tex> — якобиан функции <tex>f(\mathbf{w},\mathbf{x}_n)</tex> в точке <tex>\mathbf{w}</tex>. <tex>(N\times R)</tex>-матрицу <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: | ||
Недостаток алгоритма — значительное увеличение параметра <tex>\lambda</tex> при плохой скорости аппроксимации. | Недостаток алгоритма — значительное увеличение параметра <tex>\lambda</tex> при плохой скорости аппроксимации. | ||
- | При этом обращение матрицы <tex>J^TJ+\lambda I</tex> | + | При этом обращение матрицы <tex>J^TJ+\lambda I</tex> становится бессмысленным. |
- | Этот недостаток можно устранить, используя диагональ матрицы | + | Этот недостаток можно устранить, используя диагональ матрицы <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> | ||
Строка 64: | Строка 64: | ||
* [[Сингулярное разложение]] | * [[Сингулярное разложение]] | ||
* [[Метод наименьших квадратов]] | * [[Метод наименьших квадратов]] | ||
+ | * [[Нелинейная регрессия]] | ||
== Литература == | == Литература == |
Текущая версия
Алгоритм Левенберга-Марквардта предназначен для оптимизации параметров нелинейных регрессионных моделей. Предполагается, что в качестве критерия оптимизации используется среднеквадратичная ошибка модели на обучающей выборке. Алгоритм заключается в последовательном приближении заданных начальных значений параметров к искомому локальному оптимуму.
Алгоритм отличается от метода сопряженных градиентов тем, что использует матрицу Якоби модели, а не градиент вектора параметров. От алгоритма Гаусса-Ньютона этот алгоритм отличается тем, что использует параметр регуляризации.
Содержание |
Постановка задачи
Задана регрессионная выборка — множество пар свободной переменной и зависимой переменной . Задана регрессионная модель — функция непрерывно дифференцируемая в области .
Требуется найти такое значение вектора параметров , которое бы доставляло локальный минимум функции ошибки
Описание алгоритма
Перед началом работы алгоритма задается начальный вектор параметров . На каждом шаге итерации этот вектор заменяется на вектор . Для оценки приращения используется линейное приближение функции
где — якобиан функции в точке . -матрицу наглядно можно представить в виде
Здесь вектор параметров .
Приращение в точке , доставляющий минимум равно нулю (ср. приближение функции рядом Тейлора в статье Оптимальная хирургия мозга). Поэтому для нахождения последующего значения приращения приравняем нулю вектор частных производных по . Для этого представим в виде
где и . Преобразовывая это выражение
и дифференцируя (ср. дифференцирование вектора невязки в статье Метод наименьших квадратов), получим
Таким образом, чтобы найти значение нужно решить систему линейных уравнений
Так как число обусловленности матрицы есть квадрат числа обусловленности матрицы (см. соотв. раздел в статье Сингулярное разложение), то матрица может оказаться существенно вырожденной. Поэтому Марквардт предложил ввести параметр регуляризации ,
где — единичная матрица. Этот параметр назначается на каждой итерации алгоритма. Если значение ошибки убывает быстро, малое значение сводит этот алгоритм к алгоритму Гаусса-Ньютона.
Алгоритм останавливается, в том случае, если приращение в последующей итерации меньше заданного значения, либо если параметры доставляют ошибку меньшую заданной величины. Значение вектора на последней итерации считается искомым.
Недостаток алгоритма — значительное увеличение параметра при плохой скорости аппроксимации. При этом обращение матрицы становится бессмысленным. Этот недостаток можно устранить, используя диагональ матрицы в качестве регуляризующего слагаемого:
Смотри также
Литература
- Levenberg, K. A Method for the Solution of Certain Problems in Last Squares. Quart. Appl. Math. 1944. Vol. 2. P. 164—168.
- Демиденко Е. З. Оптимизация и регрессия. М. Наука. 1989.