Lineær regresjon og metoder for utvinning

Kilde: XKCD

Lineær regresjon er en av de grunnleggende algoritmene for mange områder knyttet til dataanalyse. Årsaken til dette er åpenbar. Dette er en veldig enkel og forståelig algoritme, som har bidratt til dens utbredte bruk i mange titalls, om ikke hundrevis, av år. Tanken er at vi antar en lineær avhengighet av en variabel på et sett med andre variabler, og deretter prøver å gjenopprette denne avhengigheten.

Men denne artikkelen handler ikke om å bruke lineær regresjon for å løse praktiske problemer. Her vil vi vurdere interessante funksjoner ved implementeringen av distribuerte algoritmer for gjenoppretting, som vi møtte da vi skrev en maskinlæringsmodul i Apache Ignite. Litt grunnleggende matematikk, maskinlæring og distribuert databehandling kan hjelpe deg med å finne ut hvordan du kan utføre lineær regresjon selv når dataene dine er fordelt på tusenvis av noder.

Hva snakker vi om?

Vi står overfor oppgaven med å gjenopprette lineær avhengighet. Som inngangsdata er det gitt et sett med vektorer med antatt uavhengige variabler, som hver er assosiert med en viss verdi av den avhengige variabelen. Disse dataene kan representeres i form av to matriser:

Nå, siden avhengigheten er antatt, og dessuten lineær, vil vi skrive antakelsen vår i form av et produkt av matriser (for å forenkle registreringen, her og under antas det at ligningens frie ledd er skjult bak , og den siste kolonnen i matrisen inneholder enheter):

Høres mye ut som et system med lineære ligninger, ikke sant? Det ser ut til, men mest sannsynlig vil det ikke finnes noen løsninger på et slikt ligningssystem. Årsaken til dette er støy, som er tilstede i nesten alle reelle data. En annen grunn kan være mangelen på lineær avhengighet som sådan, som kan bekjempes ved å introdusere tilleggsvariabler som ikke-lineært avhenger av de opprinnelige. Tenk på følgende eksempel:

Kilde: Wikipedia

Dette er et enkelt eksempel på lineær regresjon som viser forholdet til en variabel (langs aksen ) fra en annen variabel (langs aksen ). For at systemet med lineære ligninger som tilsvarer dette eksempelet skal ha en løsning, må alle punktene ligge nøyaktig på samme rette linje. Men det er ikke sant. Men de ligger ikke på samme rette linje nettopp på grunn av støy (eller fordi antagelsen om en lineær sammenheng var feil). For å gjenopprette et lineært forhold fra reelle data, er det derfor vanligvis nødvendig å introdusere en antagelse til: inngangsdataene inneholder støy og denne støyen har normal distribusjon. Man kan gjøre antakelser om andre typer støyfordeling, men i de aller fleste tilfeller er det normalfordelingen som vurderes, som vil bli diskutert videre.

Maksimal sannsynlighetsmetode

Så vi antok tilstedeværelsen av tilfeldig normalfordelt støy. Hva skal man gjøre i en slik situasjon? For dette tilfellet i matematikk er det og er mye brukt metode for maksimal sannsynlighet. Kort sagt, essensen ligger i valget sannsynlighetsfunksjoner og dens påfølgende maksimering.

Vi går tilbake til å gjenopprette et lineært forhold fra data med normal støy. Merk at den antatte lineære sammenhengen er den matematiske forventningen eksisterende normalfordeling. Samtidig er sannsynligheten for at antar en eller annen verdi, med forbehold om tilstedeværelsen av observerbare , følgende:

La oss nå erstatte i stedet и Variablene vi trenger er:

Alt som gjenstår er å finne vektoren , hvor denne sannsynligheten er maksimal. For å maksimere en slik funksjon, er det praktisk å først ta en logaritme av den (logaritmen til funksjonen vil nå et maksimum på samme punkt som selve funksjonen):

Som igjen kommer ned til å minimere følgende funksjon:

Dette kalles forresten en metode minste kvadrater. Ofte er alle de ovennevnte hensyn utelatt, og denne metoden brukes ganske enkelt.

QR-nedbrytning

Minimumet av funksjonen ovenfor kan bli funnet ved å finne punktet der gradienten til denne funksjonen er null. Og gradienten vil bli skrevet som følger:

QR-nedbrytning er en matrisemetode for å løse minimeringsproblemet som brukes i minste kvadraters metode. I denne forbindelse omskriver vi ligningen i matriseform:

Så vi dekomponerer matrisen til matriser и og utføre en serie transformasjoner (selve QR-dekomponeringsalgoritmen vil ikke bli vurdert her, bare bruken av den i forhold til oppgaven):

matrise er ortogonal. Dette gjør at vi kan kvitte oss med arbeidet :

Og hvis du bytter ut på , så ordner det seg . Vurderer er en øvre trekantet matrise, ser den slik ut:

Dette kan løses ved hjelp av substitusjonsmetoden. Element ligger som , forrige element ligger som og så videre.

Det er verdt å merke seg her at kompleksiteten til den resulterende algoritmen på grunn av bruken av QR-dekomponering er lik . Dessuten, til tross for at matrisemultiplikasjonsoperasjonen er godt parallellisert, er det ikke mulig å skrive en effektiv distribuert versjon av denne algoritmen.

Gradient Nedstigning

Når man snakker om å minimere en funksjon, er det alltid verdt å huske metoden for (stokastisk) gradientnedstigning. Dette er en enkel og effektiv minimeringsmetode basert på iterativt å beregne gradienten til en funksjon i et punkt og deretter flytte den i motsatt retning av gradienten. Hvert slikt trinn bringer løsningen nærmere minimum. Gradienten ser fortsatt den samme ut:

Denne metoden er også godt parallellisert og distribuert på grunn av de lineære egenskapene til gradientoperatøren. Legg merke til at i formelen ovenfor, under sumtegnet er det uavhengige termer. Med andre ord kan vi beregne gradienten uavhengig for alle indekser fra først til , parallelt med dette, beregne gradienten for indekser med til . Legg deretter til de resulterende gradientene. Resultatet av addisjonen vil være det samme som om vi umiddelbart beregnet gradienten for indekser fra første til . Således, hvis dataene er fordelt på flere datastykker, kan gradienten beregnes uavhengig på hver del, og deretter kan resultatene av disse beregningene summeres for å få det endelige resultatet:

Fra et implementeringssynspunkt passer dette paradigmet MapReduce. Ved hvert trinn i gradientnedstigningen sendes en oppgave til hver datanode for å beregne gradienten, deretter samles de beregnede gradientene sammen, og resultatet av summen deres brukes til å forbedre resultatet.

Til tross for den enkle implementeringen og muligheten til å utføre i MapReduce-paradigmet, har gradientnedstigning også sine ulemper. Spesielt er antallet trinn som kreves for å oppnå konvergens betydelig høyere sammenlignet med andre mer spesialiserte metoder.

LSQR

LSQR er en annen metode for å løse problemet, som er egnet både for å gjenopprette lineær regresjon og for å løse systemer med lineære ligninger. Hovedtrekket er at det kombinerer fordelene med matrisemetoder og en iterativ tilnærming. Implementeringer av denne metoden finnes i begge bibliotekene SciPy, og i MATLAB. En beskrivelse av denne metoden vil ikke bli gitt her (den kan finnes i artikkelen LSQR: En algoritme for sparsomme lineære ligninger og sparsomme minste kvadrater). I stedet vil det bli demonstrert en tilnærming for å tilpasse LSQR til utførelse i et distribuert miljø.

LSQR-metoden er basert på bidiagonaliseringsprosedyre. Dette er en iterativ prosedyre, hver iterasjon består av følgende trinn:


Men hvis vi antar at matrisen er horisontalt partisjonert, kan hver iterasjon representeres som to MapReduce-trinn. På denne måten er det mulig å minimere dataoverføringer under hver iterasjon (bare vektorer med lengde lik antall ukjente):

Det er denne tilnærmingen som brukes når man implementerer lineær regresjon i Apache Ignite ML.

Konklusjon

Det er mange lineære regresjonsgjenopprettingsalgoritmer, men ikke alle kan brukes under alle forhold. Så QR-dekomponering er utmerket for nøyaktig løsning på små datasett. Gradientnedstigning er enkel å implementere og lar deg raskt finne en omtrentlig løsning. Og LSQR kombinerer de beste egenskapene til de to foregående algoritmene, siden den kan distribueres, konvergerer raskere sammenlignet med gradientnedstigning, og tillater også tidlig stopp av algoritmen, i motsetning til QR-dekomponering, for å finne en omtrentlig løsning.

Kilde: www.habr.com