Метод наименьших квадратов с итеративным пересчётом весов
Материал из MachineLearning.
(→Описание алгоритма) |
|||
(5 промежуточных версий не показаны.) | |||
Строка 5: | Строка 5: | ||
=Описание алгоритма= | =Описание алгоритма= | ||
- | Пусть нужно найти приближенное решение уравнения <tex>Ax = | + | Пусть нужно найти приближенное решение уравнения <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 = | + | ::<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> | ||
Строка 57: | Строка 57: | ||
=Литература= | =Литература= | ||
- | Ф.П. Васильев Численные методы решения экстремальных задач - М.: Наука, 1980. — 307 с. | + | Ф.П. Васильев Численные методы решения экстремальных задач - М.: Наука, 1980. — 307 с.<br /> |
+ | [[Машинное обучение (курс лекций, К.В.Воронцов)]] | ||
+ | |||
+ | =См. также= | ||
+ | *[[Логистическая регрессия]] | ||
+ | *[[Метод стохастического градиента]] | ||
+ | *[[Многомерная линейная регрессия]] | ||
=Ссылки= | =Ссылки= | ||
Строка 64: | Строка 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}} | {{Задание|Сидоров Юрий|Константин Воронцов|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 в учебном процессе. |