Метод наименьших квадратов с итеративным пересчётом весов
Материал из MachineLearning.
| Строка 14: | Строка 14: | ||
=Пример работы алгоритма= | =Пример работы алгоритма= | ||
| - | Приведем пример работы алгоритма для решения задач [[логистической регрессии]]. | + | Приведем пример работы алгоритма для решения задач [[логистическая регрессия|логистической регрессии]]. |
| - | Пусть задано пространство объектов X и множество возможных ответов Y. Существует неизвестная целевая зависимость | + | Пусть задано пространство объектов X и множество возможных ответов Y. Существует неизвестная целевая зависимость y* : X → Y , значения которой известны только на объектах обучающей выборки <tex> X^l = (x_i, y_i)_{i=1}^n, y_i = y*(x_i)</tex>. Требуется построить алгоритм a: X → Y ,аппроксимирующий целевую зависимость y∗. |
| + | |||
| + | Определим функционал качества аппроксимации целевой зависимости на выборке <tex>X^l</tex> как : | ||
| + | ::<tex>Q(w, X^l) = \sum_{i=1}^n ln \sigma(-w^T x_i y_i)</tex>, | ||
| + | |||
| + | где <tex>\sigma(z) = (1 + exp{-z})^{-1}</tex> - сигмоидная функция. | ||
| + | |||
| + | Примененим метод Ньютона-Рафсона для минимизации нелинейного функционала Q(w): | ||
| + | ::<tex>w ^ {t + 1} = w ^ t + h_t (Q''(w^t))^{-1} Q'(w^t)</tex>, | ||
| + | |||
| + | где <tex>Q'(w^t)</tex> - вектор первых производных (градиент) функционала Q(w) в точке <tex>w^t</tex>, <tex>Q''(w^t)</tex> - матрица вторых производных (гессиан) функционала Q(w) в точке <tex>w^t</tex>, <tex>h_t</tex> - величина шага. | ||
| + | |||
| + | Обозначим <tex>\sigma_i = \sigma(y_i w^T x_i)</tex> и заметим, что производная сигмоидной функции есть <tex>\sigma'(z) = \sigma(z)(1 - \sigma(z))</tex>. | ||
| + | Элементы градиента (вектора первых производных) функционала Q(w): | ||
| + | |||
| + | Элементы гессиана (матрицы вторых производных) функционала Q(w): | ||
| + | |||
| + | Введём матричные обозначения:<br /> | ||
| + | ::<tex>F_{l * n} = f_j(x_i)</tex> - матрица признаковых описаний объектов; <br /> | ||
| + | ::<tex>\Gamma_{l * l} = diag ( sqrt{(1 - \sigma_i)\sigma_i} )</tex> - диагональная матрица весов объектов;<br /> | ||
| + | ::<tex>F' = \Gamma F </tex>- звешенная матрица признаковых описаний объектов;<br /> | ||
| + | ::<tex>y_i' = y_i sqrt {(1 - \sigma_i)\sigma_i}</tex> - взвешенный вектор ответов. | ||
| + | |||
| + | \v{t} | ||
| + | В этих обозначениях произведение матрицы, обратной к гессиану, на вектор градиента принимает следующий вид:<br /> | ||
| + | <tex>(Q''(w^t))^{-1} Q'(w^t) = -(F^T \Gamma ^ 2 F) ^ {-1} F^T \Gamma y' = -(F' ^ {T} F') ^ {-1} F^{T} y' </tex> | ||
=Сходимость алгоритма= | =Сходимость алгоритма= | ||
Версия 22:02, 4 января 2010
Метод наименьших квадратов с итеративным пересчётом весов (IRLS) - алгоритм, использующийся для решения некоторых оптимизационных задач. В частности, с помощью этого метода можно решать задачи вида:
Алгоритм является итеративным. На каждом шаге алгоритма решается задача Взвешенных наименьших квадратов:
Содержание |
Основные шаги алгоритма
- Выбор начального приближения для вектора параметров
- Здесь можно использовать обычный метод наименьших квадратов (потом подробнее)
- Решение задачи взвешенных наименьших квадратов
- При решении этой задачи можно использовать, например, алгоритм сопряженных градиентов.
- Пересчет вектора весов, если нужно.
- Оценка измененного решения
- Переход на шаг #2
Пример работы алгоритма
Приведем пример работы алгоритма для решения задач логистической регрессии.
Пусть задано пространство объектов X и множество возможных ответов Y. Существует неизвестная целевая зависимость y* : X → Y , значения которой известны только на объектах обучающей выборки . Требуется построить алгоритм a: X → Y ,аппроксимирующий целевую зависимость y∗.
Определим функционал качества аппроксимации целевой зависимости на выборке как :
,
где - сигмоидная функция.
Примененим метод Ньютона-Рафсона для минимизации нелинейного функционала Q(w):
,
где - вектор первых производных (градиент) функционала Q(w) в точке
,
- матрица вторых производных (гессиан) функционала Q(w) в точке
,
- величина шага.
Обозначим и заметим, что производная сигмоидной функции есть
.
Элементы градиента (вектора первых производных) функционала Q(w):
Элементы гессиана (матрицы вторых производных) функционала Q(w):
Введём матричные обозначения:
- матрица признаковых описаний объектов;
- диагональная матрица весов объектов;
- звешенная матрица признаковых описаний объектов;
- взвешенный вектор ответов.
\v{t}
В этих обозначениях произведение матрицы, обратной к гессиану, на вектор градиента принимает следующий вид:
Сходимость алгоритма
Метод сходится не всегда. Например, (вставляем пример из wikidoc).
Литература
Ф.П. Васильев Численные методы решения экстремальных задач - М.: Наука, 1980. — 307 с.
Ссылки
Wikipedia: Iteratively reweighted least squares
Wicidoc: Iteratively re-weighted least squares
Ю. И. Журавлев, Д. П. Ветров: Обобщенные Линейные Модели: Метод IRLS
| Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
