Метод Ньютона-Гаусса
Материал из MachineLearning.
(→Связь с итерационным методом Ньютона) |
|||
Строка 29: | Строка 29: | ||
<tex>H(\vec{x}) = J^T(\vec{x})J(\vec{x}) + Q(\vec{x})</tex>, где <br><br> | <tex>H(\vec{x}) = J^T(\vec{x})J(\vec{x}) + Q(\vec{x})</tex>, где <br><br> | ||
<tex>Q(\vec{x}) = \sum_{i=1}^m H_i(\vec{x})F_i(\vec{x})</tex><br> | <tex>Q(\vec{x}) = \sum_{i=1}^m H_i(\vec{x})F_i(\vec{x})</tex><br> | ||
- | Здесь под <tex>H_i(\vec{x})</tex> имеется ввиду [[матрица Гесса]] для функции <tex>F_i(\vec{x})</tex> ( i-ая компонента вектора <tex>\vec{F}(\vec{x}) </tex> ). <tex>J(\vec{x})</tex> - матрица Якоби для функции <tex>f(\vec{x})</tex><br> | + | Здесь под <tex>H_i(\vec{x})</tex> имеется ввиду [[Вычисление матриц Якоби и Гессе|матрица Гесса]] для функции <tex>F_i(\vec{x})</tex> ( i-ая компонента вектора <tex>\vec{F}(\vec{x}) </tex> ). <tex>J(\vec{x})</tex> - матрица Якоби для функции <tex>f(\vec{x})</tex><br> |
Если использовать итерационный процесс Ньютона для минимизации <tex>f(\vec{x})</tex>, то формула для обновления <tex>\vec{x_j}</tex> будет следующая:<br> | Если использовать итерационный процесс Ньютона для минимизации <tex>f(\vec{x})</tex>, то формула для обновления <tex>\vec{x_j}</tex> будет следующая:<br> | ||
Строка 35: | Строка 35: | ||
Метод Ньютона - Гаусса строится на предположении о том, что <tex>||J^T(\vec{x})J(\vec{x})|| >>||Q(\vec{x})||</tex>, то есть слагаемое <tex>J^T(\vec{x})J(\vec{x})</tex> доминирует над <tex>Q(\vec{x})</tex>. Также такое приближение возможно при условии, что <tex>||Q(\vec{x})||</tex> близко к 0. Это требование не соблюдается, если минимальные невязки велики, то есть если норма <tex>||F(\vec{x})||</tex>сравнима с максимальным собственным значением матрицы <tex>J^T(\vec{x})J(\vec{x})</tex>. В противном случае пренебрегаем <tex>Q(\vec{x})</tex> и получаем итерационную процедуру с формулой для обновления <tex>\vec{x_{j+1}}</tex>:<br> | Метод Ньютона - Гаусса строится на предположении о том, что <tex>||J^T(\vec{x})J(\vec{x})|| >>||Q(\vec{x})||</tex>, то есть слагаемое <tex>J^T(\vec{x})J(\vec{x})</tex> доминирует над <tex>Q(\vec{x})</tex>. Также такое приближение возможно при условии, что <tex>||Q(\vec{x})||</tex> близко к 0. Это требование не соблюдается, если минимальные невязки велики, то есть если норма <tex>||F(\vec{x})||</tex>сравнима с максимальным собственным значением матрицы <tex>J^T(\vec{x})J(\vec{x})</tex>. В противном случае пренебрегаем <tex>Q(\vec{x})</tex> и получаем итерационную процедуру с формулой для обновления <tex>\vec{x_{j+1}}</tex>:<br> | ||
::<tex>\vec{x_{j+1}} = \vec{x_{j}} - (J^T(\vec{x_{j}})J(\vec{x_{j}}))^{-1}J^T(\vec{x_{j}})F(\vec{x_{j}}) </tex> | ::<tex>\vec{x_{j+1}} = \vec{x_{j}} - (J^T(\vec{x_{j}})J(\vec{x_{j}}))^{-1}J^T(\vec{x_{j}})F(\vec{x_{j}}) </tex> | ||
- | |||
==Преимущества и недостатки метода== | ==Преимущества и недостатки метода== |
Версия 12:18, 8 января 2010
Метод Ньютона-Гаусса — это итерационный численный метод нахождения решения задачи наименьших квадратов. Является разновидностью метода Ньютона. В общих чертах, этот метод использует матрицу Якобиана J производных первого порядка функции F для нахождения вектора x значений параметра, который минимизирует остаточные суммы квадратов (сумму квадратных отклонений предсказанных значений от наблюдаемых). Усовершенствованная и полезная версия метода — это так называемый метод Левенберга-Марквардта.
Содержание |
Описание метода
В методе наименьших квадратов подлежащая минимизации функция f(x) представляет собой сумму квадратов.
Под имеется ввиду следующий вектор-столбец:
Подобного типа задачи широко распространены и имеют ряд практических применений, особенно при подборе модельной функции для некого набора данных, т.е. подбор нелинейных параметров. Пусть - матрица Якоби для функции , то есть
, где из
Выбирая некоторое начальное значение последовательные приближения находят следующим образом:
Обоснование метода
Связь с итерационным методом Ньютона
Пусть необходимо найти экстремум функции многих переменных . Это равносильно нахождению точки . Если для решения этой задачи использовать итерационный метод Ньютона (метод касательных), то формула обновления для выглядит следующим образом:
Здесь под имеется ввиду матрица Гесса функции , то есть матрица вторых производных:
Когда рассматривается задача наименьших квадратов
градиент и матрица Гесса для функции принимают особый вид:
, где
Здесь под имеется ввиду матрица Гесса для функции ( i-ая компонента вектора ). - матрица Якоби для функции
Если использовать итерационный процесс Ньютона для минимизации , то формула для обновления будет следующая:
Метод Ньютона - Гаусса строится на предположении о том, что , то есть слагаемое доминирует над . Также такое приближение возможно при условии, что близко к 0. Это требование не соблюдается, если минимальные невязки велики, то есть если норма сравнима с максимальным собственным значением матрицы . В противном случае пренебрегаем и получаем итерационную процедуру с формулой для обновления :
Преимущества и недостатки метода
В стандартном итерационном методе Ньютона на каждой итерации требуется вычисление и обращение матрицы Гесса, что зачастую является достаточно сложным процессом. В методе Ньютона-Гаусса подобная необходимость отпадает, причем скорость сходимости также может достигать квадратичной, хотя вторые производные и не учитываются. Также данный метод прост в реализации и присутствует в большинстве программных пакетов по прикладной математике. Тем не менее, в методе Ньютона-Гаусса часто встречается ряд проблем в ситуации, когда член второго порядка значителен по своей величине, что приводит к некорректной работе и медленной сходимости. Улучшением метода Ньютона-Гаусса является алгоритм Левенберга - Марквардта, основанный на эвристических соображениях.
Связь метода с многомерной линейной регрессией
Пусть задана обучающая выборка объектов и значений где из , а из . Задача состоит в том, чтобы восстановить отображение . Общий вид отображения будем искать в виде , где — вектор неизвестных параметров из , которые необходимо восстановить. Параметры восстанавливаются таким образом, чтобы функционал
.
Данная задача может быть решена с помощью метода Ньютона-Гаусса. Пусть нам известно i–ое приближение точки минимума . Рассмотрим более подробно процесс получения приближения . Разложим функцию в ряд Тейлора до первого члена в окрестности точки :
.
Следующее приближение будем искать таким образом, чтобы функционал
.
подставляя выражение для , получаем задачу восстановления многомерной линейной регрессии по методу наименьших квадратов. Выпишем ее решение в общем виде:
, где
— матрица частных производных, а
.
Выражая получаем итерационную формулу из метода Ньютона-Гаусса:
- .
- .
Таким образом было показано, что сложную задачу нелинейной регрессии получается свести к серии более простых стандартных задач линейной регрессии, которые решаются на каждой итерации.
Литература
- Машинное обучение (курс лекций, К.В.Воронцов)
- [1]
- [2]
- К.П. Ловецкий, Л.А. Севастьянов, М. В. Паукшто, О.Н. Бикеев. Математический синтез оптических наноструктур
Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |