Метод наименьших квадратов с итеративным пересчётом весов
Материал из MachineLearning.
(→Описание алгоритма) |
|||
(9 промежуточных версий не показаны.) | |||
Строка 4: | Строка 4: | ||
::<tex> \beta ^ {(t + 1)} = \mathrm{arg}\min_{\beta} \sum_{i=1}^n w_i(\beta ^ {(t)})| y_i - f_i (\beta) | ^ 2 </tex> | ::<tex> \beta ^ {(t + 1)} = \mathrm{arg}\min_{\beta} \sum_{i=1}^n w_i(\beta ^ {(t)})| y_i - f_i (\beta) | ^ 2 </tex> | ||
- | = | + | =Описание алгоритма= |
- | + | Пусть нужно найти приближенное решение уравнения <tex>Ax = y</tex>, где <tex>A = (a_{ij})</tex> - матрица размера m*n, <tex> x = (x_1,...,x_n),\ y = (y_1,..., y_m)</tex><br /> | |
- | + | Первый шаг алгоритма- это идентификация весов. В начале начале матрице весов ''W'' берется за единичную <tex>W \equiv I</tex>, и методом взвешанных наименьших квадратов ищется решения следующей задачи : | |
- | + | ::<tex>WAx = Wy</tex> | |
- | + | Получаем некоторый вектор <tex>\tilde x</tex> и вычисляем невязку : | |
- | + | ::<tex>r = y - A\tilde x</tex>, | |
- | + | по которой происходит пересчет матрицы весов <tex>W</tex> с помощью некоторой неотрицательной функции <tex>f(r)</tex>. Например, можно взять <tex>f(r) = \frac 1 {|r|}</tex> : | |
- | + | ::<tex>W = diag (f(r))</tex> | |
+ | После этого, опять решаем уравнение <tex>WAx = Wy</tex>, но уже с пересчитанными весами. Процесс повторяется до тех пор, пока вектор весов не стабилизируется. <br /> | ||
+ | Решение, к которому сходится этот итеративный процесс- это минимизация некоторой функции, связанной с функцией <tex>f (x)</tex>. Например, если взять функцию <tex>f (x) = \frac 1 {|r|}</tex>, то будет минимизироваться функция <tex>\sum_i |r_i|</tex>. | ||
+ | |||
+ | =Сходимость алгоритма= | ||
+ | Алгоритм сходится не всегда. Например, выбор в качестве функции <tex>f (x) = |r| ^ p</tex>, где <tex>p \in (-1, 1]</tex> может привести к зацикливанию, и алгоритм, таким образом, не сойдется. | ||
=Пример работы алгоритма= | =Пример работы алгоритма= | ||
- | Приведем пример работы алгоритма для решения задач [[логистической регрессии]]. | + | Приведем пример работы алгоритма для решения задач [[логистическая регрессия|логистической регрессии]]. |
- | Пусть задано пространство объектов 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>.<br /> | ||
+ | Элементы градиента (вектора первых производных) функционала Q(w):<br /> | ||
+ | ::<tex>\frac {\partial Q (t)} {\partial w_j} = -\sum_{i = 1} ^ l (1 - \sigma_i) y_i f_j (x_i),\ j = 1,...,n.</tex> | ||
+ | |||
+ | Элементы гессиана (матрицы вторых производных) функционала Q(w):<br /> | ||
+ | ::<tex>\frac {\partial ^ 2 Q (t)} {\partial w_j \partial w_k} = - \frac {\partial} {\partial w_k} \sum_{i = 1} ^ l (1 - \sigma_i) y_i f_j (x_i) = \sum_{i = 1} ^ l (1 - \sigma_i) \sigma_i f_j (x_i) f_l (x_i),\ j = 1,...,n,\ k = 1,...,n</tex> | ||
+ | |||
+ | Введём матричные обозначения:<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>\tilde F = \Gamma F </tex> - взвешенная матрица признаковых описаний объектов;<br /> | ||
+ | ::<tex>\tilde y_i = y_i sqrt {(1 - \sigma_i)\sigma_i}</tex> - взвешенный вектор ответов. | ||
+ | |||
+ | В этих обозначениях произведение матрицы, обратной к гессиану, на вектор градиента принимает следующий вид:<br /> | ||
+ | ::<tex>(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</tex> | ||
+ | |||
+ | Таким образом, получается, что на каждой итерации вектор весов ''w'' ищется по следующей формуле : | ||
+ | ::<tex>w ^ {t+1} = w ^ t + h_t * (\tilde F ^ {T} \tilde F) ^ {-1} \tilde F^{T} \tilde y </tex> | ||
+ | |||
+ | Легко заметить, что полученное выражение совпадает с решением задачи наименьших квадратов для многомерной линейной регрессии со взвешенными объектами и модифицированными ответами: | ||
+ | ::<tex>Q(w) = || \tilde F w - \tilde y|| ^ 2</tex> | ||
+ | Таким образом, решение задачи классификации сводится к последовательности регрессионных задач, для каждой из которых веса объектов и ответы пересчитываются заново. Т.е. в данном случае мы применяем алгоритм IRLS. | ||
=Литература= | =Литература= | ||
- | Ф.П. Васильев Численные методы решения экстремальных задач - М.: Наука, 1980. — 307 с. | + | Ф.П. Васильев Численные методы решения экстремальных задач - М.: Наука, 1980. — 307 с.<br /> |
+ | [[Машинное обучение (курс лекций, К.В.Воронцов)]] | ||
+ | |||
+ | =См. также= | ||
+ | *[[Логистическая регрессия]] | ||
+ | *[[Метод стохастического градиента]] | ||
+ | *[[Многомерная линейная регрессия]] | ||
=Ссылки= | =Ссылки= | ||
Строка 29: | Строка 70: | ||
[http://mmphome.1gb.ru/data/doc/4course/mfft/lecture1.pdf Ю. И. Журавлев, Д. П. Ветров: Обобщенные Линейные Модели: Метод IRLS] | [http://mmphome.1gb.ru/data/doc/4course/mfft/lecture1.pdf Ю. И. Журавлев, Д. П. Ветров: Обобщенные Линейные Модели: Метод IRLS] | ||
- | [[Категория: | + | [[Категория:Линейная регрессия]] |
- | {{Задание|Сидоров Юрий|Константин Воронцов| | + | [[Категория:Линейные классификаторы]] |
+ | {{Задание|Сидоров Юрий|Константин Воронцов|7 января 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 в учебном процессе. |