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