Ipadabọ laini ati awọn ọna fun imularada rẹ

orisun: xkcd

Ipadabọ laini jẹ ọkan ninu awọn algoridimu ipilẹ fun ọpọlọpọ awọn agbegbe ti o ni ibatan si itupalẹ data. Idi fun eyi jẹ kedere. Eyi jẹ algoridimu ti o rọrun pupọ ati oye, eyiti o ti ṣe alabapin si lilo rẹ ni ibigbogbo fun ọpọlọpọ awọn mewa, ti kii ba awọn ọgọọgọrun, awọn ọdun. Ero naa ni pe a ro igbẹkẹle laini ti oniyipada kan lori ṣeto ti awọn oniyipada miiran, ati lẹhinna gbiyanju lati mu igbẹkẹle yii pada.

Ṣugbọn nkan yii kii ṣe nipa lilo ipadasẹhin laini lati yanju awọn iṣoro to wulo. Nibi a yoo ṣe akiyesi awọn ẹya ti o nifẹ si ti imuse ti awọn algoridimu pinpin fun imularada rẹ, eyiti a pade nigba kikọ module ikẹkọ ẹrọ ni Apache Ignite. Iṣiro ipilẹ diẹ, ẹkọ ẹrọ, ati iṣiro pinpin le ṣe iranlọwọ fun ọ lati ro bi o ṣe le ṣe ipadasẹhin laini paapaa nigbati data rẹ ba pin kaakiri ẹgbẹẹgbẹrun awọn apa.

Kini a n sọrọ nipa?

A dojuko pẹlu iṣẹ-ṣiṣe ti mimu-pada sipo igbẹkẹle laini. Gẹgẹbi data titẹ sii, ṣeto ti awọn oniyipada ti awọn oniyipada ominira ti o yẹ ni a fun, ọkọọkan eyiti o ni nkan ṣe pẹlu iye kan ti oniyipada ti o gbẹkẹle. Data yii le jẹ aṣoju ni irisi awọn matrices meji:

Ni bayi, niwọn igba ti a ti ro pe igbẹkẹle naa, ati, paapaa, laini, a yoo kọ arosinu wa ni irisi ọja ti awọn matrices (lati jẹ ki gbigbasilẹ rọrun, nibi ati ni isalẹ o ro pe ọrọ ọfẹ ti idogba naa ti farapamọ lẹhin. , ati awọn ti o kẹhin iwe ti awọn matrix awọn ẹya ninu):

Ndun pupọ bi eto awọn idogba laini, ṣe kii ṣe bẹẹ? O dabi pe, ṣugbọn o ṣeese julọ kii yoo si awọn ojutu si iru eto awọn idogba. Idi fun eyi jẹ ariwo, eyiti o wa ni fere eyikeyi data gidi. Idi miiran le jẹ aini ti igbẹkẹle laini gẹgẹbi iru bẹ, eyiti o le ni ija nipasẹ iṣafihan awọn oniyipada afikun ti o da lori lainidi lori awọn atilẹba. Wo apẹẹrẹ atẹle yii:

orisun: Wikipedia

Eyi jẹ apẹẹrẹ ti o rọrun ti ipadasẹhin laini ti o fihan ibatan ti oniyipada kan (lẹgbẹẹ axis ) lati miiran oniyipada (pẹlú axis ). Ni ibere fun eto awọn idogba laini ti o baamu si apẹẹrẹ yii lati ni ojutu kan, gbogbo awọn aaye gbọdọ dubulẹ ni deede lori laini taara kanna. Ṣugbọn iyẹn kii ṣe otitọ. Ṣugbọn wọn ko dubulẹ lori laini taara kanna ni pato nitori ariwo (tabi nitori arosinu ti ibatan laini jẹ aṣiṣe). Nitorinaa, lati le mu pada ibatan laini lati data gidi, o jẹ dandan lati ṣafihan arosọ diẹ sii: data titẹ sii ni ariwo ati ariwo yii ni. deede pinpin. O le ṣe awọn arosinu nipa awọn iru pinpin ariwo miiran, ṣugbọn ninu ọpọlọpọ awọn ọran o jẹ pinpin deede ti a gbero, eyiti yoo jiroro siwaju.

