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

Часть серии по
Регрессивный анализ
Модели
Линейная регрессия Простая регрессия Полиномиальная регрессия Общая линейная модель
Обобщенная линейная модель Дискретный выбор Биномиальная регрессия Бинарная регрессия Логистическая регрессия Полиномиальный логит Смешанный логит Пробит Полиномиальный пробит Заказал логит Заказал пробит Пуассон
Многоуровневая модель Фиксированные эффекты Случайные эффекты Линейная модель смешанных эффектов Нелинейная модель смешанных эффектов
Нелинейная регрессия Непараметрический Полупараметрический Крепкий Квантиль Изотонический Основные компоненты Наименьший угол Местный Сегментированный
Ошибки в переменных
Оценка
Наименьших квадратов Линейный Нелинейный
Обычный Взвешенный Обобщенный
Частичное Общий Неотрицательный Регрессия хребта Регулярный
Наименьшие абсолютные отклонения Итеративно переназначенный Байесовский Байесовская многомерная
Фон
Проверка регрессии Средний и прогнозируемый ответ Ошибки и остатки Доброта подгонки Студентизированный остаток Теорема Гаусса – Маркова
Математический портал
v т е

Метод итеративно взвешенных наименьших квадратов ( IRLS ) используется для решения некоторых задач оптимизации с целевыми функциями вида p -нормы :

${\ displaystyle {\ underset {\ boldsymbol {\ beta}} {\ operatorname {arg \, min}}} \ sum _ {i = 1} ^ {n} {\ big |} y_ {i} -f_ {i } ({\ boldsymbol {\ beta}}) {\ big |} ^ {p},}$

с помощью итерационного метода , в котором каждый шаг включает в себя решения взвешенных наименьших квадратов задачу вида: ^[1]

${\displaystyle {\boldsymbol {\beta }}^{(t+1)}={\underset {\boldsymbol {\beta }}{\operatorname {arg\,min} }}\sum _{i=1}^{n}w_{i}({\boldsymbol {\beta }}^{(t)}){\big |}y_{i}-f_{i}({\boldsymbol {\beta }}){\big |}^{2}.}$

IRLS используется для поиска оценок максимального правдоподобия обобщенной линейной модели и в устойчивой регрессии для поиска M-оценки как способ смягчения влияния выбросов в наборе данных, обычно распределенных в других отношениях. Например, минимизируя наименьшие абсолютные ошибки, а не наименьшие квадратичные ошибки .

Одним из преимуществ IRLS перед линейным программированием и выпуклым программированием является то, что его можно использовать с численными алгоритмами Гаусса – Ньютона и Левенберга – Марквардта .

Примеры [ править ]

Минимизация L ₁ для разреженного восстановления [ править ]

IRLS может быть использован для ℓ 1 минимизации и сглаженный л р минимизации, р  <1, в сжатом зондировании проблем. Доказано , что алгоритм имеет линейную скорость сходимости для ℓ ₁ нормы и суперлинейного для л _т с т  <1, при ограниченной изометрии собственности , которая , как правило , является достаточным условием для разреженных решений. ^{[2] [3]} Однако в большинстве практических ситуаций свойство ограниченной изометрии не выполняется. ^{[ необходима цитата ]}

Линейная регрессия L ^p norm [ править ]

Чтобы найти параметры β  = ( β ₁ ,…, β _k ) ^T, которые минимизируют норму L p для задачи линейной регрессии ,

${\displaystyle {\underset {\boldsymbol {\beta }}{\operatorname {arg\,min} }}{\big \|}\mathbf {y} -X{\boldsymbol {\beta }}\|_{p}={\underset {\boldsymbol {\beta }}{\operatorname {arg\,min} }}\sum _{i=1}^{n}\left|y_{i}-X_{i}{\boldsymbol {\beta }}\right|^{p},}$

алгоритм IRLS на шаге t  + 1 включает решение взвешенной линейной задачи наименьших квадратов : ^[4]

${\displaystyle {\boldsymbol {\beta }}^{(t+1)}={\underset {\boldsymbol {\beta }}{\operatorname {arg\,min} }}\sum _{i=1}^{n}w_{i}^{(t)}\left|y_{i}-X_{i}{\boldsymbol {\beta }}\right|^{2}=(X^{\rm {T}}W^{(t)}X)^{-1}X^{\rm {T}}W^{(t)}\mathbf {y} ,}$

где W ^{( t )} - диагональная матрица весов, обычно со всеми элементами, изначально установленными на:

${\displaystyle w_{i}^{(0)}=1}$

и обновляется после каждой итерации до:

${\displaystyle w_{i}^{(t)}={\big |}y_{i}-X_{i}{\boldsymbol {\beta }}^{(t)}{\big |}^{p-2}.}$

В случае p  = 1 это соответствует регрессии с наименьшим абсолютным отклонением (в этом случае для решения проблемы лучше использовать методы линейного программирования ^[5], чтобы результат был точным) и формула имеет следующий вид:

${\displaystyle w_{i}^{(t)}={\frac {1}{{\big |}y_{i}-X_{i}{\boldsymbol {\beta }}^{(t)}{\big |}}}.}$

Чтобы избежать деления на ноль, необходимо выполнить регуляризацию , поэтому на практике формула имеет следующий вид:

${\displaystyle w_{i}^{(t)}={\frac {1}{\max \left\{\delta ,\left|y_{i}-X_{i}{\boldsymbol {\beta }}^{(t)}\right|\right\}}}.}$

где какое-то небольшое значение, например 0,0001. ^[5] Обратите внимание, что использование в весовой функции эквивалентно функции потерь Хубера в робастной оценке. ^[6]${\displaystyle \delta }$${\displaystyle \delta }$

См. Также [ править ]

• Возможные обобщенные методы наименьших квадратов
• Алгоритм Вайсфельда (для аппроксимации геометрической медианы ), который можно рассматривать как частный случай IRLS

Заметки [ править ]

Ссылки [ править ]

• Численные методы для задач наименьших квадратов, Оке Бьорк (Глава 4: Обобщенные задачи наименьших квадратов).
• Практические методы наименьших квадратов для компьютерной графики. SIGGRAPH Курс 11

Внешние ссылки [ править ]

• Итеративное решение недоопределенных линейных систем