Source:
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
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:
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.
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
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
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:
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
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
Tha an dòigh LSQR stèidhichte air
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
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