O pọju ọna ti o ṣeeṣe

Nitorinaa, a ro pe ariwo ti a pin kaakiri laileto wa. Kini lati ṣe ni iru ipo bẹẹ? Fun idi eyi ni mathimatiki o wa ati pe o wa ni lilo pupọ o pọju o ṣeeṣe ọna. Ni kukuru, koko rẹ wa ninu yiyan o ṣeeṣe awọn iṣẹ ati awọn oniwe-tele maximization.

A pada si mimu-pada sipo ibatan laini lati data pẹlu ariwo deede. Ṣe akiyesi pe ibatan laini ti a ro ni ireti mathematiki ti wa tẹlẹ deede pinpin. Ni akoko kanna, iṣeeṣe pe gba lori ọkan iye tabi miiran, koko ọrọ si awọn niwaju observables , ni atẹle:

Jẹ ki a bayi aropo dipo и Awọn oniyipada ti a nilo ni:

Gbogbo ohun ti o ku ni lati wa fekito , ni eyiti iṣeeṣe yii jẹ o pọju. Lati mu iru iṣẹ bẹẹ pọ si, o rọrun lati kọkọ mu logarithm kan (logarithm ti iṣẹ naa yoo de ibi ti o pọju ni aaye kanna bi iṣẹ naa funrararẹ):

Ewo, leteto, wa silẹ lati dinku iṣẹ atẹle:

Nipa ọna, eyi ni a npe ni ọna kan o kere onigun mẹrin. Nigbagbogbo gbogbo awọn ero ti o wa loke ni a yọkuro ati pe ọna yii jẹ lilo nirọrun.

Ibajẹ QR

O kere julọ ti iṣẹ ti o wa loke ni a le rii nipa wiwa aaye nibiti iwọn ti iṣẹ yii jẹ odo. Ati gradient yoo kọ bi atẹle:

Ibajẹ QR jẹ ọna matrix fun ipinnu iṣoro idinku ti a lo ni ọna onigun mẹrin ti o kere ju. Ni iru eyi, a tun kọ idogba ni fọọmu matrix:

Nitorina a decompose matrix si awọn matrices и ati ṣe lẹsẹsẹ awọn iyipada (algoridimu jijẹ QR funrararẹ kii yoo gbero nibi, lilo rẹ nikan ni ibatan si iṣẹ-ṣiṣe ti o wa ni ọwọ):

Akosile jẹ orthogonal. Eyi gba wa laaye lati yọkuro iṣẹ naa :

Ati pe ti o ba rọpo on , lẹhinna o yoo ṣiṣẹ jade . Ṣiyesi iyẹn jẹ matrix onigun mẹta oke, o dabi eyi:

Eyi le ṣee yanju nipa lilo ọna aropo. Eroja ti wa ni be bi , ti tẹlẹ ano ti wa ni be bi ati bẹ lori.

O tọ lati ṣe akiyesi nibi pe idiju ti algorithm Abajade nitori lilo jijẹ QR jẹ dọgba si . Pẹlupẹlu, botilẹjẹpe otitọ pe iṣẹ isodipupo matrix jẹ afiwera daradara, ko ṣee ṣe lati kọ ẹya pinpin ti o munadoko ti algorithm yii.

Isọkalẹ Ilọsiwaju

Nigbati o ba sọrọ nipa idinku iṣẹ kan, o tọ nigbagbogbo lati ranti ọna ti (sitokasitik) isọdi gradient. Eyi jẹ ọna idinku ti o rọrun ati imunadoko ti o da lori ṣiṣe iṣiro iwọntunwọnsi ti iṣẹ kan ni aaye kan ati lẹhinna yiyi pada si itọsọna idakeji si gradient. Kọọkan iru igbese mu ojutu jo si kere. Awọn gradient si tun wulẹ kanna:

