Burimi:
Regresioni linear është një nga algoritmet bazë për shumë fusha që lidhen me analizën e të dhënave. Arsyeja për këtë është e qartë. Ky është një algoritëm shumë i thjeshtë dhe i kuptueshëm, i cili ka kontribuar në përdorimin e tij të gjerë për shumë dhjetëra, nëse jo qindra vjet. Ideja është që ne të supozojmë një varësi lineare të një ndryshoreje nga një grup variablash të tjerë, dhe më pas të përpiqemi ta rivendosim këtë varësi.
Por ky artikull nuk ka të bëjë me përdorimin e regresionit linear për të zgjidhur problemet praktike. Këtu do të shqyrtojmë veçoritë interesante të zbatimit të algoritmeve të shpërndara për rikuperimin e tij, të cilat i kemi hasur gjatë shkrimit të një moduli të mësimit të makinës në . Pak matematikë bazë, mësimin e makinerive dhe llogaritjen e shpërndarë mund t'ju ndihmojnë të kuptoni se si të kryeni regresion linear edhe kur të dhënat tuaja shpërndahen në mijëra nyje.
Për çfarë po flasim?
Jemi përballë detyrës për të rivendosur varësinë lineare. Si të dhëna hyrëse, jepet një grup vektorësh të variablave të supozuar të pavarur, secila prej të cilave shoqërohet me një vlerë të caktuar të ndryshores së varur. Këto të dhëna mund të përfaqësohen në formën e dy matricave:
Tani, meqenëse varësia supozohet, dhe për më tepër, lineare, ne do ta shkruajmë supozimin tonë në formën e një produkti të matricave (për të thjeshtuar regjistrimin, këtu dhe më poshtë supozohet se termi i lirë i ekuacionit fshihet pas 
, dhe kolona e fundit e matricës 
përmban njësi):
Tingëllon shumë si një sistem ekuacionesh lineare, apo jo? Duket, por me shumë mundësi nuk do të ketë zgjidhje për një sistem të tillë ekuacionesh. Arsyeja për këtë është zhurma, e cila është e pranishme në pothuajse çdo të dhënë reale. Një arsye tjetër mund të jetë mungesa e varësisë lineare si e tillë, e cila mund të luftohet duke futur variabla shtesë që varen në mënyrë jolineare nga ato origjinale. Merrni parasysh shembullin e mëposhtëm:
Burimi:
Ky është një shembull i thjeshtë i regresionit linear që tregon marrëdhënien e një ndryshoreje (përgjatë boshtit 
) nga një variabël tjetër (përgjatë boshtit 
). Në mënyrë që sistemi i ekuacioneve lineare që korrespondojnë me këtë shembull të ketë një zgjidhje, të gjitha pikat duhet të shtrihen saktësisht në të njëjtën drejtëz. Por kjo nuk është e vërtetë. Por ata nuk shtrihen në të njëjtën vijë të drejtë pikërisht për shkak të zhurmës (ose sepse supozimi i një marrëdhënieje lineare ishte i gabuar). Kështu, për të rivendosur një marrëdhënie lineare nga të dhënat reale, zakonisht është e nevojshme të futet një supozim tjetër: të dhënat hyrëse përmbajnë zhurmë dhe kjo zhurmë ka . Ju mund të bëni supozime për llojet e tjera të shpërndarjes së zhurmës, por në shumicën dërrmuese të rasteve është shpërndarja normale ajo që merret në konsideratë, e cila do të diskutohet më tej.
Metoda e gjasave maksimale
Pra, ne supozuam praninĂ« e zhurmĂ«s sĂ« rastĂ«sishme tĂ« shpĂ«rndarĂ« normalisht. ĂfarĂ« duhet bĂ«rĂ« nĂ« njĂ« situatĂ« tĂ« tillĂ«? PĂ«r kĂ«tĂ« rast nĂ« matematikĂ« ka dhe pĂ«rdoret gjerĂ«sisht . Me pak fjalĂ«, thelbi i saj qĂ«ndron nĂ« zgjedhjen dhe maksimizimi i tij pasues.
Ne kthehemi në rivendosjen e një marrëdhënie lineare nga të dhënat me zhurmë normale. Vini re se marrëdhënia e supozuar lineare është pritshmëria matematikore 
shpërndarje normale ekzistuese. Në të njëjtën kohë, probabiliteti që 
merr një vlerë ose një tjetër, duke iu nënshtruar pranisë së vëzhguesve 
, si në vazhdim:
Le ta zëvendësojmë tani 
О 
Variablat që na duhen janë:
Mbetet vetëm për të gjetur vektorin 
, në të cilën ky probabilitet është maksimal. Për të maksimizuar një funksion të tillë, është e përshtatshme që fillimisht të merret një logaritëm i tij (logaritmi i funksionit do të arrijë një maksimum në të njëjtën pikë me vetë funksionin):
E cila, nga ana tjetër, zbret në minimizimin e funksionit të mëposhtëm:
Nga rruga, kjo quhet një metodë . Shpesh të gjitha konsideratat e mësipërme anashkalohen dhe kjo metodë përdoret thjesht.
Zbërthimi i QR
Minimumi i funksionit të mësipërm mund të gjendet duke gjetur pikën në të cilën gradienti i këtij funksioni është zero. Dhe gradienti do të shkruhet si më poshtë:
është një metodë matrice për zgjidhjen e problemit të minimizimit e përdorur në metodën e katrorëve më të vegjël. Në lidhje me këtë, ne e rishkruajmë ekuacionin në formën e matricës:
Pra, ne zbërthejmë matricën 
te matricat 
О 
dhe kryeni një seri transformimesh (vetë algoritmi i dekompozimit QR nuk do të merret parasysh këtu, vetëm përdorimi i tij në lidhje me detyrën në fjalë):
matricë 
është ortogonal. Kjo na lejon të heqim qafe punën 
:
Dhe nëse zëvendësoni 
mbi 
, atëherë do të funksionojë 
. Duke pasur parasysh atë 
është një matricë trekëndore e sipërme, duket kështu:
Kjo mund të zgjidhet duke përdorur metodën e zëvendësimit. Elementi 
ndodhet si 
, elementi i mëparshëm 
ndodhet si 
dhe kështu me radhë.
Vlen të përmendet këtu se kompleksiteti i algoritmit që rezulton për shkak të përdorimit të dekompozimit QR është i barabartë me 
. Për më tepër, pavarësisht nga fakti se operacioni i shumëzimit të matricës është i paralelizuar mirë, nuk është e mundur të shkruhet një version efektiv i shpërndarë i këtij algoritmi.
Zbritja me gradient
Kur flasim pĂ«r minimizimin e njĂ« funksioni, gjithmonĂ« ia vlen tĂ« kujtojmĂ« metodĂ«n e zbritjes (stokastike) tĂ« gradientit. Kjo Ă«shtĂ« njĂ« metodĂ« e thjeshtĂ« dhe efektive minimizimi e bazuar nĂ« llogaritjen e pĂ«rsĂ«ritur tĂ« gradientit tĂ« njĂ« funksioni nĂ« njĂ« pikĂ« dhe mĂ« pas zhvendosjen e tij nĂ« drejtim tĂ« kundĂ«rt me gradientin. Ădo hap i tillĂ« e afron zgjidhjen mĂ« afĂ«r minimumit. Gradienti duket ende i njĂ«jtĂ«:
Kjo metodë është gjithashtu e paralelizuar dhe e shpërndarë mirë për shkak të vetive lineare të operatorit të gradientit. Vini re se në formulën e mësipërme, nën shenjën e shumës ka terma të pavarur. Me fjalë të tjera, ne mund të llogarisim gradientin në mënyrë të pavarur për të gjithë indekset 
nga e para në 
, paralelisht me këtë, llogaritni gradientin për indekset me 
tek 
. Pastaj shtoni gradientët që rezultojnë. Rezultati i shtimit do të jetë i njëjtë sikur të llogarisnim menjëherë gradientin për indekset nga i pari në 
. Kështu, nëse të dhënat shpërndahen midis disa pjesëve të të dhënave, gradienti mund të llogaritet në mënyrë të pavarur në secilën pjesë, dhe më pas rezultatet e këtyre llogaritjeve mund të përmblidhen për të marrë rezultatin përfundimtar:
Nga pikëpamja e zbatimit, kjo i përshtatet paradigmës . Në çdo hap të zbritjes së gradientit, një detyrë i dërgohet çdo nyje të dhënash për të llogaritur gradientin, më pas gradientët e llogaritur mblidhen së bashku dhe rezultati i shumës së tyre përdoret për të përmirësuar rezultatin.
Pavarësisht nga lehtësia e zbatimit dhe aftësia për të ekzekutuar në paradigmën MapReduce, zbritja e gradientit ka gjithashtu të metat e saj. Në veçanti, numri i hapave të nevojshëm për të arritur konvergjencën është dukshëm më i lartë në krahasim me metodat e tjera më të specializuara.
LSQR
është një metodë tjetër për zgjidhjen e problemit, e cila është e përshtatshme si për rivendosjen e regresionit linear ashtu edhe për zgjidhjen e sistemeve të ekuacioneve lineare. Karakteristika e tij kryesore është se kombinon avantazhet e metodave të matricës dhe një qasje përsëritëse. Zbatimet e kësaj metode mund të gjenden në të dy bibliotekat , dhe në . Një përshkrim i kësaj metode nuk do të jepet këtu (mund të gjendet në artikull ). Në vend të kësaj, do të demonstrohet një qasje për të përshtatur LSQR me ekzekutimin në një mjedis të shpërndarë.
Metoda LSQR bazohet në . Kjo është një procedurë përsëritëse, çdo përsëritje përbëhet nga hapat e mëposhtëm:
Por nëse supozojmë se matrica 
është e ndarë horizontalisht, atëherë çdo përsëritje mund të përfaqësohet si dy hapa MapReduce. Në këtë mënyrë, është e mundur të minimizohen transferimet e të dhënave gjatë çdo përsëritjeje (vetëm vektorët me gjatësi të barabartë me numrin e të panjohurave):
ĂshtĂ« kjo qasje qĂ« pĂ«rdoret kur zbatohet regresioni linear nĂ« .
PĂ«rfundim
Ka shumë algoritme të rikuperimit të regresionit linear, por jo të gjithë mund të zbatohen në të gjitha kushtet. Pra, zbërthimi i QR është i shkëlqyeshëm për zgjidhje të sakta në grupe të vogla të dhënash. Zbritja e gradientit është e thjeshtë për t'u zbatuar dhe ju lejon të gjeni shpejt një zgjidhje të përafërt. Dhe LSQR kombinon vetitë më të mira të dy algoritmeve të mëparshme, pasi mund të shpërndahet, konvergjon më shpejt në krahasim me zbritjen e gradientit, dhe gjithashtu lejon ndalimin e hershëm të algoritmit, ndryshe nga dekompozimi QR, për të gjetur një zgjidhje të përafërt.
Burimi: www.habr.com
