ProHoster > Blogs > Administrācija > Lineārā regresija un metodes tās atgūŔanai

Lineārā regresija un metodes tās atgūŔanai

Lineārā regresija un metodes tās atgūŔanai
Avots: xkcd

Lineārā regresija ir viens no pamata algoritmiem daudzās ar datu analÄ«zi saistÄ«tās jomās. Iemesls tam ir acÄ«mredzams. Å is ir ļoti vienkārÅ”s un saprotams algoritms, kas ir veicinājis tā plaÅ”o izmantoÅ”anu daudzus desmitus, ja ne simtus gadu. Ideja ir tāda, ka mēs pieņemam viena mainÄ«gā lineāru atkarÄ«bu no citu mainÄ«go lielumu kopas un pēc tam mēģinām atjaunot Å”o atkarÄ«bu.

Bet Å”is raksts nav par lineārās regresijas izmantoÅ”anu praktisku problēmu risināŔanai. Å eit mēs apsvērsim interesantas tās atkopÅ”anas sadalÄ«to algoritmu ievieÅ”anas iezÄ«mes, ar kurām mēs saskārāmies, rakstot maŔīnmācÄ«Å”anās moduli Apache Ignite. Nedaudz pamata matemātikas, maŔīnmācÄ«Å”anās un izkliedētās skaitļoÅ”anas var palÄ«dzēt izdomāt, kā veikt lineāro regresiju pat tad, ja dati ir sadalÄ«ti tÅ«kstoÅ”iem mezglu.

Par ko mēs runājam?

Mēs saskaramies ar uzdevumu atjaunot lineāro atkarību. Kā ievaddati tiek dota it kā neatkarīgu mainīgo vektoru kopa, no kuriem katrs ir saistīts ar noteiktu atkarīgā mainīgā lielumu. Šos datus var attēlot divu matricu veidā:

Lineārā regresija un metodes tās atgūŔanai

Tagad, tā kā atkarÄ«ba ir pieņemta un turklāt lineāra, mēs rakstÄ«sim savu pieņēmumu matricu reizinājuma formā (lai vienkārÅ”otu ierakstu, Å”eit un zemāk tiek pieņemts, ka vienādojuma brÄ«vais termins ir paslēpts aiz Lineārā regresija un metodes tās atgÅ«Å”anai, un matricas pēdējā kolonna Lineārā regresija un metodes tās atgÅ«Å”anai satur vienÄ«bas):

Lineārā regresija un metodes tās atgūŔanai

Izklausās pēc lineāru vienādojumu sistēmas, vai ne? Å Ä·iet, bet visdrÄ«zāk Ŕādai vienādojumu sistēmai risinājumu nebÅ«s. Iemesls tam ir troksnis, kas ir gandrÄ«z visos reālos datos. Vēl viens iemesls var bÅ«t lineāras atkarÄ«bas kā tādas neesamÄ«ba, ko var apkarot, ievieÅ”ot papildu mainÄ«gos, kas nelineāri ir atkarÄ«gi no sākotnējiem. Apsveriet Ŕādu piemēru:
Lineārā regresija un metodes tās atgūŔanai
Avots: Wikipedia

Å is ir vienkārÅ”s lineārās regresijas piemērs, kas parāda viena mainÄ«gā attiecÄ«bas (gar asi Lineārā regresija un metodes tās atgÅ«Å”anai) no cita mainÄ«gā (gar asi Lineārā regresija un metodes tās atgÅ«Å”anai). Lai Å”im piemēram atbilstoŔā lineāro vienādojumu sistēmai bÅ«tu risinājums, visiem punktiem jāatrodas tieÅ”i uz vienas taisnes. Bet tā nav taisnÄ«ba. Bet tie neatrodas uz vienas taisnes tieÅ”i trokŔņa dēļ (vai tāpēc, ka pieņēmums par lineāru sakarÄ«bu bija kļūdains). Tādējādi, lai atjaunotu lineāru sakarÄ«bu no reāliem datiem, parasti ir nepiecieÅ”ams ieviest vēl vienu pieņēmumu: ievades datos ir troksnis un Å”is troksnis ir normālais sadalÄ«jums. JÅ«s varat izdarÄ«t pieņēmumus par citiem trokŔņu sadalÄ«juma veidiem, taču lielākajā daļā gadÄ«jumu tiek ņemts vērā normālais sadalÄ«jums, kas tiks apspriests tālāk.

Maksimālās varbūtības metode

Tātad, mēs pieņēmām nejauÅ”a, normāli sadalÄ«ta trokŔņa klātbÅ«tni. Ko darÄ«t Ŕādā situācijā? Å im gadÄ«jumam matemātikā ir un tiek plaÅ”i izmantots maksimālās varbÅ«tÄ«bas metode. ÄŖsāk sakot, tā bÅ«tÄ«ba ir izvēlē varbÅ«tÄ«bas funkcijas un tā turpmākā maksimizÄ“Å”ana.

