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

Чтобы узнать о Международной лунной исследовательской станции, см. Международную лунную исследовательскую станцию .

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

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

, итерационным методом в котором каждый шаг включает решение взвешенной задачи наименьших квадратов вида:

$${\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 можно использовать для минимизации ℓ ₁ и сглаженной минимизации ℓ _p , p <1, в задачах измерения сжатых данных . Доказано, что алгоритм имеет линейную скорость сходимости для ℓ ₁ нормы и суперлинейную для ℓ _t с t < 1 при ограниченном свойстве изометрии , которое обычно является достаточным условием для разреженных решений.

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

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

$${\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 предполагает решение взвешенной линейной задачи наименьших квадратов :

$${\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 ^{( т )} - это диагональная матрица весов, обычно со всеми элементами, изначально установленными на:

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

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

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

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

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

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

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

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

См. также

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

Ссылки

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

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

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