Метод Ньютона-Гаусса
Материал из MachineLearning.
Строка 1: | Строка 1: | ||
Метод Ньютона-Гаусса - это итерационный численный метод нахождения решения задачи наименьших квадратов. Является разновидностью метода Ньютона. В общих чертах, этот метод использует матрицу Якобиана J производных первого порядка функции F для нахождения вектора x значений параметра, который минимизирует остаточные суммы квадратов (сумму квадратных отклонений предсказанных значений от наблюдаемых). Усовершенствованная и полезная версия метода - это так называемый метод Левенберга-Марквардта. | Метод Ньютона-Гаусса - это итерационный численный метод нахождения решения задачи наименьших квадратов. Является разновидностью метода Ньютона. В общих чертах, этот метод использует матрицу Якобиана J производных первого порядка функции F для нахождения вектора x значений параметра, который минимизирует остаточные суммы квадратов (сумму квадратных отклонений предсказанных значений от наблюдаемых). Усовершенствованная и полезная версия метода - это так называемый метод Левенберга-Марквардта. | ||
- | + | =Описание метода= | |
В методе наименьших квадратов подлежащая минимизации функция f(x) представляет собой сумму квадратов.<br> | В методе наименьших квадратов подлежащая минимизации функция f(x) представляет собой сумму квадратов.<br> | ||
Строка 16: | Строка 16: | ||
::<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> | ||
- | + | =Обоснование метода= | |
+ | ==Связь с итерационным методом Ньютона== | ||
Пусть необходимо найти экстремум функции многих переменных <tex>f(\vec{x}):\: \mathbb{R}^m \to \mathbb{R}</tex>. Это равносильно нахождению точки <tex>\vec{x^*}:\: grad[f](\vec{x^*}) = \vec{0}</tex>. Если для решения этой задачи использовать итерационный метод Ньютона (метод касательных), то формула обновления для <tex>\vec{x_j}</tex> выглядит следующим образом: <br> | Пусть необходимо найти экстремум функции многих переменных <tex>f(\vec{x}):\: \mathbb{R}^m \to \mathbb{R}</tex>. Это равносильно нахождению точки <tex>\vec{x^*}:\: grad[f](\vec{x^*}) = \vec{0}</tex>. Если для решения этой задачи использовать итерационный метод Ньютона (метод касательных), то формула обновления для <tex>\vec{x_j}</tex> выглядит следующим образом: <br> | ||
:<tex>\vec{x_{j+1}} = \vec{x_j} - H^{-1}(\vec{x_j})grad[f](\vec{x^*})</tex> | :<tex>\vec{x_{j+1}} = \vec{x_j} - H^{-1}(\vec{x_j})grad[f](\vec{x^*})</tex> | ||
Строка 34: | Строка 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> | ||
+ | |||
==Преимущества и недостатки метода== | ==Преимущества и недостатки метода== | ||
В стандартном итерационном методе Ньютона на каждой итерации требуется вычисление и обращение матрицы Гесса, что зачастую является достаточно сложным процессом. В методе Ньютона-Гаусса подобная необходимость отпадает, причем скорость сходимости также может достигать квадратичной,, хотя вторые производные и не учитываются. Также данный метод прост в реализации и присутствует в большинстве программных пакетов по прикладной математике. Тем не менее, в методе Ньютона-Гаусса часто встречается ряд проблем в ситуации, когда член второго порядка <tex>Q(\vec{x})</tex> значителен по своей величине, что приводит к некорректной работе и медленной сходимости. Улучшением метода Ньютона-Гаусса является алгоритм Левенберга — Марквардта, основанный на эвристических соображениях. | В стандартном итерационном методе Ньютона на каждой итерации требуется вычисление и обращение матрицы Гесса, что зачастую является достаточно сложным процессом. В методе Ньютона-Гаусса подобная необходимость отпадает, причем скорость сходимости также может достигать квадратичной,, хотя вторые производные и не учитываются. Также данный метод прост в реализации и присутствует в большинстве программных пакетов по прикладной математике. Тем не менее, в методе Ньютона-Гаусса часто встречается ряд проблем в ситуации, когда член второго порядка <tex>Q(\vec{x})</tex> значителен по своей величине, что приводит к некорректной работе и медленной сходимости. Улучшением метода Ньютона-Гаусса является алгоритм Левенберга — Марквардта, основанный на эвристических соображениях. | ||
+ | |||
+ | ==Связь метода с многомерной линейной регрессией== | ||
+ | Пусть задана обучающая выборка объектов <tex>X^l</tex> и значений <tex>Y^l</tex> где <tex>\vec{x_i}</tex> из <tex>\mathbb{R}^m</tex>, а <tex>y_i</tex> из <tex>\mathbb{R}</tex>. Задача состоит в том, чтобы восстановить отображение <tex>y^*(\vec{x}):\mathbb{R}^m \to \mathbb{R}</tex>. Общий вид отображения <tex>y^*(\vec{x})</tex> будем искать в виде <tex>f(\vec{x},\vec{\alpha})</tex>, где <tex>\vec{\alpha}</tex> — вектор неизвестных параметров из <tex>\mathbb{R}^k</tex>, которые необходимо восстановить. Параметры восстанавливаются таким образом, чтобы функционал <br> | ||
+ | <tex>Q(\vec{\alpha}) = \sum_{i=1}^l (f(\vec{x_i},\vec{\alpha}) - y_i)^2 \to min_{\vec{\alpha}}</tex>.<br> | ||
+ | Данная задача может быть решена с помощью метода Ньютона-Гаусса. Пусть нам известно i–ое приближение точки минимума <tex>\vec{\alpha^{(i)}</tex>. Рассмотрим более подробно процесс получения приближения <tex>\vec{\alpha^{(i+1)}</tex>. Разложим функцию <tex>f( \vec{x_j},\vec{\alpha^{(i)} )</tex> в ряд Тейлора до первого члена в окрестности точки <tex>\vec{\alpha^{(i)}}</tex> :<br><br> | ||
+ | <tex>f^1(\vec{x_j},\vec{\alpha}) = f(\vec{x_j},\vec{\alpha^{(i)}}) + \sum_{n=1}^k \frac{\partial f}{\partial \alpha_n }(\vec{x_j},\vec{\alpha^{(i)}})(\vec{\alpha_n} - \vec{\alpha^{(i)}_n})</tex>. | ||
+ | Следующее приближение <tex>\vec{\alpha^{(i+1)}</tex> будем искать таким образом, чтобы функционал <br><br> | ||
+ | <tex>Q^1(\vec{\alpha}) = \sum_{j=1}^l (f^1(\vec{x_j},\vec{\alpha}) - y_j)^2 \to min_{\vec{\alpha}}</tex>.<br> | ||
+ | подставляя выражение для <tex>f^1(\vec{x_i},\vec{\alpha})</tex>, получаем задачу восстановления многомерной линейной регрессии по методу наименьших квадратов. Выпишем ее решение в общем виде: <br> | ||
+ | <tex>(\vec{\alpha^{(i+1)}} - \vec{\alpha^{(i)}}) = (F^T_i F_i)^{-1}F^T_i(y - f_i)</tex>, где <br> | ||
+ | <tex>F_i = [\frac{\partial f}{\partial \alpha_n }(\vec{x_j},\vec{\alpha^{(i)}})]_{j=1, n=1}^{l, k}</tex> - матрица частных производных, а <br> | ||
+ | <tex> y = [y_j]_{j=1}^l, <br> | ||
+ | f_i = [ f(\vec{x_j},\vec{\alpha^{(i)}}) ]_{j=1}^l</tex>.<br><br> Выражая <tex>\vec{\alpha^{(i+1)}}</tex> получаем метод Ньютона-Гаусса: <br> | ||
+ | ::<tex>\vec{\alpha^{(i+1)}} = \vec{\alpha^{(i)}} - (F^T_i F_i)^{-1}F^T_i(f_i - y)</tex>.<br><br> | ||
+ | Таким образом было показано, что сложную задачу нелинейной регрессии получается свести к серии более простых стандартных задач линейной регрессии, которые решаются на каждой итерации. | ||
+ | |||
==Литература== | ==Литература== |
Версия 19:47, 6 января 2010
Метод Ньютона-Гаусса - это итерационный численный метод нахождения решения задачи наименьших квадратов. Является разновидностью метода Ньютона. В общих чертах, этот метод использует матрицу Якобиана J производных первого порядка функции F для нахождения вектора x значений параметра, который минимизирует остаточные суммы квадратов (сумму квадратных отклонений предсказанных значений от наблюдаемых). Усовершенствованная и полезная версия метода - это так называемый метод Левенберга-Марквардта.
Содержание |
Описание метода
В методе наименьших квадратов подлежащая минимизации функция f(x) представляет собой сумму квадратов.
Под имеется ввиду следующий вектор-столбец:
Подобного типа задачи широко распространены и имеют ряд практических применений, особенно при подборе модельной функции для некого набора данных, т.е. подбор нелинейных параметров. Пусть - матрица Якоби для функции
, то есть
, где
из
Выбирая некоторое начальное значение последовательные приближения
находят следующим образом:
Обоснование метода
Связь с итерационным методом Ньютона
Пусть необходимо найти экстремум функции многих переменных . Это равносильно нахождению точки
. Если для решения этой задачи использовать итерационный метод Ньютона (метод касательных), то формула обновления для
выглядит следующим образом:
Здесь под имеется ввиду матрица Гесса функции
, то есть матрица вторых производных:
Когда рассматривается задача наименьших квадратов
градиент и матрица Гесса для функции принимают особый вид:
, где
Здесь под имеется ввиду матрица Гесса для функции
( i-ая компонента вектора
).
- матрица Якоби для функции
Если использовать итерационный процесс Ньютона для минимизации , то формула для обновления
будет следующая:
Метод Ньютона — Гаусса строится на предположении о том, что , то есть слагаемое
доминирует над
. Также такое приближение возможно при условии, что
близко к 0. Это требование не соблюдается, если минимальные невязки велики, то есть если норма
сравнима с максимальным собственным значением матрицы
. В противном случае пренебрегаем
и получаем итерационную процедуру с формулой для обновления
:
Преимущества и недостатки метода
В стандартном итерационном методе Ньютона на каждой итерации требуется вычисление и обращение матрицы Гесса, что зачастую является достаточно сложным процессом. В методе Ньютона-Гаусса подобная необходимость отпадает, причем скорость сходимости также может достигать квадратичной,, хотя вторые производные и не учитываются. Также данный метод прост в реализации и присутствует в большинстве программных пакетов по прикладной математике. Тем не менее, в методе Ньютона-Гаусса часто встречается ряд проблем в ситуации, когда член второго порядка значителен по своей величине, что приводит к некорректной работе и медленной сходимости. Улучшением метода Ньютона-Гаусса является алгоритм Левенберга — Марквардта, основанный на эвристических соображениях.
Связь метода с многомерной линейной регрессией
Пусть задана обучающая выборка объектов и значений
где
из
, а
из
. Задача состоит в том, чтобы восстановить отображение
. Общий вид отображения
будем искать в виде
, где
— вектор неизвестных параметров из
, которые необходимо восстановить. Параметры восстанавливаются таким образом, чтобы функционал
.
Данная задача может быть решена с помощью метода Ньютона-Гаусса. Пусть нам известно i–ое приближение точки минимума . Рассмотрим более подробно процесс получения приближения
. Разложим функцию
в ряд Тейлора до первого члена в окрестности точки
:
.
Следующее приближение
будем искать таким образом, чтобы функционал
.
подставляя выражение для , получаем задачу восстановления многомерной линейной регрессии по методу наименьших квадратов. Выпишем ее решение в общем виде:
, где
- матрица частных производных, а
.
Выражая получаем метод Ньютона-Гаусса:
.
Таким образом было показано, что сложную задачу нелинейной регрессии получается свести к серии более простых стандартных задач линейной регрессии, которые решаются на каждой итерации.
Литература
- Машинное обучение (курс лекций, К.В.Воронцов)
- [1]
- [2]
- К.П. Ловецкий, Л.А. Севастьянов, М. В. Паукшто, О.Н. Бикеев. Математический синтез оптических наноструктур
![]() | Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |