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

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

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

Версия 12:18, 8 января 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]
К.П. Ловецкий, Л.А. Севастьянов, М. В. Паукшто, О.Н. Бикеев. Математический синтез оптических наноструктур

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

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

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

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

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

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

Источник — «http://www.recognition.su/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»

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

@@ Строка 29: / Строка 29: @@
 <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>
@@ Строка 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>\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>
 ==Преимущества и недостатки метода==

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

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

Версия 12:18, 8 января 2010

Содержание

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

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

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

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

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

Литература

Просмотры

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

Навигация

Поиск

Инструменты