Mēs atgriežamies pie lineāras attiecÄ«bas atjaunoÅ”anas no datiem ar normālu troksni. Ņemiet vērā, ka pieņemtā lineārā sakarÄ«ba ir matemātiskā cerÄ«ba Lineārā regresija un metodes tās atgÅ«Å”anai esoÅ”ais normālais sadalÄ«jums. Tajā paŔā laikā varbÅ«tÄ«ba, ka Lineārā regresija un metodes tās atgÅ«Å”anai iegÅ«st vienu vai otru vērtÄ«bu atkarÄ«bā no novērojamo elementu klātbÅ«tnes Lineārā regresija un metodes tās atgÅ«Å”anai, sekojoÅ”i:

Lineārā regresija un metodes tās atgūŔanai

Ä»aujiet mums tagad aizstāt Lineārā regresija un metodes tās atgÅ«Å”anai Šø Lineārā regresija un metodes tās atgÅ«Å”anai Mums nepiecieÅ”amie mainÄ«gie ir:

Lineārā regresija un metodes tās atgūŔanai

Atliek tikai atrast vektoru Lineārā regresija un metodes tās atgÅ«Å”anai, pie kura Ŕī varbÅ«tÄ«ba ir maksimālā. Lai maksimizētu Ŕādu funkciju, ir ērti vispirms ņemt tās logaritmu (funkcijas logaritms sasniegs maksimumu tajā paŔā punktā, kur pati funkcija):

Lineārā regresija un metodes tās atgūŔanai

Tas savukārt nozÄ«mē Ŕādas funkcijas samazināŔanu:

Lineārā regresija un metodes tās atgūŔanai

Starp citu, to sauc par metodi mazākie kvadrāti. Bieži vien visi iepriekÅ” minētie apsvērumi tiek izlaisti, un Ŕī metode tiek vienkārÅ”i izmantota.

QR sadalīŔanās

IepriekÅ” minētās funkcijas minimumu var atrast, atrodot punktu, kurā Ŕīs funkcijas gradients ir nulle. Un gradients tiks uzrakstÄ«ts Ŕādi:

Lineārā regresija un metodes tās atgūŔanai

QR sadalÄ«Å”anās ir matricas metode minimizācijas problēmas risināŔanai, ko izmanto mazāko kvadrātu metodē. Å ajā sakarā mēs pārrakstām vienādojumu matricas formā:

Lineārā regresija un metodes tās atgūŔanai

Tātad mēs sadalām matricu Lineārā regresija un metodes tās atgÅ«Å”anai uz matricām Lineārā regresija un metodes tās atgÅ«Å”anai Šø Lineārā regresija un metodes tās atgÅ«Å”anai un veikt virkni transformāciju (pats QR dekompozÄ«cijas algoritms Å”eit netiks ņemts vērā, tikai tā izmantoÅ”ana saistÄ«bā ar konkrēto uzdevumu):

Lineārā regresija un metodes tās atgūŔanai

Matrica Lineārā regresija un metodes tās atgūŔanai ir ortogonāls. Tas ļauj mums atbrīvoties no darba Lineārā regresija un metodes tās atgūŔanai:

Lineārā regresija un metodes tās atgūŔanai

Un, ja jÅ«s nomaināt Lineārā regresija un metodes tās atgÅ«Å”anai par Lineārā regresija un metodes tās atgÅ«Å”anai, tad izdosies Lineārā regresija un metodes tās atgÅ«Å”anai. Ņemot vērā, ka Lineārā regresija un metodes tās atgÅ«Å”anai ir augŔējā trÄ«sstÅ«rveida matrica, tā izskatās Ŕādi:

Lineārā regresija un metodes tās atgūŔanai

To var atrisināt, izmantojot aizstāŔanas metodi. Elements Lineārā regresija un metodes tās atgÅ«Å”anai atrodas kā Lineārā regresija un metodes tās atgÅ«Å”anai, iepriekŔējais elements Lineārā regresija un metodes tās atgÅ«Å”anai atrodas kā Lineārā regresija un metodes tās atgÅ«Å”anai un tā tālāk.

Å eit ir vērts atzÄ«mēt, ka iegÅ«tā algoritma sarežģītÄ«ba QR dekompozÄ«cijas izmantoÅ”anas dēļ ir vienāda ar Lineārā regresija un metodes tās atgÅ«Å”anai. Turklāt, neskatoties uz to, ka matricas reizināŔanas darbÄ«ba ir labi paralēla, nav iespējams uzrakstÄ«t efektÄ«vu Ŕī algoritma sadalÄ«to versiju.

Gradienta nolaiŔanās

Runājot par funkcijas minimizÄ“Å”anu, vienmēr ir vērts atcerēties (stohastiskā) gradienta nolaiÅ”anās metodi. Å Ä« ir vienkārÅ”a un efektÄ«va minimizÄ“Å”anas metode, kuras pamatā ir funkcijas gradienta iteratÄ«va aprēķināŔana punktā un pēc tam novirzÄ«Å”ana virzienā, kas ir pretējs gradientam. Katrs Ŕāds solis tuvina risinājumu minimumam. Gradients joprojām izskatās tāds pats:

