Iteracyjnie ponownie ważono najmniejszych kwadratów - Iteratively reweighted least squares

Część serii na
Analiza regresji
Modele
Regresja liniowa Prosta regresja Regresja wielomianowa Ogólny model liniowy
Uogólniony model liniowy Dyskretny wybór Regresja dwumianowa Regresja binarna Regresja logistyczna Logit wielomianowy Logit mieszany Probit Wielomianowy probit Zamówiony logit Zamówiony dowód Poissona
Model wielopoziomowy Naprawiono efekty Losowe efekty Liniowy model efektów mieszanych Nieliniowy model efektów mieszanych
Regresja nieliniowa Nieparametryczne Semiparametric Krzepki Kwantyla Izotoniczne Główne składniki Najmniejszy kąt Lokalny Podzielone
Błędy w zmiennych
Oszacowanie
Najmniej kwadratów Liniowy Nieliniowy
Zwyczajny Ważona Uogólnione
Częściowy Całkowity Nieujemne Regresja grzbietu Regularyzowany
Najmniej odchyleń bezwzględnych Iteracyjnie ponownie ważone Bayesian Wiele zmiennych bayesowskich
tło
Walidacja regresji Średnia i przewidywana odpowiedź Błędy i pozostałości Dobroć dopasowania Pozostałości studenckie Twierdzenie Gaussa – Markowa
Portal matematyka
v t mi

Metoda iteracyjnie ponownie ważonych najmniejszych kwadratów ( IRLS ) służy do rozwiązywania pewnych problemów optymalizacyjnych z obiektywnymi funkcjami postaci p- normy :

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

metodą iteracyjną, w której każdy krok polega na rozwiązaniu ważonego zadania najmniejszych kwadratów postaci:

${\ 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}}) {\ duży |} ^ {2}.}$

IRLS służy do znalezienia oszacowań maksymalnego prawdopodobieństwa uogólnionego modelu liniowego oraz w solidnej regresji do znalezienia estymatora M , jako sposób na złagodzenie wpływu wartości odstających w zbiorze danych o normalnym rozkładzie. Na przykład minimalizując najmniej błędów bezwzględnych, a nie najmniejszych błędów kwadratowych .

Jedną z zalet IRLS w porównaniu z programowaniem liniowym i wypukłym jest to, że można go używać z algorytmami numerycznymi Gaussa – Newtona i Levenberga – Marquardta .

Przykłady

Minimalizacja L ₁ dla rzadkiej regeneracji

IRLS może być używany do minimalizacji ℓ ₁ i wygładzonej minimalizacji ℓ _p , p  <1, w przypadku problemów z wykrywaniem skompresowanym . Udowodniono, że algorytm ma liniową szybkość zbieżności dla ℓ ₁ normą i superlinear o £ -l _t o t  <1, pod ograniczonym własności izometrii , która jest na ogół wystarczająca warunkiem rzadkich rozwiązań. Jednak w większości praktycznych sytuacji ograniczona właściwość izometrii nie jest spełniona.

L ^p normalna regresja liniowa

Aby znaleźć parametry β  = ( β ₁ ,…, β _k ) ^T, które minimalizują normę L ^p dla problemu regresji liniowej ,

${\ Displaystyle {\ underset {\ boldsymbol {\ beta}} {\ operatorname {arg \, min}}} {\ duży \ |} \ 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},}$

algorytm IRLS w kroku t  + 1 polega na rozwiązaniu ważonego liniowego problemu najmniejszych kwadratów :

${\ 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},}$

gdzie W ^{( t )} jest ukośną macierzą wag, zwykle ze wszystkimi elementami ustawionymi początkowo na:

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

i aktualizowane po każdej iteracji do:

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

W przypadku p  = 1 odpowiada to najmniejszej bezwzględnej regresji odchyleń (w tym przypadku do problemu lepiej byłoby podejść metodami programowania liniowego , więc wynik byłby dokładny) i wzór jest następujący:

${\ Displaystyle w_ {i} ^ {(t)} = {\ Frac {1} {{\ duży |} y_ {i} -X_ {i} {\ boldsymbol {\ beta}} ^ {(t)} { \ big |}}}.}$

Aby uniknąć dzielenia przez zero, należy dokonać regularyzacji , więc w praktyce wzór wygląda następująco:

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

gdzie jest jakaś mała wartość, na przykład 0,0001. Należy zauważyć, że użycie w funkcji ważenia jest równoważne z funkcją straty Hubera w solidnej estymacji. ${\ displaystyle \ delta}$${\ displaystyle \ delta}$

Zobacz też

• Możliwe uogólnione najmniejsze kwadraty
• Algorytm Weiszfelda (do przybliżania mediany geometrycznej ), który można traktować jako szczególny przypadek IRLS

Uwagi

Bibliografia

• Metody numeryczne dla problemów najmniejszych kwadratów autorstwa Åke Björcka (Rozdział 4: Uogólnione problemy najmniejszych kwadratów).
• Praktyczne metody najmniejszych kwadratów w grafice komputerowej. Kurs SIGGRAPH 11

Zewnętrzne linki

• Rozwiązuj niedookreślone systemy liniowe iteracyjnie