Vraag:
Welk algoritme wordt gebruikt bij lineaire regressie?
Belmont
2010-08-18 18:30:32 UTC
view on stackexchange narkive permalink

Ik hoor meestal over "gewone kleinste kwadraten". Is dat het meest gebruikte algoritme voor lineaire regressie? Zijn er redenen om een ​​andere te gebruiken?

@hxd, behoudens enige speciale structuur in de ontwerpmatrix, dit zijn allemaal $ O (mn ^ 2) $ algoritmen, die alleen verschillen in de constante factor.De decompositiebenadering is een goede gewoonte die is geërfd van de traditie van numerieke lineaire algebra.
@hxd, en daarom was mijn antwoord op maat gemaakt om een uiteenzetting te zijn van de betrokken algoritmen.Als je vragen hebt die niet in deze thread worden behandeld, overweeg dan om een nieuwe vraag te stellen.
Zes antwoorden:
#1
+73
J. M. is not a statistician
2010-08-19 11:42:28 UTC
view on stackexchange narkive permalink

Om de letter van de vraag te beantwoorden: "gewone kleinste kwadraten" is geen algoritme; het is eerder een soort probleem in computationele lineaire algebra, waarvan lineaire regressie een voorbeeld is. Meestal heeft men gegevens $ \ {(x_1, y_1), \ dots, (x_m, y_m) \} $ en een voorlopige functie ("model") om de gegevens tegen te passen, in de vorm $ f (x) = c_1 f_1 (x) + \ dots + c_n f_n (x) $. De $ f_j (x) $ worden "basisfuncties" genoemd en kunnen van alles zijn, van monomials $ x ^ j $ tot trigonometrische functies (bijv. $ \ Sin (jx) $, $ \ cos (jx) $) en exponentiële functies ($ \ exp (-jx) $). De term "lineair" in "lineaire regressie" verwijst hier niet naar de basisfuncties, maar naar de coëfficiënten $ c_j $, in die zin dat het nemen van de partiële afgeleide van het model met betrekking tot een van de $ c_j $ je de factor vermenigvuldiging geeft $ c_j $; dat wil zeggen $ f_j (x) $.

Men heeft nu een $ m \ times n $ rechthoekige matrix $ \ mathbf A $ ("ontwerpmatrix") die (gewoonlijk) meer rijen dan kolommen heeft, en elk item heeft de vorm $ f_j (x_i) $, $ i $ is de rij-index en $ j $ is de kolomindex. OLS is nu de taak om de vector $ \ mathbf c = (c_1 \, \ dots \, c_n) ^ \ top $ te vinden die de hoeveelheid $ \ sqrt {\ sum \ limits_ {j = 1} ^ {m} \ minimaliseert left (y_j-f (x_j) \ right) ^ 2} $ (in matrixnotatie, $ \ | \ mathbf {A} \ mathbf {c} - \ mathbf {y} \ | _2 $; hier $ \ mathbf { y} = (y_1 \, \ dots \, y_m) ^ \ top $ wordt gewoonlijk de "antwoordvector" genoemd).

Er zijn in de praktijk ten minste drie methoden voor het berekenen van oplossingen met de kleinste kwadraten: de normale vergelijkingen, QR-ontleding en singuliere waarde-ontleding. Kort gezegd: het zijn manieren om de matrix $ \ mathbf {A} $ om te zetten in een product van matrices die gemakkelijk kunnen worden gemanipuleerd om de vector $ \ mathbf {c} $ op te lossen.

George liet de methode van normale vergelijkingen in zijn antwoord; men lost gewoon de $ n \ times n $ reeks lineaire vergelijkingen op

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

voor $ \ mathbf {c} $. Vanwege het feit dat de matrix $ \ mathbf {A} ^ \ top \ mathbf {A} $ symmetrisch positief (semi) definitief is, is de gebruikelijke methode hiervoor Cholesky-decompositie, die $ \ mathbf {A} ^ \ top \ mathbf {A} $ in de vorm $ \ mathbf {G} \ mathbf {G} ^ \ top $, met $ \ mathbf {G} $ een onderste driehoekige matrix. Het probleem met deze benadering, ondanks het voordeel van het kunnen comprimeren van de $ m \ times n $ ontwerpmatrix in een (meestal) veel kleinere $ n \ maal n $ matrix, is dat deze bewerking vatbaar is voor verlies van significante cijfers ( dit heeft iets te maken met het "conditienummer" van de ontwerpmatrix).

Een iets betere manier is QR-decompositie, die direct werkt met de ontwerpmatrix. Het houdt rekening met $ \ mathbf {A} $ als $ \ mathbf {A} = \ mathbf {Q} \ mathbf {R} $, waarbij $ \ mathbf {Q} $ een orthogonale matrix is ​​(het vermenigvuldigen van een dergelijke matrix met zijn transpositie geeft een identiteitsmatrix) en $ \ mathbf {R} $ is een bovenste driehoek. $ \ mathbf {c} $ wordt vervolgens berekend als $ \ mathbf {R} ^ {- 1} \ mathbf {Q} ^ \ top \ mathbf {y} $. Om redenen waar ik niet op inga (zie gewoon een fatsoenlijke numerieke lineaire algebra-tekst, zoals deze), heeft dit betere numerieke eigenschappen dan de methode van normale vergelijkingen.

Eén variatie in het gebruik van de QR-ontleding is de methode van seminormale vergelijkingen. In het kort, als men de decompositie $ \ mathbf {A} = \ mathbf {Q} \ mathbf {R} $ heeft, heeft het op te lossen lineaire systeem de vorm

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

In feite gebruikt men de QR-decompositie om de Cholesky-driehoek van $ \ mathbf {A} ^ \ top \ mathbf {A} $ in deze benadering. Dit is handig in het geval waarin $ \ mathbf {A} $ schaars is, en de expliciete opslag en / of vorming van $ \ mathbf {Q} $ (of een ingecalculeerde versie ervan) ongewenst of onpraktisch is.

Ten slotte is de duurste en toch veiligste manier om OLS op te lossen de singular value decomposition (SVD). Deze keer wordt $ \ mathbf {A} $ meegerekend als $ \ mathbf {A} = \ mathbf {U} \ mathbf \ Sigma \ mathbf {V} ^ \ top $, waarbij $ \ mathbf {U} $ en $ \ mathbf {V} $ zijn beide orthogonaal, en $ \ mathbf {\ Sigma} $ is een diagonale matrix, waarvan de diagonale ingangen "singuliere waarden" worden genoemd. De kracht van deze ontbinding ligt in het diagnostische vermogen dat u wordt verleend door de singuliere waarden, in die zin dat als men een of meer kleine singuliere waarden ziet, het waarschijnlijk is dat u een niet geheel onafhankelijke basisset heeft gekozen, waardoor een herformulering van uw model. (Het eerder genoemde 'conditienummer' is in feite gerelateerd aan de verhouding van de grootste singuliere waarde tot de kleinste; de ​​ratio wordt natuurlijk enorm (en de matrix is ​​dus slecht geconditioneerd) als de kleinste singuliere waarde 'klein' is .)

Dit is slechts een schets van deze drie algoritmen; elk goed boek over computationele statistieken en numerieke lineaire algebra zou je meer relevante details moeten kunnen geven.

Leuke uitleg!
Hoe bereken je `R ^ {- 1} Q ^ T y` als A niet vierkant is?Laat je de nulrijen in R vallen?
@bhan, Ik ga uit van de "economy" (of "dunne") variant van QR-decompositie, waarbij $ \ mathbf R $ vierkant is en $ \ mathbf Q $ dezelfde afmetingen heeft als de ontwerpmatrix.Iets voor jou om te doen: zoek het verschil op tussen "volledige QR" en "dunne QR".
@J.M.enige aanbevelingen over "goed boek over computationele statistieken en numerieke lineaire algebra"?wil echt meer leren.
@hxd, uit mijn hoofd: Monahan voor computationele statistiek en Golub / van Loan voor numerieke lineaire algebra.
@J.M.Vind je je antwoord echt leuk, zou je het willen verbeteren door meer methoden te behandelen, zoals LU, Cholesky en iteratieve methoden zoals gradiënt fatsoenlijk?
Als je mijn post had bekeken, @hxd,, had je gezien dat ik Cholesky al had besproken.LU wordt niet echt gebruikt om de kleinste-kwadratenproblemen op te lossen, omdat het de structuur van het probleem niet benut.Ik heb nog nooit gehoord dat gradiëntafdaling wordt gebruikt voor de kleinste vierkanten;Als je hier informatie over hebt, schrijf dan een apart antwoord.
@hxd, voor * niet-lineaire * problemen, zeker.Optimalisatiemethoden zijn een dure manier om een * lineair * probleem op te lossen.
#2
+34
George Dontas
2010-08-18 21:19:28 UTC
view on stackexchange narkive permalink

Wat betreft de vraag in de titel, wat is het algoritme dat wordt gebruikt:

In een lineair algebra-perspectief is het lineaire regressie-algoritme de manier om een ​​lineair systeem op te lossen $ \ mathbf {A} x = b $ met meer vergelijkingen dan onbekenden. In de meeste gevallen is er geen oplossing voor dit probleem. En dit komt doordat de vector $ b $ niet tot de kolomruimte van $ \ mathbf {A} $, $ C (\ mathbf {A}) $ behoort.

De beste rechte lijn is degene die de algehele fout $ e = \ mathbf {A} x-b $ zo klein maakt als nodig is. En het is handig om als klein te denken als de lengte in het kwadraat, $ \ lVert e \ rVert ^ 2 $, omdat het niet negatief is, en het is alleen gelijk aan 0 als $ b \ in C (\ mathbf {A}) $.

Projecteren (orthogonaal) van de vector $ b $ naar het dichtstbijzijnde punt in de kolomruimte van $ \ mathbf {A} $ geeft de vector $ b ^ * $ die het systeem oplost (de componenten liggen op de beste rechte lijn) met de minimale fout.

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

en de geprojecteerde vector $ b ^ * $ wordt gegeven door:

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

Misschien wordt de methode met de kleinste kwadraten niet exclusief gebruikt, omdat die kwadratuur uitbijters overcompenseert.

