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