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

Метод решения некоторых оптимизационных задач

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

$${\displaystyle \mathop {\operatorname {arg\,min} } _{\boldsymbol {\beta }}\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 перед линейным программированием и выпуклым программированием является то, что его можно использовать с численными алгоритмами Гаусса – Ньютона и Левенберга – Марквардта .

Примеры

л1минимизация для редкого восстановления

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

Л пнормальная линейная регрессия

Чтобы найти параметры β  = ( β ₁ , …, β _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 }$

Смотрите также

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

Примечания

1. К. Сидни Беррус, Итеративный перевзвешенный метод наименьших квадратов
2. Чартран, Р.; Инь, В. (31 марта – 4 апреля 2008 г.). «Итеративно перевзвешенные алгоритмы измерения сжатия». Международная конференция IEEE по акустике, речи и обработке сигналов (ICASSP), 2008 г. стр. 3869–3872. дои : 10.1109/ICASSP.2008.4518498.
3. Добеши, И.; Девор, Р.; Форназье, М.; Гюнтюрк, CSN (2010). «Итеративно перевзвешенная минимизация методом наименьших квадратов для редкого восстановления». Сообщения по чистой и прикладной математике . 63 : 1–38. arXiv : 0807.0575 . дои : 10.1002/cpa.20303.
4. Нежный, Джеймс (2007). «6.8.1 Решения, минимизирующие другие нормы невязок». Матричная алгебра . Тексты Спрингера в статистике. Нью-Йорк: Спрингер. дои : 10.1007/978-0-387-70873-7. ISBN 978-0-387-70872-0.
5. Уильям А. Пфейл, Статистические учебные пособия , диссертация бакалавра наук, Вустерский политехнический институт , 2006 г.
6. Фокс, Дж.; Вайсберг, С. (2013), Робастная регрессия , конспекты курса, Университет Миннесоты.

Рекомендации

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

Внешние ссылки

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