Küsimus:
Millist algoritmi kasutatakse lineaarses regressioonis?
Belmont
2010-08-18 18:30:32 UTC
view on stackexchange narkive permalink

Tavaliselt kuulen "tavalistest kõige väiksematest ruutudest". Kas see on lineaarse regressiooni jaoks kõige enam kasutatav algoritm? Kas on põhjust kasutada teist?

@hxd,, mis keelab mis tahes spetsiaalse struktuuri kujundusmaatriksis, on need kõik $ O (mn ^ 2) $ algoritmid, mis erinevad ainult konstantse teguri poolest.Lagunemiskäsitlus on hea harjumus, mis on päritud numbrilise lineaaralgebra traditsioonist.
@hxd, ja seetõttu kohandati minu vastus käsitletavate algoritmide kirjelduseks.Kui teil on selle lõimaga hõlmamata küsimusi, kaaluge uue küsimuse esitamist.
Kuus vastused:
#1
+73
J. M. is not a statistician
2010-08-19 11:42:28 UTC
view on stackexchange narkive permalink

Küsimuse tähele vastamiseks ei ole "tavalised kõige väiksemad ruudud" algoritm; pigem on see arvutusliku lineaaralgebra probleem, mille lineaarne regressioon on üks näide. Tavaliselt on sellel andmed $ \ {(x_1, y_1), \ dots, (x_m, y_m) \} $ ja esialgne funktsioon ("mudel"), millele andmed sobivad, kujul $ f (x) = c_1 f_1 (x) + \ dots + c_n f_n (x) $. $ F_j (x) $ nimetatakse "baasfunktsioonideks" ja need võivad olla ükskõik millised, alates monoomidest $ x ^ j $ kuni trigonomeetriliste funktsioonideni (nt $ \ sin (jx) $, $ \ cos (jx) $) ja eksponentsiaalseteks funktsioonideks ($ \ exp (-jx) $). Termin "lineaarne" ei viita "lineaarses regressioonis" siin põhifunktsioonidele, vaid koefitsientidele $ c_j $, kuna mudeli osalise tuletise võtmine mis tahes $ c_j $ suhtes annab teile teguri, mis korrutab $ c_j $; see tähendab, et $ f_j (x) $.

Ühel on nüüd ristkülikukujuline maatriks $ m \ korda n $ $ \ mathbf A $ ("kujundusmaatriks"), millel (tavaliselt) on rohkem ridu kui veerge, ja iga kirje on kujul $ f_j (x_i) $, $ i $ on reaindeks ja $ j $ on veeruindeks. Nüüd on OLS ülesandeks leida vektor $ \ mathbf c = (c_1 \, \ dots \, c_n) ^ \ top $, mis minimeerib koguse $ \ sqrt {\ sum \ limits_ {j = 1} ^ {m} \ vasakule (y_j-f (x_j) \ right) ^ 2} $ (maatriksnoteeringus $ \ | \ mathbf {A} \ mathbf {c} - \ mathbf {y} \ | _2 $; siin, $ \ mathbf { y} = (y_1 \, dots \, y_m) ^ \ top $ nimetatakse tavaliselt "vastusvektoriks").

Praktikas on vähemalt kolme ruutu lahenduste arvutamiseks kasutatud vähemalt kolme meetodit: normaalvõrrandid, QR lagunemine ja ainsuse väärtuse lagunemine. Lühidalt öeldes on need viisid maatriksi $ \ mathbf {A} $ teisendamiseks maatriksite korrutiseks, mida saab hõlpsasti manipuleerida vektori $ \ mathbf {c} $ lahendamiseks.

George näitas juba normaalvõrrandite meetod tema vastuses; lihtsalt lahendatakse lineaarvõrrandite komplekt $ n \ korda n $

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

for $ \ mathbf {c} $. Tulenevalt asjaolust, et maatriks $ \ mathbf {A} ^ \ top \ mathbf {A} $ on sümmeetriliselt positiivne (pool) kindel, on selleks tavaliselt kasutatav meetod Cholesky lagunemine, mis tegurid $ \ mathbf {A} ^ \ top \ mathbf {A} $ vormi $ \ mathbf {G} \ mathbf {G} ^ \ top $, kusjuures $ \ mathbf {G} $ on madalam kolmnurkmaatriks. Vaatamata sellele eelisele, et kujundusmaatriksit $ m \ times n $ saab tihendada (tavaliselt) palju väiksemaks $ n \ korda n $ maatriksiks, on selle lähenemisviisi probleem see, et see operatsioon on altid oluliste arvude kadumisele ( see on midagi pistmist kujundusmaatriksi "tingimusnumbriga").

Veidi parem viis on QR-lagundamine, mis töötab otseselt kujundusmaatriksiga. See arvutab $ \ mathbf {A} $ as $ \ mathbf {A} = \ mathbf {Q} \ mathbf {R} $, kus $ \ mathbf {Q} $ on ristkülikukujuline maatriks (korrutades sellist maatriksit selle transpositsiooniga, saadakse identiteedimaatriks) ja $ \ mathbf {R} $ on ülemine kolmnurk. $ \ mathbf {c} $ arvutatakse seejärel järgmiselt: $ \ mathbf {R} ^ {- 1} \ mathbf {Q} ^ \ top \ mathbf {y} $. Põhjustel, kuhu ma ei satu (vaadake lihtsalt korralikku arvulist lineaarset algebrateksti, näiteks see), on sellel paremad arvulised omadused kui tavaliste võrrandite meetodil.

Üks variatsioon QR lagundamise kasutamisel on seminormaalsete võrrandite meetod. Lühidalt, kui ühel on lagunemine $ \ mathbf {A} = \ mathbf {Q} \ mathbf {R} $, on lahendatav lineaarne süsteem kuju

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

Tõhusalt kasutatakse QR-i lagunemist, moodustades koli kolmnurga $ \ mathbf {A} ^ \ top \ mathbf {A} $ selles lähenemisviisis. See on kasulik juhul, kui $ \ mathbf {A} $ on hõre ja $ \ mathbf {Q} $ (või selle faktversioon) selgesõnaline salvestamine ja / või moodustamine on soovimatu või ebapraktiline.

Lõpuks, kõige kallim, kuid kõige turvalisem viis OLS-i lahendamiseks on ainsuse väärtuse lagunemine (SVD). Seekord arvutatakse $ \ mathbf {A} $ kujul $ \ mathbf {A} = \ mathbf {U} \ mathbf \ Sigma \ mathbf {V} ^ \ top $, kus $ \ mathbf {U} $ ja $ \ mathbf {V} $ on mõlemad ristkülikud ja $ \ mathbf {\ Sigma} $ on diagonaalmaatriks, mille diagonaalkirjeid nimetatakse "ainsuse väärtusteks". Selle lagunemise jõud peitub ainsuse väärtuste teile antud diagnostilises võimes selles, et kui näete ühte või mitut pisikest ainsuse väärtust, siis on tõenäoline, et olete valinud mitte täiesti iseseisva aluse, mis tingib vajaduse oma mudel. (Varem mainitud "tingimusnumber" on tegelikult seotud suurima ainsuse väärtuse ja väikseima suhtega; suhe muutub muidugi tohutuks (ja maatriks on seega halva tingimusega), kui väikseim ainsuse väärtus on "väike" .)

See on vaid visand nendest kolmest algoritmist; iga hea raamat arvutistatistika ja arvulise lineaaralgebra kohta peaks suutma anda teile asjakohasemat teavet.

Mõnus selgitus!
Kuidas arvutate `R ^ {- 1} Q ^ T y`, kui A pole ruut?Kas loobute nullist reast R-s?
@bhan, Eeldan QR-i lagunemise varianti "ökonoomne" (või "õhuke"), kus $ \ mathbf R $ on ruut ja $ \ mathbf Q $ on samade mõõtmetega kui kujundusmaatriks.Midagi teie jaoks teha: otsige erinevust "täis QR" ja "õhuke QR" vahel.
@J.M.soovitusi teemal "hea raamat arvutistatistika ja numbrilise lineaaralgebra kohta"?tõesti tahad rohkem teada saada.
@hxd, mu pea kohal: Monahan arvutusstatistika jaoks ja Golub / van Loan numbrilise lineaaralgebra jaoks.
@J.M.Nagu teie vastus meeldib teile, kas soovite seda täiendada, hõlmates rohkem meetodeid, näiteks LU, Cholesky ja iteratiivseid meetodeid, nagu gradient korralik?
Oleksite mu postitust läbi vaadanud, @hxd,, oleksite näinud, et ma juba Choleskyt kajastasin.LU-d ei kasutata tegelikult vähimruutude probleemide lahendamiseks, kuna see ei kasuta ära probleemi struktuuri.Ma pole kunagi kuulnud, et gradientlangust oleks kasutatud kõige väiksemate ruutude jaoks;kui teil on selle kohta teavet, kirjutage eraldi vastus.
@hxd, * mittelineaarsete * probleemide jaoks, kindlasti.Optimeerimismeetodid on kallis viis * lineaarse * probleemi lahendamiseks.
#2
+34
George Dontas
2010-08-18 21:19:28 UTC
view on stackexchange narkive permalink

Mis puutub pealkirjas olevasse küsimusse, siis milline on kasutatav algoritm:

Lineaarse algebra perspektiivis on lineaarse regressiooni algoritm viis lahendada lineaarset süsteemi $ \ mathbf {A} x = b $ rohkem võrranditega kui tundmatud. Enamasti pole sellele probleemile lahendust. Ja seda seetõttu, et vektor $ b $ ei kuulu veeru ruumi $ \ mathbf {A} $, $ C (\ mathbf {A}) $.

parim sirgjoon muudab vea $ e = \ mathbf {A} x-b $ nii väikeseks kui kulub. Ja seda on mugav mõelda nii väikseks, et see oleks ruutu pikkus $ \ lVert e \ rVert ^ 2 $, kuna see pole negatiivne ja võrdub 0-ga ainult siis, kui $ b \ on C (\ mathbf {A}) $.

Vektori $ b $ (ortogonaalselt) projitseerimine lähima punktini veeru ruumis $ \ mathbf {A} $ annab vektorile $ b ^ * $, mis lahendab süsteemi (selle komponendid asuvad parim sirge) minimaalse veaga.

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

ja projektsioonivektori $ b ^ * $ annab:

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

Võib-olla ei kasutata vähimruutude meetodit eksklusiivselt , kuna see ruudukujundus kompenseerib välissummad liiga palju.

