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