Zwykle słyszę o „zwykłych najmniejszych kwadratach”. Czy to najczęściej stosowany algorytm regresji liniowej? Czy istnieją powody, by użyć innego?
42
Zwykle słyszę o „zwykłych najmniejszych kwadratach”. Czy to najczęściej stosowany algorytm regresji liniowej? Czy istnieją powody, by użyć innego?
Odpowiedzi:
Jeśli chodzi o pytanie w tytule, jaki jest używany algorytm:
W perspektywie algebry liniowej algorytm regresji liniowej jest sposobem rozwiązania układu liniowego przy większej liczbie równań niż nieznane. W większości przypadków nie ma rozwiązania tego problemu. A to dlatego, że wektor nie należy do przestrzeni kolumn , .Ax=b b A C(A)
Toe=Ax−b ∥e∥2 b∈C(A)
best straight line
ten, który sprawia, że ogólny błąd tak mały, jak potrzeba. I wygodnie jest uważać za małą kwadratową długość, , ponieważ nie jest ujemna i równa się 0, gdy b \ w C (\ mathbf {A}) .Rzutowanie (ortogonalnie) wektora do najbliższego punktu w przestrzeni kolumn daje wektor który rozwiązuje układ (jego komponenty leżą na najlepszej linii prostej) z minimalnym błędem.b A b∗
a rzutowany wektor jest dany przez:b∗
Być może metoda najmniejszych kwadratów nie jest stosowana wyłącznie, ponieważ
squaring
nadmiernie kompensuje wartości odstające.Podam prosty przykład w języku R, który rozwiązuje problem regresji za pomocą tego algorytmu:
źródło
could not find inv
?lm
QR to powody, czy możesz wyjaśnić, dlaczego?Aby odpowiedzieć na literę pytania, „zwykłe najmniejsze kwadraty” nie są algorytmem; jest raczej rodzajem problemu w obliczeniowej algebrze liniowej, którego regresją liniową jest jeden przykład. Zwykle mamy dane i funkcję („model”), aby dopasować dane, w postaci . są nazywane "funkcji bazowych" i może być coś z jednomianów do funkcji trygonometrycznych (np , ) i funkcji wykładniczej ( ). Termin „liniowy” w „regresji liniowej” nie odnosi się tutaj do funkcji podstawowych,{(x1,y1),…,(xm,ym)} f(x)=c1f1(x)+⋯+cnfn(x) fj(x) xj sin(jx) cos(jx) c j c j c j f j ( x )exp(−jx) cj , przy tym biorąc częściową pochodną modelu w odniesieniu do dowolnego z daje współczynnik ; to znaczy, .cj cj fj(x)
Jeden ma teraz prostokątną matrycę ( „matrycy projektu”), e (zwykle) ma dwa rzędy niż kolumny i każda pozycja ma postać , będącej indeksem wiersza a będącego indeks kolumny. OLS jest teraz zadaniem znalezienia wektora który minimalizuje ilość (w notacji macierzowej, ; tutaj, jest zwykle nazywany „wektorem odpowiedzi”).A f j ( x i ) i j c = ( c 1m×n A fj(xi) i j √c=(c1…cn)⊤ ∑j=1m(yj−f(xj))2−−−−−−−−−−−−−√ ∥Ac−y∥2 y=(y1…ym)⊤
Istnieją w praktyce co najmniej trzy metody obliczania rozwiązań metodą najmniejszych kwadratów: równania normalne, rozkład QR i rozkład wartości osobliwych. W skrócie, są to sposoby na przekształcenie macierzy w produkt macierzy, które można łatwo manipulować w celu rozwiązania dla wektora .A c
George już w swojej odpowiedzi pokazał metodę normalnych równań; po prostu rozwiązuje zbiór równań liniowychn×n
for . Z uwagi na fakt, że macierz jest symetrycznie dodatnia (pół) określona, typową metodą stosowaną do tego jest rozkład Cholesky'ego, który to czynniki do postaci , z dolną trójkątną matrycą. Problem z tym podejściem, pomimo korzyści polegającej na możliwości kompresji macierzy projektowej do (zwykle) znacznie mniejszej macierzy , polega na tym, że operacja ta jest podatna na utratę znaczących liczb (ma to coś do zrobić z „numerem stanu” macierzy projektu).c A⊤A A⊤A GG⊤ G m×n n×n
Nieco lepszym sposobem jest rozkład QR, który bezpośrednio współpracuje z matrycą projektową. Uwzględnia jako , gdzie jest macierzą ortogonalną (pomnożenie takiej macierzy przez jej transpozycję daje macierz tożsamości) i ma górny trójkąt. jest następnie obliczany jako . Z powodów, dla których się nie wchodzę (wystarczy zobaczyć jakiś przyzwoity numeryczny tekst algebry liniowej, taki jak ten ), ma on lepsze właściwości numeryczne niż metoda równań normalnych.A = Q R Q R c R - 1 Q ⊤ yA A=QR Q R c R−1Q⊤y
Jedną z odmian wykorzystania rozkładu QR jest metoda równań semormormalnych . W skrócie, jeśli ktoś ma rozkład , układ liniowy, który ma być rozwiązany, przyjmuje postaćA=QR
W rzeczywistości, w tym podejściu używa się rozkładu QR do utworzenia trójkąta Cholesky'ego z . Jest to przydatne w przypadku, gdy jest rzadki, a jawne przechowywanie i / lub tworzenie (lub jego faktorowanej wersji) jest niepożądane lub niepraktyczne.A QA⊤A A Q
Wreszcie, najdroższym, ale najbezpieczniejszym sposobem rozwiązania OLS jest rozkład wartości osobliwych (SVD). Tym razem jest uwzględniony jako , gdzie i są ortogonalne iA = U Σ V ⊤ U V ΣA A=UΣV⊤ U V Σ jest macierzą diagonalną, której wpisy diagonalne nazywane są „wartościami pojedynczymi”. Siła tego rozkładu polega na zdolności diagnostycznej przyznanej ci przez wartości osobliwe, w tym sensie, że jeśli zobaczysz jedną lub więcej niewielkich wartości pojedynczych, prawdopodobnie wybierzesz niezupełnie niezależny zbiór podstaw, co będzie wymagało przeformułowania twój model. (Wspomniany wcześniej „numer warunku” jest w rzeczywistości związany ze stosunkiem największej liczby pojedynczej do najmniejszej; stosunek oczywiście staje się ogromny (a zatem macierz jest źle warunkowana), jeśli najmniejsza liczba pojedyncza jest „mała” .)
To tylko szkic tych trzech algorytmów; każda dobra książka na temat statystyki obliczeniowej i numerycznej algebry liniowej powinna być w stanie podać ci bardziej odpowiednie szczegóły.
źródło
R^{-1} Q^T y
jeśli A nie jest kwadratem? Czy upuszczasz zero wierszy w R?Link wiki: Metody szacowania dla regresji liniowej daje dość wyczerpującą listę metod szacowania, w tym OLS i konteksty, w których stosowane są alternatywne metody szacowania.
źródło
Łatwo jest pomylić definicje i terminologię. Oba terminy są używane, czasami zamiennie. Szybkie wyszukiwanie w Wikipedii powinno pomóc:
Zwyczajne najmniejsze kwadraty (OLS) to metoda stosowana do dopasowania modeli regresji liniowej. Ze względu na możliwą do wykazania spójność i wydajność (przy dodatkowych założeniach) metody OLS jest to podejście dominujące. Zobacz artykuły dla dalszych potencjalnych klientów.
źródło
Staram się myśleć o „najmniejszych kwadratach” jako kryterium definiowania najlepiej dopasowanej linii regresji (tj. Takiej, która sprawia, że suma „kwadratów” reszt jest najmniejsza) i „algorytmu” w tym kontekście jako zestawu zastosowanych kroków w celu ustalenia współczynników regresji, które spełniają to kryterium. To rozróżnienie sugeruje, że możliwe są różne algorytmy spełniające to samo kryterium.
Byłbym ciekawy, czy inni to rozróżniają i jakiej terminologii używają.
źródło
Jest to stara książka, do której jednak często się zwracam
Lawson, CL i Hanson, RJ Solving Least Squares Problems , Prentice-Hall, 1974.
Zawiera szczegółowe i bardzo czytelne omówienie niektórych algorytmów wspomnianych w poprzednich odpowiedziach. Możesz na to spojrzeć.
źródło