Метод наименьших квадратов с итеративным пересчётом весов
Материал из MachineLearning.
(→Литература) |
(→Литература) |
||
Строка 57: | Строка 57: | ||
=Литература= | =Литература= | ||
- | Ф.П. Васильев Численные методы решения экстремальных задач - М.: Наука, 1980. — 307 с. | + | Ф.П. Васильев Численные методы решения экстремальных задач - М.: Наука, 1980. — 307 с.<br /> |
- | + | К.В. Воронцов Лекции по алгоритмам восстановления регрессии | |
=Ссылки= | =Ссылки= |
Версия 19:19, 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
Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |