Zdroj:
Lineární regrese je jedním ze základních algoritmů pro mnoho oblastí souvisejících s analýzou dat. Důvod je zřejmý. Jedná se o velmi jednoduchý a srozumitelný algoritmus, který přispěl k jeho širokému používání po mnoho desítek, ne-li stovek let. Myšlenka je taková, že předpokládáme lineární závislost jedné proměnné na množině jiných proměnných a poté se pokusíme tuto závislost obnovit.
Tento článek ale není o použití lineární regrese k řešení praktických problémů. Zde zvážíme zajímavé vlastnosti implementace distribuovaných algoritmů pro jeho obnovu, se kterými jsme se setkali při psaní modulu strojového učení v . Trochu základní matematiky, strojového učení a distribuovaného počítání vám může pomoci zjistit, jak provádět lineární regresi, i když jsou vaše data distribuována mezi tisíce uzlů.
O čem to je?
Stojíme před úkolem obnovit lineární závislost. Jako vstupní data je uvedena množina vektorů domněle nezávislých proměnných, z nichž každá je spojena s určitou hodnotou závislé proměnné. Tato data mohou být reprezentována ve formě dvou matic:
Nyní, protože je závislost předpokládána, a navíc lineární, zapíšeme náš předpoklad ve formě součinu matic (pro zjednodušení záznamu se zde a níže předpokládá, že volný člen rovnice je skrytý za a poslední sloupec matice obsahuje jednotky):
Zní to hodně jako systém lineárních rovnic, že? Zdá se, ale s největší pravděpodobností nebudou řešení takového systému rovnic. Důvodem je šum, který je přítomen téměř ve všech skutečných datech. Dalším důvodem může být absence lineární závislosti jako takové, proti které lze bojovat zavedením dalších proměnných, které nelineárně závisí na těch původních. Zvažte následující příklad:
Zdroj:
Toto je jednoduchý příklad lineární regrese, který ukazuje vztah jedné proměnné (podél osy ) z jiné proměnné (podél osy ). Aby systém lineárních rovnic odpovídající tomuto příkladu měl řešení, musí všechny body ležet přesně na stejné přímce. Ale to není pravda. Ale neleží na stejné přímce právě kvůli šumu (nebo protože předpoklad lineárního vztahu byl chybný). Aby bylo možné obnovit lineární vztah z reálných dat, je obvykle nutné zavést ještě jeden předpoklad: vstupní data obsahují šum a tento šum má . Můžete si udělat předpoklady o jiných typech rozložení hluku, ale v naprosté většině případů se uvažuje s normálním rozložením, o kterém bude řeč dále.
Metoda maximální pravděpodobnosti
Předpokládali jsme tedy přítomnost náhodného normálně rozloženého šumu. Co v takové situaci dělat? Pro tento případ v matematice existuje a je široce používán . Jeho podstata zkrátka spočívá ve výběru a jeho následná maximalizace.
Vracíme se k obnově lineárního vztahu z dat s normálním šumem. Všimněte si, že předpokládaný lineární vztah je matematickým očekáváním stávající normální distribuce. Přitom pravděpodobnost, že nabývá té či oné hodnoty, s výhradou přítomnosti pozorovatelných , jak následuje:
Nyní místo toho nahrajme и Potřebujeme tyto proměnné:
Zbývá jen najít vektor , při které je tato pravděpodobnost maximální. Chcete-li maximalizovat takovou funkci, je vhodné ji nejprve logaritmovat (logaritmus funkce dosáhne maxima ve stejném bodě jako funkce samotná):
Což zase vede k minimalizaci následující funkce:
Mimochodem, tomu se říká metoda . Často jsou všechny výše uvedené úvahy vynechány a tato metoda je jednoduše použita.
QR rozklad
Minimum výše uvedené funkce lze nalézt nalezením bodu, ve kterém je gradient této funkce nulový. A gradient bude zapsán následovně:
je maticová metoda pro řešení problému minimalizace používaná v metodě nejmenších čtverců. V tomto ohledu přepíšeme rovnici do maticového tvaru:
Rozložíme tedy matici na matrice и a proveďte řadu transformací (samotný algoritmus rozkladu QR zde nebude uvažován, pouze jeho použití ve vztahu k danému úkolu):
matice je ortogonální. To nám umožňuje zbavit se práce :
A pokud vyměníte na , tak to vyjde . Vezmeme-li v úvahu, že je horní trojúhelníková matice, vypadá takto:
To lze vyřešit pomocí substituční metody. Živel se nachází jako , předchozí prvek se nachází jako a tak dále.
Zde stojí za zmínku, že složitost výsledného algoritmu díky použití QR rozkladu je rovna . Navíc, přestože je operace násobení matic dobře paralelizována, není možné napsat efektivní distribuovanou verzi tohoto algoritmu.
Gradientní sestup
Když mluvíme o minimalizaci funkce, vždy stojí za to pamatovat na metodu (stochastického) gradientního sestupu. Jedná se o jednoduchou a efektivní minimalizační metodu založenou na iterativním výpočtu gradientu funkce v bodě a jeho následném posunutí v opačném směru, než je gradient. Každý takový krok přibližuje řešení k minimu. Gradient vypadá stále stejně:
Tato metoda je také dobře paralelizována a distribuována díky lineárním vlastnostem gradientového operátoru. Všimněte si, že ve výše uvedeném vzorci jsou pod znaménkem součtu nezávislé členy. Jinými slovy, gradient můžeme vypočítat nezávisle pro všechny indexy od prvního do , souběžně s tím vypočítejte gradient pro indexy s na . Poté přidejte výsledné přechody. Výsledek sčítání bude stejný, jako kdybychom hned spočítali gradient pro indexy od prvního do . Pokud jsou tedy data rozdělena mezi několik kusů dat, lze gradient vypočítat nezávisle na každém kusu a poté lze výsledky těchto výpočtů sečíst a získat konečný výsledek:
Z hlediska implementace to odpovídá paradigmatu . Při každém kroku sestupu gradientu je každému datovému uzlu odeslán úkol pro výpočet gradientu, poté se vypočítané gradienty shromáždí a výsledek jejich součtu se použije ke zlepšení výsledku.
Navzdory snadné implementaci a schopnosti provádět v paradigmatu MapReduce má sestup gradientu také své nevýhody. Zejména počet kroků potřebných k dosažení konvergence je výrazně vyšší ve srovnání s jinými specializovanějšími metodami.
LSQR
je další metoda řešení úlohy, která je vhodná jak pro obnovu lineární regrese, tak pro řešení soustav lineárních rovnic. Jeho hlavním rysem je, že kombinuje výhody maticových metod a iterativního přístupu. Implementace této metody lze nalézt v obou knihovnách a v . Popis této metody zde nebude uveden (naleznete jej v článku ). Místo toho bude demonstrován přístup k přizpůsobení LSQR provádění v distribuovaném prostředí.
Metoda LSQR je založena na . Jedná se o iterativní postup, přičemž každá iterace se skládá z následujících kroků:
Pokud ale předpokládáme, že matice je horizontálně rozdělena, pak lze každou iteraci reprezentovat jako dva kroky MapReduce. Tímto způsobem je možné minimalizovat přenosy dat během každé iterace (pouze vektory s délkou rovnou počtu neznámých):
Právě tento přístup se používá při implementaci lineární regrese .
Závěr
Existuje mnoho algoritmů obnovy lineární regrese, ale ne všechny lze použít za všech podmínek. Rozklad QR je tedy vynikající pro přesné řešení malých souborů dat. Gradient sestup je jednoduchý na implementaci a umožňuje rychle najít přibližné řešení. A LSQR kombinuje nejlepší vlastnosti předchozích dvou algoritmů, protože může být distribuován, konverguje rychleji ve srovnání s gradientním sestupem a také umožňuje včasné zastavení algoritmu, na rozdíl od rozkladu QR, za účelem nalezení přibližného řešení.
Zdroj: www.habr.com