Jaki algorytm stosuje się w regresji liniowej?

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

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 , .$\mathbf{A}x=b$$b$$\mathbf{A}$$C(\mathbf{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=\mathbf{A}x-b$$\lVert e \rVert^2$$b\in 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$$\mathbf{A}$$b^*$

$\mathbf{A}^T\mathbf{A}\hat{x}=\mathbf{A}^Tb \Rightarrow \hat{x}=(\mathbf{A}^T\mathbf{A})^{-1}\mathbf{A}^Tb$

a rzutowany wektor jest dany przez:$b^*$

$b^*=\mathbf{A}\hat{x}=\mathbf{A}(\mathbf{A}^T\mathbf{A})^{-1}\mathbf{A}^Tb$

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])

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,$\{(x_1,y_1),\dots,(x_m,y_m)\}$$f(x)=c_1 f_1(x)+\dots+c_n f_n(x)$$f_j(x)$$x^j$$\sin(jx)$$\cos(jx)$c j c j c j f j ( x $\exp(-jx)$$c_j$, przy tym biorąc częściową pochodną modelu w odniesieniu do dowolnego z daje współczynnik ; to znaczy, .$c_j$$c_j$$f_j(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 $m\times n$$\mathbf A$$f_j(x_i)$$i$$j$$\mathbf c=(c_1\,\dots\,c_n)^\top$$\sqrt{\sum\limits_{j=1}^{m}\left(y_j-f(x_j)\right)^2}$$\|\mathbf{A}\mathbf{c}-\mathbf{y}\|_2$$\mathbf{y}=(y_1\,\dots\,y_m)^\top$

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 .$\mathbf{A}$$\mathbf{c}$

George już w swojej odpowiedzi pokazał metodę normalnych równań; po prostu rozwiązuje zbiór równań liniowych$n\times n$

$\mathbf{A}^\top\mathbf{A}\mathbf{c}=\mathbf{A}^\top\mathbf{y}$

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).$\mathbf{c}$$\mathbf{A}^\top\mathbf{A}$$\mathbf{A}^\top\mathbf{A}$$\mathbf{G}\mathbf{G}^\top$$\mathbf{G}$$m\times n$$n\times 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 ⊤ $\mathbf{A}$$\mathbf{A}=\mathbf{Q}\mathbf{R}$$\mathbf{Q}$$\mathbf{R}$$\mathbf{c}$$\mathbf{R}^{-1}\mathbf{Q}^\top\mathbf{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ć$\mathbf{A}=\mathbf{Q}\mathbf{R}$

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 $\mathbf{A}^\top\mathbf{A}$$\mathbf{A}$$\mathbf{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 $\mathbf{A}$$\mathbf{A}=\mathbf{U}\mathbf \Sigma\mathbf{V}^\top$$\mathbf{U}$$\mathbf{V}$$\mathbf{\Sigma}$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.

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.

Łatwo jest pomylić definicje i terminologię. Oba terminy są używane, czasami zamiennie. Szybkie wyszukiwanie w Wikipedii powinno pomóc:

• zwykłe najmniejsze kwadraty
• regresja liniowa

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.

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

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