Lineārā regresija un metodes tās atgūŔanai

Å Ä« metode ir arÄ« labi paralēla un sadalÄ«ta gradienta operatora lineāro Ä«paŔību dēļ. Ņemiet vērā, ka iepriekÅ” minētajā formulā zem summas zÄ«mes ir neatkarÄ«gi termini. Citiem vārdiem sakot, mēs varam neatkarÄ«gi aprēķināt gradientu visiem indeksiem Lineārā regresija un metodes tās atgÅ«Å”anai no pirmā lÄ«dz Lineārā regresija un metodes tās atgÅ«Å”anai, paralēli tam aprēķina gradientu indeksiem ar Lineārā regresija un metodes tās atgÅ«Å”anai lÄ«dz Lineārā regresija un metodes tās atgÅ«Å”anai. Pēc tam pievienojiet iegÅ«tos gradientus. SaskaitÄ«Å”anas rezultāts bÅ«s tāds pats kā tad, ja mēs uzreiz aprēķinātu indeksu gradientu no pirmā lÄ«dz Lineārā regresija un metodes tās atgÅ«Å”anai. Tādējādi, ja dati ir sadalÄ«ti starp vairākām datu vienÄ«bām, gradientu var aprēķināt neatkarÄ«gi no katras daļas, un pēc tam Å”o aprēķinu rezultātus var summēt, lai iegÅ«tu gala rezultātu:

Lineārā regresija un metodes tās atgūŔanai

No Ä«stenoÅ”anas viedokļa tas atbilst paradigmai MapReduce. Katrā gradienta nolaiÅ”anās posmā katram datu mezglam tiek nosÅ«tÄ«ts uzdevums, lai aprēķinātu gradientu, pēc tam aprēķinātie gradienti tiek apkopoti kopā, un to summas rezultāts tiek izmantots rezultāta uzlaboÅ”anai.

Neskatoties uz ievieÅ”anas vieglumu un spēju izpildÄ«t MapReduce paradigmā, gradienta nolaiÅ”anai ir arÄ« savi trÅ«kumi. Jo Ä«paÅ”i konverÄ£ences sasniegÅ”anai nepiecieÅ”amo darbÄ«bu skaits ir ievērojami lielāks salÄ«dzinājumā ar citām specializētākām metodēm.

LSQR

LSQR ir vēl viena problēmas risināŔanas metode, kas piemērota gan lineārās regresijas atjaunoÅ”anai, gan lineāro vienādojumu sistēmu risināŔanai. Tās galvenā iezÄ«me ir tā, ka tā apvieno matricas metožu priekÅ”rocÄ«bas un iteratÄ«vu pieeju. Å Ä«s metodes realizācijas iespējas ir atrodamas abās bibliotēkās SciPyun iekŔā MATLAB. Å Ä«s metodes apraksts Å”eit netiks sniegts (to var atrast rakstā LSQR: algoritms retiem lineāriem vienādojumiem un retajiem mazākajiem kvadrātiem). Tā vietā tiks demonstrēta pieeja, lai pielāgotu LSQR izpildei izplatÄ«tā vidē.

LSQR metode ir balstīta uz bidiagonalizācijas procedūra. Šī ir iteratīva procedūra, un katra iterācija sastāv no Ŕādām darbībām:
Lineārā regresija un metodes tās atgūŔanai

Bet, ja pieņemam, ka matrica Lineārā regresija un metodes tās atgÅ«Å”anai ir horizontāli sadalÄ«ts, tad katru iterāciju var attēlot kā divus MapReduce soļus. Tādā veidā ir iespējams minimizēt datu pārsÅ«tÄ«Å”anu katras iterācijas laikā (tikai vektori, kuru garums ir vienāds ar nezināmo skaitu):

Lineārā regresija un metodes tās atgūŔanai

Šī pieeja tiek izmantota, ievieŔot lineāro regresiju Apache Ignite ML.

Secinājums

Ir daudz lineārās regresijas atkopÅ”anas algoritmu, taču ne visus no tiem var izmantot visos apstākļos. Tātad QR dekompozÄ«cija ir lieliska precÄ«zam risinājumam mazās datu kopās. Gradienta nolaiÅ”anās ir vienkārÅ”i Ä«stenojama un ļauj ātri atrast aptuvenu risinājumu. Un LSQR apvieno abu iepriekŔējo algoritmu labākās Ä«paŔības, jo to var izplatÄ«t, saplÅ«st ātrāk, salÄ«dzinot ar gradienta nolaiÅ”anos, kā arÄ« ļauj agrÄ«ni apturēt algoritmu, atŔķirÄ«bā no QR dekompozÄ«cijas, lai atrastu aptuvenu risinājumu.

Avots: www.habr.com

Pievieno komentāru