Vir:
Linearna regresija je eden od osnovnih algoritmov za številna področja, povezana z analizo podatkov. Razlog za to je očiten. To je zelo preprost in razumljiv algoritem, ki je prispeval k njegovi široki uporabi že več deset, če ne sto let. Ideja je, da predpostavimo linearno odvisnost ene spremenljivke od niza drugih spremenljivk in nato poskušamo obnoviti to odvisnost.
Vendar ta članek ne govori o uporabi linearne regresije za reševanje praktičnih problemov. Tukaj bomo preučili zanimive značilnosti implementacije porazdeljenih algoritmov za njegovo obnovitev, na katere smo naleteli pri pisanju modula strojnega učenja v . Malo osnovne matematike, strojnega učenja in porazdeljenega računalništva vam lahko pomaga ugotoviti, kako izvajati linearno regresijo, tudi če so vaši podatki porazdeljeni na tisoče vozlišč.
Za kaj se gre?
Soočeni smo z nalogo ponovne vzpostavitve linearne odvisnosti. Kot vhodni podatek je podan niz vektorjev domnevno neodvisnih spremenljivk, od katerih je vsaka povezana z določeno vrednostjo odvisne spremenljivke. Te podatke je mogoče predstaviti v obliki dveh matrik:
Zdaj, ker je odvisnost predpostavljena in poleg tega linearna, bomo našo predpostavko zapisali v obliki zmnožka matrik (za poenostavitev zapisa tukaj in spodaj predpostavljamo, da se prosti člen enačbe skriva za , in zadnji stolpec matrike vsebuje enote):
Sliši se zelo podobno sistemu linearnih enačb, kajne? Zdi se, a najverjetneje ne bo rešitev za tak sistem enačb. Razlog za to je šum, ki je prisoten v skoraj vseh realnih podatkih. Drugi razlog je lahko pomanjkanje linearne odvisnosti kot take, proti čemur se je mogoče boriti z uvedbo dodatnih spremenljivk, ki so nelinearno odvisne od prvotnih. Razmislite o naslednjem primeru:
Vir:
To je preprost primer linearne regresije, ki prikazuje odnos ene spremenljivke (vzdolž osi ) iz druge spremenljivke (vzdolž osi ). Da bi imel sistem linearnih enačb, ki ustreza temu primeru, rešitev, morajo vse točke ležati točno na isti ravni črti. Ampak to ni res. Ne ležijo pa na isti premici prav zaradi šuma (ali ker je bila predpostavka o linearnem razmerju zmotna). Da bi obnovili linearno razmerje iz realnih podatkov, je običajno treba uvesti še eno predpostavko: vhodni podatki vsebujejo šum in ta šum ima . Lahko domnevate o drugih vrstah porazdelitve hrupa, vendar je v veliki večini primerov upoštevana normalna porazdelitev, o kateri bomo še razpravljali.
Metoda največje verjetnosti
Torej smo predpostavili prisotnost naključnega normalno porazdeljenega šuma. Kaj storiti v takšni situaciji? Za ta primer v matematiki obstaja in se pogosto uporablja . Skratka, njeno bistvo je v izbiri in njegovo kasnejšo maksimizacijo.
Vrnemo se k obnavljanju linearne povezave iz podatkov z običajnim šumom. Upoštevajte, da je predpostavljeno linearno razmerje matematično pričakovanje obstoječa normalna porazdelitev. Ob tem je verjetnost, da prevzame eno ali drugo vrednost, odvisno od prisotnosti opazovanih , izgleda na naslednji način:
Namesto tega zamenjajmo и Spremenljivke, ki jih potrebujemo, so:
Vse, kar ostane, je najti vektor , pri kateri je ta verjetnost največja. Za maksimiranje takšne funkcije je primerno, da jo najprej logaritemujemo (logaritem funkcije bo dosegel maksimum na isti točki kot funkcija sama):
Kar pa se zmanjša na minimum naslednje funkcije:
Mimogrede, temu se reče metoda . Pogosto so vsi zgornji vidiki izpuščeni in se preprosto uporabi ta metoda.
QR razgradnja
Najmanjšo vrednost zgornje funkcije je mogoče najti tako, da poiščete točko, v kateri je gradient te funkcije enak nič. In gradient bo zapisan na naslednji način:
je matrična metoda za reševanje problema minimizacije, ki se uporablja v metodi najmanjših kvadratov. V zvezi s tem enačbo prepišemo v matrično obliko:
Torej razgradimo matrico na matrice и in izvedite niz transformacij (samega algoritma za razgradnjo QR tu ne bomo obravnavali, temveč samo njegovo uporabo v zvezi z nalogo, ki jo obravnavamo):
matrica je pravokoten. To nam omogoča, da se znebimo dela :
In če zamenjate o , potem bo šlo . Glede na to je zgornja trikotna matrika, izgleda takole:
To je mogoče rešiti z metodo zamenjave. Element se nahaja kot , prejšnji element se nahaja kot in tako naprej.
Pri tem velja omeniti, da je kompleksnost dobljenega algoritma zaradi uporabe QR dekompozicije enaka . Še več, kljub dejstvu, da je operacija množenja matrik dobro vzporedna, ni mogoče napisati učinkovite porazdeljene različice tega algoritma.
Gradientni spust
Ko govorimo o minimiziranju funkcije, si velja vedno zapomniti metodo (stohastičnega) gradientnega spusta. To je preprosta in učinkovita metoda minimizacije, ki temelji na iterativnem izračunu gradienta funkcije v točki in njenem nato premikanju v smeri, ki je nasprotna gradientu. Vsak tak korak približa rešitev minimumu. Gradient je še vedno enak:
Ta metoda je prav tako dobro vzporedna in porazdeljena zaradi linearnih lastnosti operatorja gradienta. Upoštevajte, da so v zgornji formuli pod znakom za vsoto neodvisni členi. Z drugimi besedami, gradient lahko izračunamo neodvisno za vse indekse od prvega do , vzporedno s tem izračunajte gradient za indekse z za . Nato dodajte nastale prelive. Rezultat seštevanja bo enak, kot če bi takoj izračunali gradient za indekse od prvega do . Torej, če so podatki porazdeljeni med več kosov podatkov, je mogoče gradient izračunati neodvisno za vsak del, nato pa je mogoče rezultate teh izračunov sešteti, da dobimo končni rezultat:
Z izvedbenega vidika to ustreza paradigmi . Pri vsakem koraku spuščanja gradienta se vsakemu podatkovnemu vozlišču pošlje naloga za izračun gradienta, nato se izračunani gradienti zberejo skupaj, rezultat njihove vsote pa se uporabi za izboljšanje rezultata.
Kljub enostavnosti implementacije in zmožnosti izvajanja v paradigmi MapReduce ima gradientni spust tudi svoje pomanjkljivosti. Zlasti število korakov, potrebnih za dosego konvergence, je znatno večje v primerjavi z drugimi bolj specializiranimi metodami.
LSQR
je še ena metoda za reševanje problema, ki je primerna tako za obnavljanje linearne regresije kot za reševanje sistemov linearnih enačb. Njegova glavna značilnost je, da združuje prednosti matričnih metod in iterativnega pristopa. Izvedbe te metode lahko najdete v obeh knjižnicah , in v . Opis te metode tukaj ne bo podan (najdete ga v članku ). Namesto tega bo predstavljen pristop za prilagoditev LSQR izvajanju v porazdeljenem okolju.
Metoda LSQR temelji na . To je iterativni postopek, pri čemer je vsaka ponovitev sestavljena iz naslednjih korakov:
Če pa predpostavimo, da je matrika je vodoravno razdeljen, potem lahko vsako ponovitev predstavimo kot dva koraka MapReduce. Na ta način je mogoče minimizirati prenose podatkov med vsako iteracijo (samo vektorji z dolžino, ki je enaka številu neznank):
Ta pristop se uporablja pri izvajanju linearne regresije v .
Zaključek
Obstaja veliko algoritmov za obnovitev linearne regresije, vendar vseh ni mogoče uporabiti v vseh pogojih. Tako je razčlenitev QR odlična za natančne rešitve na majhnih nizih podatkov. Gradientni spust je preprost za izvedbo in omogoča hitro iskanje približne rešitve. In LSQR združuje najboljše lastnosti prejšnjih dveh algoritmov, saj je lahko porazdeljen, konvergira hitreje v primerjavi s spuščanjem po gradientu in omogoča tudi zgodnjo zaustavitev algoritma, za razliko od QR dekompozicije, za iskanje približne rešitve.
Vir: www.habr.com