Sursa:
Regresia liniară este unul dintre algoritmii de bază pentru multe domenii legate de analiza datelor. Motivul pentru aceasta este evident. Acesta este un algoritm foarte simplu și ușor de înțeles, care a contribuit la utilizarea sa pe scară largă timp de multe zeci, dacă nu sute, de ani. Ideea este că presupunem o dependență liniară a unei variabile de un set de alte variabile și apoi încercăm să restabilim această dependență.
Dar acest articol nu este despre utilizarea regresiei liniare pentru a rezolva probleme practice. Aici vom lua în considerare caracteristici interesante ale implementării algoritmilor distribuiți pentru recuperarea acestuia, pe care le-am întâlnit când scriem un modul de învățare automată în . Un pic de matematică de bază, învățare automată și calcul distribuit vă pot ajuta să vă dați seama cum să efectuați regresia liniară chiar și atunci când datele sunt distribuite pe mii de noduri.
Despre ce vorbim?
Ne confruntăm cu sarcina de a restabili dependența liniară. Ca date de intrare, este dat un set de vectori de variabile presupuse independente, fiecare dintre acestea fiind asociat cu o anumită valoare a variabilei dependente. Aceste date pot fi reprezentate sub forma a două matrice:
Acum, deoarece dependența este presupusă și, în plus, liniară, vom scrie ipoteza noastră sub forma unui produs de matrice (pentru a simplifica înregistrarea, aici și mai jos se presupune că termenul liber al ecuației este ascuns în spatele , și ultima coloană a matricei conţine unităţi):
Sună mult ca un sistem de ecuații liniare, nu-i așa? Se pare, dar cel mai probabil nu vor exista soluții pentru un astfel de sistem de ecuații. Motivul pentru aceasta este zgomotul, care este prezent în aproape orice date reale. Un alt motiv poate fi lipsa dependenței liniare ca atare, care poate fi combătută prin introducerea unor variabile suplimentare care depind neliniar de cele originale. Luați în considerare următorul exemplu:
Sursa:
Acesta este un exemplu simplu de regresie liniară care arată relația unei variabile (de-a lungul axei ) dintr-o altă variabilă (de-a lungul axei ). Pentru ca sistemul de ecuații liniare corespunzător acestui exemplu să aibă o soluție, toate punctele trebuie să se afle exact pe aceeași dreaptă. Dar asta nu este adevărat. Dar ele nu se află pe aceeași linie dreaptă tocmai din cauza zgomotului (sau pentru că presupunerea unei relații liniare a fost eronată). Astfel, pentru a restabili o relație liniară din datele reale, este de obicei necesar să se introducă încă o ipoteză: datele de intrare conțin zgomot și acest zgomot are . Puteți face ipoteze despre alte tipuri de distribuție a zgomotului, dar în marea majoritate a cazurilor este considerată distribuția normală, care va fi discutată în continuare.
Metoda maximă de probabilitate
Deci, am presupus prezența zgomotului normal distribuit aleatoriu. Ce să faci într-o astfel de situație? Pentru acest caz în matematică există și este utilizat pe scară largă . Pe scurt, esența sa constă în alegere și maximizarea lui ulterioară.
Revenim la restabilirea unei relații liniare din date cu zgomot normal. Rețineți că relația liniară asumată este așteptarea matematică distribuția normală existentă. În același timp, probabilitatea ca capătă o valoare sau alta, sub rezerva prezenței observabilelor , după cum urmează:
Să înlocuim acum în schimb и Variabilele de care avem nevoie sunt:
Tot ce rămâne este să găsim vectorul , la care această probabilitate este maximă. Pentru a maximiza o astfel de funcție, este convenabil să luați mai întâi un logaritm al acesteia (logaritmul funcției va atinge un maxim în același punct cu funcția însăși):
Care, la rândul său, se reduce la minimizarea următoarei funcții:
Apropo, aceasta se numește o metodă . Adesea, toate considerațiile de mai sus sunt omise și această metodă este pur și simplu utilizată.
Descompunerea QR
Minimul funcției de mai sus poate fi găsit prin găsirea punctului în care gradientul acestei funcții este zero. Și gradientul va fi scris după cum urmează:
este o metodă matriceală pentru rezolvarea problemei de minimizare utilizată în metoda celor mai mici pătrate. În acest sens, rescriem ecuația sub formă de matrice:
Deci descompunem matricea la matrice и și efectuați o serie de transformări (algoritmul de descompunere QR în sine nu va fi luat în considerare aici, ci doar utilizarea lui în raport cu sarcina în cauză):
matrice este ortogonală. Acest lucru ne permite să scăpăm de muncă :
Și dacă înlocuiești pe , atunci se va rezolva . Având în vedere că este o matrice triunghiulară superioară, arată astfel:
Acest lucru poate fi rezolvat folosind metoda substituției. Element este situat ca , element anterior este situat ca și așa mai departe.
Este demn de remarcat aici că complexitatea algoritmului rezultat datorită utilizării descompunerii QR este egală cu . Mai mult, în ciuda faptului că operația de multiplicare a matricei este bine paralelizată, nu este posibil să se scrie o versiune distribuită eficientă a acestui algoritm.
Coborâre în gradient
Când vorbim despre minimizarea unei funcții, merită întotdeauna să ne amintim metoda de coborâre a gradientului (stochastic). Aceasta este o metodă simplă și eficientă de minimizare bazată pe calcularea iterativă a gradientului unei funcții într-un punct și apoi deplasarea acesteia în direcția opusă gradientului. Fiecare astfel de pas aduce soluția mai aproape de minim. Gradientul arată în continuare același:
Această metodă este, de asemenea, bine paralelizată și distribuită datorită proprietăților liniare ale operatorului de gradient. Rețineți că în formula de mai sus, sub semnul sumei există termeni independenți. Cu alte cuvinte, putem calcula gradientul independent pentru toți indicii de la primul la , în paralel cu aceasta, se calculează gradientul pentru indici cu la . Apoi adăugați gradienții rezultați. Rezultatul adunării va fi același ca și cum am calcula imediat gradientul pentru indici de la primul la . Astfel, dacă datele sunt distribuite între mai multe date, gradientul poate fi calculat independent pe fiecare bucată, iar apoi rezultatele acestor calcule pot fi însumate pentru a obține rezultatul final:
Din punct de vedere al implementării, aceasta se potrivește paradigmei . La fiecare pas de coborâre a gradientului, o sarcină este trimisă fiecărui nod de date pentru a calcula gradientul, apoi gradienții calculati sunt colectați împreună, iar rezultatul sumei lor este folosit pentru a îmbunătăți rezultatul.
În ciuda ușurinței de implementare și a capacității de a executa în paradigma MapReduce, coborârea gradientului are și dezavantajele sale. În special, numărul de pași necesari pentru a obține convergența este semnificativ mai mare în comparație cu alte metode mai specializate.
LSQR
este o altă metodă de rezolvare a problemei, care este potrivită atât pentru restabilirea regresiei liniare, cât și pentru rezolvarea sistemelor de ecuații liniare. Caracteristica sa principală este că combină avantajele metodelor matriceale și o abordare iterativă. Implementări ale acestei metode pot fi găsite în ambele biblioteci și în . O descriere a acestei metode nu va fi oferită aici (poate fi găsită în articol ). În schimb, va fi demonstrată o abordare pentru adaptarea LSQR la execuția într-un mediu distribuit.
Metoda LSQR se bazează pe . Aceasta este o procedură iterativă, fiecare iterație constând din următorii pași:
Dar dacă presupunem că matricea este partiționat orizontal, apoi fiecare iterație poate fi reprezentată ca doi pași MapReduce. În acest fel, este posibil să se minimizeze transferurile de date în timpul fiecărei iterații (doar vectori cu o lungime egală cu numărul de necunoscute):
Această abordare este utilizată la implementarea regresiei liniare în .
Concluzie
Există mulți algoritmi de recuperare a regresiei liniare, dar nu toți pot fi aplicați în toate condițiile. Deci, descompunerea QR este excelentă pentru soluții precise pe seturi mici de date. Coborârea în gradient este ușor de implementat și vă permite să găsiți rapid o soluție aproximativă. Și LSQR combină cele mai bune proprietăți ale celor doi algoritmi anteriori, deoarece poate fi distribuit, converge mai rapid în comparație cu coborârea gradientului și, de asemenea, permite oprirea timpurie a algoritmului, spre deosebire de descompunerea QR, pentru a găsi o soluție aproximativă.
Sursa: www.habr.com