logo-IBA Pokročilé neparametrické metody MARS - Multivariate Adaptive Regression Splines logo-IBA Pokročilé neparametrické metody logo-IBA Pokročilé neparametrické metody MARS - Multivariate Adaptive Regression Splines ¢ ¢Friedman (1991) ¢technika pro regresní problémy ¢na rozhraní mezi stromovou technikou a parametrickou regresí→zobecnění postupné (stepwise) lineární regrese ¢odstraňuje určité nedostatky binárních regresních stromů, především nespojitosti odhadnutých hodnot závisle proměnné ¢prediktory mohou být spojité i kategoriální ¢výsledkem metody je regresní rovnice → chybí stromová struktura a interpretace výsledků při velkém počtu proměnných může být obtížnější ¢k rozdělení pozorování závisle proměnné se nepoužívá konstanta, ale lineární aproximace ¢ logo-IBA Pokročilé neparametrické metody Spline- interpolace Interpolace - n body mohu proložit polynom (n -1) řádu - větší stupeň polynomu - oscilace mezi body daná množina bodů se aproximuje po částech = spline křivky logo-IBA Pokročilé neparametrické metody MARS (x - t)+ = (x - t), pokud x > t 0, jinak (t - x)+ = (t - x), pokud x < t 0, jinak Příklad funkce (x – 10)+ a (10 - x)+ Alternativní zápis:max(0, x − t) a max(0, t − x) Zrcadlový pár (Hastie et. al, 2009) mars t = 10 logo-IBA Pokročilé neparametrické metody ŷ = - 37 + 5.1x ŷ = 25 + 6.1max(0, x - 13) – 3.1max(0, 13 – x ) MARS - příklad Lineární regrese MARS logo-IBA Pokročilé neparametrické metody MARS x lineární regrese ¢Mějme regresní rovnici: ¢ ¢ ¢ ¢ ¢ ¢kde Y je závisle proměnná, X1,…, XM jsou prediktory ¢β0 je intercept a β1,…, βM regresní koeficienty ¢u jednorozměrné lineární regrese je k vyjádření závislosti Y na X použita přímka a koeficienty jsou odhadnuty metodou nejmenších čtverců 1. logo-IBA Pokročilé neparametrické metody MARS ¢předpokládejme model s jedním prediktorem a hodnotou uzlu t = 10, který můžeme zapsat pomocí dvou regresních rovnic: pro x > 10 pro x < 10 Rovnice můžeme vyjádřit ve tvaru: kde b0 ≡ β0, b1 ≡ β1 a b2 ≡ β2 logo-IBA Pokročilé neparametrické metody MARS – interakce proměnných ¢Stejně jako u lineární regrese lze i u metody MARS použít interakce proměnných ¢pro dva prediktory X1, X2: z čehož plyne: logo-IBA Pokročilé neparametrické metody MARS - interakce h(X1,X2) = (X1-x51)+ *(x72 – X2)+ (Hastie et. al, 2009) logo-IBA Pokročilé neparametrické metody MARS - příklad ozone = 25 + 3.1*max(0; temperature-85) -1.28*max(0; 85-temperature) -4.9*max(0; 13-wind) - 0.09*max(0; radiation-139) -0.049*max(0; radiation-112)*max(0; 13.21-wind) - % denní měření koncentrace ozonu, rychlosti větru, teploty vzduchu a intenzita slunečního záření v New Yorku logo-IBA Pokročilé neparametrické metody MARS ¢Regresní funkci pro MARS můžeme tedy vyjádřit jako: ¢ ¢ ¢ ¢ ¢ ¢kde hm jsou bázové funkce nebo jejich interakce a koeficienty bm pro dané hm jsou odhadovány stejně jako u lineární regrese metodou nejmenších čtverců. ¢Algoritmus MARS je velmi podobný postupnému dopřednému výběru (forward stepwise selection) vysvětlujících proměnných v regresním modelu → namísto proměnných se vybírají lineární splajny. ¢Začínáme s nulovým modelem (bez prediktorů). ¢Postupně se přidávají jednotlivé členy do rovnice (bázové funkce) → pouze takové, jejichž příspěvek k variabilitě vysvětlené modelem je statisticky významný. ¢Tento příspěvek se určuje na základě snížení residuálního součtu čtverců modelu. 1. logo-IBA Pokročilé neparametrické metody MARS- krovalidace ¢krosvalidační kritérium GCV (generalized cross-validation) → vybere se model s optimálním počtem členů v rovnici. ¢GCV lze použít i pro odhady relativních významností jednotlivých prediktorů. kde N je počet pozorování, ŷi je hodnota závisle proměnné odhadnutá modelem a M(l) je parametr složitosti modelu, který má tvar: kde r je počet nekonstantních bázových funkcí v modelu a K je počet uzlů t v modelu, kde již proběhl výběr parametrů pomocí dopředného výběru Konstanta c je určena experimentálně: c = 3 pokud nejsou zahrnuty interakce c = 2 pro rovnici s interakcemi logo-IBA Pokročilé neparametrické metody MARS - krovalidace ¢Datový soubor je rozdělen na testovací a trénovací v poměru zadaném uživatelem (často 70% trénovací a 30% testovací) ¢ ¢Na trénovacím souboru je vytvořen model a je spočítána jeho přesnost (R2) na testovacím souboru. ¢ ¢Hodnota GCV je spočítána pro různé podmodely, mající různý počet členů v rovnici, který označuje parametr λ. ¢ ¢Je vybrán podmodel s nejmenší hodnotou GCV. ¢ ¢Analogie s CART a CHAID → optimální počet terminálních uzlů stromu a PRIM → okna optimální velikosti. logo-IBA Pokročilé neparametrické metody Algoritmus metody MARS ¢Krok1: Algoritmus začíná s konstantní funkcí hm(X) = 1 ¢ ¢Krok2: Vytvoří se splajny (zrcadlové páry) se svým středem (uzlem t) v každé hodnotě xij, pro každý prediktor Xj → získáme množinu všech „kandidátských“ bázových funkcí C → model je tvořen prvky z této množiny nebo jejich kombinací. ¢ ¢Krok3: Z množiny C jsou do modelu přidávány pomocí postupného výběru významné bázové funkce, které snižují reziduální chybu modelu. ¢ ¢ !Proces postupuje hierarchicky, významné interakce jsou přidávány do modelu pouze z kombinace bázových funkcí, které již byly do modelu vybrány! ¢ ¢Z kroku 1 - 3 jsme získali rovnici s vybranými členy → počet členů však bývá většinou velmi velký ¢ ¢Krok4: procedura zpětného odstraňování. —Z rovnice jsou odstraněny ty členy, u kterých po jejich odstranění dojde k nejmenšímu zvýšení chyby modelu. — Zpětné odstraňování je učiněno pomocí krosvalidace. Hodnota GCV je spočítána pro různé velikosti modelu (s různým počtem členů v rovnici) a je vybrán model, pro který je hodnota GCV minimální. logo-IBA Pokročilé neparametrické metody MARS - algoritmus (Hastie et. al, 2009) logo-IBA Pokročilé neparametrické metody MARS ¢ J modelovaná plocha je spojitá J zahrnuje aditivitu proměnných J zahrnuje interakci proměnných J vhodná i pro větší počet prediktorů ¢ L nevýhodou je méně názorná interpretace → chybí stromová struktura L dopředný výběr proměnných je hierarchický L každý vstup se může v modelu objevit pouze jednou ¢ ¢PolyMARS (Stone et al., 1997) – pro klasifikaci logo-IBA Pokročilé neparametrické metody Skupinové modely Klasifikační a regresní lesy logo-IBA Pokročilé neparametrické metody Moudrost davu (Wisdom of Crowds) ¢ ¢James Surowiecki, 2004 ¢„skupinový úsudek je daleko inteligentnější a přesnější než úsudek jednotlivce, v případech, kdy jde o hodnocení faktů“ ¢každý příslušník davu musí činit svůj úsudek na základě vlastních, nezávislých informací ¢Výsledek je dán hlasováním ¢ ¢ logo-IBA Pokročilé neparametrické metody Skupinové modely (ensamble models) ¢skupině modelů zadáme stejný problém, na kterém se naučí ¢ výstupy naučených modelů se kombinují ¢ výsledkem skupinového modelu je —v případě regrese → zprůměrování všech výsledků jednotlivých modelů —u klasifikace → většinové hlasování jednotlivých modelů (lze však použít průměrování) ensemble logo-IBA Pokročilé neparametrické metody Skupinové modely (ensamble models) ¢Můžeme však kombinací modelů získat přesnější model? ¢ ¢Podmínka → jednotlivé modely musejí být různé například použitím různých souborů pro učení modelu, které získáme náhodný výběrem z trénovací množiny dat. ¢Modely tak budou vykazovat „odlišné“ chyby. ¢Přesnost a stabilita těchto modelů se následně ověřuje na testovacích souborech. ¢ ¢ ¢Označení skupinové modely se občas používá také pro kombinaci výsledků z různých modelů (např. neuronových sítí, rozhodovacích stromů a regrese) na stejném souboru. ¢ logo-IBA Pokročilé neparametrické metody Čím je způsobena chyba modelu…? ¢Př: měříme náhodnou veličinu Y v populaci (např. váha člověka) a chceme vyjádřit její reprezentativní hodnotu pro celou populaci. ¢ ¢Hledáme takový odhad ŷ, který minimalizuje střední hodnotu chyby Ey(y-ŷ)2 přes celou populaci. ¢ ¢V ideálním případě bychom změřili všechny vzorky v populaci (zvážili všechny lidi) a zjistili jejich střední hodnotu Ey(y) (např. průměr, medián), kterou bychom prohlásili za optimální odhad. ¢ ¢V praxi však tento přístup není možný a pomůžeme si výběrem pouze určité skupiny pozorování z populace, který však musí mít stejné vlastnosti jako celá populace. Takovýto výběr vytvoříme náhodným výběrem. logo-IBA Pokročilé neparametrické metody Skupinové modely -Rozklad chyby ¢analogie u modelů, kdy vybíráme pozorování pro trénovací soubor z množiny všech pozorování ¢Odchylky pozorovaných od predikovaných hodnot (chybovost modelu) nebudou způsobeny pouze „přírodní“ variabilitou, kterou jsme modelem nevysvětlili, ale také rozdílem ve výsledcích pro různé náhodné výběry a celou populaci. ¢ ¢ ¢Mějme soubor trénovacích dat: — —L = (yi,xi), i = 1,…,n. ¢ ¢→ hledáme takovou funkci v prostoru všech prediktorů a hodnot závisle proměnné, aby predikční chyba byla malá. ¢ logo-IBA Pokročilé neparametrické metody Skupinové modely -Rozklad chyby ¢Pokud mají (Y,X) stejné rozdělení a daná funkce R udává rozdíl mezi pozorovanou hodnotou yi a predikovanou hodnotou ŷi závisle proměnné Y, pak můžeme predikční chybu (prediction error) obecně vyjádřit jako: ¢ ¢ ¢ ¢kde f(X,L) jsou predikované hodnoty ŷi pro trénovací soubor L logo-IBA Pokročilé neparametrické metody Skupinové modely -Rozklad chyby ¢Průměrná obecná chyba (mean-squared generalization error) na trénovacím souboru L je rovna: ¢ ¢ ¢ ¢Optimální model by měl mít minimální průměrnou chybu pro různé výběry L → výsledky modelu pro jednotlivé výběry trénovacích souborů by se neměly příliš lišit. ¢ ¢Vyjádříme průměr trénovacích souborů stejné velikosti ze stejného rozložení: ¢ ¢ ¢kde je průměr přes všechny trénovací soubory L predikované hodnoty yi v hodnotě xi. logo-IBA Pokročilé neparametrické metody Rozklad na systematickou chybu a varianci (Bias-Variance Decomposition) ¢ ¢ ¢ ¢ ¢ ¢ ¢Šum – je reziduální chyba neboli minimální dosažitelná chyba modelu, kterou nejsme schopni modelem vysvětlit. ¢Zkreslení2- určuje systematickou chybu modelu. Je to rozdíl optimálního modelu od průměrného modelu. ¢Variance – je variabilita výsledků jednotlivých výběrů, jinými slovy, jak moc se predikované hodnoty ŷi liší v rámci trénovacích podsouborů L → vysoká variance značí přeučený model. ¢ ¢ šum zkreslení2 variance logo-IBA Pokročilé neparametrické metody Rozklad na systematickou chybu a varianci (Bias-Variance Decomposition) Ey(Y) ET(Y) bias2 šum variance ŷ Šum – chyba modelu Zkreslení2- systematická chyba modelu → optimální x průměrný Variance –variabilita výsledků jednotlivých výběrů logo-IBA Pokročilé neparametrické metody Slabé modely ¢Modely, které se používají ve skupinových modelech, se označují jako slabé modely neboli weak learners (slabý žák, u klasifikace také slabý klasifikátor). ¢ ¢Slabý model je definován obecně jako model, který má malé zkreslení, ale vysokou varianci → mají velmi vysokou přesnost, ale pouze pro pozorování z trénovacího souboru ¢Příkladem slabých modelů s velkým zkreslením, ale nízkou variancí může být interpolace bodů pomocí lineárních splajnů obr4 logo-IBA Pokročilé neparametrické metody Slabé modely – vytvoření skupinového modelu ¢Hledáme tedy model, který by měl nízkou varianci i zkreslení. Kombinováním několika slabých modelů můžeme snížit obě tyto složky. ¢Jak na to? obr4 logo-IBA Pokročilé neparametrické metody A co na to stromy? ¢Rozhodovací stromy jsou dobrými kandidáty pro použití ve skupinových modelech. ¢Neprořezané stromy mají totiž vysokou přesnost pro trénovací soubor (tedy nízký bias), ale vysokou varianci (výsledky mezi testovacím a trénovacím souborem se liší). ¢Rozhodovací stromy, na které nejsou aplikovány metody pro hledání optimální velikosti stromu, jsou tedy podle výše uvedené definice slabými modely. ¢u rozhodovacích stromů jsme pro určení jeho optimální velikosti museli rovněž najít kompromis mezi variancí a zkreslením! obr4