Opakovaně vyvažoval nejméně čtverců - Iteratively reweighted least squares

Část série na
Regresní analýza
Modely
Lineární regrese Jednoduchá regrese Polynomiální regrese Obecný lineární model
Zobecněný lineární model Diskrétní volba Binomická regrese Binární regrese Logistická regrese Multinomiální logit Smíšený logit Probit Multinomiální probit Objednaný logit Objednaný probit jed
Víceúrovňový model Opravené efekty Náhodné efekty Lineární model se smíšenými efekty Nelineární model smíšených efektů
Nelineární regrese Neparametrické Semiparametrické Robustní Kvantilní Izotonický Hlavní součásti Nejméně úhel Místní Segmentované
Chyby v proměnných
Odhad
Nejmenší čtverce Lineární Nelineární
Obyčejný Vážený Zobecněný
Částečný Celkový Nezáporné Ridgeova regrese Regularizováno
Nejméně absolutní odchylky Opakovaně váhovaný Bayesian Bayesovský multivariační
Pozadí
Ověření regrese Střední a předpokládaná odpověď Chyby a zbytky Dobře padne Studentizovaný zbytek Gauss – Markovova věta
Matematický portál

Metoda iterativně vyvažované nejméně čtverce (IRLS) se používá k řešení určitých optimalizačních problémů s objektivní funkce formy a str-norma:

${displaystyle {underset {oldsymbol {eta}} {operatorname {arg, min}}} součet _ {i = 1} ^ {n} {ig |} y_ {i} -f_ {i} ({oldsymbol {eta}} ) {ig |} ^ {p},}$

podle iterační metoda ve kterém každý krok zahrnuje řešení a vážené nejmenší čtverce problém formy:^[1]

${displaystyle {oldsymbol {eta}} ^ {(t + 1)} = {podmnožina {oldsymbol {eta}} {operatorname {arg, min}}} součet _ {i = 1} ^ {n} w_ {i} ( {oldsymbol {eta}} ^ {(t)}) {ig |} y_ {i} -f_ {i} ({oldsymbol {eta}}) {ig |} ^ {2}.}$

IRLS se používá k nalezení maximální pravděpodobnost odhady a zobecněný lineární model a v robustní regrese najít M-odhad, jako způsob zmírnění vlivu odlehlých hodnot v jinak normálně distribuovaném souboru dat. Například minimalizací nejméně absolutní chyby spíše než chyby nejmenších čtverců.

Jednou z výhod IRLS oproti lineární programování a konvexní programování je, že lze použít s Gauss – Newton a Levenberg – Marquardt numerické algoritmy.

Příklady

L₁ minimalizace pro řídké zotavení

IRLS lze použít pro ℓ₁ minimalizace a vyhlazení ℓ_str minimalizace, str <1, v komprimované snímání problémy. Bylo prokázáno, že algoritmus má pro lineární rychlost konvergence ℓ₁ norma a superlineární pro ℓ_t s t <1, pod omezená izometrická vlastnost, což je obecně dostatečná podmínka pro řídká řešení.^[2][3] Ve většině praktických situací však není omezená vlastnost izometrie splněna.^{[Citace je zapotřebí ]}

L^str normová lineární regrese

Chcete-li najít parametry β = (β₁, …,β_k)^T které minimalizují L^str norma pro lineární regrese problém,

${displaystyle {underset {oldsymbol {eta}} {operatorname {arg, min}}} {ig |} mathbf {y} -X {oldsymbol {eta}} | _ {p} = {underset {oldsymbol {eta}} { operatorname {arg, min}}} součet _ {i = 1} ^ {n} left | y_ {i} -X_ {i} {oldsymbol {eta}} ight | ^ {p},}$

algoritmus IRLS v kroku t + 1 zahrnuje řešení vážené lineární nejmenší čtverce problém:^[4]

${displaystyle {oldsymbol {eta}} ^ {(t + 1)} = {podmnožina {oldsymbol {eta}} {operatorname {arg, min}}} součet _ {i = 1} ^ {n} w_ {i} ^ {(t)} vlevo | y_ {i} -X_ {i} {oldsymbol {eta}} ight | ^ {2} = (X ^ {m {T}} W ^ {(t)} X) ^ {- 1} X ^ {m {T}} W ^ {(t)} mathbf {y},}$

kde Ž^(t) je diagonální matice vah, obvykle se všemi prvky nastavenými zpočátku na:

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

a po každé iteraci aktualizován na:

${displaystyle w_ {i} ^ {(t)} = {ig |} y_ {i} -X_ {i} {oldsymbol {eta}} ^ {(t)} {ig |} ^ {p-2}.}$

V případě str = 1, odpovídá to nejmenší absolutní odchylka regrese (v tomto případě by se problém lépe vyřešil použitím lineární programování metody,^[5] takže výsledek by byl přesný) a vzorec je:

${displaystyle w_ {i} ^ {(t)} = {frac {1} {{ig |} y_ {i} -X_ {i} {oldsymbol {eta}} ^ {(t)} {ig |}}} .}$

Abyste se vyhnuli dělení nulou, regulace musí být provedeno, takže v praxi je vzorec:

${displaystyle w_ {i} ^ {(t)} = {frac {1} {max left {delta, left | y_ {i} -X_ {i} {oldsymbol {eta}} ^ {(t)} ight | ight }}}.}$

kde ${displaystyle delta}$ je nějaká malá hodnota, například 0,0001.^[5] Všimněte si použití ${displaystyle delta}$ ve funkci vážení je ekvivalentní s Huberova ztráta funkce v robustním odhadu. ^[6]

Viz také

• Realizovatelné zobecněné nejmenší čtverce
• Weiszfeldův algoritmus (pro přiblížení geometrický medián ), který lze považovat za zvláštní případ IRLS

Poznámky

Reference

• Numerické metody řešení problémů nejmenších čtverců od Åke Björcka (Kapitola 4: Zobecněné problémy nejmenších čtverců.)
• Praktické nejmenší čtverce pro počítačovou grafiku. Kurz SIGGRAPH 11

externí odkazy

• Řešte iterativně podceňované lineární systémy