Najmniejsze bezwzględne odchylenia - Least absolute deviations

Najmniejsze odchylenia bezwzględne ( LAD ), znane również jako najmniejsze błędy bezwzględne ( LAE ), najmniejsza wartość bezwzględna ( LAV ), najmniejsza bezwzględna reszta ( LAR ), suma odchyleń bezwzględnych lub warunek normy L ₁ , jest statystycznym kryterium optymalności, a technika optymalizacji statystycznej , która na nim bazuje. Podobnie jak technika najmniejszych kwadratów , próbuje znaleźć funkcję, która ściśle aproksymuje zbiór danych. W prostym przypadku zbioru danych ( x , y ) funkcją aproksymacji jest prosta „linia trendu” w dwuwymiarowych współrzędnych kartezjańskich . Metoda minimalizuje sumę błędów bezwzględnych (SAE) (suma wartości bezwzględnych „reszt” pionowych między punktami generowanymi przez funkcję a odpowiadającymi im punktami w danych). Oszacowanie najmniejszych odchyleń bezwzględnych powstaje również jako oszacowanie maksymalnego prawdopodobieństwa, jeśli błędy mają rozkład Laplace'a . Został wprowadzony w 1757 roku przez Rogera Josepha Boscovicha .

Sformułowanie

Załóżmy, że zbiór danych składa się z punktów ( x _i , y _i ) o i = 1, 2, ..., n . Chcemy znaleźć funkcję f taką, że${\ Displaystyle f (x_ {i}) \ w przybliżeniu y_ {i}.}$

Aby osiągnąć ten cel, zakładamy, że funkcja f ma określoną postać zawierającą pewne parametry, które należy określić. Na przykład najprostsza postać byłaby liniowa: f ( x ) = bx + c , gdzie b i c to parametry, których wartości nie są znane, ale które chcielibyśmy oszacować. Prościej załóżmy, że f ( x ) jest kwadratowe , co oznacza, że f ( x ) = ax ² + bx + c , gdzie a , b i c nie są jeszcze znane. (Ogólnie rzecz biorąc, może istnieć nie tylko jeden eksplanator x , ale raczej wiele eksplanatorów, wszystkie pojawiające się jako argumenty funkcji f .)

Poszukujemy teraz szacunkowych wartości nieznanych parametrów, które minimalizują sumę bezwzględnych wartości reszt:

${\ Displaystyle S = \ suma _ {i = 1} ^ {n} | y_ {i} -f (x_ {i}) |.}$

Rozwiązanie

Chociaż idea regresji najmniejszych odchyleń bezwzględnych jest tak samo prosta, jak regresji najmniejszych kwadratów, linia najmniejszych odchyleń bezwzględnych nie jest tak prosta do wydajnego obliczenia. W przeciwieństwie do regresji najmniejszych kwadratów, regresja najmniejszych odchyleń bezwzględnych nie ma analitycznej metody rozwiązywania. Dlatego wymagane jest podejście iteracyjne. Poniżej znajduje się wyliczenie niektórych metod rozwiązywania najmniejszych odchyleń bezwzględnych.

• Metody oparte na simpleksie (takie jak algorytm Barrodale-Roberts)
  • Ponieważ problemem jest program liniowy , można zastosować dowolną z wielu technik programowania liniowego (w tym metodę simpleks i inne).
• Iteracyjnie ponownie ważone najmniejszych kwadratów
• Metoda bezpośredniego zejścia Wesołowskiego
• Metoda maksymalnego prawdopodobieństwa Li-Arce
• Podejście rekurencyjnej redukcji wymiarowości
• Sprawdź wszystkie kombinacje linii punkt-punkt pod kątem minimalnej sumy błędów

Metody oparte na simpleksie są „preferowanym” sposobem rozwiązywania problemu najmniejszych odchyleń bezwzględnych. Metoda Simplex to metoda rozwiązywania problemu w programowaniu liniowym. Najpopularniejszym algorytmem jest zmodyfikowany algorytm Barrodale-Roberts Simplex. Algorytmy dla IRLS, metody Wesołowskiego i metody Li można znaleźć w dodatku A wśród innych metod. Sprawdzenie wszystkich kombinacji linii przechodzących przez dowolne dwa (x,y) punkty danych to kolejna metoda znajdowania linii o najmniejszych odchyleniach bezwzględnych. Ponieważ wiadomo, że co najmniej jedna linia odchyleń bezwzględnych przechodzi przez co najmniej dwa punkty danych, ta metoda znajdzie linię, porównując SAE (najmniejszy błąd bezwzględny w punktach danych) każdej linii i wybierając linię o najmniejszym SAE. Ponadto, jeśli wiele linii ma ten sam, najmniejszy SAE, wówczas linie wyznaczają region wielu rozwiązań. Choć prosta, ta ostateczna metoda jest nieefektywna w przypadku dużych zestawów danych.

