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

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 45: Строка 45:
-
[[Категория:Классификация]]
 
-
[[Категория:Машинное обучение]]
 

Версия 22:53, 4 января 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})||=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}) значителен по своей величине, что приводит к некорректной работе и медленной сходимости. Улучшением метода Ньютона-Гаусса является алгоритм Левенберга — Марквардта, основанный на эвристических соображениях.

Литература

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




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

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

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


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