Метод Ньютона-Гаусса

Материал из MachineLearning.

(Различия между версиями)

Текущая версия

Метод Ньютона-Гаусса — это итерационный численный метод нахождения решения задачи наименьших квадратов. Является разновидностью метода Ньютона. В общих чертах, этот метод использует матрицу Якобиана J производных первого порядка функции F для нахождения вектора x значений параметра, который минимизирует остаточные суммы квадратов (сумму квадратных отклонений предсказанных значений от наблюдаемых). Усовершенствованная и полезная версия метода — это так называемый метод Левенберга-Марквардта.

Описание метода

В методе наименьших квадратов подлежащая минимизации функция f(x) представляет собой сумму квадратов.

$f(\vec{x}) = ||\vec{F}(\vec{x})||^2 = \textstyle\sum_{k=1}^n\ ( g_k(\vec{x}) - a_k )^2$

Под $F(\vec{x})$ имеется ввиду следующий вектор-столбец:
$[( g_k(\vec{x}) - a_k )]_{k=1}^n$

Подобного типа задачи широко распространены и имеют ряд практических применений, особенно при подборе модельной функции для некого набора данных, т.е. подбор нелинейных параметров. Пусть $J(\vec{x})$ - матрица Якоби для функции $F(\vec{x})$ , то есть
$J(\vec{x}) = [\frac{\partial g_i(\vec{x})}{\partial x_j }]_{i=1,j=1 }^{n, m}$ , где $\vec{x}$ из $\mathbb{R}^m$

Выбирая некоторое начальное значение $\vec{x_0}$ последовательные приближения $\vec{x_{j+1}}$ находят следующим образом:

$\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}})$

Обоснование метода

Связь с итерационным методом Ньютона

Пусть необходимо найти экстремум функции многих переменных $f(\vec{x}):\: \mathbb{R}^m \to \mathbb{R}$ . Это равносильно нахождению точки $\vec{x^*}:\: grad[f](\vec{x^*}) = \vec{0}$ . Если для решения этой задачи использовать итерационный метод Ньютона (метод касательных), то формула обновления для $\vec{x_j}$ выглядит следующим образом:

$\vec{x_{j+1}} = \vec{x_j} - H^{-1}(\vec{x_j})grad[f](\vec{x^*})$

Здесь под $H(\vec{x})$ имеется ввиду матрица Гесса функции $f(\vec{x})$ , то есть матрица вторых производных:
$H(\vec{x}) = [\frac{\partial f(\vec{x})}{\partial x_i\partial x_j }]_{i=1,j=1 }^{m}$

Когда рассматривается задача наименьших квадратов
$f(\vec{x})=1/2||\vec{F}(\vec{x})||^2=1/2\sum_{i=1}^m F_i^2(\vec{x})=1/2\sum_{i=1}^m (\varphi_i(\vec{x})-\mathcal{F}_i)^2\to\min,$
градиент и матрица Гесса для функции $f(\vec{x})$ принимают особый вид:
$grad[f](\vec{x}) = J^T(\vec{x})\vec{F}(\vec{x})$

$H(\vec{x}) = J^T(\vec{x})J(\vec{x}) + Q(\vec{x})$ , где

$Q(\vec{x}) = \sum_{i=1}^m H_i(\vec{x})F_i(\vec{x})$
Здесь под $H_i(\vec{x})$ имеется ввиду матрица Гесса для функции $F_i(\vec{x})$ ( i-ая компонента вектора $\vec{F}(\vec{x})$ ). $J(\vec{x})$ - матрица Якоби для функции $f(\vec{x})$
Если использовать итерационный процесс Ньютона для минимизации $f(\vec{x})$ , то формула для обновления $\vec{x_j}$ будет следующая:

$\vec{x_{j+1}} = \vec{x_{j}} - \left[J^T(\vec{x})J(\vec{x})+\sum_{i=1}^m \vec{F}_i(\vec{x})H_i(\vec{x})\right]^{-1}J^T(\vec{x})\vec{F}(\vec{x}).$

Метод Ньютона - Гаусса строится на предположении о том, что $||J^T(\vec{x})J(\vec{x})|| >>||Q(\vec{x})||$ , то есть слагаемое $J^T(\vec{x})J(\vec{x})$ доминирует над $Q(\vec{x})$ . Также такое приближение возможно при условии, что $||Q(\vec{x})||$ близко к 0. Это требование не соблюдается, если минимальные невязки велики, то есть если норма $||F(\vec{x})||$ сравнима с максимальным собственным значением матрицы $J^T(\vec{x})J(\vec{x})$ . В противном случае пренебрегаем $Q(\vec{x})$ и получаем итерационную процедуру с формулой для обновления $\vec{x_{j+1}}$ :

