Kysymys:
Mitä algoritmia käytetään lineaarisessa regressiossa?
Belmont
2010-08-18 18:30:32 UTC
view on stackexchange narkive permalink

Kuulen yleensä "tavallisista pienimmistä neliöistä". Onko se eniten käytetty algoritmi, jota käytetään lineaarisessa regressiossa? Onko syytä käyttää toista?

@hxd,, joka estää minkä tahansa erityisen rakenteen suunnittelumatriisissa, ovat kaikki $ O (mn ^ 2) $ -algoritmeja, jotka eroavat toisistaan vain vakiotekijän suhteen.Hajoamismenetelmä on hyvä tapa, joka on peritty numeerisen lineaarisen algebran perinteestä.
@hxd, ja siksi vastaukseni räätälöitiin esittämään mukana olevat algoritmit.Jos sinulla on kysymyksiä, joita tämä säie ei kata, harkitse uuden kysymyksen esittämistä.
Kuusi vastused:
#1
+73
J. M. is not a statistician
2010-08-19 11:42:28 UTC
view on stackexchange narkive permalink

Kysymyksen kirjaimeen vastaamiseksi "tavalliset pienimmät neliöt" ei ole algoritmi; pikemminkin se on tietyntyyppinen ongelma laskennallisessa lineaarisessa algebrassa, josta yksi esimerkki on lineaarinen regressio. Tavallisesti yhdellä on tiedot $ \ ((x_1, y_1), \ pisteet, (x_m, y_m) \} $ ja alustava funktio ("malli"), johon tiedot sovitetaan, muodossa $ f (x) = c_1 f_1 (x) + \ pistettä + c_n f_n (x) $. $ F_j (x) $ kutsutaan "perustoiminnoiksi", ja ne voivat olla mitä tahansa monomaaaleista $ x ^ j $ trigonometrisiin funktioihin (esim. $ \ Sin (jx) $, $ \ cos (jx) $) ja eksponentiaalisiin funktioihin ($ \ exp (-jx) $). Termi "lineaarinen" "lineaarisessa regressiossa" tässä ei viittaa perustoimintoihin, vaan kertoimiin $ c_j $ siinä, että mallin osittaisen johdannaisen ottaminen mihin tahansa $ c_j $: sta antaa sinulle kertoimen $ c_j $; eli $ f_j (x) $.

Yhdellä on nyt $ m \ kertaa n $ suorakulmainen matriisi $ \ mathbf A $ ("suunnittelumatriisi"), jolla (yleensä) on enemmän rivejä kuin sarakkeita, ja jokainen merkintä on muodoltaan $ f_j (x_i) $, $ i $ on riviindeksi ja $ j $ on sarakeindeksi. OLS: n tehtävänä on nyt löytää vektori $ \ mathbf c = (c_1 \, \ dots \, c_n) ^ \ top $, joka minimoi määrän $ \ sqrt {\ sum \ limits_ {j = 1} ^ {m} \ vasen (y_j-f (x_j) \ oikea) ^ 2} $ (matriisimerkinnässä $ \ | \ mathbf {A} \ mathbf {c} - \ mathbf {y} \ | _2 $; tässä, $ \ mathbf { y} = (y_1 \, \ pisteet \, y_m) ^ \ top $ kutsutaan yleensä "vastevektoriksi").

Käytännössä käytetään ainakin kolmea menetelmää pienimmän neliösumman ratkaisujen laskemiseksi: normaaliyhtälöt, QR-hajoaminen ja yksikköarvon hajoaminen. Lyhyesti sanottuna ne ovat tapoja muuttaa matriisi $ \ mathbf {A} $ matriisien tuloksi, joita on helppo käsitellä vektorin $ \ mathbf {c} $ ratkaisemiseksi.

George osoitti jo normaalien yhtälöiden menetelmä vastauksessaan; ratkaistaan ​​vain lineaaristen yhtälöiden $ n \ kertaa n $ joukko

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

kohteelle $ \ mathbf {c} $. Johtuen siitä, että matriisi $ \ mathbf {A} ^ \ top \ mathbf {A} $ on symmetrinen positiivinen (puoli) selvä, tavallinen tähän käytetty menetelmä on Cholesky-hajoaminen, joka kertoo $ \ mathbf {A} ^ \ top \ mathbf {A} $ muotoon $ \ mathbf {G} \ mathbf {G} ^ \ top $ ja $ \ mathbf {G} $ alemman kolmion matriisin. Tämän lähestymistavan ongelmana on se etu, että $ m \ times n $ -matriisista voidaan pakata (yleensä) paljon pienempi $ n \ kertaa n $ -matriisi, että tämä operaatio on taipuvainen merkittävien lukujen menetykseen ( tällä on jotain tekemistä suunnittelumatriisin "ehtonumeron" kanssa.

Hieman parempi tapa on QR-hajoaminen, joka toimii suoraan suunnittelumatriisin kanssa. Se kertoo $ \ mathbf {A} $ as $ \ mathbf {A} = \ mathbf {Q} \ mathbf {R} $, missä $ \ mathbf {Q} $ on ortogonaalinen matriisi (kertomalla tällainen matriisi sen transponoidulla saadaan identiteettimatriisi) ja $ \ mathbf {R} $ on ylempi kolmiomainen. $ \ mathbf {c} $ lasketaan myöhemmin nimellä $ \ mathbf {R} ^ {- 1} \ mathbf {Q} ^ \ top \ mathbf {y} $. Syistä, joihin en pääse (katso vain kunnollinen numeerinen lineaarinen algebrateksti, kuten tämä), tällä on paremmat numeeriset ominaisuudet kuin normaalien yhtälöiden menetelmällä.

Yksi vaihtelu QR-hajotuksen käytössä on seminaalinormaalien yhtälöiden menetelmä. Lyhyesti sanottuna, jos jollakin on hajotus $ \ mathbf {A} = \ mathbf {Q} \ mathbf {R} $, ratkaistava lineaarinen järjestelmä on muoto

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

Käytetään käytännössä QR-hajotusta muodostaen koleskyinen kolmio $ \ mathbf {A} ^ \ top \ mathbf {A} $ tässä lähestymistavassa. Tämä on hyödyllinen tilanteessa, jossa $ \ mathbf {A} $ on harva ja $ \ mathbf {Q} $ (tai sen eräs versio) nimenomainen tallennus ja / tai muodostus on ei-toivottua tai epäkäytännöllistä.

Lopuksi, kallein, mutta turvallisin tapa ratkaista OLS on singular value decomposition (SVD). Tällä kertaa $ \ mathbf {A} $ lasketaan muodossa $ \ mathbf {A} = \ mathbf {U} \ mathbf \ Sigma \ mathbf {V} ^ \ top $, missä $ \ mathbf {U} $ ja $ \ mathbf {V} $ ovat molemmat kohtisuoria, ja $ \ mathbf {\ Sigma} $ on lävistäjämatriisi, jonka lävistäjämerkintöjä kutsutaan "yksikköarvoiksi". Tämän hajoamisen voima on diagnoosikyvyssä, jonka yksittäiset arvot antavat sinulle siinä, että jos joku näkee yhden tai useamman pienen yksikön arvon, on todennäköistä, että olet valinnut ei täysin itsenäisen perustan, mikä edellyttää mallisi. (Aikaisemmin mainittu "ehtoluku" liittyy itse asiassa suurimman yksikköarvon ja pienimmän väliseen suhteeseen; suhde tietysti kasvaa valtavaksi (ja matriisi on siten huonosti ehdollistettu), jos pienin yksikköarvo on "pieni" .)

Tämä on vain luonnos näistä kolmesta algoritmista; minkä tahansa hyvän kirjan laskennallisista tilastoista ja numeerisesta lineaarisesta algebrasta pitäisi pystyä antamaan sinulle olennaisempia yksityiskohtia

Hieno selitys!
Kuinka lasketaan `R ^ {- 1} Q ^ T y`, jos A ei ole neliö?Pudotatko nollarivit R: ssä?
@bhan, Oletan QR-hajoamisen "taloudelliseksi" (tai "ohueksi") muunnokseksi, jossa $ \ mathbf R $ on neliö ja $ \ mathbf Q $ on samat mitat kuin suunnittelumatriisi.Jotain sinun tehtäväsi: etsi ero "täyden QR: n" ja "ohuen QR: n" välillä.
@J.M.onko suosituksia "hyvästä laskennallisen tilastotiedon ja numeerisen lineaarisen algebran kirjasta"?todella haluavat oppia lisää.
@hxd, pois pääni päältä: Monahan laskennallisiin tilastoihin ja Golub / van Loan numeeriseen lineaariseen algebraan.
@J.M.Haluatko todella vastauksesi, haluatko parantaa sitä kattamalla enemmän menetelmiä, kuten LU, Cholesky, ja iteratiiviset menetelmät, kuten gradient kunnollinen?
Olisit käynyt läpi postini, @hxd,, olisit nähnyt, että olen jo katsonut Choleskyn.LU: ta ei todellakaan käytetä pienimpien neliöiden ongelmien ratkaisemiseen, koska se ei hyödynnä ongelman rakennetta.En ole koskaan kuullut gradientin laskeutumista pienimmille neliöille;jos sinulla on tietoa tästä, kirjoita erillinen vastaus.
@hxd, * epälineaarisista * ongelmista, varmasti.Optimointimenetelmät ovat kallis tapa ratkaista * lineaarinen * ongelma.
#2
+34
George Dontas
2010-08-18 21:19:28 UTC
view on stackexchange narkive permalink

Mitä tulee otsikossa olevaan kysymykseen, mikä on käytetty algoritmi:

Lineaarisen algebran näkökulmasta lineaarinen regressioalgoritmi on tapa ratkaista lineaarinen järjestelmä $ \ mathbf {A} x = b $, jossa on enemmän yhtälöitä kuin tuntemattomia. Useimmissa tapauksissa ongelmaan ei ole ratkaisua. Ja tämä johtuu siitä, että vektori $ b $ ei kuulu $ \ mathbf {A} $, $ C (\ mathbf {A}) $ -saraketilaan.

paras suora on se, joka tekee kokonaisvirheen $ e = \ mathbf {A} x-b $ niin pieneksi kuin tarvitaan. Ja on kätevää ajatella niin pieneksi neliön pituudeksi, $ \ lVert e \ rVert ^ 2 $, koska se ei ole negatiivinen ja se on yhtä suuri kuin 0, kun $ b \ C: ssä (\ mathbf {A}) $.

Vektorin $ b $ projisointi (kohtisuoraan) lähimpään pisteeseen $ \ mathbf -saraketilassa {A} $ antaa vektorin $ b ^ * $, joka ratkaisee järjestelmän (sen komponentit ovat paras suora) mahdollisimman pienellä virheellä.

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

ja projisoidun vektorin $ b ^ * $ antaa:

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

Ehkä pienimmän neliösumman menetelmää ei käytetä yksinomaan , koska kyseinen neliö kompensoi ylimitoitetut.

Annan yksinkertaisen esimerkin R: stä, joka ratkaisee regressio-ongelman tällä algoritmilla:

  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"), otsikko = T) liitä (rekisteritiedot) <- malli.matriisi (b ~ x) # leikkaus ja kaltevuus (t (A)% *% A)% *% t (A)% *% b # sovitetut arvot - projisoitu vektori b C (A) A% *% inv (t (A)% *% A)% *% t (A)% *% b # Projisointi on helpompaa, jos käytetään kohtisuoraa matriisia Q, # koska t (Q)% *% Q = IQ <- qr.Q (qr (A)) R <- qr.R ( qr (A)) # sieppaus ja kaltevuus parhaiten. viiva <- inv (R)% *% t (Q)% *% b
# sovitetut arvot Q% *% t (Q)% *% bplot (x, b, pch = 16) viiva (paras.viiva [1], paras.viiva [2])  
Saan erehdyksen "ei löytynyt inv"
Lataa fBasics-paketti. http://finzi.psych.upenn.edu/R/library/fBasics/html/matrix-inv.html
Onko mitään syytä käyttää inv from fBasics -palvelua, kun se on vain synonyymi ratkaisulle? Eikö olisi parempi, jos vastaus ei vaadi riippuvuutta ulkoisista paketeista, jos se ei ole tarpeellista?
@George Rakastan selkeää vastausta. Luulen kuitenkin, että alkuperäinen kysymys esitti algoritmeja, ja QR on vain yksi niistä.Entä LU, SVD, kolesky hajoaminen?Lisäksi R: ssä menetelmä "lm" on QR, siihen on syitä, voisitko selittää miksi?
@GeorgeDontas Huomaa, että saattaa olla, että $ A ^ T A $ ei ole käänteinen.Kuten [tässä vastauksessa] (https://stats.stackexchange.com/a/363874/215801) on selitetty, yksi tapa käsitellä sitä on poistaa $ A $ -sarakkeista, jotka ovat muiden sarakkeiden lineaarisia yhdistelmiä.
#3
+6
user28
2010-08-18 19:01:06 UTC
view on stackexchange narkive permalink

Wiki-linkki: Estimation Methods for Linear Regression antaa melko kattavan luettelon arviointimenetelmistä, mukaan lukien OLS ja kontekstit, joissa vaihtoehtoisia arviointimenetelmiä käytetään.

Ei käsittele kysymystä (sivulla ei edes mainita QR: tä)
#4
+4
Dirk Eddelbuettel
2010-08-18 19:01:20 UTC
view on stackexchange narkive permalink

Määritelmien ja terminologian välillä on helppo sekoittua. Molempia termejä käytetään, toisinaan keskenään. Nopean haun Wikipediasta pitäisi auttaa:

Tavalliset pienimmät neliöt (OLS) on menetelmä lineaaristen regressiomallien sovittamiseksi. OLS-menetelmän osoitettavissa olevan johdonmukaisuuden ja tehokkuuden vuoksi (lisäoletusten perusteella) se on hallitseva lähestymistapa. Katso lisää viitteitä artikkeleista.

Aivan, siksi pidän OLS: ää "algoritmina", jota käytetään lineaarisessa regressiossa ...
Tavalliset pienimmät neliöt ovat arvio. Estimaatin laskemiseksi on olemassa useita algoritmeja: yleensä käytetään jonkinlaista ortogonaalista matriisihajotusta, kuten QR. Katso 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

Minulla on tapana ajatella 'pienimmät neliöt' kriteerinä määritettäessä parhaiten sopiva regressioviiva (ts. mikä tekee 'neliöisten' jäännösten summasta pienimmän ') ja' 'algoritmin' 'tässä yhteydessä joukoksi vaiheet, joita käytetään kyseisen kriteerin täyttävien regressiokertoimien määrittämiseen. Tämä ero viittaa siihen, että on mahdollista saada erilaisia ​​algoritmeja, jotka täyttävät saman kriteerin.

Olisin utelias tietämään, tekevätkö muut tämän eron ja mitä terminologiaa he käyttävät.

Algoritmilla tarkoitan karkeasti ohjelmiston toteutusta, jota käytetään linjan sovittamiseen jakelun keskiarvon mallintamiseen.
#6
+3
F. Tusell
2011-10-26 13:50:45 UTC
view on stackexchange narkive permalink

Vanha kirja, kuitenkin sellainen, johon käyn toistuvasti kääntämässä, on

Lawson, C.L. ja Hanson, R.J. Ratkaisu pienimmän neliösumman ongelmiin , Prentice-Hall, 1974.

Se sisältää yksityiskohtaisen ja hyvin luettavan keskustelun joistakin algoritmeista, jotka aiemmat vastaukset ovat maininneet. Haluat ehkä tarkastella sitä.

Jos luet tämän vanhan kirjan, sinun tulee myös tutkia Åke Björckin * [Numeerisia menetelmiä vähiten neliöongelmiin] (http://books.google.com/books/?id=ZecsDBMz5-IC) *, jossa ei ole juttuja käsitelty Lawson / Hansonissa. Lawson / Hanson-kirjassa olevat rutiinit ovat [saatavana Netlibistä] (http://netlib.org/lawson-hanson/).


Tämä Q & A käännettiin automaattisesti englanniksi.Alkuperäinen sisältö on saatavilla stackexchange-palvelussa, jota kiitämme cc by-sa 2.0-lisenssistä, jolla sitä jaetaan.
Loading...