Jaki algorytm stosuje się w regresji liniowej?

42

Zwykle słyszę o „zwykłych najmniejszych kwadratach”. Czy to najczęściej stosowany algorytm regresji liniowej? Czy istnieją powody, by użyć innego?

Belmont
źródło
@hxd, pomijając jakąkolwiek specjalną strukturę w macierzy projektowej, są to wszystkie algorytmy , różniące się tylko stałym współczynnikiem. Metoda dekompozycji jest dobrym nawykiem odziedziczonym z tradycji numerycznej algebry liniowej. O(mn2)
JM nie jest statystykiem
@hxd, i dlatego moja odpowiedź została opracowana tak, aby była prezentacją zaangażowanych algorytmów. Jeśli masz pytania nie ujęte w tym wątku, zastanów się nad zadaniem nowego pytania.
JM nie jest statystykiem

Odpowiedzi:

32

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=bbAC(A)

To best straight lineten, 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}) .e=Axbe2bC(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.bAb

ATAx^=ATbx^=(ATA)1ATb

a rzutowany wektor jest dany przez:b

b=Ax^=A(ATA)1ATb

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:

library(fBasics)

reg.data <- read.table(textConnection("
   b      x
  12      0
  10      1
   8      2
  11      3
   6      4
   7      5
   2      6
   3      7
   3      8 "), header = T)

attach(reg.data)

A <- model.matrix(b~x)

# intercept and slope
inv(t(A) %*% A) %*% t(A) %*% b

# fitted values - the projected vector b in the C(A)
A %*% inv(t(A) %*%A ) %*% t(A) %*% b

# The projection is easier if the orthogonal matrix Q is used, 
# because t(Q)%*%Q = I
Q <- qr.Q(qr(A))
R <- qr.R(qr(A))

# intercept and slope 
best.line <- inv(R) %*% t(Q) %*% b

# fitted values 
Q %*% t(Q) %*% b

plot(x,b,pch=16)
abline(best.line[1],best.line[2])
George Dontas
źródło
Mam błąd could not find inv?
hhh
1
Załaduj pakiet fBasics. finzi.psych.upenn.edu/R/library/fBasics/html/matrix-inv.html
George Dontas
5
Czy istnieje powód, aby używać inv z fBasics, gdy jest to tylko synonim rozwiązania? Czy nie byłoby lepiej, aby odpowiedź nie wymagała zależności od zewnętrznych pakietów, jeśli jest to niepotrzebne?
Dason,
@George Uwielbiam jasną odpowiedź. Myślę jednak, że pierwotne pytanie dotyczyło algorytmów, a QR jest tylko jednym z nich. Co z rozkładem LU, SVD, Cholesky'ego? Ponadto w R metoda na lmQR to powody, czy możesz wyjaśnić, dlaczego?
Haitao Du
@GeorgeDontas Pamiętaj, że może być tak, że nie jest odwracalny. Jak wyjaśniono w tej odpowiedzi , jednym ze sposobów radzenia sobie z tym jest usunięcie z kolumn które są liniowymi kombinacjami innych kolumn. ATAA
Oren Milman,
70

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)xjsin(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, .cjcjfj(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×nAfj(xi)ijc=(c1cn)j=1m(yjf(xj))2Acy2y=(y1ym)

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 .Ac

George już w swojej odpowiedzi pokazał metodę normalnych równań; po prostu rozwiązuje zbiór równań liniowychn×n

AAc=Ay

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).cAAAAGGGm×nn×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 QyAA=QRQRcR1Qy

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

RRc=Ay

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 QAAAQ

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 Σ VU V ΣAA=UΣVUVΣ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.

JM nie jest statystykiem
źródło
3
Ładne wyjaśnienie!
Mike Spivey,
Jak obliczyć, R^{-1} Q^T yjeśli A nie jest kwadratem? Czy upuszczasz zero wierszy w R?
bhan
1
@ bhan, zakładam „ekonomiczny” (lub „cienki”) wariant rozkładu QR, w którym jest kwadratowy, a ma takie same wymiary jak macierz projektowa. Coś do zrobienia: sprawdź różnicę między „pełnym QR” a „cienkim QR”. QRQ
JM nie jest statystykiem
@JM jakieś zalecenia dotyczące „dobrej książki na temat statystyki obliczeniowej i numerycznej algebry liniowej”? naprawdę chcę dowiedzieć się więcej.
Haitao Du
1
@hxd, z góry mojej głowy: Monahan dla statystyki obliczeniowej i Golub / van Loan dla numerycznej algebry liniowej.
JM nie jest statystykiem
6

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.

użytkownik603
źródło
1
Nie odpowiada na pytanie (strona nawet nie wspomina o QR)
użytkownik603,
4

Ł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.

Dirk Eddelbuettel
źródło
Właśnie dlatego uważam OLS za „algorytm” stosowany w regresji liniowej ...
Belmont,
3
Zwykłe najmniejsze kwadraty to estymator. Istnieje wiele algorytmów do obliczania oszacowania: zwykle stosuje się pewien rodzaj rozkładu macierzy ortogonalnej, taki jak QR. Zobacz en.wikipedia.org/wiki/…
Simon Byrne
4

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ą.

Jeromy Anglim
źródło
Przez algorytm rozumiem mniej więcej implementację oprogramowania zastosowaną do dopasowania linii do modelowania średniej rozkładu.
Belmont
3

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ć.

F. Tusell
źródło
1
Jeśli czytasz tę starą książkę, powinieneś również zapoznać się z Numerycznymi metodami rozwiązywania problemów najmniejszych kwadratów Åke Björcka , w których nie ma dyskusji na temat Lawsona / Hansona. Procedury zawarte w książce Lawson / Hanson są dostępne w Netlib .
JM nie jest statystykiem