Urejeshaji wa mstari na njia za urejeshaji wake

Chanzo: xkcd

Urejeshaji wa mstari ni mojawapo ya kanuni za msingi za maeneo mengi yanayohusiana na uchanganuzi wa data. Sababu ya hii ni dhahiri. Hii ni algorithm rahisi sana na inayoeleweka, ambayo imechangia matumizi yake kuenea kwa makumi mengi, ikiwa sio mamia ya miaka. Wazo ni kwamba tunadhania utegemezi wa mstari wa tofauti moja kwenye seti ya vigezo vingine, na kisha jaribu kurejesha utegemezi huu.

Lakini nakala hii sio juu ya kutumia rejista ya mstari kutatua shida za vitendo. Hapa tutazingatia vipengele vya kuvutia vya utekelezaji wa algorithms iliyosambazwa kwa urejeshaji wake, ambayo tulikutana nayo wakati wa kuandika moduli ya kujifunza mashine katika Apache Ignite. Hisabati kidogo ya msingi, kujifunza kwa mashine, na kompyuta iliyosambazwa inaweza kukusaidia kujua jinsi ya kufanya urejeshaji wa mstari hata wakati data yako inasambazwa katika maelfu ya nodi.

Tunazungumzia nini?

Tunakabiliwa na kazi ya kurejesha utegemezi wa mstari. Kama data ya pembejeo, seti ya vekta za anuwai zinazodaiwa kuwa huru hupewa, ambayo kila moja inahusishwa na thamani fulani ya tofauti tegemezi. Data hii inaweza kuwakilishwa katika mfumo wa matrices mbili:

Sasa, kwa kuwa utegemezi unachukuliwa, na, zaidi ya hayo, mstari, tutaandika dhana yetu kwa namna ya bidhaa ya matrices (ili kurahisisha kurekodi, hapa na chini inachukuliwa kuwa muda wa bure wa equation umefichwa nyuma. , na safu ya mwisho ya matrix ina vitengo):

Inaonekana kama mfumo wa milinganyo ya mstari, sivyo? Inaonekana, lakini uwezekano mkubwa hakutakuwa na ufumbuzi wa mfumo huo wa equations. Sababu ya hii ni kelele, ambayo iko karibu na data yoyote halisi. Sababu nyingine inaweza kuwa ukosefu wa utegemezi wa mstari kama hivyo, ambao unaweza kushughulikiwa kwa kuanzisha vibadala vya ziada ambavyo hutegemea bila mstari kwenye zile za asili. Fikiria mfano ufuatao:

Chanzo: Wikipedia

Huu ni mfano rahisi wa urekebishaji wa mstari ambao unaonyesha uhusiano wa tofauti moja (kando ya mhimili ) kutoka kwa tofauti nyingine (kando ya mhimili ) Ili mfumo wa milinganyo ya mstari unaolingana na mfano huu uwe na suluhisho, nukta zote lazima ziwe kwenye mstari sawa sawa. Lakini hiyo si kweli. Lakini hawalali kwenye mstari ulionyooka haswa kwa sababu ya kelele (au kwa sababu dhana ya uhusiano wa mstari ilikuwa na makosa). Kwa hivyo, ili kurejesha uhusiano wa mstari kutoka kwa data halisi, kwa kawaida ni muhimu kuanzisha dhana moja zaidi: data ya pembejeo ina kelele na kelele hii ina. usambazaji wa kawaida. Unaweza kufanya mawazo kuhusu aina nyingine za usambazaji wa kelele, lakini katika idadi kubwa ya matukio ni usambazaji wa kawaida unaozingatiwa, ambao utajadiliwa zaidi.

Mbinu ya juu ya uwezekano

Kwa hivyo, tulidhani uwepo wa kelele za kawaida zinazosambazwa bila mpangilio. Nini cha kufanya katika hali kama hiyo? Kwa kesi hii katika hisabati kuna na hutumiwa sana njia ya uwezekano mkubwa. Kwa kifupi, asili yake iko katika uchaguzi uwezekano wa kazi na uboreshaji wake unaofuata.

Tunarudi kurejesha uhusiano wa mstari kutoka kwa data na kelele ya kawaida. Kumbuka kuwa uhusiano wa mstari unaodhaniwa ni matarajio ya hisabati usambazaji wa kawaida uliopo. Wakati huo huo, uwezekano huo inachukua thamani moja au nyingine, kulingana na uwepo wa vitu vinavyoonekana , kama ifuatavyo:

Hebu sasa tubadilishe badala yake и Vigezo tunavyohitaji ni:

Kinachobaki ni kupata vekta , ambapo uwezekano huu ni wa juu zaidi. Ili kuongeza kazi kama hiyo, ni rahisi kwanza kuchukua logarithm yake (logarithm ya kazi itafikia kiwango cha juu katika hatua sawa na kazi yenyewe):

Ambayo, kwa upande wake, inakuja kupunguza kazi ifuatayo:

Kwa njia, hii inaitwa njia angalau mraba. Mara nyingi mambo yote hapo juu yameachwa na njia hii hutumiwa tu.

Mtengano wa QR

Kima cha chini cha chaguo za kukokotoa hapo juu kinaweza kupatikana kwa kutafuta hatua ambayo gradient ya kitendakazi hiki ni sifuri. Na gradient itaandikwa kama ifuatavyo:

Mtengano wa QR ni mbinu ya matrix ya kutatua tatizo la kupunguza linalotumiwa katika mbinu ya angalau miraba. Katika suala hili, tunaandika tena equation katika fomu ya matrix:

Kwa hivyo tunatenganisha matrix kwa matrices и na fanya mabadiliko kadhaa (algorithm ya mtengano wa QR yenyewe haitazingatiwa hapa, matumizi yake tu kuhusiana na kazi iliyopo):

tumbo ni orthogonal. Hii inaruhusu sisi kuondokana na kazi :

Na ikiwa utabadilisha juu ya , basi itafanikiwa . Kwa kuzingatia hilo ni matrix ya pembetatu ya juu, inaonekana kama hii:

Hii inaweza kutatuliwa kwa kutumia njia mbadala. Kipengele iko kama , kipengele kilichotangulia iko kama na kadhalika.

Inafaa kumbuka hapa kuwa ugumu wa algorithm inayosababishwa kwa sababu ya utumiaji wa mtengano wa QR ni sawa na . Zaidi ya hayo, licha ya ukweli kwamba operesheni ya kuzidisha matrix inafanana vizuri, haiwezekani kuandika toleo la kusambazwa kwa ufanisi la algorithm hii.

Kushuka kwa Gradient

Wakati wa kuzungumza juu ya kupunguza kazi, inafaa kukumbuka kila wakati njia ya asili ya gradient (stochastic). Hii ni mbinu rahisi na faafu ya kupunguza kulingana na kukokotoa mara kwa mara kipenyo cha chaguo cha kukokotoa kwenye sehemu fulani na kisha kuihamisha kuelekea upande ulio kinyume na upinde rangi. Kila hatua kama hiyo huleta suluhisho karibu na kiwango cha chini. Gradient bado inaonekana sawa:

Njia hii pia inalinganishwa vizuri na inasambazwa kwa sababu ya sifa za mstari wa mwendeshaji wa gradient. Kumbuka kuwa katika fomula iliyo hapo juu, chini ya ishara ya jumla kuna masharti huru. Kwa maneno mengine, tunaweza kuhesabu gradient kwa kujitegemea kwa fahirisi zote kutoka kwanza hadi , sambamba na hii, hesabu upinde rangi kwa fahirisi na kwa . Kisha kuongeza gradients kusababisha. Matokeo ya nyongeza yatakuwa sawa na ikiwa tulihesabu mara moja gradient kwa fahirisi kutoka kwa kwanza hadi . Kwa hivyo, ikiwa data inasambazwa kati ya vipande kadhaa vya data, gradient inaweza kuhesabiwa kwa kujitegemea kwa kila kipande, na kisha matokeo ya mahesabu haya yanaweza kufupishwa ili kupata matokeo ya mwisho:

Kwa mtazamo wa utekelezaji, hii inafaa dhana RamaniKupunguza. Katika kila hatua ya kushuka kwa gradient, kazi hutumwa kwa kila nodi ya data ili kuhesabu gradient, kisha gradients zilizohesabiwa zinakusanywa pamoja, na matokeo ya jumla yao hutumiwa kuboresha matokeo.

Licha ya urahisi wa utekelezaji na uwezo wa kutekeleza katika dhana ya MapReduce, ukoo wa gradient pia una shida zake. Hasa, idadi ya hatua zinazohitajika kufikia muunganisho ni kubwa zaidi ikilinganishwa na njia zingine maalum.

LSQR

LSQR ni njia nyingine ya kutatua shida, ambayo inafaa kwa kurejesha urejeshaji wa mstari na kwa kutatua mifumo ya hesabu za mstari. Kipengele chake kuu ni kwamba inachanganya faida za njia za matrix na mbinu ya kurudia. Utekelezaji wa njia hii unaweza kupatikana katika maktaba zote mbili SciPy, na MATLAB. Maelezo ya njia hii hayatatolewa hapa (inaweza kupatikana katika makala LSQR: Algoriti ya milinganyo midogo midogo na miraba chache zaidi) Badala yake, mbinu itaonyeshwa ili kurekebisha LSQR kwa utekelezaji katika mazingira yaliyosambazwa.

Njia ya LSQR inategemea utaratibu wa kuunganisha pande mbili. Huu ni utaratibu wa kurudia, kila marudio yanajumuisha hatua zifuatazo:


Lakini kama sisi kudhani kwamba tumbo imegawanywa kwa mlalo, basi kila marudio yanaweza kuwakilishwa kama hatua mbili za MapReduce. Kwa njia hii, inawezekana kupunguza uhamishaji wa data wakati wa kila marudio (vekta pekee zilizo na urefu sawa na idadi ya haijulikani):

Ni njia hii ambayo hutumiwa wakati wa kutekeleza urekebishaji wa mstari ndani Apache Ignite ML.

Hitimisho

Kuna algorithms nyingi za urejeshaji urejeshi wa mstari, lakini sio zote zinaweza kutumika katika hali zote. Kwa hivyo mtengano wa QR ni bora kwa suluhisho sahihi kwenye seti ndogo za data. Kushuka kwa gradient ni rahisi kutekeleza na hukuruhusu kupata suluhisho la takriban haraka. Na LSQR inachanganya mali bora ya algorithms mbili zilizopita, kwa kuwa inaweza kusambazwa, hubadilika kwa kasi ikilinganishwa na asili ya gradient, na pia inaruhusu kusimamishwa mapema kwa algorithm, tofauti na mtengano wa QR, ili kupata suluhisho la takriban.

Chanzo: mapenzi.com