Allikas:
Lineaarne regressioon on üks põhilisi algoritme paljude valdkondade jaoks, mis on seotud andmete analüüsiga. Selle põhjused on ilmsed. See on väga lihtne ja arusaadav algoritm, mis on juba mitmeid kümneid, kui mitte sadu aastaid laialdaselt rakendatud. Idee seisneb selles, et eeldame, et ühe muutuja sõltuvus tuleneb tõelisest komplektist teistest muutujatest, ja proovime seejärel seda sõltuvust taastada.
Kuid käesolevas artiklis ei käsitleta lineaarse regressiooni rakendamist praktiliste probleemide lahendamiseks. Siin käsitletakse huvitavaid omadusi jaotatud algoritmide rakendamisel, millega me kokku puutusime masinõppe mooduli kirjutamisel . Natuke põhiteadmisi matemaatikast, masinõppe alustest ja jaotatud arvutustest aitab aru saada, kuidas taastada lineaarset regressiooni, isegi kui andmed on jaotatud tuhandete sõlmedeni.
Mille üle jutt käib?
Meie ülesanne on taastada lineaarne seos. Sisendandmetena antakse hulk vektoreid, mis on eeldatavasti sõltumatud muutujad, millele vastab mingi sõltuva muutuja väärtus. Need andmed on esitatavad kahes maatriksis:
Kuna eeldame seost, ja veelgi enam, et see on lineaarne, kirjutame meie oletuse maatriksite korrutise kujul (kergenduseks eeldatakse, et tasuta liikme väärtus peidetakse 
, ja maatriksi viimane veerg 
kannab numbreid):
Kas see ei näe välja nagu lineaarsete võrrandite süsteem? Tõepoolest, kuid sellisel süsteemil ei pruugi lahendusi olla. Selle põhjuseks on müra, mis on praktikas peaaegu igas reaalses andmekogus. Samuti võib olla põhjuseks lineaarse sõltuvuse puudumine, millega võib proovida võidelda, lisades täiendavaid muutujaid, mis sõltuvad algsetest mittelineaarselt. Vaatame järgmist näidet:
Allikas:
See on lihtne lineaarse regressiooni näide, mis demonstreerib ühe muutuja sõltuvust (teljel 
) teise muutuja kaudu (teljel 
). Et süsteem lineaarsetest võrranditest antud näite kohaselt lahenduse saavutamiseks, peavad kõik punktid olema täpselt ühel sirgel. Kuid see ei ole nii. Nad ei asu ühel sirgel just mürabäire tõttu (või seetõttu, et eeldus lineaarse seose olemasolu kohta osutus valeks). Seetõttu, et taastada lineaarne seos reaalses andmestikus, on tavaliselt vajalik lisada veel üks eeldus: sisendid sisaldavad müra ja see müra järgib . Krüpteerimiseks on võimalik teha oletusi ka muude müra jaotustüüpide kohta, kuid enamikes juhtudest käsitletakse just normaaljaotust, millest edaspidi juttu tuleb.
Maksimaalne tõenäosusmeetod
Oleme seega teinud oletusi juhuslikult normaaljaotunud mürast. Kuidas käituda sellises olukorras? Selliste olukordade jaoks on matemaatikas olemas ja laialdaselt kasutatakse . Üldiselt seisneb selle olemus valimises ja selle maksimeerimises.
Jätkame lineaarse seose taastamist normaalsete müraandmete põhjal. Täheldame, et eelnevalt oletatud lineaarne seos on matemaatiline ootus 
olemasolevast normaaljaotusest. Samal ajal on tõenäosus, et 
võtab mingi väärtuse, sõltuvalt olemasolevatest 
, näeb välja järgmiselt:
Asendame nüüd 
ja 
meie vajalike muutujatega:
Järjest on vaid leida vektor 
, mille korral see tõenäosus on maksimaalne. Sellise funktsiooni maksimeerimiseks on mugav see esmalt logaritmeerida (funktsiooni logaritm saavutab maksimumi samas punktis, kus ka funktsioon ise):
See, omakorda, viib järgmise funktsiooni minimaliseerimiseni:
Muide, seda nimetatakse . Tihti jäetakse kõik ülaltoodud arutlused vahele ja kasutatavaks jääb lihtsalt see meetod.
QR dekompositsioon
Antud funktsiooni miinimumi võib leida, kui leitakse punkt, kus selle funktsiooni gradient on null. Gradient kirjutatakse järgmiselt:
on matriitsmeetodi kasutamine minimaalse lahendamise ülesande lahendamisel, mis on seotud väikseimate ruutude meetodiga. Seetõttu kirjutame võrdsuse ümber matriitskujul:
Nii et jagame matriitsi 
matriitsiteks 
ja 
ja teeme hulga muundamisi (QR jaotuse algoritmi ei käsitleta siin, ainult selle rakendust antud ülesande jaoks):
Matriits 
on ortogonaalne. See võimaldab meil vabaneda korrutisest 
:
Ja kui asendada 
järgnevaga 
, siis saadakse 
. Arvesse võttes, et 
on ülemine kolmnurkne matriits, näeb see välja järgmiselt:
Seda saab lahendada asendamise meetodil. Element 
leidub kui 
, eelmine element 
leidub kui 
ja nii edasi.
Siinkohal tasub märkida, et saadud algoritmi keerukus QR jaotuse kasutamise tõttu on võrreldav 
. Samas, kuigi matriitside korrutamine on hästi paralleelne, ei ole võimalik kirjutada efektiivset jaotatud versiooni sellest algoritmist.
Gradientne allakäik
Räägides mõne funktsiooni minimiseerimisest, tuleks alati meeles pidada (stohhastilise) gradientide langemise meetodit. See on lihtne ja tõhus minimiseerimismeetod, mis põhineb funktsiooni gradientide iteratiivsel arvutamisel punktis ja sellele järgneval nihkel vastassuunas gradientile. Iga selline samm viib lahenduse lähemale miinimumile. Gradient näeb välja endiselt selline:
Lisaks on see meetod hästi paralleelne ja jaotatav gradientide operaatori lineaarsuse tõttu. Tuleb märkida, et ülaltoodud valemis summa all on sõltumatud kordajad. Teisisõnu, me saame gradienti kõikide indeksite jaoks sõltumatult arvutada 
esimesest 
, samal ajal arvutada gradienti indeksite jaoks 
kuni 
. Seejärel saame saadud gradientid kokku liita. Liitmise tulemuseks on sama, nagu kui me oleksime arvutanud kohe gradienti indeksite jaoks esimesest 
. Seega, kui andmed on jaotatud mitme andmeosa vahel, saab gradienti arvutada sõltumatult igas osas ning seejärel saab nende arvutuste tulemused kokku liita lõpliku tulemuse saamiseks:
Rakenduslikult sobib see paradigma . Iga samm gradientide langemise protsessis saadetakse iga andmesõlmele ülesanne gradientide arvutamiseks, seejärel kogutakse arvutatud gradientid kokku, ja nende summeerimise tulemust kasutatakse tulemuse parendamiseks.
Hoolimata lihtsast rakendamisest ja võimalusest täita MapReduce paradigmas, omab gradientide langemisel siiski oma puudusi. Eelkõige on nende sammude arv, mis on vajalik konvergentsi saavutamiseks, oluliselt suurem võrreldes teiste spetsialiseeritumate meetoditega.
LSQR
on veel üks meetod antud ülesande lahendamiseks, mis sobib nii lineaarse regressiooni taastamiseks kui ka lineaarsete võrrandisüsteemide lahendamiseks. Selle peamine omadus on see, et see ühendab endas hübriidi maatriksitehnikatest ja iteratiivsetest lähenemistest. Selle meetodi rakendusi võib leida nii raamatukog ποσ “ , kui ka . Selle meetodi kirjeldust ei tooda siinkohal (seda võib leida artiklist ). Selle asemel demonstreeritakse lähenemist, mis võimaldab LSQR-i kohandamist jagatud keskkonnas täitmiseks.
LSQR meetodi tuum on . See on iteratiivne protseduur, kus iga iteratsioon koosneb järgmistest sammudest:
Kuid kui eeldada, et maatriks 
on horisontaalselt jaotatud, siis saab iga iteratsiooni esitada kahes MapReduce sammus. Nii õnnestub minimeerida andmete edastamist iga iteratsiooni käigus (ainult vektorid, mille pikkus vastab tundmatute arvule):
Just seda lähenemist kasutatakse lineaarse regressiooni rakendamisel .
Kokkuvõte
Eksisteerib palju lineaarse regressiooni taastamise algoritme, kuid mitte kõik neist ei sobi erinevates tingimustes kasutamiseks. Näiteks QR-dekompositsioon on suurepärane täpsete lahenduste saamiseks väikestes andmehulkades. Gradientne allakäik on lihtsalt rakendatav ja võimaldab kiiresti leida lähendatud lahendusi. LSQR aga kombineerib endas kahe eelneva algoritmi parimaid omadusi, kuna seda saab hajutada, see konvergib kiiresti võrreldes gradientse allakäiguga ning võimaldab varajast algoritmi lõpetamist, erinevalt QR-dekompositsioonist, et leida lähendatud lahendust.
Allikas: habr.com
