Ffynhonnell:
Mae atchweliad llinol yn un o'r algorithmau sylfaenol ar gyfer llawer o feysydd sy'n ymwneud â dadansoddi data. Mae'r rheswm am hyn yn amlwg. Mae hwn yn algorithm syml a dealladwy iawn, sydd wedi cyfrannu at ei ddefnydd eang ers degau, os nad cannoedd, o flynyddoedd. Y syniad yw ein bod yn tybio dibyniaeth linol un newidyn ar set o newidynnau eraill, ac yna ceisio adfer y ddibyniaeth hon.
Ond nid yw'r erthygl hon yn ymwneud â defnyddio atchweliad llinol i ddatrys problemau ymarferol. Yma byddwn yn ystyried nodweddion diddorol gweithredu algorithmau gwasgaredig ar gyfer ei adferiad, y daethom ar eu traws wrth ysgrifennu modiwl dysgu peiriant . Gall ychydig o fathemateg sylfaenol, dysgu peiriant, a chyfrifiadura gwasgaredig eich helpu i ddarganfod sut i berfformio atchweliad llinol hyd yn oed pan fydd eich data'n cael ei ddosbarthu ar draws miloedd o nodau.
Am beth rydyn ni'n siarad?
Rydym yn wynebu'r dasg o adfer dibyniaeth llinol. Fel data mewnbwn, rhoddir set o fectorau o newidynnau tybiedig annibynnol, pob un ohonynt yn gysylltiedig â gwerth penodol y newidyn dibynnol. Gellir cynrychioli'r data hwn ar ffurf dau fatrics:
Yn awr, gan fod y ddibyniaeth yn cael ei thybio, ac, ar ben hynny, yn llinol, byddwn yn ysgrifennu ein rhagdybiaeth ar ffurf cynnyrch matricsau (i symleiddio'r recordiad, yma ac isod cymerir yn ganiataol bod term rhydd yr hafaliad wedi'i guddio y tu ôl. , a cholofn olaf y matrics yn cynnwys unedau):
Mae'n swnio'n debyg iawn i system o hafaliadau llinol, yn tydi? Mae'n ymddangos, ond yn fwyaf tebygol ni fydd unrhyw atebion i system o hafaliadau o'r fath. Y rheswm am hyn yw sŵn, sy'n bresennol mewn bron unrhyw ddata go iawn. Rheswm arall efallai yw'r diffyg dibyniaeth linol fel y cyfryw, y gellir ei frwydro trwy gyflwyno newidynnau ychwanegol sy'n dibynnu'n aflinol ar y rhai gwreiddiol. Ystyriwch yr enghraifft ganlynol:
Ffynhonnell:
Dyma enghraifft syml o atchweliad llinol sy'n dangos perthynas un newidyn (ar hyd yr echelin ) o newidyn arall (ar hyd yr echelin ). Er mwyn i'r system o hafaliadau llinol sy'n cyfateb i'r enghraifft hon gael datrysiad, rhaid i bob pwynt orwedd yn union ar yr un llinell syth. Ond nid yw hynny'n wir. Ond nid ydynt yn gorwedd ar yr un llinell syth oherwydd sŵn yn union (neu oherwydd bod y rhagdybiaeth o berthynas linellol yn wallus). Felly, er mwyn adfer perthynas linellol o ddata go iawn, fel arfer mae angen cyflwyno un dybiaeth arall: mae'r data mewnbwn yn cynnwys sŵn ac mae'r sŵn hwn wedi . Gallwch wneud rhagdybiaethau am fathau eraill o ddosbarthiad sŵn, ond yn y mwyafrif helaeth o achosion, y dosbarthiad arferol a ystyrir, a fydd yn cael ei drafod ymhellach.
Dull tebygolrwydd mwyaf
Felly, fe wnaethom dybio presenoldeb sŵn a ddosberthir yn normal ar hap. Beth i'w wneud mewn sefyllfa o'r fath? Ar gyfer yr achos hwn mewn mathemateg mae ac fe'i defnyddir yn eang . Yn fyr, mae ei hanfod yn gorwedd yn y dewis a'i huchafiaeth ddilynol.
Rydym yn dychwelyd i adfer perthynas llinol o ddata gyda sŵn arferol. Sylwch mai'r berthynas llinol dybiedig yw'r disgwyliad mathemategol dosbarthiad arferol presennol. Ar yr un pryd, mae'r tebygolrwydd bod yn cymryd rhyw werth neu'i gilydd, yn amodol ar bresenoldeb pethau gweladwy , fel a ganlyn:
Gadewch i ni yn awr amnewid yn lle и Y newidynnau sydd eu hangen arnom yw:
Y cyfan sydd ar ôl yw dod o hyd i'r fector , lle mae'r tebygolrwydd hwn yn uchaf. I wneud y mwyaf o swyddogaeth o'r fath, mae'n gyfleus cymryd logarithm ohono yn gyntaf (bydd logarithm y swyddogaeth yn cyrraedd uchafswm ar yr un pwynt â'r swyddogaeth ei hun):
Sydd, yn ei dro, yn dibynnu ar leihau'r swyddogaeth ganlynol:
Gyda llaw, gelwir hyn yn ddull . Yn aml, caiff yr holl ystyriaethau uchod eu hepgor a defnyddir y dull hwn yn syml.
QR dadelfeniad
Gellir canfod lleiafswm y ffwythiant uchod trwy ddarganfod y pwynt lle mae graddiant y ffwythiant hwn yn sero. A bydd y graddiant yn cael ei ysgrifennu fel a ganlyn:
yn ddull matrics ar gyfer datrys y broblem lleihau a ddefnyddir yn y dull sgwariau lleiaf. Yn hyn o beth, rydym yn ailysgrifennu'r hafaliad ar ffurf matrics:
Felly rydym yn dadelfennu'r matrics i matricsau и a pherfformio cyfres o drawsnewidiadau (ni fydd yr algorithm dadelfennu QR ei hun yn cael ei ystyried yma, dim ond ei ddefnydd mewn perthynas â'r dasg dan sylw):
matrics yn orthogonal. Mae hyn yn ein galluogi i gael gwared ar y gwaith :
Ac os byddwch yn cymryd lle ar , yna bydd yn gweithio allan . O ystyried hynny yn fatrics trionglog uchaf, mae'n edrych fel hyn:
Gellir datrys hyn gan ddefnyddio'r dull amnewid. Elfen wedi ei leoli fel , elfen flaenorol wedi ei leoli fel ac yn y blaen.
Mae'n werth nodi yma bod cymhlethdod yr algorithm canlyniadol oherwydd y defnydd o ddadelfennu QR yn hafal i . Ar ben hynny, er gwaethaf y ffaith bod gweithrediad lluosi'r matrics yn gyfochrog yn dda, nid yw'n bosibl ysgrifennu fersiwn ddosbarthedig effeithiol o'r algorithm hwn.
Disgyniad Graddfa
Wrth siarad am leihau swyddogaeth, mae bob amser yn werth cofio'r dull o ddisgyn graddiant (stochastig). Mae hwn yn ddull lleihau syml ac effeithiol sy'n seiliedig ar gyfrifo graddiant ffwythiant ar bwynt yn ailadroddus ac yna ei symud i'r cyfeiriad gyferbyn â'r graddiant. Mae pob cam o'r fath yn dod â'r ateb yn nes at y lleiafswm. Mae'r graddiant yn dal i edrych yr un fath:
Mae'r dull hwn hefyd wedi'i gyfochrog a'i ddosbarthu'n dda oherwydd priodweddau llinellol y gweithredwr graddiant. Sylwch fod termau annibynnol o dan yr arwydd swm yn y fformiwla uchod. Mewn geiriau eraill, gallwn gyfrifo'r graddiant yn annibynnol ar gyfer pob mynegrif o'r cyntaf i , yn gyfochrog â hyn, cyfrifwch y graddiant ar gyfer mynegeion gyda i . Yna ychwanegwch y graddiannau canlyniadol. Bydd canlyniad yr ychwanegiad yr un fath â phe baem yn cyfrifo'r graddiant ar gyfer mynegeion ar unwaith o'r cyntaf i . Felly, os dosberthir y data rhwng sawl darn o ddata, gellir cyfrifo'r graddiant yn annibynnol ar bob darn, ac yna gellir crynhoi canlyniadau'r cyfrifiadau hyn i gael y canlyniad terfynol:
O safbwynt gweithredu, mae hyn yn cyd-fynd â'r patrwm . Ar bob cam o ddisgyniad graddiant, anfonir tasg i bob nod data i gyfrifo'r graddiant, yna cesglir y graddiannau a gyfrifwyd gyda'i gilydd, a defnyddir canlyniad eu swm i wella'r canlyniad.
Er gwaethaf rhwyddineb gweithredu a'r gallu i weithredu yn y patrwm MapReduce, mae anfanteision i ddisgyniad graddiant hefyd. Yn benodol, mae nifer y camau sydd eu hangen i gyflawni cydgyfeiriant yn sylweddol uwch o gymharu â dulliau eraill mwy arbenigol.
LSQR
yn ddull arall ar gyfer datrys y broblem, sy'n addas ar gyfer adfer atchweliad llinol ac ar gyfer datrys systemau hafaliadau llinol. Ei brif nodwedd yw ei fod yn cyfuno manteision dulliau matrics a dull ailadroddus. Gellir dod o hyd i weithrediad y dull hwn yn y ddwy lyfrgell , ac yn . Ni roddir disgrifiad o'r dull hwn yma (mae i'w weld yn yr erthygl ). Yn lle hynny, dangosir dull gweithredu i addasu LSQR i gyflawni mewn amgylchedd gwasgaredig.
Mae'r dull LSQR yn seiliedig ar . Mae hon yn weithdrefn ailadroddus, gyda phob iteriad yn cynnwys y camau canlynol:
Ond os tybiwn fod y matrics wedi'i rannu'n llorweddol, yna gellir cynrychioli pob iteriad fel dau gam MapReduce. Yn y modd hwn, mae'n bosibl lleihau trosglwyddiadau data yn ystod pob iteriad (dim ond fectorau sydd â hyd sy'n hafal i nifer yr anhysbys):
Y dull hwn a ddefnyddir wrth weithredu atchweliad llinol yn .
Casgliad
Mae yna lawer o algorithmau adfer atchweliad llinol, ond ni ellir cymhwyso pob un ohonynt ym mhob cyflwr. Felly mae dadelfennu QR yn ardderchog ar gyfer datrysiad cywir ar setiau data bach. Mae disgyniad graddiant yn syml i'w weithredu ac yn caniatáu ichi ddod o hyd i ateb bras yn gyflym. Ac mae LSQR yn cyfuno priodweddau gorau'r ddau algorithm blaenorol, gan y gellir ei ddosbarthu, yn cydgyfeirio'n gyflymach o'i gymharu â disgyniad graddiant, ac mae hefyd yn caniatáu atal yr algorithm yn gynnar, yn wahanol i ddadelfennu QR, i ddod o hyd i ateb bras.
Ffynhonnell: hab.com