Foinse:
Tá aischéimniú líneach ar cheann de na halgartaim bhunúsacha do go leor réimsí a bhaineann le hanailís sonraí. Is léir an chúis atá leis seo. Is algartam an-simplí sothuigthe é seo, a chuidigh lena úsáid fhorleathan le go leor blianta, más rud é nach na céadta bliain. Is é an smaoineamh go nglacfaimid le spleáchas líneach d'athróg amháin ar shraith athróg eile, agus ansin déanaimid iarracht an spleáchas seo a athbhunú.
Ach ní bhaineann an t-alt seo le aischéimniú líneach a úsáid chun fadhbanna praiticiúla a réiteach. Anseo beimid ag smaoineamh ar ghnéithe suimiúla a bhaineann le cur i bhfeidhm na n-halgartaim dáilte chun é a ghnóthú, ar tháinig muid trasna orthu agus modúl meaisínfhoghlama á scríobh . Is féidir le beagán matamaitice bunúsach, meaisínfhoghlama agus ríomhaireachta dáilte cabhrú leat a dhéanamh amach conas aischéimniú líneach a dhéanamh fiú nuair a dhéantar do shonraí a dháileadh ar na mílte nóid.
Cad faoi a bhfuilimid ag caint?
Tá sé de chúram orainn spleáchas líneach a athbhunú. Mar shonraí ionchuir, tugtar sraith veicteoirí d'athróga neamhspleácha, a bhfuil baint ag gach ceann acu le luach áirithe den athróg spleách. Is féidir na sonraí seo a léiriú i bhfoirm dhá mhaitrís:
Anois, ós rud é go nglactar leis an spleáchas, agus, ina theannta sin, líneach, scríobhfaimid ár mbonn tuisceana i bhfoirm táirge maitrísí (chun an taifeadadh a shimpliú, anseo agus thíos glactar leis go bhfuil téarma saor na cothromóide i bhfolach taobh thiar de. , agus an colún deiridh den mhaitrís ina bhfuil aonaid):
Is cosúil go mór le córas cothromóidí líneacha, nach ea? Dealraíonn sé, ach is dócha nach mbeidh aon réitigh ar a leithéid de chóras cothromóidí. Is é an chúis atá leis seo ná torann, atá i láthair i mbeagnach aon sonraí fíor. Cúis eile a d’fhéadfadh a bheith ann ná an easpa spleáchais líneach mar sin, ar féidir é a chomhrac trí athróga breise a thabhairt isteach a bhraitheann go neamhlíne ar na cinn bhunaidh. Smaoinigh ar an sampla seo a leanas:
Foinse:
Is sampla simplí é seo d’aischéimniú líneach a thaispeánann an gaol atá ag athróg amháin (ar feadh na haise ) ó athróg eile (ar feadh na haise ). Ionas go mbeidh réiteach ag córas na gcothromóidí líneacha a fhreagraíonn don sampla seo, ní mór do gach pointe a bheith suite go díreach ar an líne dhíreach chéanna. Ach níl sé sin fíor. Ach ní luíonn siad ar an líne dhíreach chéanna go beacht mar gheall ar thorann (nó toisc go raibh an toimhde de ghaol líneach earráideach). Mar sin, chun caidreamh líneach a athbhunú ó fhíorshonraí, is gá de ghnáth toimhde amháin eile a thabhairt isteach: bíonn torann sna sonraí ionchuir agus tá an torann sin ag baint leis. . Is féidir leat toimhdí a dhéanamh faoi chineálacha eile dáileadh torainn, ach i bhformhór mór na gcásanna is é an gnáthdháileadh a mheastar, a phléifear tuilleadh.
Modh dóchúlacht uasta
Mar sin, ghlacamar leis go raibh torann randamach arna dháileadh de ghnáth. Cad atá le déanamh i gcás den sórt sin? Sa chás seo sa mhatamaitic tá agus úsáidtear go forleathan . I mbeagán focal, luíonn a bunúsach sa rogha agus a uasmhéadú ina dhiaidh sin.
Fillimid ar chaidreamh líneach a athbhunú ó shonraí le gnáththorann. Tabhair faoi deara gurb é an gaol líneach measta an ionchas matamaiticiúil dáileadh gnáth atá ann cheana féin. Ag an am céanna, an dóchúlacht go glacann sé le luach amháin nó luach eile, faoi réir láithreacht nithe inbhraite , mar seo a leanas:
Lig dúinn anois ionadach и Is iad na hathróga a theastaíonn uainn:
Níl fágtha ach an veicteoir a aimsiú , ag a bhfuil an dóchúlacht seo uasta. Chun feidhm den sórt sin a uasmhéadú, tá sé áisiúil logartamach a ghlacadh ar dtús (sroichfidh logarithm na feidhme uasmhéid ag an bpointe céanna leis an bhfeidhm féin):
Rud a thagann síos, ina dhiaidh sin, ar an bhfeidhm seo a leanas a íoslaghdú:
Dála an scéil, tugtar modh ar seo . Go minic fágtar na cúinsí thuas ar lár agus úsáidtear an modh seo go simplí.
QR lobhadh
Is féidir íosmhéid na feidhme thuas a fháil ach an pointe ag a bhfuil grádán na feidhme seo ná nialas a fháil. Agus scríobhfar an grádán mar seo a leanas:
is modh maitrís é chun an fhadhb íoslaghdaithe a úsáidtear sa mhodh is lú cearnóga a réiteach. Maidir leis seo, déanaimid an chothromóid a athscríobh i bhfoirm maitrís:
Mar sin déanaimid an maitrís a dhianscaoileadh go maitrísí и agus sraith claochluithe a dhéanamh (ní dhéanfar an t-algartam dianscaoilte QR féin a mheas anseo, ach a úsáid i ndáil leis an tasc atá ar láimh):
maitrís is orthogonal. Ligeann sé seo dúinn fáil réidh leis an obair :
Agus má tá tú in ionad ar , ansin beidh sé ag obair amach . Ag cur san áireamh sin is maitrís triantánach uachtarach é, tá an chuma air seo:
Is féidir é seo a réiteach ag baint úsáide as an modh ionadaíochta. Eilimint suite mar , eilimint roimhe seo suite mar agus mar sin de.
Is fiú a thabhairt faoi deara anseo go bhfuil castacht an algartam mar thoradh air mar gheall ar úsáid a bhaint as dianscaoileadh QR comhionann . Thairis sin, in ainneoin go bhfuil an oibríocht iolraithe maitrís comhthreomhar go maith, ní féidir leagan dáilte éifeachtach den algartam seo a scríobh.
Ghinealach Grádáin
Agus tú ag caint faoi fheidhm a íoslaghdú, is fiú cuimhneamh i gcónaí ar an modh chun grádán a shliocht (stochastic). Is modh íoslaghdaithe simplí agus éifeachtach é seo atá bunaithe ar ghrádán feidhme ag pointe a ríomh go atriallach agus ansin é a aistriú sa treo eile leis an ngrádán. Tugann gach céim den sórt sin an réiteach níos gaire don íosmhéid. Breathnaíonn an grádán mar an gcéanna fós:
Tá an modh seo comhthreomhar agus dáileadh go maith freisin mar gheall ar airíonna líneacha an oibreora grádáin. Tabhair faoi deara go bhfuil téarmaí neamhspleácha sa bhfoirmle thuas faoin gcomhartha suime. I bhfocail eile, is féidir linn an grádán a ríomh go neamhspleách do gach innéacs ón gcéad go , i gcomhthreo leis seo, ríomh an grádán le haghaidh innéacsanna le до . Ansin cuir na grádáin mar thoradh air. Beidh toradh an tsuimithe mar an gcéanna agus dá ndéanfaimis an grádán d’innéacsanna a ríomh láithreach ón gcéad go dtí . Mar sin, má dhéantar na sonraí a dháileadh ar roinnt píosaí sonraí, is féidir an grádán a ríomh go neamhspleách ar gach píosa, agus ansin is féidir torthaí na ríomhanna seo a achoimriú chun an toradh deiridh a fháil:
Ó thaobh an chur chun feidhme de, oireann sé seo don paraidím . Ag gach céim de shliocht grádáin, seoltar tasc chuig gach nód sonraí chun an grádán a ríomh, ansin bailítear na grádáin ríofa le chéile, agus úsáidtear toradh a suime chun an toradh a fheabhsú.
In ainneoin a éascaíocht le cur i bhfeidhm agus an cumas forghníomhú i bparaidím MapReduce, tá a míbhuntáistí ag baint le sliocht an ghrádáin freisin. Go háirithe, tá líon na gcéimeanna is gá chun cóineasú a bhaint amach i bhfad níos airde i gcomparáid le modhanna eile níos speisialaithe.
LSQR
Is modh eile é chun an fhadhb a réiteach, atá oiriúnach chun aischéimniú líneach a athbhunú agus chun córais cothromóidí líneacha a réiteach. Is í an phríomhghné atá aige ná buntáistí modhanna maitrís agus cur chuige atriallach a chomhcheangal. Is féidir cur i bhfeidhm an mhodha seo a fháil sa dá leabharlann agus i . Ní thabharfar cur síos ar an modh seo anseo (is féidir é a fháil san alt ). Ina áit sin, léireofar cur chuige chun LSQR a oiriúnú don fhorghníomhú i dtimpeallacht dháilte.
Tá an modh LSQR bunaithe ar . Is nós imeachta atriallach é seo, agus tá na céimeanna seo a leanas i ngach atriall:
Ach má glacaimid go bhfuil an maitrís roinnte go cothrománach, ansin is féidir gach atriall a léiriú mar dhá chéim MapReduce. Ar an mbealach seo, is féidir aistrithe sonraí a íoslaghdú le linn gach atriallta (veicteora amháin a bhfuil fad comhionann leis an líon anaithnid):
Is é an cur chuige seo a úsáidtear agus aischéimniú líneach á chur i bhfeidhm i .
Conclúid
Tá go leor halgartaim aisghabhála aischéimniúcháin líneach ann, ach ní féidir gach ceann acu a chur i bhfeidhm i ngach coinníoll. Mar sin tá dianscaoileadh QR den scoth le haghaidh réiteach cruinn ar thacair bheaga sonraí. Tá sé simplí a chur i bhfeidhm ó shliocht grádán agus ligeann sé duit teacht ar réiteach gar go tapa. Agus comhcheanglaíonn LSQR na hairíonna is fearr den dá algartam roimhe seo, toisc gur féidir é a dháileadh, coinbhéirsíonn sé níos tapúla i gcomparáid le shliocht grádán, agus ceadaíonn sé freisin stop a chur leis an algartam go luath, murab ionann agus dianscaoileadh QR, chun teacht ar réiteach garbh.
Foinse: will.com