Zdroj:
Lineárna regresia je jedným zo základných algoritmov pre mnohé oblasti súvisiace s analýzou údajov. Dôvod je zrejmý. Ide o veľmi jednoduchý a zrozumiteľný algoritmus, ktorý prispel k jeho širokému používaniu už desiatky, ak nie stovky rokov. Myšlienka je taká, že predpokladáme lineárnu závislosť jednej premennej od množiny iných premenných a potom sa pokúsime túto závislosť obnoviť.
Ale tento článok nie je o použití lineárnej regresie na riešenie praktických problémov. Tu zvážime zaujímavé vlastnosti implementácie distribuovaných algoritmov na jeho obnovu, s ktorými sme sa stretli pri písaní modulu strojového učenia v . Malá základná matematika, strojové učenie a distribuované výpočty vám môžu pomôcť zistiť, ako vykonávať lineárnu regresiu, aj keď sú vaše údaje distribuované medzi tisíckami uzlov.
o čom to hovoríme?
Stojíme pred úlohou obnoviť lineárnu závislosť. Ako vstupné údaje sa uvádza množina vektorov údajne nezávislých premenných, z ktorých každá je spojená s určitou hodnotou závislej premennej. Tieto údaje môžu byť reprezentované vo forme dvoch matíc:
Teraz, keďže závislosť je predpokladaná a navyše lineárna, zapíšeme náš predpoklad vo forme súčinu matíc (pre zjednodušenie záznamu sa tu a nižšie predpokladá, že voľný člen rovnice je skrytý za a posledný stĺpec matice obsahuje jednotky):
Znie to dosť ako systém lineárnych rovníc, však? Zdá sa, ale s najväčšou pravdepodobnosťou nebudú žiadne riešenia takéhoto systému rovníc. Dôvodom je šum, ktorý je prítomný takmer vo všetkých skutočných údajoch. Ďalším dôvodom môže byť absencia lineárnej závislosti ako takej, proti ktorej sa dá bojovať zavedením ďalších premenných, ktoré nelineárne závisia od pôvodných. Zvážte nasledujúci príklad:
Zdroj:
Toto je jednoduchý príklad lineárnej regresie, ktorý ukazuje vzťah jednej premennej (pozdĺž osi ) z inej premennej (pozdĺž osi ). Aby systém lineárnych rovníc zodpovedajúci tomuto príkladu mal riešenie, musia všetky body ležať presne na tej istej priamke. Ale to nie je pravda. Ale neležia na rovnakej priamke práve kvôli šumu (alebo preto, že predpoklad lineárneho vzťahu bol chybný). Na obnovenie lineárneho vzťahu z reálnych údajov je teda zvyčajne potrebné zaviesť ešte jeden predpoklad: vstupné údaje obsahujú šum a tento šum má . Môžete urobiť predpoklady o iných typoch rozloženia hluku, ale vo veľkej väčšine prípadov sa uvažuje o normálnom rozdelení, o ktorom sa bude ďalej diskutovať.
Metóda maximálnej pravdepodobnosti
Predpokladali sme teda prítomnosť náhodného normálne rozloženého šumu. Čo robiť v takejto situácii? Pre tento prípad v matematike existuje a je široko používaný . Jeho podstata skrátka spočíva vo výbere a jeho následná maximalizácia.
Vraciame sa k obnoveniu lineárneho vzťahu z údajov s normálnym šumom. Všimnite si, že predpokladaný lineárny vzťah je matematickým očakávaním existujúce normálne rozdelenie. Zároveň pravdepodobnosť, že nadobúda jednu alebo druhú hodnotu v závislosti od prítomnosti pozorovateľných prvkov , nasledovne:
Teraz namiesto toho nahraďme и Premenné, ktoré potrebujeme, sú:
Zostáva len nájsť vektor , pri ktorej je táto pravdepodobnosť maximálna. Na maximalizáciu takejto funkcie je vhodné najprv jej logaritmus (logaritmus funkcie dosiahne maximum v rovnakom bode ako samotná funkcia):
Čo zase vedie k minimalizácii nasledujúcej funkcie:
Mimochodom, toto sa nazýva metóda . Často sú všetky vyššie uvedené úvahy vynechané a táto metóda sa jednoducho používa.
QR rozklad
Minimum vyššie uvedenej funkcie možno nájsť nájdením bodu, v ktorom je gradient tejto funkcie nulový. A gradient bude napísaný takto:
je maticová metóda na riešenie úlohy minimalizácie používaná v metóde najmenších štvorcov. V tomto ohľade prepíšeme rovnicu do maticového tvaru:
Takže rozložíme maticu do matrík и a vykonajte sériu transformácií (samotný algoritmus rozkladu QR sa tu nebude brať do úvahy, iba jeho použitie vo vzťahu k danej úlohe):
matice je ortogonálny. To nám umožňuje zbaviť sa práce :
A ak vymeníte na , potom to vyjde . Zvažujem to je horná trojuholníková matica, vyzerá takto:
Dá sa to vyriešiť pomocou substitučnej metódy. Element sa nachádza ako , predchádzajúci prvok sa nachádza ako a tak ďalej.
Tu stojí za zmienku, že zložitosť výsledného algoritmu v dôsledku použitia QR rozkladu sa rovná . Navyše, napriek tomu, že operácia násobenia matíc je dobre paralelizovaná, nie je možné napísať efektívnu distribuovanú verziu tohto algoritmu.
Gradientný zostup
Keď hovoríme o minimalizácii funkcie, vždy stojí za to pamätať na metódu (stochastického) gradientového zostupu. Ide o jednoduchú a efektívnu metódu minimalizácie založenú na iteratívnom výpočte gradientu funkcie v bode a jeho následnom posunutí v smere opačnom k gradientu. Každý takýto krok približuje riešenie k minimu. Gradient vyzerá stále rovnako:
Táto metóda je tiež dobre paralelizovaná a distribuovaná vďaka lineárnym vlastnostiam gradientového operátora. Všimnite si, že vo vyššie uvedenom vzorci sú pod znakom súčtu nezávislé pojmy. Inými slovami, gradient môžeme vypočítať nezávisle pre všetky indexy od prvého do , súbežne s tým vypočítajte gradient pre indexy s na . Potom pridajte výsledné prechody. Výsledok sčítania bude rovnaký, ako keby sme hneď vypočítali gradient pre indexy od prvého do . Ak sú teda údaje rozdelené medzi niekoľko údajov, gradient sa môže vypočítať nezávisle pre každý kus a potom sa výsledky týchto výpočtov môžu sčítať, aby sa získal konečný výsledok:
Z hľadiska implementácie to zodpovedá paradigme . Pri každom kroku zostupu gradientu sa každému dátovému uzlu odošle úloha na výpočet gradientu, potom sa vypočítané gradienty zhromaždia a výsledok ich súčtu sa použije na zlepšenie výsledku.
Napriek ľahkej implementácii a schopnosti vykonávať v paradigme MapReduce má gradientný zostup aj svoje nevýhody. Najmä počet krokov potrebných na dosiahnutie konvergencie je výrazne vyšší v porovnaní s inými špecializovanejšími metódami.
LSQR
je ďalšou metódou riešenia úlohy, ktorá je vhodná ako na obnovu lineárnej regresie, tak aj na riešenie sústav lineárnych rovníc. Jeho hlavnou črtou je, že kombinuje výhody maticových metód a iteračného prístupu. Implementácie tejto metódy možno nájsť v oboch knižniciach a v . Popis tejto metódy tu nebude uvedený (nájdete ho v článku ). Namiesto toho bude demonštrovaný prístup na prispôsobenie LSQR na vykonávanie v distribuovanom prostredí.
Metóda LSQR je založená na . Ide o iteratívny postup, pričom každá iterácia pozostáva z nasledujúcich krokov:
Ale ak predpokladáme, že matica je horizontálne rozdelená, potom každá iterácia môže byť reprezentovaná ako dva kroky MapReduce. Týmto spôsobom je možné minimalizovať prenosy dát počas každej iterácie (iba vektory s dĺžkou rovnajúcou sa počtu neznámych):
Práve tento prístup sa používa pri implementácii lineárnej regresie v .
Záver
Existuje mnoho algoritmov obnovy lineárnej regresie, ale nie všetky sa dajú použiť vo všetkých podmienkach. Rozklad QR je teda vynikajúci na presné riešenie malých súborov údajov. Gradientný zostup je jednoduchý na implementáciu a umožňuje vám rýchlo nájsť približné riešenie. A LSQR kombinuje najlepšie vlastnosti predchádzajúcich dvoch algoritmov, pretože môže byť distribuovaný, konverguje rýchlejšie v porovnaní s gradientovým zostupom a tiež umožňuje skoré zastavenie algoritmu, na rozdiel od rozkladu QR, s cieľom nájsť približné riešenie.
Zdroj: hab.com