Korzystanie z programowania liniowego

Problem można rozwiązać przy użyciu dowolnej techniki programowania liniowego na następującej specyfikacji problemu. Chcemy

${\ Displaystyle {\ tekst {Minimalizuj}} \ suma _ {i = 1} ^ {n} | y_ {i} -a_ {0}-a_ {1} x_ {i1} -a_ {2} x_ {i2} -\cdots -a_{k}x_{ik}|}$

ze względu na dobór wartości parametrów , gdzie y _i jest wartością i- ^tej obserwacji zmiennej zależnej, a x _ij jest wartością i- ^tej obserwacji j- ^tej zmiennej niezależnej ( j = 1, ..., k ). Przepiszmy ten problem w kategoriach zmiennych sztucznych u _i as ${\displaystyle a_{0},\ldots,a_{k}}$

${\ Displaystyle {\ tekst {Minimalizuj}} \ suma _ {i = 1} ^ {n} u_ {i}}$

w odniesieniu do i${\displaystyle a_{0},\ldots,a_{k}}$${\displaystyle u_{1},\ldots,u_{n}}$

podlega

${\ Displaystyle u_ {i} \ geq y_ {i} -a_{0}-a_ {1}x_ {i1} -a_ {2}x_ {i2} - \ cdots -a_ {k} x_ {ik} \, \ \,\ \,\ \,\ \,\ {\text{dla }}i=1,\ldots ,n}$

${\ Displaystyle u_ {i} \ geq - [y_ {i} -a_ {0}-a_ {1} x_ {i1} - a_ {2} x_ {i2} - \ cdots - a_ {k} x_ {ik} ]\,\ \,\ {\text{ dla }}i=1,\ldots ,n.}$

Te ograniczenia skutkują wymuszaniem równości każdego z nich po zminimalizowaniu, więc funkcja celu jest równoważna pierwotnej funkcji celu. Ponieważ ta wersja instrukcji problemu nie zawiera operatora wartości bezwzględnej, jest w formacie, który można rozwiązać za pomocą dowolnego pakietu programowania liniowego. ${\displaystyle u_{i}}$${\ Displaystyle | y_ {i} -a_ {0}-a_ {1}x_ {i1} -a_ {2} x_ {i2} - \ cdots - a_ {k} x_ {ik} |}$

Nieruchomości

Istnieją inne unikalne własności linii najmniejszych odchyleń bezwzględnych. W przypadku zestawu danych ( x , y ) linia najmniejszych odchyleń bezwzględnych zawsze przechodzi przez co najmniej dwa punkty danych, chyba że istnieje wiele rozwiązań. Jeśli istnieje wiele rozwiązań, wówczas obszar prawidłowych rozwiązań najmniejszych odchyleń bezwzględnych będzie ograniczony przez co najmniej dwie linie, z których każda przechodzi przez co najmniej dwa punkty danych. Mówiąc bardziej ogólnie, jeśli istnieje k regresorów (w tym stała), to co najmniej jedna optymalna powierzchnia regresji przejdzie przez k punktów danych.

To „zatrzaskiwanie” linii do punktów danych może pomóc w zrozumieniu właściwości „niestabilności”: jeśli linia zawsze zatrzaśnie się w co najmniej dwóch punktach, to linia będzie przeskakiwać między różnymi zestawami punktów w miarę zmiany punktów danych. „Zatrzaskiwanie” pomaga również zrozumieć właściwość „odporności”: jeśli istnieje wartość odstająca, a linia najmniejszego odchylenia bezwzględnego musi zatrzasnąć się na dwóch punktach danych, wartość odstająca najprawdopodobniej nie będzie jednym z tych dwóch punktów, ponieważ nie będzie to minimalizować suma odchyleń bezwzględnych w większości przypadków.

Jednym znanym przypadkiem, w którym istnieje wiele rozwiązań, jest zbiór punktów symetrycznych względem linii poziomej, jak pokazano na rysunku A poniżej.

Rysunek A: Zestaw punktów danych z rozwiązaniami symetrii odbicia i wielokrotnymi najmniejszymi odchyleniami bezwzględnymi. „Obszar rozwiązania” jest zaznaczony na zielono. Pionowe niebieskie linie reprezentują bezwzględne błędy od różowej linii do każdego punktu danych. Różowa linia to jedno z nieskończenie wielu rozwiązań w obszarze zieleni.

