Regresioni linear dhe metodat për rikuperimin e tij

Burimi: xkcd

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ë Apache Ignite. 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: wikipedia

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 shpërndarje normale. 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 metoda e gjasave maksimale. Me pak fjalë, thelbi i saj qëndron në zgjedhjen funksionet e gjasave 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ë katrorët më të vegjël. 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ë:

Zbërthimi i QR ë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 Ulja e Hartë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

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 Shkencëtar, dhe në MATLAB. Një përshkrim i kësaj metode nuk do të jepet këtu (mund të gjendet në artikull LSQR: Një algoritëm për ekuacionet lineare të rralla dhe katrorët më të vegjël të rrallë). 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ë procedura e bidiagonalizimit. 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ë Apache Ignite ML.

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