Allikas:
Lineaarne regressioon on üks põhialgoritme paljudes andmeanalüüsiga seotud valdkondades. Selle põhjus on ilmne. See on väga lihtne ja arusaadav algoritm, mis on aidanud kaasa selle laialdasele kasutamisele kümneid, kui mitte sadu aastaid. Idee seisneb selles, et eeldame ühe muutuja lineaarset sõltuvust teiste muutujate hulgast ja proovime seejärel seda sõltuvust taastada.
Kuid see artikkel ei käsitle lineaarse regressiooni kasutamist praktiliste probleemide lahendamiseks. Siin käsitleme selle taastamiseks hajutatud algoritmide rakendamise huvitavaid funktsioone, millega puutusime kokku masinõppemooduli kirjutamisel . Väike matemaatika, masinõpe ja hajutatud andmetöötlus aitavad teil mõista, kuidas teostada lineaarset regressiooni isegi siis, kui teie andmed on jaotatud tuhandete sõlmede vahel.
Millest me räägime?
Me seisame silmitsi ülesandega taastada lineaarne sõltuvus. Sisendandmetena on antud väidetavalt sõltumatute muutujate vektorite kogum, millest igaüks on seotud sõltuva muutuja teatud väärtusega. Neid andmeid saab esitada kahe maatriksi kujul:
Kuna sõltuvus on eeldatud ja pealegi lineaarne, siis kirjutame oma eelduse maatriksite korrutise kujul (salvestamise lihtsustamiseks eeldatakse siin ja all, et võrrandi vaba liige on peidetud taga ja maatriksi viimane veerg sisaldab ühikuid):
Kõlab nagu lineaarsete võrrandite süsteem, kas pole? Tundub, aga suure tõenäosusega sellisele võrrandisüsteemile lahendusi ei tule. Selle põhjuseks on müra, mis esineb peaaegu kõigis reaalsetes andmetes. Teine põhjus võib olla lineaarse sõltuvuse kui sellise puudumine, mille vastu saab võidelda lisamuutujate sisseviimisega, mis mittelineaarselt sõltuvad algsetest muutujatest. Kaaluge järgmist näidet:
Allikas:
See on lihtne näide lineaarsest regressioonist, mis näitab ühe muutuja suhet (piki telge ) teisest muutujast (piki telge ). Et sellele näitele vastaval lineaarvõrrandisüsteemil oleks lahendus, peavad kõik punktid asuma täpselt samal sirgel. Aga see pole tõsi. Kuid nad ei asu samal sirgel just müra tõttu (või seetõttu, et lineaarse seose eeldus oli ekslik). Seega, et taastada lineaarne seos reaalsetest andmetest, on tavaliselt vaja sisse viia veel üks eeldus: sisendandmed sisaldavad müra ja see müra on . Eeldusi saab teha ka teist tüüpi mürajaotuse kohta, kuid enamikul juhtudel võetakse arvesse normaaljaotust, millest tuleb edaspidi juttu.
Maksimaalse tõenäosuse meetod
Niisiis eeldasime juhusliku normaalselt jaotatud müra olemasolu. Mida teha sellises olukorras? Sel juhul matemaatikas on ja kasutatakse laialdaselt . Lühidalt, selle olemus seisneb valikus ja selle järgnev maksimeerimine.
Naaseme normaalse müraga andmetest lineaarse seose taastamise juurde. Pange tähele, et eeldatud lineaarne seos on matemaatiline ootus olemasolev normaaljaotus. Samas on tõenäosus, et omandab ühe või teise väärtuse, olenevalt vaadeldavate tegurite olemasolust , järgnevalt:
Asendame nüüd selle asemel и Muutujad, mida vajame, on:
Jääb üle vaid vektor leida , mille puhul see tõenäosus on maksimaalne. Sellise funktsiooni maksimeerimiseks on mugav kõigepealt võtta selle logaritm (funktsiooni logaritm saavutab maksimumi funktsiooni endaga samas punktis):
Mis omakorda taandub järgmise funktsiooni minimeerimisele:
Muide, seda nimetatakse meetodiks . Sageli jäetakse kõik ülaltoodud kaalutlused välja ja seda meetodit kasutatakse lihtsalt.
QR-de lagunemine
Ülaltoodud funktsiooni miinimumi saab leida, leides punkti, kus selle funktsiooni gradient on null. Ja gradient kirjutatakse järgmiselt:
on maatriksmeetod minimeerimisülesande lahendamiseks, mida kasutatakse vähimruutude meetodil. Sellega seoses kirjutame võrrandi ümber maatriksi kujul:
Seega lagundame maatriksi maatriksitele и ja tehke seeria teisendusi (siin ei võeta arvesse QR-i lagunemisalgoritmi ennast, vaid ainult selle kasutamist seoses käsiloleva ülesandega):
maatriks on ortogonaalne. See võimaldab meil tööst lahti saada :
Ja kui asendate edasi , siis läheb korda . Võttes arvesse, et on ülemine kolmnurkne maatriks, näeb see välja järgmine:
Seda saab lahendada asendusmeetodi abil. Element asub kui , eelmine element asub kui ja nii edasi.
Siinkohal väärib märkimist, et saadud algoritmi keerukus QR-dekompositsiooni kasutamisest on võrdne . Veelgi enam, hoolimata asjaolust, et maatriksi korrutamise operatsioon on hästi paralleelne, ei ole võimalik kirjutada selle algoritmi efektiivset hajutatud versiooni.
Gradiendi laskumine
Funktsiooni minimeerimisest rääkides tasub alati meeles pidada (stohhastilise) gradiendi laskumise meetodit. See on lihtne ja tõhus minimeerimismeetod, mis põhineb funktsiooni gradiendi iteratiivsel arvutamisel punktis ja seejärel selle nihutamisel gradiendile vastupidises suunas. Iga selline samm viib lahenduse miinimumile lähemale. Gradient näeb endiselt välja sama:
See meetod on ka gradiendi operaatori lineaarsete omaduste tõttu hästi paralleelne ja hajutatud. Pange tähele, et ülaltoodud valemis on summamärgi all sõltumatud terminid. Teisisõnu saame kõigi indeksite gradiendi arvutada iseseisvalt esimesest kuni , arvutage paralleelselt sellega indeksite gradient kuni . Seejärel lisage saadud gradiendid. Lisamise tulemus on sama, kui arvutaksime kohe indeksite gradiendi esimesest kuni . Seega, kui andmed on jaotatud mitme andmeüksuse vahel, saab gradiendi arvutada iga üksuse kohta iseseisvalt ja seejärel nende arvutuste tulemused summeerida, et saada lõpptulemus:
Rakendamise seisukohast sobib see paradigmaga . Gradiendi laskumise igal etapil saadetakse igale andmesõlmele ülesanne gradiendi arvutamiseks, seejärel kogutakse arvutatud gradiendid kokku ja nende summa tulemust kasutatakse tulemuse parandamiseks.
Vaatamata rakendamise lihtsusele ja MapReduce'i paradigma täitmise võimalusele on gradiendi laskumisel ka omad puudused. Eelkõige on konvergentsi saavutamiseks vajalike sammude arv oluliselt suurem võrreldes teiste spetsiifilisemate meetoditega.
LSQR
on teine ülesande lahendamise meetod, mis sobib nii lineaarse regressiooni taastamiseks kui ka lineaarvõrrandisüsteemide lahendamiseks. Selle peamine omadus on see, et see ühendab maatriksmeetodite ja iteratiivse lähenemisviisi eelised. Selle meetodi rakendusi võib leida mõlemast raamatukogust ja sisse . Selle meetodi kirjeldust siin ei esitata (selle leiate artiklist ). Selle asemel demonstreeritakse lähenemist LSQR-i kohandamiseks hajutatud keskkonnas täitmiseks.
LSQR meetod põhineb . See on iteratiivne protseduur, mille iga iteratsioon koosneb järgmistest sammudest:
Aga kui eeldame, et maatriks on horisontaalselt jaotatud, siis saab iga iteratsiooni esitada kahe MapReduce sammuna. Sel viisil on võimalik minimeerida andmeedastusi iga iteratsiooni ajal (ainult vektorid, mille pikkus on võrdne tundmatute arvuga):
Just seda lähenemisviisi kasutatakse lineaarse regressiooni rakendamisel .
Järeldus
Lineaarse regressiooni taastamise algoritme on palju, kuid kõiki neid ei saa kõigis tingimustes rakendada. Seega on QR-de dekomponeerimine suurepärane väikeste andmekogumite täpseks lahendamiseks. Gradiendi laskumist on lihtne rakendada ja see võimaldab teil kiiresti leida ligikaudse lahenduse. Ja LSQR ühendab kahe eelmise algoritmi parimad omadused, kuna seda saab hajutada, koondub kiiremini võrreldes gradiendi laskumisega ja võimaldab ka algoritmi varakult peatada, erinevalt QR-dekompositsioonist, et leida ligikaudne lahendus.
Allikas: www.habr.com