Ọna yii tun jẹ afiwe daradara ati pinpin nitori awọn ohun-ini laini ti oniṣẹ gradient. Ṣe akiyesi pe ninu agbekalẹ loke, labẹ ami apao awọn ofin ominira wa. Ni awọn ọrọ miiran, a le ṣe iṣiro gradient ni ominira fun gbogbo awọn atọka lati akọkọ si , ni afiwe pẹlu eyi, ṣe iṣiro gradient fun awọn atọka pẹlu si . Lẹhinna ṣafikun awọn gradients abajade. Abajade ti afikun yoo jẹ kanna bi ti a ba ṣe iṣiro gradient lẹsẹkẹsẹ fun awọn atọka lati akọkọ si . Nitorinaa, ti data naa ba pin laarin awọn ege data pupọ, gradient le ṣe iṣiro ni ominira lori nkan kọọkan, lẹhinna awọn abajade ti awọn iṣiro wọnyi le ṣe akopọ lati gba abajade ikẹhin:

Lati oju-ọna imuse, eyi ni ibamu pẹlu apẹrẹ MapDinku. Ni igbesẹ kọọkan ti isunmọ gradient, iṣẹ kan ni a fi ranṣẹ si ipade data kọọkan lati ṣe iṣiro gradient, lẹhinna a kojọpọ awọn gradients ti a ṣe iṣiro papọ, ati abajade ti apao wọn ni a lo lati mu abajade dara si.

Laibikita irọrun ti imuse ati agbara lati ṣiṣẹ ni MapReduce paradigm, irandiwọn tun ni awọn ailagbara rẹ. Ni pataki, nọmba awọn igbesẹ ti o nilo lati ṣaṣeyọri isọdọkan jẹ pataki ga julọ ni akawe si awọn ọna amọja diẹ sii.

LSQR

LSQR jẹ ọna miiran lati yanju iṣoro naa, eyiti o dara mejeeji fun mimu-pada sipo ipadasẹhin laini ati fun awọn ọna ṣiṣe ti awọn idogba laini. Ẹya akọkọ rẹ ni pe o dapọ awọn anfani ti awọn ọna matrix ati ọna aṣetunṣe. Awọn imuse ti ọna yii ni a le rii ni awọn ile-ikawe mejeeji SciPyati ninu MATLAB. Apejuwe ti ọna yii kii yoo fun nibi (o le rii ninu nkan naa LSQR: algorithm kan fun awọn idogba laini ṣoki ati awọn onigun mẹrin ti o kere ju). Dipo, ọna kan yoo ṣe afihan lati ṣe deede LSQR si ipaniyan ni agbegbe pinpin.

Ọna LSQR da lori ilana bidiagonalization. Eyi jẹ ilana aṣetunṣe, aṣetunṣe kọọkan ni awọn igbesẹ wọnyi:


Ṣugbọn ti a ba ro pe matrix ti pin si petele, lẹhinna aṣetunṣe kọọkan le jẹ aṣoju bi awọn igbesẹ MapReduce meji. Ni ọna yii, o ṣee ṣe lati dinku awọn gbigbe data lakoko aṣetunṣe kọọkan (awọn alakan nikan pẹlu ipari ti o dọgba si nọmba awọn aimọ):

O jẹ ọna yii ti a lo nigba imuse ipadasẹhin laini ni Apache Ignite ML.

ipari

Ọpọlọpọ awọn algoridimu imularada laini laini wa, ṣugbọn kii ṣe gbogbo wọn ni a le lo ni gbogbo awọn ipo. Nitorinaa jijẹ QR jẹ o tayọ fun ojutu deede lori awọn eto data kekere. Isọkalẹ gradient rọrun lati ṣe ati gba ọ laaye lati wa ojutu isunmọ ni iyara. Ati LSQR daapọ awọn ohun-ini ti o dara julọ ti awọn algoridimu meji ti tẹlẹ, niwọn bi o ti le pin kaakiri, yiyara yiyara ni akawe si isunmọ gradient, ati tun gba idaduro ni kutukutu ti algorithm, ko dabi ibajẹ QR, lati wa ojutu isunmọ.

orisun: www.habr.com