Lineara regreso kaj metodoj por ĝia reakiro

fonto: xkcd

Lineara regreso estas unu el la bazaj algoritmoj por multaj areoj ligitaj al datuma analizo. La kialo de ĉi tio estas evidenta. Ĉi tio estas tre simpla kaj komprenebla algoritmo, kiu kontribuis al sia disvastigita uzo dum multaj dekoj, se ne centoj da jaroj. La ideo estas ke ni supozas linearan dependecon de unu variablo sur aro de aliaj variabloj, kaj tiam provas restarigi ĉi tiun dependecon.

Sed ĉi tiu artikolo ne temas pri uzado de lineara regreso por solvi praktikajn problemojn. Ĉi tie ni konsideros interesajn trajtojn de la efektivigo de distribuitaj algoritmoj por ĝia reakiro, kiujn ni renkontis dum verkado de maŝinlernada modulo en Apache Ignite. Iom da baza matematiko, maŝinlernado kaj distribuita komputado povas helpi vin eltrovi kiel fari linearan regreson eĉ kiam viaj datumoj estas distribuitaj tra miloj da nodoj.

Pri kio ni parolas?

Ni alfrontas la taskon restarigi linearan dependecon. Kiel enigdatenoj, aro de vektoroj de supozeble sendependaj variabloj ricevas, ĉiu el kiuj estas rilata al certa valoro de la dependa variablo. Ĉi tiuj datumoj povas esti reprezentitaj en la formo de du matricoj:

Nun, ĉar la dependeco estas supozata, kaj, krome, linia, ni skribos nian supozon en la formo de produkto de matricoj (por simpligi la registradon, ĉi tie kaj sube oni supozas, ke la libera termino de la ekvacio estas kaŝita malantaŭe). , kaj la lasta kolumno de la matrico enhavas unuojn):

Sonas tre kiel sistemo de linearaj ekvacioj, ĉu ne? Ŝajnas, sed plej verŝajne ne estos solvoj al tia sistemo de ekvacioj. La kialo de tio estas bruo, kiu ĉeestas en preskaŭ ĉiuj realaj datumoj. Alia kialo povas esti la manko de linia dependeco kiel tia, kiu povas esti kontraŭbatalita enkondukante kromajn variablojn kiuj nelinie dependas de la originaj. Konsideru la sekvan ekzemplon:

fonto: Vikipedio

Ĉi tio estas simpla ekzemplo de linia regreso kiu montras la rilaton de unu variablo (laŭ la akso ) de alia variablo (laŭ la akso ). Por ke la sistemo de linearaj ekvacioj respondaj al ĉi tiu ekzemplo havu solvon, ĉiuj punktoj devas kuŝi ĝuste sur la sama rekto. Sed tio ne estas vera. Sed ili ne kuŝas sur la sama rekto ĝuste pro bruo (aŭ ĉar la supozo de linia rilato estis erara). Tiel, por restarigi liniaran rilaton de realaj datenoj, estas kutime necese enkonduki unu plian supozon: la enirdatenoj enhavas bruon kaj tiu bruo havas normala distribuo. Vi povas fari supozojn pri aliaj specoj de brua distribuo, sed en la granda plimulto de kazoj estas la normala distribuo kiu estas konsiderata, kiu estos diskutita plu.

Maksimuma verŝajneca metodo

Do, ni supozis la ĉeeston de hazarda normale distribuita bruo. Kion fari en tia situacio? Por ĉi tiu kazo en matematiko ekzistas kaj estas vaste uzata metodo de maksimuma verŝajneco. Resume, ĝia esenco kuŝas en la elekto verŝajnaj funkcioj kaj ĝia posta maksimumigo.

Ni revenas al restarigo de lineara rilato de datumoj kun normala bruo. Notu ke la supozita linia rilato estas la matematika atendo ekzistanta normala distribuo. Samtempe, la probablo ke alprenas unu valoron aŭ alian, kondiĉe de la ĉeesto de observeblaj , jene:

Ni anstataŭu nun и La variabloj, kiujn ni bezonas, estas:

Restas nur trovi la vektoron , ĉe kiu ĉi tiu probablo estas maksimuma. Por maksimumigi tian funkcion, estas oportune unue preni logaritmon de ĝi (la logaritmo de la funkcio atingos maksimumon en la sama punkto kiel la funkcio mem):

Kio, siavice, signifas minimumigi la sekvan funkcion:

Cetere, ĉi tio nomiĝas metodo minimumaj kvadratoj. Ofte ĉiuj ĉi-supraj konsideroj estas preterlasitaj kaj ĉi tiu metodo estas simple uzata.

QR-malkomponaĵo

La minimumo de ĉi-supra funkcio povas esti trovita trovante la punkton ĉe kiu la gradiento de ĉi tiu funkcio estas nul. Kaj la gradiento estos skribita jene:

QR-malkomponaĵo estas matrica metodo por solvi la minimumigproblemon uzatan en la metodo de malplej kvadrataj. Ĉi-rilate, ni reverkas la ekvacion en matrica formo:

Do ni malkomponas la matricon al matricoj и kaj faru serion da transformoj (la QR-malkompona algoritmo mem ne estos konsiderata ĉi tie, nur ĝia uzo rilate la taskon):

Matrico estas orta. Ĉi tio ebligas al ni forigi la laboron :

Kaj se vi anstataŭas sur , tiam ĝi funkcios . Konsiderante tion estas supra triangula matrico, ĝi aspektas jene:

Ĉi tio povas esti solvita per la anstataŭiga metodo. Elemento situas kiel , antaŭa elemento situas kiel kaj tiel plu.

Estas notinde ĉi tie, ke la komplekseco de la rezulta algoritmo pro la uzo de QR-malkomponaĵo estas egala al . Krome, malgraŭ la fakto, ke la matrica multiplika operacio estas bone paraleligita, ne eblas skribi efikan distribuitan version de ĉi tiu algoritmo.

Gradienta Deveno

Kiam oni parolas pri minimumigo de funkcio, ĉiam indas memori la metodon de (stokastika) gradienta deveno. Ĉi tio estas simpla kaj efika minimumigmetodo bazita sur ripeta kalkulo de la gradiento de funkcio ĉe punkto kaj tiam movi ĝin en la direkto kontraŭa al la gradiento. Ĉiu tia paŝo proksimigas la solvon al la minimumo. La gradiento ankoraŭ aspektas same:

Ĉi tiu metodo ankaŭ estas bone paraleligita kaj distribuita pro la liniaj trajtoj de la gradientfunkciigisto. Notu, ke en la supra formulo, sub la sumsigno estas sendependaj terminoj. Alivorte, ni povas kalkuli la gradienton sendepende por ĉiuj indeksoj de la unua ĝis , paralele kun tio, kalkulu la gradienton por indeksoj kun por . Poste aldonu la rezultajn gradientojn. La rezulto de la aldono estos la sama kvazaŭ ni tuj kalkulus la gradienton por indeksoj de la unua ĝis . Tiel, se la datenoj estas distribuitaj inter pluraj datenoj, la gradiento povas esti kalkulita sendepende sur ĉiu peco, kaj tiam la rezultoj de tiuj kalkuloj povas esti sumigitaj por akiri la finan rezulton:

De efektivigpunkto, ĉi tio kongruas kun la paradigmo MapReduce. Je ĉiu paŝo de gradienta deveno, tasko estas sendita al ĉiu datennodo por kalkuli la gradienton, tiam la kalkulitaj gradientoj estas kolektitaj kune, kaj la rezulto de ilia sumo estas uzata por plibonigi la rezulton.

Malgraŭ la facileco de efektivigo kaj la kapablo ekzekuti en la paradigmo MapReduce, gradienta deveno ankaŭ havas siajn malavantaĝojn. Aparte, la nombro da ŝtupoj necesaj por atingi konverĝon estas signife pli alta kompare kun aliaj pli specialecaj metodoj.

LSQR

LSQR estas alia metodo por solvi la problemon, kiu taŭgas kaj por restarigo de lineara regreso kaj por solvi sistemojn de linearaj ekvacioj. Ĝia ĉefa trajto estas, ke ĝi kombinas la avantaĝojn de matricaj metodoj kaj ripeta aliro. Efektivigoj de ĉi tiu metodo troveblas en ambaŭ bibliotekoj SciPy, kaj en MATLAB. Priskribo de ĉi tiu metodo ne estos donita ĉi tie (ĝi troveblas en la artikolo LSQR: algoritmo por malabundaj liniaj ekvacioj kaj malabundaj malplej kvadratoj). Anstataŭe, aliro estos pruvita por adapti LSQR al ekzekuto en distribuita medio.

La metodo LSQR baziĝas sur proceduro de bidiagonaligo. Ĉi tio estas ripeta proceduro, ĉiu ripeto konsistanta el la sekvaj paŝoj:


Sed se ni supozas ke la matrico estas horizontale dividita, tiam ĉiu ripeto povas esti reprezentita kiel du MapReduce-ŝtupoj. Tiamaniere, estas eble minimumigi datumtranslokigojn dum ĉiu ripeto (nur vektoroj kun longo egala al la nombro da nekonataĵoj):

Estas ĉi tiu aliro kiu estas uzata dum efektivigado de lineara regreso en Apache Ignite ML.

konkludo

Ekzistas multaj linearaj regresaj reakiro-algoritmoj, sed ne ĉiuj el ili povas esti aplikitaj en ĉiuj kondiĉoj. Do QR-malkomponaĵo estas bonega por preciza solvo sur malgrandaj datumaj aroj. Gradienta deveno estas simple efektivigi kaj permesas vin rapide trovi proksimuman solvon. Kaj LSQR kombinas la plej bonajn ecojn de la antaŭaj du algoritmoj, ĉar ĝi povas esti distribuita, konverĝas pli rapide kompare kun gradienta deveno, kaj ankaŭ permesas fruan ĉesigon de la algoritmo, male al QR-malkomponaĵo, por trovi proksimuman solvon.

fonto: www.habr.com