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

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 61: Строка 61:
[[Категория:Машинное обучение]]
[[Категория:Машинное обучение]]
-
{{Задание|Сидоров Юрий|Константин Воронцов|4 января 2010}}
+
{{Задание|Сидоров Юрий|Константин Воронцов|7 января 2010}}

Версия 22:26, 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 , значения которой известны только на объектах обучающей выборки X^l = (x_i, y_i)_{i=1}^n, y_i = y*(x_i). Требуется построить алгоритм a: X → Y ,аппроксимирующий целевую зависимость y∗.

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

Q(w, X^l) = \sum_{i=1}^n ln \sigma(-w^T x_i y_i),

где \sigma(z) = (1 + exp{-z})^{-1} - сигмоидная функция.

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

w ^ {t + 1} = w ^ t + h_t (Q''(w^t))^{-1} Q'(w^t),

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

Обозначим \sigma_i = \sigma(y_i w^T x_i) и заметим, что производная сигмоидной функции есть \sigma'(z) = \sigma(z)(1 - \sigma(z)). Элементы градиента (вектора первых производных) функционала Q(w):

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

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

F_{l * n} = f_j(x_i) - матрица признаковых описаний объектов;
\Gamma_{l * l} = diag ( sqrt{(1 - \sigma_i)\sigma_i} ) - диагональная матрица весов объектов;
\tilde F = \Gamma F - взвешенная матрица признаковых описаний объектов;
\tilde y_i = y_i sqrt {(1 - \sigma_i)\sigma_i} - взвешенный вектор ответов.

В этих обозначениях произведение матрицы, обратной к гессиану, на вектор градиента принимает следующий вид:
(Q''(w^t))^{-1} Q'(w^t) = -(F^T \Gamma ^ 2 F) ^ {-1} F^T \Gamma \tilde y = -(\tilde F ^ {T} \tilde F) ^ {-1} \tilde F^{T} \tilde y = -\tilde F ^ + \tilde y

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

w ^ {t+1} = w ^ t + h_t * (\tilde F ^ {T} \tilde F) ^ {-1} \tilde F^{T} \tilde y

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

Q(w) = || \tilde F w - \tilde y|| ^ 2

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

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

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

Литература

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

Ссылки

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

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

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

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


Источник — «http://machinelearning.ru/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»
Личные инструменты