Dib u noqoshada toosan iyo hababka dib u soo kabashada

Source: xkcd

Dib-u-celinta tooska ah waa mid ka mid ah algorithms-yada aasaasiga ah ee meelo badan oo la xidhiidha falanqaynta xogta. Sababta tani waa caddahay. Tani waa algorithm aad u fudud oo la fahmi karo, taas oo ka qayb qaadatay isticmaalkeeda baahsan ee tobanaan badan, haddii aysan ahayn boqolaal, sano. Fikradda ayaa ah in aan u qaadanno ku tiirsanaanta toosan ee doorsoomayaal kale, ka dibna aan isku dayno inaan soo celino ku tiirsanaantan.

Laakiin maqaalkani maaha mid ku saabsan isticmaalka dib-u-celinta tooska ah si loo xalliyo dhibaatooyinka la taaban karo. Halkan waxaan ku tixgelin doonaa sifooyinka xiisaha leh ee hirgelinta algorithms-yada loo qaybiyey ee soo kabashada, taas oo aan la kulannay markii aan qoraynay cutubka barashada mashiinka Apache Ignite. Xisaab yar oo aasaasi ah, barashada mashiinka, iyo xisaabinta la qaybiyey ayaa kaa caawin karta inaad ogaato sida loo sameeyo dib u noqoshada toosan xitaa marka xogtaada loo qaybiyo kumanaan nood ah.

Maxaan ka hadlaynaa?

Waxa ina soo food saartay hawsha soo celinta ku tiirsanaanta toosan. Sida xogta la gelinayo, waxaa la bixiyaa qaybo ka mid ah doorsoomayaal loo malaynayo inay madaxbannaan yihiin, kuwaas oo mid kastaa uu la xidhiidho qiime cayiman oo doorsoomayaal ku tiirsan ah. Xogtan waxa loo matalli karaa qaab laba qaybood:

Hadda, maadaama ku-tiirsanaanta loo maleynayo, iyo, sidoo kale, toosan, waxaan ku qori doonaa malo-awaalkeena qaabka wax soo saarka matrixka (si loo fududeeyo duubista, halkan iyo hoos waxaa loo maleynayaa in ereyga bilaashka ah ee isla'egta uu qarsoon yahay). , iyo tiirka u dambeeya ee matrixka ka kooban yahay cutubyo):

Waxay aad ugu dhawdahay nidaamka isla'egta toosan, miyaanay ahayn? Waxay u muuqataa, laakiin waxay u badan tahay inaysan jirin wax xal ah oo loo helo nidaamkan isla'egta ah. Sababta tani waa buuq, taas oo ku jirta ku dhawaad ​​xog kasta oo dhab ah. Sababta kale waxay noqon kartaa la'aanta ku-tiirsanaanta tooska ah sida oo kale, taas oo lagula dagaallami karo iyada oo la soo bandhigayo doorsoomayaal dheeraad ah oo si aan toos ahayn ugu xiran yihiin kuwa asalka ah. Tixgeli tusaalaha soo socda:

Source: Wikipedia

Kani waa tusaale fudud oo dib u noqoshada toosan ah oo tusinaya xidhiidhka hal doorsoome (dhinaca dhidiga ) ka doorsoome kale (dhinaca dhidibka ). Si nidaamka isla'egta toosan ee tusaalahan u dhiganta uu xal u helo, dhammaan qodobbada waa in ay si sax ah u jiifaan isla xariiq toosan. Laakiin taasi run maaha. Laakin kuma been sheegaan isla xariiq toosan oo sax ah sawaxan dartiis (ama malaha xidhiidhka toosan ayaa khalad ahaa). Sidaa darteed, si loo soo celiyo xiriirka tooska ah ee xogta dhabta ah, sida caadiga ah waa lagama maarmaan in la soo bandhigo hal male oo dheeraad ah: xogta gelinta ayaa ka kooban buuq iyo sawaxan ayaa leh. qaybinta caadiga ah. Waxaad samayn kartaa malo-awaal ku saabsan noocyada kale ee qaybinta qaylada, laakiin inta badan kiisaska waa qaybinta caadiga ah ee la tixgeliyo, taas oo si dheeraad ah looga hadli doono.

Habka suurtogalka ah ee ugu badan

Markaa, waxaanu u qaadanay in uu jiro qaylo si caadi ah loo qaybiyay. Maxaa la sameeyaa marka ay xaaladdu sidaas tahay? Kiiskan xagga xisaabta waxaa jira oo si weyn loo isticmaalaa habka ugu badan ee suurtogalka ah. Marka la soo koobo, nuxurkeedu wuxuu ku jiraa doorashada hawlaha suurtagalka ah iyo ugu badnaanteeda danbe.

Waxaan ku soo laabaneynaa soo celinta xiriirka tooska ah ee xogta leh buuq caadi ah. Ogow in xidhiidhka toosan ee la malaynayo uu yahay filashada xisaabeed qaybinta caadiga ah ee jira. Isla mar ahaantaana, itimaalka in waxay qaadataa hal qiime ama mid kale, iyadoo ku xiran joogitaanka waxyaabaha la arki karo , sida soo socota:

Aan hadda beddelno и Doorsoomayaasha aan u baahanahay waa:

Waxa hadhay oo dhan waa in la helo vector-ka , taas oo itimaalkani uu yahay ugu badnaan. Si loo kordhiyo shaqada noocan oo kale ah, way ku habboon tahay in marka hore la qaato logarithm (logarithm-ka shaqadu wuxuu gaari doonaa ugu badnaan isla goobta shaqada lafteeda):

Taas oo, iyana, ku soo degta si loo yareeyo shaqada soo socota:

By habka, tan waxaa loo yaqaan hab afar geesoodka ugu yar. Badanaa dhammaan tixgalinta kor ku xusan waa laga tagay oo habkan si fudud ayaa loo isticmaalaa.

Qulqulka QR

Inta ugu yar ee shaqada kor ku xusan waxaa lagu heli karaa marka la helo barta uu jaan-gooyada shaqadani yahay eber. Oo gradient-ku wuxuu u qori doonaa sidan soo socota:

Qulqulka QR waa hab matrix ah oo lagu xallinayo dhibaatada yaraynta ee loo isticmaalo habka ugu yar ee labajibbaaran. Arrin tan la xiriirta, waxaan dib ugu qoreynaa isla'egta qaabka matrixka:

Markaa waxaan kala jajabineynaa matrixka si loo mariyo и oo samee isbeddelo taxane ah (algorithmiyaha kala-goynta QR laftiisa halkan laguma tixgalin doono, kaliya isticmaalkeeda ee la xidhiidha hawsha gacanta lagu hayo):

Matrix waa orthogonal. Tani waxay noo ogolaaneysaa inaan ka takhalusno shaqada :

Iyo haddii aad beddesho on , ka dibna way shaqayn doontaa . Iyadoo la tixgelinayo taas waa matrix saddex xagal sare ah, waxay u egtahay sidan:

Tan waxaa lagu xallin karaa iyadoo la adeegsanayo habka beddelka. Cunsurka waxa uu ku yaalaa sida , element hore waxa uu ku yaalaa sida iyo wixii la mid ah.

Waxaa xusid mudan in kakanaanta algorithm-ka soo baxay ay sabab u tahay isticmaalka kala-goynta QR ay la mid tahay . Waxaa intaa dheer, inkastoo xaqiiqda ah in hawlgalka isku dhufashada matrixka uu si fiican u siman yahay, suurtagal maaha in la qoro nuqul qaybsan oo waxtar leh oo algorithm this.

Hoos-u-dhac

Markaad ka hadlaysid yaraynta shaqada, waxaa had iyo jeer mudan in la xasuusto habka (stochastic) hoos-u-dhaca gradient. Tani waa hab fudud oo wax ku ool ah oo yaraynta iyadoo ku salaysan si isdaba joog ah loo xisaabinayo jaangooyooyinka shaqada meel ka mid ah ka dibna loo wareejinayo jihada ka soo horjeeda jaan-gooyaha. Tallaabo kasta oo noocaas ah waxay keenaysaa xalka ugu dhow ugu yaraan. Gradient-ku wali wuxuu u eg yahay isla:

Habkani waxa kale oo si fiican u barbar socda oo loo qaybiyey sababtoo ah sifooyinka toosan ee hawlwadeenka gradient. Ogsoonow in qaacidada sare, hoosta calaamadda wadarta ay jiraan ereyo madax-bannaan. Si kale haddii loo dhigo, waxaan u xisaabin karnaa gradient si madax banaan dhammaan tusmooyinka marka hore ilaa , taas oo barbar socota tan, xisaabi jaangooyooyinka tusmooyinka leh si ay u . Ka dibna ku dar jaangooyooyinka ka soo baxay. Natiijada isku-darka waxay la mid noqon doontaa haddii aan isla markiiba xisaabinnay jaangooyooyinka tusmooyinka laga bilaabo ugu horreeya ilaa . Sidaa darteed, haddii xogta loo qaybiyo dhowr qaybood oo xog ah, gradient-ka waxaa loo xisaabin karaa si madax-bannaan qayb kasta, ka dibna natiijooyinka xisaabintan ayaa lagu soo koobi karaa si loo helo natiijada kama dambaysta ah:

Marka laga eego dhinaca fulinta, tani waxay ku habboon tahay jaantuska Khariidadda. Tallaabo kasta oo ka mid ah hoos-u-dhac kasta, hawl ayaa loo diraa dhudhun kasta oo xog ah si loo xisaabiyo jaangooyooyinka, ka dibna jaangooyooyinka la xisaabiyay ayaa la isla ururiyaa, natiijada wadarkooda ayaa loo isticmaalaa si loo hagaajiyo natiijada.

In kasta oo ay fududdahay hirgelinta iyo awoodda lagu fulinayo MapReduce paradigm, soo degid tartiib tartiib ah ayaa sidoo kale leh cilladaheeda. Gaar ahaan, tirada tillaabooyinka loo baahan yahay si loo gaaro isu-tagga ayaa aad u sarreeya marka loo eego hababka kale ee gaarka ah.

LSQR

LSQR waa hab kale oo lagu xaliyo dhibaatada, kaas oo ku haboon labadaba soo celinta dib u noqoshada toosan iyo xalinta nidaamyada isla'egyada toosan. Muuqaalkeeda ugu muhiimsan waa in ay isku darayso faa'iidooyinka hababka matrixka iyo habka soo noqnoqda. Hirgelinta habkan waxaa laga heli karaa labada maktabadood SciPy, iyo MATLAB. Sharaxaada habkan laguma bixin doono halkan (waxaa laga heli karaa maqaalka LSQR: Algorithm ee isla'egyada toosan ee aan fiicneyn iyo labajibbaaranyada ugu yar). Taa beddelkeeda, hab ayaa la soo bandhigi doonaa si loo waafajiyo LSQR si loogu fuliyo deegaan loo qaybiyey.

Habka LSQR wuxuu ku salaysan yahay habka laba geesoodka. Tani waa habraac soo noqnoqonaya, soo noqnoqon kasta oo ka kooban tallaabooyinka soo socda:


Laakiin haddii aan u qaadan in matrix ah si toosan ayaa loo kala qaybiyay, ka dib shaandheyn kasta waxaa loo soo bandhigi karaa sidii laba tilaabo oo MapReduce ah. Sidan, waxaa suurtagal ah in la yareeyo wareejinta xogta inta lagu jiro dib-u-eegis kasta (kaliya vectors leh dherer la mid ah tirada aan la garanayn):

Waa habkan la isticmaalo marka la hirgelinayo dib u noqoshada toosan ee gudaha Apache Ignite ML.

gunaanad

Waxaa jira algorithms soo kabashada toosan oo badan, laakiin dhammaantood laguma dabaqi karo dhammaan xaaladaha. Markaa burburka QR wuxuu u fiican yahay xalka saxda ah ee xogta yar yar. Soo degitaanka gradient waa sahlan tahay in la hirgeliyo waxayna kuu ogolaaneysaa inaad si degdeg ah u hesho xal qiyaas ah. LSQR-na waxay isku daraysaa sifooyinka ugu fiican ee labadii algorithm ee hore, maadaama la qaybin karo, si dhakhso leh ayay isugu soo ururtaa marka la barbar dhigo farcanka gradient, waxayna sidoo kale ogolaataa joojinta hore ee algorithm, si ka duwan burburka QR, si loo helo xal qiyaas ah.

Source: www.habr.com