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

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

(Различия между версиями)

Текущая версия

Метод наименьших квадратов с итеративным пересчётом весов (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$

Описание алгоритма

Пусть нужно найти приближенное решение уравнения $Ax = y$ , где $A = (a_{ij})$ - матрица размера m*n, $x = (x_1,...,x_n),\ y = (y_1,..., y_m)$
Первый шаг алгоритма- это идентификация весов. В начале начале матрице весов W берется за единичную $W \equiv I$ , и методом взвешанных наименьших квадратов ищется решения следующей задачи :

$WAx = Wy$

Получаем некоторый вектор $\tilde x$ и вычисляем невязку :

$r = y - A\tilde x$ ,

по которой происходит пересчет матрицы весов $W$ с помощью некоторой неотрицательной функции $f(r)$ . Например, можно взять $f(r) = \frac 1 {|r|}$ :

$W = diag (f(r))$

После этого, опять решаем уравнение $WAx = Wy$ , но уже с пересчитанными весами. Процесс повторяется до тех пор, пока вектор весов не стабилизируется.
Решение, к которому сходится этот итеративный процесс- это минимизация некоторой функции, связанной с функцией $f (x)$ . Например, если взять функцию $f (x) = \frac 1 {|r|}$ , то будет минимизироваться функция $\sum_i |r_i|$ .

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

Алгоритм сходится не всегда. Например, выбор в качестве функции $f (x) = |r| ^ p$ , где $p \in (-1, 1]$ может привести к зацикливанию, и алгоритм, таким образом, не сойдется.

Пример работы алгоритма

Приведем пример работы алгоритма для решения задач логистической регрессии.

Пусть задано пространство объектов 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):

$\frac {\partial Q (t)} {\partial w_j} = -\sum_{i = 1} ^ l (1 - \sigma_i) y_i f_j (x_i),\ j = 1,...,n.$

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

$\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$

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

$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.

Литература

Ф.П. Васильев Численные методы решения экстремальных задач - М.: Наука, 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»

Категории: Линейная регрессия | Линейные классификаторы | Непроверенные учебные задания

@@ Строка 1: / Строка 1: @@
-{{Задание|Сидоров Юрий|Константин Воронцов|4 января 2010}}
+'''Метод наименьших квадратов с итеративным пересчётом весов''' (IRLS) - алгоритм, использующийся для решения некоторых оптимизационных задач. В частности, с помощью этого метода можно решать задачи вида:
+::<tex> \mathrm{arg}\min_{\beta} \sum_{i=1}^n w_i(\beta)| y_i - f_i (\beta) | ^ 2 </tex>
+Алгоритм является итеративным. На каждом шаге алгоритма решается задача [http://en.wikipedia.org/wiki/Weighted_least_squares#Weighted_least_squares Взвешенных наименьших квадратов]:
+::<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. Существует неизвестная целевая зависимость 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 с.<br />
+[[Машинное обучение (курс лекций, К.В.Воронцов)]]
+=См. также=
+*[[Логистическая регрессия]]
+*[[Метод стохастического градиента]]
+*[[Многомерная линейная регрессия]]
+=Ссылки=
+[http://en.wikipedia.org/wiki/Iteratively_reweighted_least_squares Wikipedia: Iteratively reweighted least squares]<br />
+[http://www.wikidoc.org/index.php/Iteratively_re-weighted_least_squares Wicidoc: Iteratively re-weighted least squares]<br />
+[http://mmphome.1gb.ru/data/doc/4course/mfft/lecture1.pdf Ю. И. Журавлев, Д. П. Ветров: Обобщенные Линейные Модели: Метод IRLS]
+[[Категория:Линейная регрессия]]
+[[Категория:Линейные классификаторы]]
+{{Задание|Сидоров Юрий|Константин Воронцов|7 января 2010}}

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

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

Текущая версия

Содержание

Описание алгоритма

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

Пример работы алгоритма

Литература

См. также

Ссылки

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты