Pitanje:
Koji se algoritam koristi u linearnoj regresiji?
Belmont
2010-08-18 18:30:32 UTC
view on stackexchange narkive permalink

Obično čujem za "obične najmanje kvadrate". Je li to najčešće korišten algoritam koji se koristi za linearnu regresiju? Postoje li razlozi za korištenje drugog?

@hxd, zabranjuje bilo koju posebnu strukturu u matrici dizajna, sve su to $ O (mn ^ 2) $ algoritmi, koji se razlikuju samo u konstantnom faktoru.Dekompozicijski pristup dobra je navika naslijeđena iz tradicije numeričke linearne algebre.
@hxd, i zato je moj odgovor skrojen tako da predstavlja izlaganje uključenih algoritama.Ako imate pitanja koja nisu obuhvaćena ovom niti, razmislite o postavljanju novog pitanja.
šest odgovori:
#1
+73
J. M. is not a statistician
2010-08-19 11:42:28 UTC
view on stackexchange narkive permalink

Da biste odgovorili na slovo pitanja, "obični najmanji kvadrati" nisu algoritam; nego je to vrsta problema u računalnoj linearnoj algebri, čiji je primjer linearna regresija. Obično netko ima podatke $ \ {(x_1, y_1), \ dots, (x_m, y_m) \} $ i okvirnu funkciju ("model") za uklapanje podataka, oblika $ f (x) = c_1 f_1 (x) + \ točkice + c_n f_n (x) $. $ F_j (x) $ nazivaju se "osnovnim funkcijama" i mogu biti bilo što, od monoma $ x ^ j $ do trigonometrijskih funkcija (npr. $ \ Sin (jx) $, $ \ cos (jx) $) i eksponencijalnih funkcija ($ \ exp (-jx) $). Izraz "linearno" u "linearnoj regresiji" ovdje se ne odnosi na osnovne funkcije, već na koeficijente $ c_j $, jer uzimanje djelomičnog izvoda modela u odnosu na bilo koji od $ c_j $ daje faktor množenja $ c_j $; odnosno $ f_j (x) $.

Jedan sada ima $ m \ puta n $ pravokutnu matricu $ \ mathbf A $ ("matrica dizajna") koja (obično) ima više redaka nego stupaca, i svaki je unos oblika $ f_j (x_i) $, $ i $ indeks reda, a $ j $ indeks stupca. OLS je sada zadatak pronalaženja vektora $ \ mathbf c = (c_1 \, \ dots \, c_n) ^ \ top $ koji minimalizira količinu $ \ sqrt {\ sum \ limit_ {j = 1} ^ {m} \ lijevo (y_j-f (x_j) \ desno) ^ 2} $ (u matričnom zapisu, $ \ | \ mathbf {A} \ mathbf {c} - \ mathbf {y} \ | _2 $; ovdje, $ \ mathbf { y} = (y_1 \, \ dots \, y_m) ^ \ top $ obično se naziva "vektor odgovora").

U praksi se koriste najmanje tri metode za izračunavanje rješenja s najmanjim kvadratima: normalne jednadžbe, QR dekompozicija i dekompozicija pojedinačne vrijednosti. Ukratko, to su načini za pretvaranje matrice $ \ mathbf {A} $ u proizvod matrica kojima se lako manipulira za rješavanje vektora $ \ mathbf {c} $.

George je već pokazao metoda normalnih jednadžbi u svom odgovoru; samo se rješava $ n \ puta n $ skup linearnih jednadžbi

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

za $ \ mathbf {c} $. Zbog činjenice da je matrica $ \ mathbf {A} ^ \ top \ mathbf {A} $ simetrično pozitivna (polu) određena, uobičajena metoda koja se koristi za to je Choleskyova dekompozicija koja utječe na $ \ mathbf {A} ^ \ top \ mathbf {A} $ u oblik $ \ mathbf {G} \ mathbf {G} ^ \ top $, s $ \ mathbf {G} $ donja trokutasta matrica. Problem s ovim pristupom, unatoč prednosti mogućnosti komprimiranja matrice $ m \ times n $ dizajna u (obično) mnogo manju matricu $ n \ times n $, jest taj što je ova operacija sklona gubitku značajnih brojki ovo ima neke veze s "brojem uvjeta" matrice dizajna).

Nešto bolji način je QR dekompozicija, koja izravno radi s matricom dizajna. Faktorizira $ \ mathbf {A} $ kao $ \ mathbf {A} = \ mathbf {Q} \ mathbf {R} $, gdje je $ \ mathbf {Q} $ ortogonalna matrica (množenjem takve matrice s transponiranjem dobije se matrica identiteta) i $ \ mathbf {R} $ je gornji trokut. $ \ mathbf {c} $ naknadno se izračunava kao $ \ mathbf {R} ^ {- 1} \ mathbf {Q} ^ \ top \ mathbf {y} $. Iz razloga iz kojih se neću upuštati (samo pogledajte bilo koji pristojan numerički linearni algebarski tekst, poput ovog), ovaj ima bolja numerička svojstva od metode normalnih jednadžbi.

Jedna varijacija u korištenju QR dekompozicije je metoda seminormalnih jednadžbi. Ukratko, ako netko ima dekompoziciju $ \ mathbf {A} = \ mathbf {Q} \ mathbf {R} $, linearni sustav koji treba riješiti poprima oblik

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

Učinkovito je da se pomoću QR dekompozicije formira Choleskyev trokut od $ \ mathbf {A} ^ \ top \ mathbf {A} $ u ovom pristupu. To je korisno u slučaju kada je $ \ mathbf {A} $ oskudan, a izričita pohrana i / ili formiranje $ \ mathbf {Q} $ (ili njegova faktorska verzija) je neželjeno ili nepraktično.

Konačno, najskuplji, ali najsigurniji način rješavanja OLS-a je dekompozicija pojedinačne vrijednosti (SVD). Ovaj se put $ \ mathbf {A} $ računa kao $ \ mathbf {A} = \ mathbf {U} \ mathbf \ Sigma \ mathbf {V} ^ \ top $, gdje $ \ mathbf {U} $ i $ \ mathbf {V} $ su oboje pravokutni, a $ \ mathbf {\ Sigma} $ je dijagonalna matrica, čiji se dijagonalni unosi nazivaju "pojedinačne vrijednosti". Moć ovog razlaganja leži u dijagnostičkoj sposobnosti koju su vam dodijelile pojedinačne vrijednosti, u tome što ako netko vidi jednu ili više malenih singularnih vrijednosti, onda je vjerojatno da ste odabrali ne potpuno neovisan skup osnova, pa je potrebna preformulacija svoj model. (Ranije spomenuti "uvjetni broj" zapravo je povezan s omjerom najveće singularne vrijednosti prema najmanjoj; omjer naravno postaje ogroman (a matrica je stoga loše uvjetovana) ako je najmanja singularna vrijednost "sićušna" .)

Ovo je samo skica ova tri algoritma; bilo koja dobra knjiga o računalnoj statistici i numeričkoj linearnoj algebri trebala bi vam dati relevantnije detalje.

Lijepo objašnjenje!
Kako izračunati `R ^ {- 1} Q ^ T y` ako A nije kvadrat?Ispadate li nula redaka u R?
@bhan, Pretpostavljam "ekonomičnu" (ili "tanku") varijantu QR dekompozicije, gdje je $ \ mathbf R $ kvadrat, a $ \ mathbf Q $ ima iste dimenzije kao matrica dizajna.Nešto što trebate učiniti: potražite razliku između "punog QR" i "tankog QR".
@J.M.bilo kakve preporuke o "dobroj knjizi o računalnoj statistici i numeričkoj linearnoj algebri"?stvarno želim naučiti više.
@hxd, s vrha glave: Monahan za računsku statistiku i Golub / van Loan za numeričku linearnu algebru.
@J.M.Stvarno poput vašeg odgovora, želite li ga poboljšati pokrivanjem više metoda, kao što su LU, Cholesky i iterativnih metoda kao što je gradijent pristojan?
Da ste pregledali moj post, @hxd,, vidjeli biste da sam već pokrivao Choleskog.LU se zapravo ne koristi za rješavanje problema s najmanjim kvadratima, jer ne koristi strukturu problema.Nikad nisam čuo da se gradijentni spust koristi za najmanje kvadrate;ako imate informacije o tome, napišite zaseban odgovor.
@hxd, za * nelinearne * probleme, naravno.Metode optimizacije skup su način rješavanja * linearnog * problema.
#2
+34
George Dontas
2010-08-18 21:19:28 UTC
view on stackexchange narkive permalink

Što se tiče pitanja iz naslova, o tome koji se algoritam koristi:

U perspektivi linearne algebre, algoritam linearne regresije način je za rješavanje linearnog sustava $ \ mathbf {A} x = b $ s više jednadžbi nego nepoznanica. U većini slučajeva za ovaj problem nema rješenja. A to je zato što vektor $ b $ ne pripada prostoru stupca $ \ mathbf {A} $, $ C (\ mathbf {A}) $.

najbolja ravna crta je ona koja ukupnu pogrešku $ e = \ mathbf {A} x-b $ čini koliko god je potrebna. A prikladno je smatrati da je kvadrat kvadratne duljine $ \ lVert e \ rVert ^ 2 $ malen, jer je nenegativan i iznosi 0 samo kada je $ b \ u C (\ mathbf {A}) $.

Projektiranjem (ortogonalno) vektora $ b $ na najbližu točku u prostoru stupca $ \ mathbf {A} $ daje se vektor $ b ^ * $ koji rješava sustav (njegove komponente leže na najbolja ravna crta) s minimalnom pogreškom.

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

i projicirani vektor $ b ^ * $ dat je kao:

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

Možda se metoda najmanje kvadrata ne koristi isključivo jer ta kvadratura prekompenzira izvanredne vrijednosti.

Dopustite mi jednostavan primjer u R-u koji rješava problem regresije pomoću ovog algoritma:

  knjižnica (fBasics) reg.data <- read.table (textConnection ( "bx 12 0 10 1 8 2 11 3 6 4 7 5 2 6 3 7 3 8"), zaglavlje = T) priložiti (reg.data) A <- model.matrix (b ~ x) # presretanje i nagibinv (t (A)% *% A)% *% t (A)% *% b # postavljene vrijednosti - projicirani vektor b u C (A) A% *% inv (t (A)% *% A)% *% t (A)% *% b # Projekcija je lakša ako se koristi ortogonalna matrica Q, # jer je t (Q)% *% Q = IQ <- qr.Q (qr (A)) R <- qr.R ( qr (A)) # presretanje i nagib najbolji.linija <- inv (R)% *% t (Q)% *% b
# ugrađene vrijednosti Q% *% t (Q)% *% bplot (x, b, pch = 16) abline (best.line [1], best.line [2])  
Dobio sam pogrešku `nisam mogao pronaći inv` ?!
Učitajte paket fBasics. http://finzi.psych.upenn.edu/R/library/fBasics/html/matrix-inv.html
Postoji li razlog za upotrebu poziva iz fBasics-a kada je to samo sinonim za rješavanje? Ne bi li bilo bolje da odgovor ne zahtijeva ovisnost o vanjskim paketima ako je nepotreban?
@George Volim jasan odgovor, međutim, mislim da je izvorno pitanje postavljalo algoritme, a QR je samo jedan od njih.Što kažete na LU, SVD, razgradnju Choleskog?Također, u R, metoda `lm` je QR, postoje razlozi za to, možete li objasniti zašto?
@GeorgeDontas Imajte na umu da možda $ A ^ T A $ nije invertibilan.Kao što je objašnjeno u [ovom odgovoru] (https://stats.stackexchange.com/a/363874/215801), jedan od načina rješavanja toga je uklanjanje iz $ A $ stupaca koji su linearne kombinacije ostalih stupaca.
#3
+6
user28
2010-08-18 19:01:06 UTC
view on stackexchange narkive permalink

wiki poveznica: Metode procjene za linearnu regresiju daju prilično opsežan popis metoda procjene, uključujući OLS i kontekst u kojem se koriste alternativne metode procjene.

Ne odnosi se na pitanje (na stranici se čak ni ne spominje QR)
#4
+4
Dirk Eddelbuettel
2010-08-18 19:01:20 UTC
view on stackexchange narkive permalink

Lako je zbuniti se između definicija i terminologije. Oba se izraza koriste, ponekad i naizmjenično. Brzo traženje na Wikipediji trebalo bi pomoći:

Obični najmanji kvadrati (OLS) metoda je koja se koristi za uklapanje u modele linearne regresije. Zbog vidljive dosljednosti i učinkovitosti (pod dodatnim pretpostavkama) metode OLS, ona je dominantan pristup. Pogledajte članke za daljnje potencijalne kupce.

Točno, zato smatram OLS "algoritmom" koji se koristi u linearnoj regresiji ...
Obični najmanji kvadratići su procjenitelji. Postoje razni algoritmi za izračunavanje procjene: obično se koristi neka vrsta dekompozicije pravokutne matrice, kao što je QR. Pogledajte http://en.wikipedia.org/wiki/Numerical_methods_for_linear_least_squares
#5
+4
Jeromy Anglim
2010-08-18 19:57:01 UTC
view on stackexchange narkive permalink

Sklon sam mišljenju 'najmanjih kvadrata' kao kriterija za definiranje najbolje prikladne regresione crte (tj. one koja čini zbroj 'kvadratnih' ostataka 'najmanje') i 'algoritma' u ovom kontekstu kao skupa koraka korištenih za određivanje koeficijenata regresije koji zadovoljavaju taj kriterij. Ova razlika sugerira da je moguće imati različite algoritme koji bi zadovoljili isti kriterij.

Bilo bi me znati znati čine li drugi tu razliku i koju terminologiju koriste.

Pod algoritmom mislim otprilike na softversku implementaciju koja se koristi za uklapanje linije za modeliranje srednje vrijednosti distribucije.
#6
+3
F. Tusell
2011-10-26 13:50:45 UTC
view on stackexchange narkive permalink

Stara knjiga, kojoj se ipak neprestano obraćam, je

Lawson, C.L. i Hanson, R.J. Rješavanje problema s najmanjim kvadratima , Prentice-Hall, 1974.

Sadrži detaljnu i vrlo čitljivu raspravu o nekim algoritmima koje su spominjali prethodni odgovori. Možda biste to htjeli pogledati.

Ako čitate ovu staru knjigu, trebali biste proučiti i Åkea Björcka * [Numeričke metode za probleme s najmanjim kvadratima] (http://books.google.com/books/?id=ZecsDBMz5-IC) *, u kojem nema stvari raspravljano u Lawson / Hanson. Rutine uključene u knjigu Lawson / Hanson su [dostupne na Netlibu] (http://netlib.org/lawson-hanson/).


Ova pitanja su automatski prevedena s engleskog jezika.Izvorni sadržaj dostupan je na stackexchange-u, što zahvaljujemo na cc by-sa 2.0 licenci pod kojom se distribuira.
Loading...