Línuleg aðhvarf og aðferðir við endurheimt hennar

Heimild: XKCD

Línuleg aðhvarf er eitt af grunnalgrímunum á mörgum sviðum sem tengjast gagnagreiningu. Ástæðan fyrir þessu er augljós. Þetta er mjög einfalt og skiljanlegt reiknirit, sem hefur stuðlað að víðtækri notkun þess í marga tugi, ef ekki hundruð, ára. Hugmyndin er sú að við gerum ráð fyrir línulegri háð einni breytu á mengi annarra breyta og reynum síðan að endurheimta þessa ósjálfstæði.

En þessi grein snýst ekki um að nota línulega aðhvarf til að leysa hagnýt vandamál. Hér munum við íhuga áhugaverða eiginleika útfærslu dreifðra reiknirita fyrir endurheimt þess, sem við fundum þegar við skrifuðum vélanámseiningu í Apache Ignite. Smá grunn stærðfræði, vélanám og dreifð tölvumál geta hjálpað þér að finna út hvernig á að framkvæma línulega aðhvarf jafnvel þegar gögnunum þínum er dreift yfir þúsundir hnúta.

Hvað erum við að tala um?

Við stöndum frammi fyrir því verkefni að endurheimta línulega ósjálfstæði. Sem inntaksgögn er sett af vigrum af meintum óháðum breytum, sem hver um sig er tengdur við ákveðið gildi háðu breytunnar. Þessi gögn geta verið táknuð í formi tveggja fylkja:

Nú, þar sem gert er ráð fyrir háðinni, og þar að auki línulegri, munum við skrifa forsendur okkar í formi margfeldis fylkja (til að einfalda upptökuna, hér og neðan er gert ráð fyrir að frjálsa lið jöfnunnar sé falið á bak við , og síðasta dálkinn í fylkinu inniheldur einingar):

Hljómar mjög eins og línuleg jöfnukerfi, er það ekki? Það virðist, en líklegast verða engar lausnir á slíku jöfnukerfi. Ástæðan fyrir þessu er hávaði, sem er til staðar í næstum öllum raunverulegum gögnum. Önnur ástæða getur verið skortur á línulegri ósjálfstæði sem slíkri, sem hægt er að berjast gegn með því að setja inn viðbótarbreytur sem eru ólínulega háðar þeim upprunalegu. Lítum á eftirfarandi dæmi:

Heimild: Wikipedia

Þetta er einfalt dæmi um línulega aðhvarf sem sýnir tengsl einnar breytu (meðfram ásnum ) frá annarri breytu (meðfram ásnum ). Til þess að línujafnakerfið sem samsvarar þessu dæmi hafi lausn verða allir punktar að liggja nákvæmlega á sömu beinu línunni. En það er ekki satt. En þeir liggja ekki á sömu beinu línunni einmitt vegna hávaða (eða vegna þess að forsendan um línulegt samband var röng). Þannig að til að endurheimta línulegt samband frá raunverulegum gögnum er venjulega nauðsynlegt að setja eina forsendu í viðbót: inntaksgögnin innihalda hávaða og þessi hávaði hefur eðlileg dreifing. Hægt er að gefa sér forsendur um annars konar hávaðadreifingu en í langflestum tilfellum er það eðlileg dreifing sem kemur til greina sem nánar verður fjallað um.

Hámarkslíkur aðferð

Þannig að við gerðum ráð fyrir að tilviljunarkenndur, venjulega dreifður hávaði væri til staðar. Hvað á að gera í slíkum aðstæðum? Fyrir þetta tilvik í stærðfræði er og er mikið notað hámarkslíkindaaðferð. Í stuttu máli liggur kjarni þess í valinu líkindaaðgerðir og hámörkun þess í kjölfarið.

Við snúum aftur að því að endurheimta línulegt samband frá gögnum með eðlilegum hávaða. Athugið að áætluð línuleg tengsl eru stærðfræðileg vænting núverandi eðlileg dreifing. Á sama tíma eru líkurnar á því að tekur á sig eitt eða annað gildi, með fyrirvara um að sjáanlegir hlutir séu til staðar , eins og hér segir:

Við skulum nú skipta út í staðinn и Breyturnar sem við þurfum eru:

Það eina sem er eftir er að finna vektorinn , þar sem þessar líkur eru hámarkar. Til að hámarka slíkt fall er þægilegt að taka fyrst lógaritma af því (lógaritmi fallsins nær hámarki á sama stað og fallið sjálft):

Sem aftur kemur niður á að lágmarka eftirfarandi aðgerð:

Við the vegur, þetta er kallað aðferð minnstu ferninga. Oft er öllum ofangreindum sjónarmiðum sleppt og þessi aðferð einfaldlega notuð.

QR niðurbrot

Lágmarkið af ofangreindu falli er hægt að finna með því að finna punktinn þar sem halli þessa falls er núll. Og hallinn verður skrifaður sem hér segir:

