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

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

(Различия между версиями)
Перейти к: навигация, поиск
(категория)
(Описание алгоритма)
 
Строка 5: Строка 5:
=Описание алгоритма=
=Описание алгоритма=
-
Пусть нужно найти приближенное решение уравнения <tex>Ax = b</tex>, где <tex>A = (a_{ij})</tex> - матрица размера m*n, <tex> x = (x_1,...,x_n),\ y = (y_1,..., y_m)</tex><br />
+
Пусть нужно найти приближенное решение уравнения <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>, и методом взвешанных наименьших квадратов ищется решения следующей задачи :
Первый шаг алгоритма- это идентификация весов. В начале начале матрице весов ''W'' берется за единичную <tex>W \equiv I</tex>, и методом взвешанных наименьших квадратов ищется решения следующей задачи :
::<tex>WAx = Wy</tex>
::<tex>WAx = Wy</tex>
Получаем некоторый вектор <tex>\tilde x</tex> и вычисляем невязку :
Получаем некоторый вектор <tex>\tilde x</tex> и вычисляем невязку :
-
::<tex>r = b - A\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</tex> с помощью некоторой неотрицательной функции <tex>f(r)</tex>. Например, можно взять <tex>f(r) = \frac 1 {|r|}</tex> :
::<tex>W = diag (f(r))</tex>
::<tex>W = diag (f(r))</tex>

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

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


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