Aby zrozumieć, dlaczego istnieje wiele rozwiązań w przypadku pokazanym na rysunku A, rozważ różową linię w zielonym obszarze. Jej sumą błędów bezwzględnych jest pewna wartość S. Gdyby przechylić linię nieco w górę, jednocześnie utrzymując ją w zielonym obszarze, suma błędów nadal wynosiłaby S. Nie zmieniłaby się, ponieważ odległość od każdego punktu do linia rośnie po jednej stronie linii, podczas gdy odległość do każdego punktu po przeciwnej stronie linii zmniejsza się dokładnie o taką samą wartość. Zatem suma błędów bezwzględnych pozostaje taka sama. Ponadto, ponieważ można przechylać linię w nieskończenie małych krokach, pokazuje to również, że jeśli jest więcej niż jedno rozwiązanie, jest nieskończenie wiele rozwiązań.

Zalety i wady

Poniżej znajduje się tabela zestawiająca niektóre właściwości metody najmniejszych odchyleń bezwzględnych z właściwościami metody najmniejszych kwadratów (dla problemów nieosobliwych).

*Pod warunkiem, że liczba punktów danych jest większa lub równa liczbie funkcji.

Metoda najmniejszych odchyleń bezwzględnych znajduje zastosowanie w wielu obszarach, ze względu na swoją odporność w porównaniu z metodą najmniejszych kwadratów. Najmniejsze bezwzględne odchylenia są solidne, ponieważ są odporne na wartości odstające w danych. LAD kładzie jednakowy nacisk na wszystkie obserwacje, w przeciwieństwie do zwykłych najmniejszych kwadratów (OLS), które poprzez podniesienie do kwadratu reszt przypisują większą wagę dużym resztom, czyli wartościom odstającym, w których przewidywane wartości są dalekie od rzeczywistych obserwacji. Może to być pomocne w badaniach, w których wartościom odstającym nie trzeba przypisywać większej wagi niż innym obserwacjom. Jeśli ważne jest, aby nadać większą wagę wartościom odstającym, lepszym wyborem jest metoda najmniejszych kwadratów.

Odmiany, rozszerzenia, specjalizacje

Jeżeli w sumie wartości bezwzględnych reszt uogólnimy funkcję wartości bezwzględnej na nachyloną funkcję wartości bezwzględnej, która na lewej półprostej ma nachylenie a na prawej półprostej nachylenie , gdzie , otrzymujemy regresję kwantylową . Przypadek daje standardową regresję przez najmniejsze odchylenia bezwzględne i jest również znany jako regresja mediana. ${\ Displaystyle \ tau -1}$${\ Displaystyle \ tau}$${\displaystyle 0<\tau <1}$${\ Displaystyle \ tau = 1/2}$

Problem najmniejszego odchylenia bezwzględnego można rozszerzyć o wiele objaśnień, ograniczeń i regularyzacji , np. model liniowy z ograniczeniami liniowymi:

zminimalizować ${\ Displaystyle S (\ mathbf {\ beta}, b) = \ suma _ {i} | \ mathbf {x} '_ {i} \ mathbf {\ beta} + b-y_ {i} |}$

z zastrzeżeniem m.in. ${\ Displaystyle \ mathbf {x} '_ {1} \ mathbf {\ beta} + b-y_ {1} \ równoważnik k}$

gdzie jest wektorem kolumnowym współczynników do oszacowania, b jest wyrazem wolnym do oszacowania, x _i jest wektorem kolumnowym i- ^tej obserwacji na różnych objaśnieniach, y _i jest i- ^tą obserwacją zmiennej zależnej, a k jest znana stała. ${\displaystyle \mathbf {\beta}}$

Regularyzacja z Lasso może być również połączony z LAD.

Zobacz też

• Regresja kwantylowa
• Analiza regresji
• Model regresji liniowej
• Odchylenie bezwzględne
• Średnie odchylenie bezwzględne
• Mediana bezwzględnego odchylenia
• Zwykłe najmniejsze kwadraty
• Solidna regresja

Bibliografia

Dalsza lektura

• Petera Bloomfielda i Williama Steigera (1980). „Dopasowanie krzywej najmniejszych bezwzględnych odchyleń”. SIAM Journal on Scientific Computing . 1 (2): 290–301. doi : 10.1137/0901019 .
• Subhash C. Narula i John F. Wellington (1982). „Minimalna suma błędów bezwzględnych regresji: stan badań”. Międzynarodowy Przegląd Statystyczny . 50 (3): 317–326. doi : 10.2307/1402501 . JSTOR  1402501 .
• Robert F. Phillips (lipiec 2002). „Oszacowanie najmniejszych odchyleń bezwzględnych za pomocą algorytmu EM”. Statystyka i informatyka . 12 (3): 281–285. doi : 10.1023/A:1020759012226 .
• Enno Siemsen i Kenneth A. Bollen (2007). „Oszacowanie najmniejszego odchylenia bezwzględnego w modelowaniu równań strukturalnych”. Metody i badania socjologiczne . 36 (2): 227–265. doi : 10.1177/0049124107301946 .