QR niðurbrot er fylkisaðferð til að leysa lágmarksvandamálið sem notað er í minnstu ferningaaðferðinni. Í þessu sambandi endurskrifum við jöfnuna á fylkisformi:

Þannig að við sundurliðum fylkinu til fylkja и og framkvæma röð af umbreytingum (QR niðurbrotsreikniritið sjálft verður ekki skoðað hér, aðeins notkun þess í tengslum við verkefnið sem fyrir hendi er):

Matrix er hornrétt. Þetta gerir okkur kleift að losa okkur við verkið :

Og ef þú skiptir um á , þá gengur það upp . Miðað við það er þríhyrningslaga fylki, lítur það svona út:

Þetta er hægt að leysa með skiptaaðferðinni. Frumefni er staðsett sem , fyrri þáttur er staðsett sem og svo framvegis.

Hér er rétt að taka fram að flókið reiknirit sem myndast vegna notkunar á QR niðurbroti er jafnt og . Ennfremur, þrátt fyrir þá staðreynd að fylkismargföldunaraðgerðin sé vel samhliða, er ekki hægt að skrifa skilvirka dreifða útgáfu af þessu reikniriti.

Gradient Descent

Þegar talað er um að lágmarka fall er alltaf þess virði að muna aðferðina við (stochastic) hallafall. Þetta er einföld og áhrifarík lágmörkunaraðferð sem byggir á því að reikna ítrekað halla falls í punkti og færa hann síðan í áttina gegn hallanum. Hvert slíkt skref færir lausnina nær lágmarkinu. Hallinn lítur enn eins út:

Þessi aðferð er einnig vel samsíða og dreifð vegna línulegra eiginleika hallans. Athugaðu að í formúlunni hér að ofan, undir summumerkinu, eru sjálfstæð hugtök. Með öðrum orðum, við getum reiknað hallann sjálfstætt fyrir allar vísitölur frá fyrstu til , samhliða þessu, reiknaðu hallann fyrir vísitölur með í . Bættu síðan við halla sem myndast. Niðurstaða samlagningarinnar verður sú sama og ef við reiknuðum strax hallann fyrir vísitölur frá fyrsta til . Þannig að ef gögnunum er dreift á nokkra gagnahluta er hægt að reikna hallann sjálfstætt á hvern hluta og síðan er hægt að leggja saman niðurstöður þessara útreikninga til að fá endanlega niðurstöðu:

Frá útfærslusjónarmiði passar þetta við hugmyndafræðina MapReduce. Í hverju skrefi hallans er verkefni sent á hvern gagnahnút til að reikna út hallann, síðan er reiknuðum halla safnað saman og niðurstaðan af summu þeirra notuð til að bæta niðurstöðuna.

Þrátt fyrir auðvelda útfærslu og getu til að framkvæma í MapReduce hugmyndafræðinni, hefur halli einnig sína galla. Sérstaklega er fjöldi þrepa sem þarf til að ná samleitni verulega hærri miðað við aðrar sérhæfðari aðferðir.

LSQR

LSQR er önnur aðferð til að leysa vandamálið, sem hentar bæði til að endurheimta línulega aðhvarf og til að leysa línuleg jöfnukerfi. Megineinkenni þess er að það sameinar kosti fylkisaðferða og endurtekinnar nálgun. Útfærslur á þessari aðferð er að finna á báðum söfnunum SciPy, og í MATLAB. Lýsing á þessari aðferð verður ekki gefin hér (það er að finna í greininni LSQR: Reiknirit fyrir dreifðar línulegar jöfnur og dreifðar minnstu ferninga). Þess í stað verður sýnd nálgun til að laga LSQR að framkvæmd í dreifðu umhverfi.

LSQR aðferðin byggir á aðferð við tvíhyrning. Þetta er endurtekið ferli, hver endurtekning samanstendur af eftirfarandi skrefum:


En ef við gerum ráð fyrir að fylkið er lárétt skipt, þá er hægt að tákna hverja endurtekningu sem tvö MapReduce skref. Þannig er hægt að lágmarka gagnaflutning við hverja endurtekningu (aðeins vektorar með lengd sem er jöfn fjölda óþekktra):

Það er þessi nálgun sem er notuð þegar línuleg aðhvarf er útfærð í Apache Ignite ML.

Ályktun

Það eru mörg línuleg aðhvarfsbata reiknirit, en ekki er hægt að beita þeim öllum við allar aðstæður. Svo QR niðurbrot er frábært fyrir nákvæma lausn á litlum gagnasöfnum. Lækkun halla er einföld í framkvæmd og gerir þér kleift að finna fljótt áætlaða lausn. Og LSQR sameinar bestu eiginleika fyrri tveggja algrímanna, þar sem hægt er að dreifa því, sameinast hraðar samanborið við hallafall og gerir einnig kleift að stöðva reikniritið snemma, ólíkt niðurbroti QR, til að finna áætlaða lausn.

Heimild: www.habr.com