Tilleadh sreathach agus dòighean airson faighinn seachad air

Source: xkcd

Is e ais-tharraing sreathach aon de na h-algorithms bunaiteach airson iomadh raon co-cheangailte ri mion-sgrùdadh dàta. Tha an t-adhbhar airson seo follaiseach. Is e algairim gu math sìmplidh agus so-thuigsinn a tha seo, a tha air cur ri bhith ga chleachdadh fad is farsaing airson deichean, mura ceudan, de bhliadhnaichean. Is e am beachd gu bheil sinn a’ gabhail ri eisimeileachd sreathach de aon chaochladair air seata de chaochladairean eile, agus an uairsin feuchaidh sinn ris an eisimeileachd seo a thoirt air ais.

Ach chan eil an artaigil seo mu bhith a’ cleachdadh ais-tharraing sreathach gus fuasgladh fhaighinn air duilgheadasan practaigeach. An seo beachdaichidh sinn air feartan inntinneach a thaobh buileachadh algorithms sgaoilte airson faighinn air ais, ris an do thachair sinn nuair a bha sinn a’ sgrìobhadh modal ionnsachaidh inneal Ignite Apache. Faodaidh beagan matamataigs bunaiteach, ionnsachadh innealan, agus coimpiutaireachd sgaoilte do chuideachadh le bhith a’ faighinn a-mach mar a nì thu ath-thilleadh sreathach eadhon nuair a thèid an dàta agad a sgaoileadh thairis air mìltean de nodan.

Cò mu dheidhinn a tha thu a ’bruidhinn?

Tha e mar dhleastanas oirnn eisimeileachd sreathach a thoirt air ais. Mar dàta cuir a-steach, tha seata de vectaran de chaochladairean neo-eisimeileach air an toirt seachad, gach aon dhiubh co-cheangailte ri luach sònraichte den chaochladair eisimeileach. Faodar an dàta seo a riochdachadh ann an cruth dà mhatrics:

A-nis, leis gu bheilear a’ gabhail ris an eisimeileachd, agus, a bharrachd air sin, sreathach, sgrìobhaidh sinn ar barail ann an cruth toradh matrices (gus an clàradh a dhèanamh nas sìmplidhe, an seo agus gu h-ìosal thathas a’ gabhail ris gu bheil teirm an-asgaidh na co-aontar falaichte air a chùlaibh. , agus an colbh mu dheireadh den mhaitris Tha aonadan ann):

Tha e gu math coltach ri siostam de cho-aontaran sreathach, nach eil? Tha e coltach, ach is coltaiche nach bi fuasglaidhean ann airson siostam co-aontaran mar sin. Is e an adhbhar airson seo fuaim, a tha an làthair ann an cha mhòr dàta fìor. Is dòcha gur e adhbhar eile an dìth eisimeileachd sreathach mar sin, a dh’ fhaodar a shabaid le bhith a’ toirt a-steach caochladairean a bharrachd nach eil an urra ris an fheadhainn thùsail. Beachdaich air an eisimpleir a leanas:

Source: Uicipeid

Is e seo eisimpleir sìmplidh de ath-thilleadh sreathach a tha a’ sealltainn an dàimh eadar aon chaochladair (air an axis ) bho chaochladair eile (air an axis ). Gus am bi fuasgladh aig an t-siostam de cho-aontaran sreathach a fhreagras air an eisimpleir seo, feumaidh a h-uile puing laighe dìreach air an aon loidhne dhìreach. Ach chan eil sin fìor. Ach chan eil iad a 'laighe air an aon loidhne dhìreach dìreach air sgàth fuaim (no air sgàth' s gu robh a 'bheachd air dàimh sreathach mearachdach). Mar sin, gus dàimh sreathach a thoirt air ais bho fhìor dhàta, mar as trice feumar aon bharail eile a thoirt a-steach: tha fuaim anns an dàta cuir a-steach agus tha fuaim aig an fhuaim seo. sgaoileadh àbhaisteach. Faodaidh tu barailean a dhèanamh mu sheòrsachan eile de chuairteachadh fuaim, ach anns a 'mhòr-chuid de chùisean is e an cuairteachadh àbhaisteach a thathar a' beachdachadh, a thèid a dheasbad nas fhaide.

An dòigh as àirde de choltas

Mar sin, ghabh sinn ris gu robh fuaim air thuaiream air a chuairteachadh gu h-àbhaisteach. Dè a dhèanamh ann an suidheachadh mar sin? Airson a 'chùis seo ann am matamataig tha agus tha e air a chleachdadh gu farsaing dòigh-obrach as coltaiche. Ann an ùine ghoirid, tha a bhrìgh anns an roghainn gnìomhan coltachd agus a mheudachadh an dèidh sin.

Bidh sinn a’ tilleadh gu bhith ag ath-nuadhachadh dàimh sreathach bho dhàta le fuaim àbhaisteach. Thoir an aire gur e an dàimh sreathach ris an canar an dùil matamataigeach sgaoileadh àbhaisteach gnàthach. Aig an aon àm, tha an coltachd gu bheil a’ gabhail aon luach no luach eile, le ùmhlachd do làthaireachd nithean faicsinneach , mar a leanas:

Leig leinn a-nis cuir na àite и Is iad na caochladairean a tha a dhìth oirnn:

Chan eil air fhàgail ach an vector a lorg , aig a bheil an coltachd seo as àirde. Gus an leithid de ghnìomh a mheudachadh, tha e goireasach logarithm a ghabhail dheth an-toiseach (bidh logarithm na gnìomh a ’ruighinn a’ char as àirde aig an aon àm ris a ’ghnìomh fhèin):

A tha, an uair sin, a’ tighinn sìos gu bhith a’ lughdachadh na h-obrach a leanas:

Air an t-slighe, canar dòigh-obrach ris an seo ceàrnagan as lugha. Gu math tric tha a h-uile beachd gu h-àrd air an dearmad agus tha an dòigh seo dìreach air a chleachdadh.

QR lobhadh

Faodar an ìre as lugha den ghnìomh gu h-àrd a lorg le bhith a’ lorg a’ phuing aig a bheil caisead na gnìomh seo neoni. Agus thèid an caisead a sgrìobhadh mar a leanas:

QR lobhadh na dhòigh matrix airson fuasgladh fhaighinn air an duilgheadas lughdachadh a thathas a’ cleachdadh anns an dòigh as lugha de cheàrnagan. A thaobh seo, bidh sinn ag ath-sgrìobhadh an co-aontar ann an cruth matrix:

Mar sin bidh sinn a 'briseadh sìos an matrix gu matrices и agus dèan sreath de chruth-atharrachaidhean (cha tèid beachdachadh air an algairim lobhadh QR fhèin an seo, dìreach a chleachdadh a thaobh na h-obrach a tha ri làimh):

Matrix tha orthogonal. Leigidh seo leinn faighinn cuidhteas an obair :

Agus ma chuireas tu an àite air , an uairsin obraichidh e a-mach . A’ beachdachadh air sin Is e matrix triantanach àrd a th’ ann, tha e a’ coimhead mar seo:

Faodar seo fhuasgladh le bhith a’ cleachdadh an dòigh ionadachaidh. Eileamaid air a shuidheachadh mar , eileamaid roimhe air a shuidheachadh mar agus mar sin air.

'S fhiach toirt fa-near an seo gu bheil an iom-fhillteachd an algairim mar thoradh air a bhith a' cleachdadh QR lobhadh co-ionann ri . A bharrachd air an sin, a dh ’aindeoin gu bheil gnìomhachd iomadachaidh matrix air a cho-thaobhadh gu math, chan eil e comasach dreach sgaoilte èifeachdach den algairim seo a sgrìobhadh.

Sliochd caisead

Nuair a bhios tu a 'bruidhinn mu bhith a' lùghdachadh gnìomh, is fhiach cuimhneachadh an-còmhnaidh air an dòigh air teàrnadh caisead (stochastic). Is e dòigh lughdachadh sìmplidh agus èifeachdach a tha seo a tha stèidhichte air a bhith ag obrachadh a-mach caisead gnìomh aig puing gu ath-aithriseach agus an uairsin ga ghluasad chun taobh mu choinneamh a’ chaismeachd. Bheir gach ceum mar seo am fuasgladh nas fhaisge air an ìre as ìsle. Tha an caisead fhathast a’ coimhead mar a leanas:

Tha an dòigh seo cuideachd air a cho-thaobhadh gu math agus air a chuairteachadh air sgàth feartan sreathach gnìomhaiche caisead. Thoir an aire gu bheil teirmean neo-eisimeileach anns an fhoirmle gu h-àrd, fon t-soidhne sùim. Ann am faclan eile, is urrainn dhuinn an caisead obrachadh a-mach gu neo-eisimeileach airson a h-uile clàr-amais bhon toiseach gu , co-shìnte ri seo, obraich a-mach an caisead airson clàran-amais le gu . An uairsin cuir ris na caiseadan a thig às. Bidh toradh an cur-ris an aon rud ri bhith a’ tomhas sa bhad an caisead airson clàran-amais bhon chiad fhear gu . Mar sin, ma thèid an dàta a sgaoileadh am measg grunn phìosan dàta, faodar an caisead a thomhas gu neo-eisimeileach air gach pìos, agus an uairsin faodar toraidhean nan àireamhachadh sin a chruinneachadh gus an toradh deireannach fhaighinn:

Bho thaobh buileachaidh, tha seo a 'freagairt air a' phàtran Mapa Lùghdaich. Aig gach ceum de shliochd caisead, thèid gnìomh a chuir gu gach nód dàta gus an caisead obrachadh a-mach, an uairsin bidh na caiseadan àireamhaichte air an cruinneachadh còmhla, agus thèid toradh an t-suim aca a chleachdadh gus an toradh a leasachadh.

A dh ’aindeoin cho furasta‘ s a tha e a chuir an gnìomh agus an comas a chuir an gnìomh ann am paradigm MapReduce, tha eas-bhuannachdan aig teàrnadh caisead. Gu sònraichte, tha an àireamh de cheumannan a tha a dhìth gus co-fhilleadh gu math nas àirde an taca ri dòighean eile nas sònraichte.

LSQR

LSQR dòigh eile airson fuasgladh fhaighinn air an duilgheadas, a tha freagarrach an dà chuid airson ath-thilleadh sreathach a thoirt air ais agus airson siostaman de cho-aontaran sreathach fhuasgladh. Is e a phrìomh fheart gu bheil e a’ cothlamadh buannachdan dòighean matrix agus dòigh-obrach ath-aithriseach. Gheibhear buileachadh an dòigh seo anns an dà leabharlann SciPy, agus a-staigh MATLAB. Cha tèid tuairisgeul den dòigh seo a thoirt seachad an seo (gheibhear e san artaigil LSQR: Algairim airson co-aontaran sreathach gann agus na ceàrnagan as ìsle). An àite sin, thèid dòigh-obrach a shealltainn gus LSQR atharrachadh gu coileanadh ann an àrainneachd sgaoilte.

Tha an dòigh LSQR stèidhichte air modh-obrach bidiagonalization. Is e modh ath-aithriseach a tha seo, le gach tionndadh air a dhèanamh suas de na ceumannan a leanas:


Ach ma tha sinn a 'gabhail ris gu bheil am matrix air a sgaradh gu còmhnard, agus an uairsin faodar gach tionndadh a riochdachadh mar dà cheum MapReduce. San dòigh seo, tha e comasach gluasadan dàta a lughdachadh aig gach tionndadh (dìreach vectaran le fad co-ionann ris an àireamh de neo-aithnichte):

Is e an dòigh-obrach seo a thathas a’ cleachdadh nuair a thathar a’ buileachadh ais-tharraing sreathach ann an Apache Ignite ML.

co-dhùnadh

Tha mòran algoirmean ath-tharraing sreathach ann, ach chan urrainnear a h-uile gin dhiubh a chuir an sàs anns a h-uile suidheachadh. Mar sin tha lobhadh QR sàr-mhath airson fuasgladh ceart air seataichean dàta beaga. Tha teàrnadh caisead sìmplidh a chuir an gnìomh agus leigidh e leat fuasgladh tuairmseach a lorg gu sgiobalta. Agus bidh LSQR a’ cothlamadh nan togalaichean as fheàrr den dà algorithm a bh’ ann roimhe, leis gum faodar a chuairteachadh, a’ tighinn còmhla nas luaithe an taca ri teàrnadh caisead, agus cuideachd a’ ceadachadh stad tràth air an algairim, eu-coltach ri lobhadh QR, gus fuasgladh tuairmseach a lorg.

Source: www.habr.com