$\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}})$

Преимущества и недостатки метода

В стандартном итерационном методе Ньютона на каждой итерации требуется вычисление и обращение матрицы Гесса, что зачастую является достаточно сложным процессом. В методе Ньютона-Гаусса подобная необходимость отпадает, причем скорость сходимости также может достигать квадратичной, хотя вторые производные и не учитываются. Также данный метод прост в реализации и присутствует в большинстве программных пакетов по прикладной математике. Тем не менее, в методе Ньютона-Гаусса часто встречается ряд проблем в ситуации, когда член второго порядка $Q(\vec{x})$ значителен по своей величине, что приводит к некорректной работе и медленной сходимости. Улучшением метода Ньютона-Гаусса является алгоритм Левенберга - Марквардта, основанный на эвристических соображениях.

Связь метода с многомерной линейной регрессией

Пусть задана обучающая выборка объектов $X^l$ и значений $Y^l$ где $\vec{x_i}$ из $\mathbb{R}^m$ , а $y_i$ из $\mathbb{R}$ . Задача состоит в том, чтобы восстановить отображение $y^*(\vec{x}):\mathbb{R}^m \to \mathbb{R}$ . Общий вид отображения $y^*(\vec{x})$ будем искать в виде $f(\vec{x},\vec{\alpha})$ , где $\vec{\alpha}$ — вектор неизвестных параметров из $\mathbb{R}^k$ , которые необходимо восстановить. Параметры восстанавливаются таким образом, чтобы функционал
$Q(\vec{\alpha}) = \sum_{i=1}^l (f(\vec{x_i},\vec{\alpha}) - y_i)^2 \to min_{\vec{\alpha}}$ .
Данная задача может быть решена с помощью метода Ньютона-Гаусса. Пусть нам известно i–ое приближение точки минимума $\vec{\alpha^{(i)}$ . Рассмотрим более подробно процесс получения приближения $\vec{\alpha^{(i+1)}$ . Разложим функцию $f( \vec{x_j},\vec{\alpha^{(i)} )$ в ряд Тейлора до первого члена в окрестности точки $\vec{\alpha^{(i)}}$ :

$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})$ . Следующее приближение $\vec{\alpha^{(i+1)}$ будем искать таким образом, чтобы функционал

$Q^1(\vec{\alpha}) = \sum_{j=1}^l (f^1(\vec{x_j},\vec{\alpha}) - y_j)^2 \to min_{\vec{\alpha}}$ .
подставляя выражение для $f^1(\vec{x_i},\vec{\alpha})$ , получаем задачу восстановления многомерной линейной регрессии по методу наименьших квадратов. Выпишем ее решение в общем виде:
$(\vec{\alpha^{(i+1)}} - \vec{\alpha^{(i)}}) = (F^T_i F_i)^{-1}F^T_i(y - f_i)$ , где
$F_i = [\frac{\partial f}{\partial \alpha_n }(\vec{x_j},\vec{\alpha^{(i)}})]_{j=1, n=1}^{l, k}$ — матрица частных производных, а
$y = [y_j]_{j=1}^l, <br> f_i = [ f(\vec{x_j},\vec{\alpha^{(i)}}) ]_{j=1}^l$ .

Выражая $\vec{\alpha^{(i+1)}}$ получаем итерационную формулу из метода Ньютона-Гаусса:

$\vec{\alpha^{(i+1)}} = \vec{\alpha^{(i)}} - (F^T_i F_i)^{-1}F^T_i(f_i - y)$ .

Таким образом было показано, что сложную задачу нелинейной регрессии получается свести к серии более простых стандартных задач линейной регрессии, которые решаются на каждой итерации.

Литература

Машинное обучение (курс лекций, К.В.Воронцов)
[1]
[2]
К.П. Ловецкий, Л.А. Севастьянов, М. В. Паукшто, О.Н. Бикеев. Математический синтез оптических наноструктур

Данная статья является непроверенным учебным заданием.

Студент: Участник:DenisGKolev

Преподаватель: Участник:Константин Воронцов

Срок: 6 января 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%9D%D1%8C%D1%8E%D1%82%D0%BE%D0%BD%D0%B0-%D0%93%D0%B0%D1%83%D1%81%D1%81%D0%B0»

Категории: Непроверенные учебные задания | Нелинейная регрессия

@@ Строка 1: / Строка 1: @@
-Метод Ньютона-Гаусса - это итерационный численный метод нахождения решения задачи наименьших квадратов. Является разновидностью метода Ньютона. В общих чертах, этот метод использует матрицу Якобиана J производных первого порядка  функции F для нахождения вектора x значений параметра, который минимизирует остаточные суммы квадратов (сумму квадратных отклонений предсказанных значений от наблюдаемых). Усовершенствованная и полезная версия метода - это так называемый метод Левенберга-Марквардта.
+Метод Ньютона-Гаусса — это итерационный численный метод нахождения решения задачи наименьших квадратов. Является разновидностью [[Метод Ньютона. Проблема области сходимости. Метод парабол. Совмещение методов Ньютона и парабол|метода Ньютона]]. В общих чертах, этот метод использует матрицу Якобиана J производных первого порядка  функции F для нахождения вектора x значений параметра, который минимизирует остаточные суммы квадратов (сумму квадратных отклонений предсказанных значений от наблюдаемых). Усовершенствованная и полезная версия метода — это так называемый метод Левенберга-Марквардта.
-==Описание метода==
+=Описание метода=
 В методе наименьших квадратов подлежащая минимизации функция f(x) представляет собой сумму квадратов.<br>
@@ Строка 9: / Строка 9: @@
 <tex>[( g_k(\vec{x}) - a_k )]_{k=1}^n</tex>
-Подобного типа задачи широко распространены и имеют ряд практических применений, особенно при подборе модельной функции для некого набора данных, т.е. подбор нелинейных параметров. Пусть <tex>J(\vec{x})</tex> - матрица Якоби для функции <tex>F(\vec{x})</tex>, то есть<br>
+Подобного типа задачи широко распространены и имеют ряд практических применений, особенно при подборе модельной функции для некого набора данных, т.е. подбор нелинейных параметров. Пусть <tex>J(\vec{x})</tex> - [[Вычисление матриц Якоби и Гессе|матрица Якоби]] для функции <tex>F(\vec{x})</tex>, то есть<br>
 <tex>J(\vec{x}) = [\frac{\partial g_i(\vec{x})}{\partial x_j }]_{i=1,j=1 }^{n, m}</tex> , где <tex>\vec{x}</tex> из <tex>\mathbb{R}^m</tex>
@@ Строка 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>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>
@@ Строка 23: / Строка 24: @@
 Когда рассматривается задача наименьших квадратов <br>
-<tex>f(\vec{x})=1/2||\vec{F}(\vec{x})||=1/2\sum_{i=1}^m F_i^2(\vec{x})=1/2\sum_{i=1}^m (\varphi_i(\vec{x})-\mathcal{F}_i)^2\to\min,</tex><br>
+<tex>f(\vec{x})=1/2||\vec{F}(\vec{x})||^2=1/2\sum_{i=1}^m F_i^2(\vec{x})=1/2\sum_{i=1}^m (\varphi_i(\vec{x})-\mathcal{F}_i)^2\to\min,</tex><br>
 градиент и матрица Гесса для функции <tex>f(\vec{x})</tex> принимают особый вид:<br>
 <tex>grad[f](\vec{x}) = J^T(\vec{x})\vec{F}(\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>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>\vec{x_{j+1}} = \vec{x_{j}} - \left[J^T(\vec{x})J(\vec{x})+\sum_{i=1}^m \vec{F}_i(\vec{x})H_i(\vec{x})\right]^{-1}J^T(\vec{x})\vec{F}(\vec{x}).</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>||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>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>
+Таким образом было показано, что сложную задачу нелинейной регрессии получается свести к серии более простых стандартных задач линейной регрессии, которые решаются на каждой итерации.
+=Литература=
 #[[Машинное обучение (курс лекций, К.В.Воронцов)]]
 #[http://ru.wikipedia.org/wiki/Метод_Ньютона]
@@ Строка 45: / Строка 62: @@
-[[Категория:Классификация]]
-[[Категория:Машинное обучение]]
@@ Строка 53: / Строка 68: @@
 {{Задание|DenisGKolev|Константин Воронцов|6 января 2010}}
+[[Категория:Нелинейная регрессия]]

Метод Ньютона-Гаусса

Материал из MachineLearning.

Текущая версия

Содержание

Описание метода

Обоснование метода

Связь с итерационным методом Ньютона

Преимущества и недостатки метода

Связь метода с многомерной линейной регрессией

Литература

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты