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

Версия 19:21, 5 января 2010

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

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

Описание алгоритма

Пусть нужно найти приближенное решение уравнения , где - матрица размера m*n,
Первый шаг алгоритма- это идентификация весов. В начале начале матрице весов W берется за единичную , и методом взвешанных наименьших квадратов ищется решения следующей задачи :

Получаем некоторый вектор и вычисляем невязку :

,

по которой происходит пересчет матрицы весов с помощью некоторой неотрицательной функции . Например, можно взять  :

После этого, опять решаем уравнение , но уже с пересчитанными весами. Процесс повторяется до тех пор, пока вектор весов не стабилизируется.
Решение, к которому сходится этот итеративный процесс- это минимизация некоторой функции, связанной с функцией . Например, если взять функцию , то будет минимизироваться функция .

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

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

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

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

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

Определим функционал качества аппроксимации целевой зависимости на выборке как :

,

где - сигмоидная функция.

Примененим метод Ньютона-Рафсона для минимизации нелинейного функционала Q(w):

,

где - вектор первых производных (градиент) функционала Q(w) в точке , - матрица вторых производных (гессиан) функционала Q(w) в точке , - величина шага.

Обозначим и заметим, что производная сигмоидной функции есть .
Элементы градиента (вектора первых производных) функционала Q(w):

Элементы гессиана (матрицы вторых производных) функционала Q(w):

Введём матричные обозначения:

- матрица признаковых описаний объектов;

- диагональная матрица весов объектов;

- взвешенная матрица признаковых описаний объектов;

- взвешенный вектор ответов.

В этих обозначениях произведение матрицы, обратной к гессиану, на вектор градиента принимает следующий вид:

Таким образом, получается, что на каждой итерации вектор весов w ищется по следующей формуле :

Легко заметить, что полученное выражение совпадает с решением задачи наименьших квадратов для многомерной линейной регрессии со взвешенными объектами и модифицированными ответами:

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

Литература

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

Ссылки

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

Данная статья является непроверенным учебным заданием. Студент: Участник:Сидоров Юрий Преподаватель: Участник:Константин Воронцов Срок: 7 января 2010 До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.