Метод наименьших квадратов с итеративным пересчётом весов
Материал из MachineLearning.
Метод наименьших квадратов с итеративным пересчётом весов (IRLS) - алгоритм, использующийся для решения некоторых оптимизационных задач. В частности, с помощью этого метода можно решать задачи вида:
Алгоритм является итеративным. На каждом шаге алгоритма решается задача Взвешенных наименьших квадратов:
Содержание |
Основные шаги алгоритма
- Выбор начального приближения для вектора параметров
- Здесь можно использовать обычный метод наименьших квадратов (потом подробнее)
- Решение задачи взвешенных наименьших квадратов
- При решении этой задачи можно использовать, например, алгоритм сопряженных градиентов.
- Пересчет вектора весов, если нужно.
- Оценка измененного решения
- Переход на шаг #2
Пример работы алгоритма
Приведем пример работы алгоритма для решения задач логистической регрессии.
Пусть задано пространство объектов X и множество возможных ответов Y. Существует неизвестная целевая зависимость y* : X → Y , значения которой известны только на объектах обучающей выборки . Требуется построить алгоритм a: X → Y ,аппроксимирующий целевую зависимость y∗.
Определим функционал качества аппроксимации целевой зависимости на выборке как :
,
где - сигмоидная функция.
Примененим метод Ньютона-Рафсона для минимизации нелинейного функционала Q(w):
,
где - вектор первых производных (градиент) функционала Q(w) в точке
,
- матрица вторых производных (гессиан) функционала Q(w) в точке
,
- величина шага.
Обозначим и заметим, что производная сигмоидной функции есть
.
Элементы градиента (вектора первых производных) функционала Q(w):
Элементы гессиана (матрицы вторых производных) функционала Q(w):
Введём матричные обозначения:
- матрица признаковых описаний объектов;
- диагональная матрица весов объектов;
- взвешенная матрица признаковых описаний объектов;
- взвешенный вектор ответов.
В этих обозначениях произведение матрицы, обратной к гессиану, на вектор градиента принимает следующий вид:
Таким образом, получается, что на каждой итерации вектор весов w ищется по следующей формуле :
Легко заметить, что полученное выражение совпадает с решением задачи наименьших квадратов для многомерной линейной регрессии со взвешенными объектами и модифицированными ответами:
Таким образом, решение задачи классификации сводится к последовательности регрессионных задач, для каждой из которых веса объектов и ответы пересчитываются заново. Т.е. в данном случае мы применяем алгоритм IRLS.
Сходимость алгоритма
Метод сходится не всегда. Например, пример из wikidoc.
Литература
Ф.П. Васильев Численные методы решения экстремальных задач - М.: Наука, 1980. — 307 с.
Ссылки
Wikipedia: Iteratively reweighted least squares
Wicidoc: Iteratively re-weighted least squares
Ю. И. Журавлев, Д. П. Ветров: Обобщенные Линейные Модели: Метод IRLS
![]() | Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |