Lähde:
Lineaarinen regressio on yksi perusalgoritmeista monilla data-analyysiin liittyvillä aloilla. Syy tähän on ilmeinen. Tämä on hyvin yksinkertainen ja ymmärrettävä algoritmi, joka on edistänyt sen laajaa käyttöä useiden kymmenien, ellei satojen vuosien ajan. Ajatuksena on, että oletamme yhden muuttujan lineaarisen riippuvuuden muiden muuttujien joukosta ja yritämme sitten palauttaa tämän riippuvuuden.
Mutta tässä artikkelissa ei ole kyse lineaarisen regression käyttämisestä käytännön ongelmien ratkaisemiseen. Tässä tarkastelemme mielenkiintoisia ominaisuuksia hajautettujen algoritmien toteutuksessa sen palauttamiseksi, joita kohtasimme kirjoittaessamme koneoppimismoduulia . Pieni perusmatematiikka, koneoppiminen ja hajautettu laskenta voivat auttaa sinua selvittämään, kuinka suoritat lineaarisen regression, vaikka tietosi olisi jaettu tuhansien solmujen kesken.
Mistä me puhumme?
Edessämme on lineaarisen riippuvuuden palauttaminen. Syöttötietona annetaan joukko oletusarvoisesti riippumattomia muuttujia, joista kukin liittyy tiettyyn riippuvaisen muuttujan arvoon. Nämä tiedot voidaan esittää kahden matriisin muodossa:
Nyt, koska riippuvuus on oletettu ja lisäksi lineaarinen, kirjoitamme oletuksemme matriisien tulon muodossa (tallennuksen yksinkertaistamiseksi tässä ja alla oletetaan, että yhtälön vapaa termi on piilossa , ja matriisin viimeinen sarake sisältää yksiköitä):
Kuulostaa paljon lineaaristen yhtälöiden järjestelmältä, eikö niin? Näyttää siltä, mutta todennäköisesti tällaiselle yhtälöjärjestelmälle ei ole ratkaisuja. Syynä tähän on melu, jota esiintyy lähes kaikissa todellisissa tiedoissa. Toinen syy voi olla lineaarisen riippuvuuden puute sinänsä, jota voidaan torjua ottamalla käyttöön lisämuuttujia, jotka riippuvat epälineaarisesti alkuperäisistä. Harkitse seuraavaa esimerkkiä:
Lähde:
Tämä on yksinkertainen esimerkki lineaarisesta regressiosta, joka näyttää yhden muuttujan suhteen (akselia pitkin ) toisesta muuttujasta (akselia pitkin ). Jotta tätä esimerkkiä vastaavalla lineaariyhtälöjärjestelmällä olisi ratkaisu, kaikkien pisteiden on oltava täsmälleen samalla suoralla. Mutta se ei ole totta. Mutta ne eivät makaa samalla suoralla juuri kohinan takia (tai siksi, että olettamus lineaarisesta suhteesta oli virheellinen). Siten lineaarisen suhteen palauttamiseksi todellisesta tiedosta on yleensä tarpeen esittää vielä yksi oletus: syöttödata sisältää kohinaa ja tämä kohina on . Voit tehdä oletuksia muun tyyppisistä kohinan jakautumisesta, mutta suurimmassa osassa tapauksista huomioidaan normaalijakauma, jota käsitellään tarkemmin.
Suurimman todennäköisyyden menetelmä
Joten oletimme satunnaisen normaalijakauman kohinan olemassaolon. Mitä tehdä tällaisessa tilanteessa? Tätä varten matematiikassa on ja käytetään laajasti . Lyhyesti sanottuna sen ydin on valinnassa ja sen myöhempi maksimointi.
Palaamme lineaarisen suhteen palauttamiseen normaalikohinaisista tiedoista. Huomaa, että oletettu lineaarinen suhde on matemaattinen odotus olemassa oleva normaalijakauma. Samalla todennäköisyys, että saa yhden tai toisen arvon, jos havaittavissa on olemassa , näyttää seuraavalta:
Korvaakaamme nyt sen sijaan и Tarvitsemme muuttujia:
Jäljelle jää vain löytää vektori , jolla tämä todennäköisyys on suurin. Tällaisen funktion maksimoimiseksi on kätevää ensin ottaa siitä logaritmi (funktion logaritmi saavuttaa maksimin samassa kohdassa kuin itse funktio):
Mikä puolestaan päätyy seuraavan toiminnon minimoimiseen:
Muuten, tätä kutsutaan menetelmäksi . Usein kaikki edellä mainitut huomiot jätetään pois ja tätä menetelmää käytetään yksinkertaisesti.
QR-hajotus
Yllä olevan funktion minimi voidaan löytää etsimällä piste, jossa tämän funktion gradientti on nolla. Ja gradientti kirjoitetaan seuraavasti:
on matriisimenetelmä pienimmän neliösumman menetelmässä käytetyn minimointitehtävän ratkaisemiseksi. Tässä suhteessa kirjoitamme yhtälön uudelleen matriisimuotoon:
Joten hajotamme matriisin matriiseihin и ja suorita joukko muunnoksia (itse QR-hajotusalgoritmia ei käsitellä tässä, vain sen käyttöä käsillä olevaan tehtävään liittyen):
matriisi on ortogonaalinen. Tämä antaa meille mahdollisuuden päästä eroon työstä :
Ja jos vaihdat päälle , sitten se selviää . Ottaen huomioon on ylempi kolmiomatriisi, se näyttää tältä:
Tämä voidaan ratkaista korvausmenetelmällä. Elementti sijaitsee nimellä , edellinen elementti sijaitsee nimellä ja niin edelleen.
Tässä on syytä huomata, että tuloksena olevan algoritmin monimutkaisuus QR-hajoamisen käytöstä on yhtä suuri kuin . Lisäksi huolimatta siitä tosiasiasta, että matriisin kertolaskuoperaatio on hyvin rinnakkain, ei ole mahdollista kirjoittaa tehokasta hajautettua versiota tästä algoritmista.
Gradientti laskeutuminen
Kun puhutaan funktion minimoinnista, kannattaa aina muistaa (stokastisen) gradientin laskeutumisen menetelmä. Tämä on yksinkertainen ja tehokas minimointimenetelmä, joka perustuu funktion gradientin iteratiiviseen laskemiseen pisteessä ja sen siirtämiseen gradientin vastakkaiseen suuntaan. Jokainen tällainen vaihe tuo ratkaisun lähemmäs minimiä. Gradientti näyttää edelleen samalta:
Tämä menetelmä on myös hyvin rinnakkainen ja hajautunut gradienttioperaattorin lineaaristen ominaisuuksien vuoksi. Huomaa, että yllä olevassa kaavassa summamerkin alla on itsenäisiä termejä. Toisin sanoen voimme laskea gradientin itsenäisesti kaikille indekseille ensimmäisestä asti , laske rinnakkain tämän kanssa gradientti indekseille до . Lisää sitten saadut gradientit. Lisäyksen tulos on sama kuin jos laskisimme heti gradientin indekseille ensimmäisestä . Näin ollen, jos data on jaettu usealle datalle, gradientti voidaan laskea itsenäisesti jokaisesta osasta, ja sitten näiden laskelmien tulokset voidaan laskea yhteen lopullisen tuloksen saamiseksi:
Toteutuksen näkökulmasta tämä sopii paradigmaan . Gradientin laskun jokaisessa vaiheessa kullekin datasolmulle lähetetään tehtävä gradientin laskemiseksi, sitten lasketut gradientit kerätään yhteen ja niiden summan tulosta käytetään tuloksen parantamiseen.
Huolimatta toteutuksen helppoudesta ja suorituskyvystä MapReduce-paradigmassa, gradienttilaskeutumisella on myös haittapuolensa. Erityisesti konvergenssin saavuttamiseen tarvittavien vaiheiden määrä on huomattavasti suurempi verrattuna muihin erikoistuneempiin menetelmiin.
LSQR
on toinen menetelmä ongelman ratkaisemiseksi, joka sopii sekä lineaarisen regression palauttamiseen että lineaaristen yhtälöjärjestelmien ratkaisemiseen. Sen pääominaisuus on, että se yhdistää matriisimenetelmien edut ja iteratiivisen lähestymistavan. Tämän menetelmän toteutukset löytyvät molemmista kirjastoista , ja in . Tämän menetelmän kuvausta ei anneta tässä (se löytyy artikkelista ). Sen sijaan esitellään lähestymistapaa, jolla LSQR mukautetaan suoritukseen hajautetussa ympäristössä.
LSQR-menetelmä perustuu . Tämä on iteratiivinen menettely, jossa jokainen iteraatio koostuu seuraavista vaiheista:
Mutta jos oletetaan, että matriisi on vaakasuoraan osioitu, jokainen iteraatio voidaan esittää kahdeksi MapReduce-vaiheeksi. Tällä tavalla on mahdollista minimoida tiedonsiirrot jokaisen iteroinnin aikana (vain vektorit, joiden pituus on yhtä suuri kuin tuntemattomien lukumäärä):
Juuri tätä lähestymistapaa käytetään toteutettaessa lineaarista regressiota .
Johtopäätös
Lineaarisen regression palautusalgoritmeja on monia, mutta kaikkia niistä ei voida soveltaa kaikissa olosuhteissa. Joten QR-hajotus on erinomainen tarkkaan ratkaisuun pienille tietojoukoille. Gradienttilasku on helppo toteuttaa ja sen avulla voit nopeasti löytää likimääräisen ratkaisun. Ja LSQR yhdistää kahden edellisen algoritmin parhaat ominaisuudet, koska se voidaan hajauttaa, konvergoi nopeammin verrattuna gradienttilaskeutumiseen ja mahdollistaa myös algoritmin varhaisen pysäyttämisen, toisin kuin QR-hajotus, likimääräisen ratkaisun löytämiseksi.
Lähde: will.com