Lubage mul tuua R-s lihtne näide, mis lahendab regressiooniprobleemi selle algoritmi abil:

  library (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"), päis = T) manus (reg.andmed) <- mudel.maatriks (b ~ x) # lõikepunkt ja slopeinv (t (A)% *% A)% *% t (A)% *% b # sobitatud väärtused - projitseeritud vektor b C (A) A% *% inv (t (A)% *% A)% *% t (A)% *% b # Projektsioon on lihtsam, kui kasutatakse ortogonaalset maatriksit Q, # kuna t (Q)% *% Q = IQ <- qr.Q (qr (A)) R <- qr.R ( qr (A)) # lõikepunkt ja kalle kõige paremini. joon <- inv (R)% *% t (Q)% *% b
# sobitatud väärtused Q% *% t (Q)% *% bplot (x, b, pch = 16) joon (parim.rida [1], parim.rida [2])  
Mul on viga `ei leidnud inv`i ?!
Laadige fBasicsi pakett. http://finzi.psych.upenn.edu/R/library/fBasics/html/matrix-inv.html
Kas on põhjust kasutada inv from fBasics, kui see on lihtsalt lahenduse sünonüüm? Kas poleks parem, kui vastus ei nõua sõltuvust välistest pakettidest, kui see pole vajalik?
@George Mulle meeldib selge vastus. Kuid ma arvan, et algses küsimuses küsiti algoritme ja QR on lihtsalt üks sellest.Kuidas oleks LU, SVD, koleski lagunemisega?Samuti on R-is `lm` meetod QR, sellel on põhjuseid, kas saaksite seletada, miks?
@GeorgeDontas Pange tähele, et võib juhtuda, et $ A ^ T A $ pole pööratav.Nagu [selles vastuses] (https://stats.stackexchange.com/a/363874/215801) on selgitatud, on üks viis sellega toime tulla, eemaldades veergudest $ A $ veerud, mis on teiste veergude lineaarsed kombinatsioonid.
#3
+6
user28
2010-08-18 19:01:06 UTC
view on stackexchange narkive permalink

Vikilink: Lineaarse regressiooni hindamismeetodid annab üsna põhjaliku loetelu hindamismeetoditest, sealhulgas OLS ja kontekstid, milles kasutatakse alternatiivseid hindamismeetodeid.

Ei käsitle küsimust (lehel pole isegi QR-d mainitud)
#4
+4
Dirk Eddelbuettel
2010-08-18 19:01:20 UTC
view on stackexchange narkive permalink

Definitsioonide ja terminoloogia vahel on lihtne segi minna. Mõlemat terminit kasutatakse mõnikord vahetatult. Kiire otsing Wikipediast peaks aitama:

Tavalised kõige väiksemad ruudud (OLS) on meetod, mida kasutatakse lineaarse regressiooni mudelite sobitamiseks. OLS-meetodi demonstreeritava järjepidevuse ja efektiivsuse tõttu (täiendavate eelduste kohaselt) on see domineeriv lähenemisviis. Lisateavet leiate artiklitest.

Eks seepärast pean OLS-i lineaarses regressioonis kasutatavaks "algoritmiks" ...
Hinnanguline on tavaline väikseim ruut. Hinnangu arvutamiseks on mitmesuguseid algoritme: tavaliselt kasutatakse mingit ortogonaalset maatriksi lagunemist, näiteks QR. Vt http://et.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

Kipun kõige paremini sobituva regressioonijoone (st selle, mis muudab ruuduliste jääkide summa kõige väiksemaks) määramise kriteeriumiks kriteeriumi „kõige väiksemad ruudud“ ja „kontekstis algoritmi“ kui komplekti kriteeriumile vastavate regressioonikordajate määramiseks kasutatavate sammude arv. See eristamine viitab sellele, et on võimalik omada erinevaid algoritme, mis vastavad samale kriteeriumile.

Mul oleks huvitav teada, kas teised teevad seda vahet ja millist terminoloogiat nad kasutavad.

Algoritmi all mõtlen ma umbes tarkvara rakendamist, mida kasutatakse joone keskmise modelleerimiseks joone sobitamiseks.
#6
+3
F. Tusell
2011-10-26 13:50:45 UTC
view on stackexchange narkive permalink

Vana raamat, mille poole pöördun korduvalt, on

Lawson, C.L. ja Hanson, R.J. Vähimruutude probleemide lahendamine , Prentice-Hall, 1974.

See sisaldab üksikasjalikku ja väga loetavat arutelu algoritmide üle, mida varasemad vastused on maininud. Võiksite seda vaadata.

Kui loete seda vana raamatut, peaksite uurima ka Åke Björcki raamatut * [Numerical Methods for Least Squares Problems] (http://books.google.com/books/?id=ZecsDBMz5-IC) *, milles pole asju arutati Lawson / Hansonis. Lawsoni / Hansoni raamatus sisalduvad rutiinid on [saadaval Netlibist] (http://netlib.org/lawson-hanson/).


See küsimus ja vastus tõlgiti automaatselt inglise keelest.Algne sisu on saadaval stackexchange-is, mida täname cc by-sa 2.0-litsentsi eest, mille all seda levitatakse.
Loading...