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

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

(Различия между версиями)
Перейти к: навигация, поиск
(поправил ссылку)
 
(13 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
Метод Ньютона-Гаусса - это итерационный численный метод нахождения решения задачи наименьших квадратов. Является разновидностью метода Ньютона. В общих чертах, этот метод использует матрицу Якобиана J производных первого порядка функции F для нахождения вектора x значений параметра, который минимизирует остаточные суммы квадратов (сумму квадратных отклонений предсказанных значений от наблюдаемых). Усовершенствованная и полезная версия метода - это так называемый метод Левенберга-Марквардта.
+
Метод Ньютона-Гаусса это итерационный численный метод нахождения решения задачи наименьших квадратов. Является разновидностью [[Метод Ньютона. Проблема области сходимости. Метод парабол. Совмещение методов Ньютона и парабол|метода Ньютона]]. В общих чертах, этот метод использует матрицу Якобиана J производных первого порядка функции F для нахождения вектора x значений параметра, который минимизирует остаточные суммы квадратов (сумму квадратных отклонений предсказанных значений от наблюдаемых). Усовершенствованная и полезная версия метода это так называемый метод Левенберга-Марквардта.
-
==Описание метода==
+
=Описание метода=
В методе наименьших квадратов подлежащая минимизации функция f(x) представляет собой сумму квадратов.<br>
В методе наименьших квадратов подлежащая минимизации функция f(x) представляет собой сумму квадратов.<br>
Строка 9: Строка 9:
<tex>[( g_k(\vec{x}) - a_k )]_{k=1}^n</tex>
<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>
<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>\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>
Строка 28: Строка 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>
::<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>\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>\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/Метод_Ньютона]
#[http://ru.wikipedia.org/wiki/Метод_Ньютона]
Строка 51: Строка 68:
{{Задание|DenisGKolev|Константин Воронцов|6 января 2010}}
{{Задание|DenisGKolev|Константин Воронцов|6 января 2010}}
 +
 +
[[Категория:Нелинейная регрессия]]

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

Метод Ньютона-Гаусса — это итерационный численный метод нахождения решения задачи наименьших квадратов. Является разновидностью метода Ньютона. В общих чертах, этот метод использует матрицу Якобиана 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. [1]
  3. [2]
  4. К.П. Ловецкий, Л.А. Севастьянов, М. В. Паукшто, О.Н. Бикеев. Математический синтез оптических наноструктур





Данная статья является непроверенным учебным заданием.
Студент: Участник:DenisGKolev
Преподаватель: Участник:Константин Воронцов
Срок: 6 января 2010

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

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

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