Kilde:
Lineær regression er en af de grundlæggende algoritmer for mange områder relateret til dataanalyse. Årsagen til dette er indlysende. Dette er en meget enkel og forståelig algoritme, som har bidraget til dens udbredte brug i mange ti, hvis ikke hundreder, af år. Ideen er, at vi antager en lineær afhængighed af en variabel af et sæt af andre variable, og derefter forsøger at genoprette denne afhængighed.
Men denne artikel handler ikke om at bruge lineær regression til at løse praktiske problemer. Her vil vi overveje interessante funktioner i implementeringen af distribuerede algoritmer til dets gendannelse, som vi stødte på, da vi skrev et maskinlæringsmodul i . Lidt grundlæggende matematik, maskinlæring og distribueret computing kan hjælpe dig med at finde ud af, hvordan du udfører lineær regression, selv når dine data er fordelt på tværs af tusindvis af noder.
Hvad taler vi om?
Vi står over for opgaven med at genoprette lineær afhængighed. Som inputdata gives et sæt vektorer af formodet uafhængige variable, som hver især er forbundet med en bestemt værdi af den afhængige variabel. Disse data kan repræsenteres i form af to matricer:
Nu, da afhængigheden er antaget, og desuden lineær, vil vi skrive vores antagelse i form af et produkt af matricer (for at forenkle registreringen, her og nedenfor antages det, at ligningens frie led er skjult bagved , og den sidste kolonne i matrixen indeholder enheder):
Det lyder meget som et system af lineære ligninger, ikke? Det ser ud til, men højst sandsynligt vil der ikke være nogen løsninger på sådan et ligningssystem. Årsagen til dette er støj, som er til stede i næsten alle rigtige data. En anden grund kan være manglen på lineær afhængighed som sådan, som kan bekæmpes ved at indføre yderligere variabler, der ikke-lineært afhænger af de oprindelige. Overvej følgende eksempel:
Kilde:
Dette er et simpelt eksempel på lineær regression, der viser sammenhængen mellem en variabel (langs aksen ) fra en anden variabel (langs aksen ). For at det lineære ligningssystem, der svarer til dette eksempel, skal have en løsning, skal alle punkter ligge nøjagtigt på den samme rette linje. Men det er ikke sandt. Men de ligger ikke på den samme lige linje netop på grund af støj (eller fordi antagelsen om en lineær sammenhæng var fejlagtig). For at genoprette et lineært forhold fra reelle data er det således normalt nødvendigt at introducere endnu en antagelse: inputdataene indeholder støj, og denne støj har . Man kan lave antagelser om andre former for støjfordeling, men i langt de fleste tilfælde er det normalfordelingen, der tages i betragtning, som vil blive diskuteret nærmere.
Maksimal sandsynlighed metode
Så vi antog tilstedeværelsen af tilfældig normalfordelt støj. Hvad skal man gøre i sådan en situation? For dette tilfælde i matematik er der og er meget brugt . Kort sagt, dens essens ligger i valget og dens efterfølgende maksimering.
Vi vender tilbage til at genoprette et lineært forhold fra data med normal støj. Bemærk, at den antagne lineære sammenhæng er den matematiske forventning eksisterende normalfordeling. Samtidig er sandsynligheden for, at antager en eller anden værdi, afhængigt af tilstedeværelsen af observerbare , som følger:
Lad os nu erstatte i stedet и De variabler vi har brug for er:
Tilbage er blot at finde vektoren , hvor denne sandsynlighed er maksimal. For at maksimere en sådan funktion er det praktisk først at tage en logaritme af den (funktionens logaritme når et maksimum på samme punkt som selve funktionen):
Hvilket igen kommer ned til at minimere følgende funktion:
Det kaldes i øvrigt en metode . Ofte er alle ovenstående overvejelser udeladt, og denne metode bruges simpelthen.
QR-nedbrydning
Minimumet af ovenstående funktion kan findes ved at finde det punkt, hvor denne funktions gradient er nul. Og gradienten vil blive skrevet som følger:
er en matrixmetode til løsning af minimeringsproblemet, der bruges i mindste kvadraters metode. I denne henseende omskriver vi ligningen i matrixform:
Så vi nedbryder matrixen til matricer и og udfør en række transformationer (selve QR-dekomponeringsalgoritmen vil ikke blive overvejet her, kun dens brug i forhold til den aktuelle opgave):
matrix er ortogonal. Dette giver os mulighed for at slippe af med arbejdet :
Og hvis du erstatter på , så går det nok . Overvejer det er en øvre trekantet matrix, ser den sådan ud:
Dette kan løses ved hjælp af substitutionsmetoden. Element er placeret som , forrige element er placeret som og så videre.
Det er værd at bemærke her, at kompleksiteten af den resulterende algoritme på grund af brugen af QR-nedbrydning er lig med . På trods af det faktum, at matrixmultiplikationsoperationen er godt paralleliseret, er det desuden ikke muligt at skrive en effektiv distribueret version af denne algoritme.
Gradient nedstigning
Når man taler om at minimere en funktion, er det altid værd at huske metoden til (stokastisk) gradientnedstigning. Dette er en enkel og effektiv minimeringsmetode baseret på iterativt at beregne gradienten af en funktion i et punkt og derefter flytte den i retning modsat gradienten. Hvert sådant trin bringer løsningen tættere på minimum. Gradienten ser stadig den samme ud:
Denne metode er også godt paralleliseret og fordelt på grund af gradientoperatorens lineære egenskaber. Bemærk, at i ovenstående formel er der uafhængige udtryk under sumtegnet. Med andre ord kan vi beregne gradienten uafhængigt for alle indekser fra først til , parallelt med dette, beregne gradienten for indekser med til . Tilføj derefter de resulterende gradienter. Resultatet af tilføjelsen vil være det samme, som hvis vi straks beregnede gradienten for indeks fra første til . Således, hvis dataene er fordelt på flere datastykker, kan gradienten beregnes uafhængigt af hver enkelt brik, og derefter kan resultaterne af disse beregninger summeres for at opnå det endelige resultat:
Fra et implementeringssynspunkt passer dette til paradigmet . Ved hvert trin af gradientnedstigning sendes en opgave til hver dataknude for at beregne gradienten, derefter samles de beregnede gradienter sammen, og resultatet af deres sum bruges til at forbedre resultatet.
På trods af den lette implementering og evnen til at udføre i MapReduce-paradigmet, har gradientnedstigning også sine ulemper. Især antallet af trin, der kræves for at opnå konvergens, er væsentligt højere sammenlignet med andre mere specialiserede metoder.
LSQR
er en anden metode til at løse problemet, som er velegnet både til at genoprette lineær regression og til at løse lineære ligningssystemer. Dens hovedtræk er, at den kombinerer fordelene ved matrixmetoder og en iterativ tilgang. Implementeringer af denne metode kan findes i begge biblioteker , og i . En beskrivelse af denne metode vil ikke blive givet her (den kan findes i artiklen ). I stedet vil der blive demonstreret en tilgang til at tilpasse LSQR til udførelse i et distribueret miljø.
LSQR-metoden er baseret på . Dette er en iterativ procedure, hvor hver iteration består af følgende trin:
Men hvis vi antager, at matrixen er vandret opdelt, så kan hver iteration repræsenteres som to MapReduce-trin. På denne måde er det muligt at minimere dataoverførsler under hver iteration (kun vektorer med en længde svarende til antallet af ukendte):
Det er denne tilgang, der bruges, når man implementerer lineær regression i .
Konklusion
Der er mange lineære regressionsgendannelsesalgoritmer, men ikke alle kan anvendes under alle forhold. Så QR-nedbrydning er fremragende til præcis løsning på små datasæt. Gradient nedstigning er enkel at implementere og giver dig mulighed for hurtigt at finde en omtrentlig løsning. Og LSQR kombinerer de bedste egenskaber fra de to foregående algoritmer, da den kan distribueres, konvergerer hurtigere sammenlignet med gradientnedstigning og tillader også tidlig stop af algoritmen, i modsætning til QR-nedbrydning, for at finde en omtrentlig løsning.
Kilde: www.habr.com