Šaltinis:
Tiesinė regresija yra vienas iš pagrindinių algoritmų daugelyje sričių, susijusių su duomenų analize. To priežastis akivaizdi. Tai labai paprastas ir suprantamas algoritmas, dėl kurio jis plačiai naudojamas daugelį dešimčių, jei ne šimtų metų. Idėja yra ta, kad darome prielaidą, kad vieno kintamojo tiesinė priklausomybė nuo kitų kintamųjų rinkinio, ir tada bandome atkurti šią priklausomybę.
Tačiau šiame straipsnyje kalbama ne apie tiesinės regresijos naudojimą sprendžiant praktines problemas. Čia apžvelgsime įdomias paskirstytų algoritmų diegimo ypatybes jo atkūrimui, su kuriomis susidūrėme rašydami mašininio mokymosi modulį . Šiek tiek pagrindinės matematikos, mašininio mokymosi ir paskirstytojo skaičiavimo gali padėti išsiaiškinti, kaip atlikti tiesinę regresiją net tada, kai jūsų duomenys yra paskirstyti tūkstančiams mazgų.
apie ką mes kalbame?
Mes susiduriame su užduotimi atkurti tiesinę priklausomybę. Kaip įvesties duomenys, pateikiamas tariamai nepriklausomų kintamųjų vektorių rinkinys, kurių kiekvienas yra susietas su tam tikra priklausomo kintamojo reikšme. Šie duomenys gali būti pateikiami dviejų matricų pavidalu:
Dabar, kadangi priklausomybė daroma prielaida, be to, tiesinė, savo prielaidą parašysime matricų sandauga (kad būtų supaprastintas įrašymas, čia ir žemiau daroma prielaida, kad lygties laisvasis narys yra paslėptas už , ir paskutinis matricos stulpelis yra vienetų):
Skamba kaip tiesinių lygčių sistema, ar ne? Atrodo, bet greičiausiai tokios lygčių sistemos sprendimų nebus. To priežastis yra triukšmas, kuris yra beveik visuose tikruose duomenyse. Kita priežastis gali būti tiesinės priklausomybės trūkumas, su kuriuo galima kovoti įvedant papildomus kintamuosius, kurie netiesiškai priklauso nuo pradinių. Apsvarstykite šį pavyzdį:
Šaltinis:
Tai paprastas tiesinės regresijos pavyzdys, rodantis vieno kintamojo ryšį (išilgai ašies ) iš kito kintamojo (išilgai ašies ). Kad šį pavyzdį atitinkanti tiesinių lygčių sistema turėtų sprendimą, visi taškai turi būti tiksliai toje pačioje tiesėje. Bet tai netiesa. Bet jie guli ant tos pačios tiesės būtent dėl triukšmo (arba dėl to, kad tiesinio ryšio prielaida buvo klaidinga). Taigi, norint atkurti tiesinį ryšį su realiais duomenimis, paprastai reikia įvesti dar vieną prielaidą: įvesties duomenyse yra triukšmo ir šis triukšmas turi . Galite daryti prielaidas apie kitus triukšmo pasiskirstymo tipus, tačiau daugeliu atvejų atsižvelgiama į normalųjį pasiskirstymą, kuris bus aptartas toliau.
Didžiausios tikimybės metodas
Taigi, mes manėme, kad yra atsitiktinis normaliai paskirstytas triukšmas. Ką daryti tokioje situacijoje? Šiuo atveju matematikoje yra ir yra plačiai naudojamas . Trumpai tariant, jo esmė slypi pasirinkime ir vėlesnis jo padidinimas.
Grįžtame prie tiesinio ryšio atkūrimo iš duomenų su normaliu triukšmu. Atkreipkite dėmesį, kad tariamas tiesinis ryšys yra matematinis lūkestis esamas normalusis skirstinys. Tuo pačiu tikimybė, kad įgyja vienokią ar kitokią vertę, priklausomai nuo stebimų dalykų , taip:
Vietoj to dabar pakeisime и Mums reikalingi kintamieji:
Belieka tik surasti vektorių , kai ši tikimybė yra didžiausia. Norint maksimaliai padidinti tokią funkciją, patogu pirmiausia paimti jos logaritmą (funkcijos logaritmas pasieks maksimumą tame pačiame taške kaip ir pati funkcija):
O tai savo ruožtu reiškia šios funkcijos sumažinimą:
Beje, tai vadinama metodu . Dažnai visi pirmiau minėti svarstymai praleidžiami ir tiesiog naudojamas šis metodas.
QR skaidymas
Aukščiau pateiktos funkcijos minimumą galima rasti suradus tašką, kuriame šios funkcijos gradientas lygus nuliui. Ir gradientas bus parašytas taip:
yra matricinis metodas, skirtas minimalizavimo uždaviniui išspręsti, naudojamas mažiausių kvadratų metodu. Šiuo atžvilgiu lygtį perrašome matricos forma:
Taigi mes išskaidome matricą į matricas и ir atlikti transformacijų seriją (čia nebus svarstomas pats QR išskaidymo algoritmas, tik jo naudojimas, susijęs su atliekama užduotimi):
matrica yra ortogonalus. Tai leidžia mums atsikratyti darbo :
O jei pakeisite apie , tada viskas pavyks . Atsižvelgiant į tai yra viršutinė trikampė matrica, ji atrodo taip:
Tai galima išspręsti naudojant pakeitimo metodą. Elementas yra kaip , ankstesnis elementas yra kaip ir taip toliau.
Čia verta paminėti, kad gauto algoritmo sudėtingumas dėl QR dekompozicijos yra lygus . Be to, nepaisant to, kad matricos daugybos operacija yra gerai lygiagreti, neįmanoma parašyti efektyvios paskirstytos šio algoritmo versijos.
Gradiento nusileidimas
Kalbant apie funkcijos sumažinimą, visada verta prisiminti (stochastinio) gradiento nusileidimo metodą. Tai paprastas ir efektyvus sumažinimo metodas, pagrįstas funkcijos gradiento iteraciniu apskaičiavimu taške ir po to perkėlimu jį gradientui priešinga kryptimi. Kiekvienas toks žingsnis priartina sprendimą prie minimumo. Gradientas atrodo taip pat:
Šis metodas taip pat yra gerai lygiagretus ir paskirstytas dėl gradiento operatoriaus tiesinių savybių. Atkreipkite dėmesį, kad aukščiau pateiktoje formulėje po sumos ženklu yra nepriklausomi terminai. Kitaip tariant, visų indeksų gradientą galime apskaičiuoti nepriklausomai nuo pirmos iki , lygiagrečiai su tuo apskaičiuokite indeksų gradientą su į . Tada pridėkite gautus gradientus. Sudėjimo rezultatas bus toks pat, lyg tuoj pat apskaičiuotume indeksų gradientą nuo pirmojo iki . Taigi, jei duomenys yra paskirstyti tarp kelių duomenų vienetų, gradientas gali būti apskaičiuojamas atskirai kiekvienoje dalyje, o tada šių skaičiavimų rezultatus galima susumuoti, kad būtų gautas galutinis rezultatas:
Įgyvendinimo požiūriu tai atitinka paradigmą . Kiekviename gradiento nusileidimo žingsnyje į kiekvieną duomenų mazgą siunčiama užduotis gradientui apskaičiuoti, tada apskaičiuoti gradientai surenkami kartu, o jų sumos rezultatas naudojamas rezultatui pagerinti.
Nepaisant lengvo įgyvendinimo ir galimybės vykdyti MapReduce paradigmą, gradiento nusileidimas taip pat turi trūkumų. Visų pirma, veiksmų, kurių reikia konvergencijai pasiekti, skaičius yra žymiai didesnis, palyginti su kitais labiau specializuotais metodais.
LSQR
yra dar vienas uždavinio sprendimo būdas, tinkantis tiek tiesinei regresijai atkurti, tiek tiesinių lygčių sistemoms spręsti. Pagrindinis jo bruožas yra tas, kad jis sujungia matricinių metodų ir iteracinio metodo privalumus. Šio metodo įgyvendinimus galima rasti abiejose bibliotekose ir in . Šio metodo aprašymas čia nebus pateiktas (jį rasite straipsnyje ). Vietoj to bus parodytas būdas pritaikyti LSQR vykdymui paskirstytoje aplinkoje.
LSQR metodas pagrįstas . Tai kartotinė procedūra, kiekvieną iteraciją sudaro šie žingsniai:
Bet jei manytume, kad matrica yra horizontaliai padalintas, tada kiekviena iteracija gali būti pavaizduota kaip du MapReduce žingsniai. Tokiu būdu galima sumažinti duomenų perdavimą kiekvienos iteracijos metu (tik vektoriai, kurių ilgis lygus nežinomųjų skaičiui):
Būtent šis metodas naudojamas įgyvendinant tiesinę regresiją .
išvada
Yra daug tiesinės regresijos atkūrimo algoritmų, tačiau ne visus juos galima pritaikyti visomis sąlygomis. Taigi QR išskaidymas puikiai tinka tiksliam mažų duomenų rinkinių sprendimui. Gradiento nusileidimas yra lengvai įgyvendinamas ir leidžia greitai rasti apytikslį sprendimą. Ir LSQR sujungia geriausias ankstesnių dviejų algoritmų savybes, nes jis gali būti paskirstytas, greičiau konverguoja, palyginti su gradiento nusileidimu, taip pat leidžia anksti sustabdyti algoritmą, skirtingai nei QR skaidymas, kad būtų galima rasti apytikslį sprendimą.
Šaltinis: www.habr.com