Laat me een eenvoudig voorbeeld geven in R, dat het regressieprobleem oplost met behulp van dit algoritme:

  bibliotheek (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"), header = T) attach (reg.data) A <- model.matrix (b ~ x) # intercept en hellinginv (t (A)% *% A)% *% t (A)% *% b # aangepaste waarden - de geprojecteerde vector b in de C (A) A% *% inv (t (A)% *% A)% *% t (A)% *% b # De projectie is gemakkelijker als de orthogonale matrix Q wordt gebruikt, # omdat t (Q)% *% Q = IQ <- qr.Q (qr (A)) R <- qr.R ( qr (A)) # onderscheppen en beste helling. lijn <- inv (R)% *% t (Q)% *% b
# aangepaste waarden Q% *% t (Q)% *% bplot (x, b, pch = 16) abline (best.line [1], best.line [2])  
Ik krijg een foutmelding `kon inv` niet vinden ?!
Laad het fBasics-pakket. http://finzi.psych.upenn.edu/R/library/fBasics/html/matrix-inv.html
Is er een reden om inv van fBasics te gebruiken als het slechts een synoniem is voor oplossen? Zou het niet beter zijn als het antwoord geen afhankelijkheid van externe pakketten vereist als het niet nodig is?
@George Ik ben dol op het duidelijke antwoord, maar ik denk dat de oorspronkelijke vraag het stellen van algoritmen was, en QR is er slechts een van.Hoe zit het met de ontbinding van LU, SVD, Cholesky?Ook in R is de methode voor 'lm' QR, daar zijn redenen voor, kun je uitleggen waarom?
@GeorgeDontas Merk op dat het kan zijn dat $ A ^ T A $ niet omkeerbaar is.Zoals uitgelegd in [dit antwoord] (https://stats.stackexchange.com/a/363874/215801), is een manier om hiermee om te gaan, het verwijderen van $ A $ kolommen die lineaire combinaties zijn van andere kolommen.
#3
+6
user28
2010-08-18 19:01:06 UTC
view on stackexchange narkive permalink

De wikilink: Estimation Methods for Linear Regression geeft een vrij uitgebreide lijst van schattingsmethoden, waaronder OLS en de contexten waarin alternatieve schattingsmethoden worden gebruikt.

Beantwoordt de vraag niet (de pagina vermeldt niet eens QR)
#4
+4
Dirk Eddelbuettel
2010-08-18 19:01:20 UTC
view on stackexchange narkive permalink

Het is gemakkelijk om verwarring te raken tussen definities en terminologie. Beide termen worden gebruikt, soms door elkaar. Een snelle zoekactie op Wikipedia zou moeten helpen:

Ordinary Least Squares (OLS) is een methode die wordt gebruikt om lineaire regressiemodellen te passen. Vanwege de aantoonbare consistentie en efficiëntie (onder aanvullende aannames) van de OLS-methode, is het de dominante benadering. Zie de artikelen voor verdere aanwijzingen.

Juist, daarom beschouw ik OLS als een "algoritme" dat wordt gebruikt in lineaire regressie ...
Gewone kleinste kwadraten is een schatter. Er zijn verschillende algoritmen voor het berekenen van de schatting: meestal wordt een soort orthogonale matrixontleding, zoals QR, gebruikt. Zie 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

Ik heb de neiging om 'kleinste kwadraten' te beschouwen als een criterium voor het definiëren van de best passende regressielijn (dat wil zeggen, degene die de som van 'kwadraat' residuen 'het minst' maakt) en het 'algoritme' in deze context als de set van stappen die worden gebruikt om de regressiecoëfficiënten te bepalen die aan dat criterium voldoen. Dit onderscheid suggereert dat het mogelijk is om verschillende algoritmen te hebben die aan hetzelfde criterium voldoen.

Ik zou graag willen weten of anderen dit onderscheid maken en welke terminologie ze gebruiken.

Met algoritme bedoel ik ruwweg de software-implementatie die wordt gebruikt om een ​​regel aan te passen om het gemiddelde van een distributie te modelleren.
#6
+3
F. Tusell
2011-10-26 13:50:45 UTC
view on stackexchange narkive permalink

Een oud boek, maar een boek waar ik mezelf herhaaldelijk naar verwijs, is

Lawson, C.L. en Hanson, R.J. Solving Least Squares Problems , Prentice-Hall, 1974.

Het bevat een gedetailleerde en zeer leesbare bespreking van enkele van de algoritmen die in eerdere antwoorden werden genoemd. Misschien wil je ernaar kijken.

Als je dit oude boek leest, zou je ook Åke Björck's * [Numerical Methods for Least Squares Problems] (http://books.google.com/books/?id=ZecsDBMz5-IC) * moeten bekijken, die dingen niet besproken in Lawson / Hanson. De routines die zijn opgenomen in het Lawson / Hanson-boek zijn [verkrijgbaar bij Netlib] (http://netlib.org/lawson-hanson/).


Deze Q&A is automatisch vertaald vanuit de Engelse taal.De originele inhoud is beschikbaar op stackexchange, waarvoor we bedanken voor de cc by-sa 2.0-licentie waaronder het wordt gedistribueerd.
Loading...