Метод наименьших квадратов с итеративным пересчётом весов

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 1: Строка 1:
-
'''Метод наименьших квадратов с итеративным пересчётом весов''' (IRLS) - алгоритм, использующийся для настройки вектора весов в задаче [[логистическая регрессия|логистической регрессии]].
+
'''Метод наименьших квадратов с итеративным пересчётом весов''' (IRLS) - алгоритм, использующийся для решения некоторых оптимизационных задач. В частности, с помощью этого метода можно решать задачи вида:
 +
::<tex> \mathrm{arg}\min_{\beta} \sum_{i=1}^n w_i(\beta)| y_i - f_i (\beta) | ^ 2 </tex>
 +
Алгоритм является итеративным. На каждом шаге алгоритма решается задача [http://en.wikipedia.org/wiki/Weighted_least_squares#Weighted_least_squares Взвешенных наименьших квадратов]:
 +
::<tex> \beta ^ {(t + 1)} = \mathrm{arg}\min_{\beta} \sum_{i=1}^n w_i(\beta ^ {(t)})| y_i - f_i (\beta) | ^ 2 </tex>
 +
=Основные шаги алгоритма=
 +
#Выбор начального приближения для вектора параметров <tex> \beta </tex>
 +
##Здесь можно использовать обычный метод наименьших квадратов (потом подробнее)
 +
#Решение задачи взвешенных наименьших квадратов
 +
##При решении этой задачи можно использовать, например, алгоритм сопряженных градиентов.
 +
#Пересчет вектора весов, если нужно.
 +
#Оценка измененного решения
 +
#Переход на шаг #2
 +
 +
=Пример работы алгоритма=
 +
Приведем пример работы алгоритма для решения задач [[логистической регрессии]].
 +
 +
Пусть задано пространство объектов X и множество возможных ответов Y. Существует неизвестная целевая зависимость <tex>y∗ : X → Y</tex> , значения которой известны только на объектах обучающей выборки.
 +
 +
=Сходимость алгоритма=
 +
Метод сходится не всегда. Например, (вставляем пример из wikidoc).
 +
 +
=Литература=
 +
Ф.П. Васильев Численные методы решения экстремальных задач - М.: Наука, 1980. — 307 с.
 +
 +
=Ссылки=
 +
[http://en.wikipedia.org/wiki/Iteratively_reweighted_least_squares Wikipedia: Iteratively reweighted least squares]<br />
 +
[http://www.wikidoc.org/index.php/Iteratively_re-weighted_least_squares Wicidoc: Iteratively re-weighted least squares]<br />
 +
[http://mmphome.1gb.ru/data/doc/4course/mfft/lecture1.pdf Ю. И. Журавлев, Д. П. Ветров: Обобщенные Линейные Модели: Метод IRLS]
[[Категория:Машинное обучение]]
[[Категория:Машинное обучение]]
{{Задание|Сидоров Юрий|Константин Воронцов|4 января 2010}}
{{Задание|Сидоров Юрий|Константин Воронцов|4 января 2010}}

Версия 20:43, 4 января 2010

Метод наименьших квадратов с итеративным пересчётом весов (IRLS) - алгоритм, использующийся для решения некоторых оптимизационных задач. В частности, с помощью этого метода можно решать задачи вида:

\mathrm{arg}\min_{\beta} \sum_{i=1}^n w_i(\beta)| y_i - f_i (\beta) | ^ 2

Алгоритм является итеративным. На каждом шаге алгоритма решается задача Взвешенных наименьших квадратов:

\beta ^ {(t + 1)} = \mathrm{arg}\min_{\beta} \sum_{i=1}^n w_i(\beta ^ {(t)})| y_i - f_i (\beta) | ^ 2

Содержание

Основные шаги алгоритма

  1. Выбор начального приближения для вектора параметров \beta
    1. Здесь можно использовать обычный метод наименьших квадратов (потом подробнее)
  2. Решение задачи взвешенных наименьших квадратов
    1. При решении этой задачи можно использовать, например, алгоритм сопряженных градиентов.
  3. Пересчет вектора весов, если нужно.
  4. Оценка измененного решения
  5. Переход на шаг #2

Пример работы алгоритма

Приведем пример работы алгоритма для решения задач логистической регрессии.

Пусть задано пространство объектов X и множество возможных ответов Y. Существует неизвестная целевая зависимость y∗ : X → Y , значения которой известны только на объектах обучающей выборки.

Сходимость алгоритма

Метод сходится не всегда. Например, (вставляем пример из wikidoc).

Литература

Ф.П. Васильев Численные методы решения экстремальных задач - М.: Наука, 1980. — 307 с.

Ссылки

Wikipedia: Iteratively reweighted least squares
Wicidoc: Iteratively re-weighted least squares
Ю. И. Журавлев, Д. П. Ветров: Обобщенные Линейные Модели: Метод IRLS

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

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

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


Источник — «http://www.recognition.su/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0%D0%B8%D0%BC%D0%B5%D0%BD%D1%8C%D1%88%D0%B8%D1%85_%D0%BA%D0%B2%D0%B0%D0%B4%D1%80%D0%B0%D1%82%D0%BE%D0%B2_%D1%81_%D0%B8%D1%82%D0%B5%D1%80%D0%B0%D1%82%D0%B8%D0%B2%D0%BD%D1%8B%D0%BC_%D0%BF%D0%B5%D1%80%D0%B5%D1%81%D1%87%D1%91%D1%82%D0%BE%D0%BC_%D0%B2%D0%B5%D1%81%D0%BE%D0%B2»