Obsah

Obsah	1

1. 2. 4. Učení s učitelem - učení založené na instancích (Ch. 2)	2

❢ k-Nearest Neigbour	2

❢ Lineární regrese	3

3. Rozhodovací stromy (Ch. 9)	6

❢ Entropie - míra neuspořádanosti v systému	6

❢ Informační zisk (information gain)	6

❢ Prořezávání	7

5. Support vector machines (Ch. 12)	8

❢ Optimální separující nadrovina	8

❢ Support Vector Machines	9

6. Ohodnocení a volba modelů (Ch. 7)	10

❢ Míry chyby pro regresi	10

❢ Míry chyby pro klasifikaci	10

❢ dost dat x málo dat	10

7. Kombinace modelů (Ch. 8,10)	11

❢ boosting	11

8. Bayesovské učení	12

❢ maximálně pravděpodobná hypotéza (max. apost. probability)	12

❢ Bayesovsky optimální odhad	12

❢ maximálně věrohodná hypotéza (max. likelihood)	12

9. EM algoritmus	13

❢ Shlukování metodou k-středů (k-means)	13

❢ EM algoritmus (estimate maximize)	14

10. Učení bez učitele (Ch. 14)	15

❢ MBA (Asociační pravidla) Analýza nákupního koše	15

❢ Algoritmus APRIORI	15

11. Genetické algoritmy	16

1. 2. 4. Učení s učitelem - učení založené na instancích (Ch. 2)

☀ instance = příklady, vzory

vstupy (nezávislé proměnné)

výstupy (závislé proměnné)

❢ k-Nearest Neigbour

Vstup:

trénovací množina klasifikovaných vzoru M

vzor v, který chceme klasifikovat

a celé kladné číslo k

Algoritmus:

v množine M najdeme množinu N obsahujíci k vzoru, ktere jsou k vzoru v nejbližší ze všech vzorů z M

vzoru v dáme klasifikaci, která je nejčastejší v množine N

příklad:

vlastnosti

se přizpůsobí libovolné (spojité..) hranici

predikce záleží na pozici a hodnotách pár okolních bodů, proto je nestabilní

velký rozptyl, malé vychýlení (bias)

trpí prokletím dimezionality

učíme se ukládáním dat

lze použít na klasifikaci, regresi a klastrování

❢ Lineární regrese

jaké parametry má lin. závislost mezi 2 veličinami

Regresní analýza - určit, jaký vztah má proměnná Y k jedné anebo vícero jiným proměnným X1,…,Xn

typy závislostí 2 proměnných

funkční vztah - 2 závislé proměnné, určité x odpovídá jediná hodnota y

korelace - 2 náhodné (nezávislé) proměnné, síla vztahu popisovaná korelačním koef. R

regrese - vztah náhodné (nezávislé, vysvětlující) proměnné x a závislé (vysvětlované) proměnné y, má pravděpodobnostní rozdělení

pro x a y hledáme přímku (její parametry) vystihující průběh jejich závislostí = je nejblíže všem bodům

závislost y na x můžeme popsat (aproximovat) pomocí regresní rovnice (přímky):

y = β1x + β0 + ε

ε je regresní odchylka

alternativně používaný zápis: y = bx + a

metodou nejmenších čtverců - minimalizace rozdílů mezi skutečnou a očekávanou hodnotou

(jednorozměrná regrese)

nejpoužívanější metoda pro odhad parametrů qi do regresního modelu

minimalizuje střední kvadratickou chybu RSS:

regresní koeficienty

odvození

sumu zderivujeme podle všech qi a získáme rovnice rovné 0 (jako při hledání minima)

β1 – směrnice

tan úhlu s osou x

β0 - absolutní člen

Mnohorozměrná regrese

β0 se často zahrnuje do celého vektoru β

pak se mu říká bias

není-li XTX singulární:

vlastnosti

je hladká, stabilní (cluster dat mimo přímku jí moc nerozhodí)

výrazně závisí na předpokladu linearity hranice

má malý rozptyl, potenciálně velké vychýlení (bias).

❢ přeučení - přílišná závislost modelu na trénovacích datech, která zvyšuje chybu na testovacích datech

Příklad: růst oranžové křivky při klesající modré

❢ optimální bayesovská hranice - Pokud víme, jakým procesem jsou data generována, můžeme v každém bodě predikovat nejčastější hodnotu (při stejné ceně chyby)

obě hodnoty stejně časté

❢ prokletí dimenzionality - nejbližší sousedé jsou při velké dimenzi hodně daleko

řeší se například pomocí PCA

3. Rozhodovací stromy (Ch. 9)

Vstup: Vektory příznaků; Výstup: Třídy klasifikace

Vnitřní uzel se větví podle hodnoty svého atributu (s atributy rodičů již zafixovanými)

klasifikace množiny na zaklade atributu každého prvku

posloupnost dotazu na jednotlivé atributy (na rovnost nebo vetší/menší)

chceme mít co nejkratší cesty

složitost rozhodovacích stromu: hnlog(n)

kde h je pocet atributu

❢ Entropie (disorder) - míra neuspořádanosti v systému

pi - relativní četnost třídy i, pro 0 doplníme výsledek limitou = 0

pi - počet dat v data patřící do třídy g dělený celkovým počtem dat v data

❢ Informační zisk (information gain)

entropie mínus vážená entropie

ID3 indukce - Jako TDIDT, ale pracuje na výstupu místo třídy jen s bool hodnotami

Iterative Dichotomiser 3

algoritmus

spocitej entropii pro každý atribut množiny S

rozděl S do podmnožin použitím atributu nejlépe klasifikujícím množinu

nejnišší součet entropií podmnožin

podmnožin je stejně jako hodnot atributu

nejvyšší gain

vytvoř uzel stromu obsahující atribut

rekurze na podmnožiny pomocí zbývajících atributů

pokud mají všechny stejnou klasifikaci, nebo dojdou atributy -> list

❢ Prořezávání

Mám validační data, nepoužitá k učení.

Na těchto datech spočtu chybu predikce stromu.

Rekurzivně zvažuji sloučit listy a z rodiče udělat list – provedu, pokud to sníží chybu.

Occamova břitva – jednodušší modely jsou lepší

Nebo můžeme i bez validačních dat:

❢ CART - krosvalidací určím velikost stromu (bez potřeby validačních dat)

generuje stromy postupným slučováním listů

Classification And Regression Trees

prostor hodnot atributu rozpivotován dělící hodnotou

Minimalizace přes pivoty:

statistikou motivovaný odhad chyby z trénovacích dat.

5. Support vector machines (Ch. 12)

❢ Optimální separující nadrovina

nadrovina okolo které je takový maximálně široký pás, že na každé straně jsou vzorky jedné třídy

kde

kde

Cílovou třídu (= ) kódujeme -1,1

Data pošleme do optimalizační procedury, dostaneme pro každý datový vzor αi

Vybereme vzorek s , označíme s.

parametr ("váhu" ) musíme určit laděním

Klasifikační pravidlo (nový vzorek x klasifikujeme)

což je

slack ξi (odchylky, relaxační proměnné) - vzdálenost vzorku i od hranice jeho třídy

je-li příklad na správné straně ξi = 0

❢ Support Vector Machines

hledají optimální separující narovinu v nelineární transformaci prostoru

separujeme pomocí nelineární funkce:

skalární součin nového a trénovacího vzoru

v transformovaném prostoru

volíme transformační prostor tak aby se dobře počítal skalární součin málo dimenzí

jádrové (kernal) funkce - počítaní skalární součin v transformačním prostoru

Příklady:

Klasifikační pravidlo

6. Ohodnocení a volba modelů (Ch. 7)

❢ Míry chyby pro regresi

jak se chybí predikce od správné hodnoty

Regrese - spojitá cílová veličina (nejčastěji)

kvadratická chyba:

absolutní chyba:

❢ Míry chyby pro klasifikaci

klasifikace - diskrétní G nabývající jednu z K možných hodnot 1...K, modelujeme pravděpodobnosti , predikujeme to s největší

chyba predikce (0-1 chyba)

log-likelihood = - logaritmus věrohodnosti (cross-entropy, deviance)

❢ dost dat x málo dat

Ohodnocení modelu, dost dat

Doporučuje se poměr: ½,1/4,1/4

Ohodnocení klasifikátoru, málo dat

Tuto úlohu převedu na ohodnocení algoritmu při málo datech.

Průměrem přes několik až mnoho vzorků získám odhad chyby algoritmu, který použiji i na můj ohodnocovaný klasifikátor (přímo nebo přepočtený).

Ohodnocení algoritmu, málo dat

krosvalidace (10 dílů) provést více testů, výsledky zprůměrovat

one-leave-out (spec.případ krosvalidace) vždy testuji jen na 1 vzorku

bootstrap do testovací/trénovací množiny vybíráme s opakováním

odhad chyby: součet prům.chyb příkladů

*korekce pro počet dat (0,632) + chyba na trén.datech

*korekce pro přeučení

7. Kombinace modelů (Ch. 8,10)

bagging - bootstrap aggregating

pomocí bootstrap vygenerujeme více datových sad,

naučíme modely, necháme hlasovat či průměrujeme.

stacking - učíme model (váhy) který kombinuje nižší modely

❢ boosting

učíme na vážených datech, váhu špatně klasifikovaných dat zvyšujeme

❢ AdaBoost.M1

přiřaď stejnou váhu všem trénovacím instancím

∀m ∈ M iterací

spočti chybu errm modelu Gm(x) na vážených trénovacích datech

☀ I je char.fce (vrací 1 pokud je splněna podmínka, jinak 0)

pokud errm = 0 nebo errm ≥ 0.5 končíme tvorbu modelu

upravíme váhy

normalizuj váhy všech instancí: (vynucuje distribuci)

vracíme prediktor

8. Bayesovské učení

❢ maximálně pravděpodobná hypotéza (max. apost. probability)

☀ podmíněná = aposteriorní

spočtu přes tabulku

❢ Bayesovsky optimální odhad

váží předpovědi jednotlivých hypotéz pravděpodobností těchto hypotéz

❢ maximálně věrohodná hypotéza (max. likelihood)

všechny hypotézy považuji za stejně pravděpodobné

hledám nejpravděpodobnější odhad

např. pro alt. rozdělení:

p najdu zlogaritmováním(argmin) a zderivováním (+položením =0)

9. EM algoritmus

❢ Shlukování metodou k-středů (k-means)

Inicializace:

Náhodně zvol rozklad do k shluků

Iterace:

Update-step: Urči centroidy pro všechny shluky v aktuálním rozkladu

např:

Assignment-step: Pro každý vzor x přesuň do nejbližšího shluku

nedošlo-li k žádnému přesunu -> KONEC

Příklad:

Volba reprezentace důležitější než algoritmus

např. pro vektorovou kvantizaci zpracování obrazu

k-medoids pro vzdálenost bez metriky

vzdálenost musíme počítat pokaždé = kvadr. složitost

Algoritmus hierarchického shlukování (metodou „zdola nahoru“)

na začátku je každý bod cluster

dokud je více než k shluků

Urči vzájemné vzdálenosti mezi všemi clustery

vždy shluknu dva nejbližší body do nového clusteru

❢ EM algoritmus (estimate maximize)

používá se pro odhad nepozorovaných veličin

Inicializace:

náhodně zvol parametry distribuce

Hlavní cyklus:

Estimate: podle parametrů distribuce spočítej hodnotu skrytých veličin

(odhad hodnot nepozorovaných dat)

Maximalizace: z nich urči max. věrohodný odhad parametrů distribuce

(max.věrohodnost vzhledem k datům přes uvažované modely)

pokud došlo ke změně parametrů, opakuj

iteruj až k pevnému bodu

❢ Směs jednorozměrných gausovských distribucí

2 distribuce mají parametry:

na začátku náhodně, , výběrový rozptyl

Estimate - krok:

je distribuční funkce

Maximize krok: odhadnout střední hodnoty a rozptyly

(vážené průměry)

(pravděpodobnost 1. klastru)

Směs gausovských distribucí

Estimate: každý příklad "rozdělím" mezi klastry

Součtem přes všechny příklady i spočteme váhu klastrů

Maximize: pro daná data spočteme maximálně věrohodný odhad

10. Učení bez učitele (Ch. 14)

❢ MBA (Asociační pravidla) Analýza nákupního koše

hledá četné kombinace atributů

3 míry

support

confidence (přesnost, spolehlivost, predictability)

interval [0; 1]

lift (zdvih, zlepšení)

pokud je <1 je pravidlo horší než náhodná volba

hlavní kroky

zvolte položky na adekvátní úrovni

vytvořte if-then pravidla z tabulky četností

určete nejlepší pravidla (zlepšení by mělo být >1)

❢ Algoritmus APRIORI

generování asociačních pravidel (frequent itemsets)

Generování kombinací do šířky - |kombinace| = k z kombinací délky k-1

Každou kombinaci délky k-1 porovnáme s každou jinou, shodují-li se v k-2 itemech, spojíme

Spojené zpětně profiltrujeme, chybí-li nám nějaká jejich podkombinace délky k-1, zahodíme je

Do L1 přiřaď všechny kategorie s četností ≥ t

for(k = 2; Lk-1 != {}; k++)

vygeneruj na základě Lk-1 kandidáty Ck

kartézský součin Lk-1 x Lk-1 a odstraň pokud její podkombinace délky k-1 není obsažena v Lk-1

Do Lk zařaď ty kombinace z Ck s četností ≥ t

return ∪ Lk;

PRIM

11. Genetické algoritmy

Populace P(t) umělých chromozomů

Chromozom (genotyp) - řetězec symbolů kódující vlastnosti jedince (fenotyp)

Fitness funkce Φ: genotyp → R

jak dobře řeší problém, čím vyšší tím lepší

Jednoduchý genet.algoritmus

Inicializace: vygeneruj populaci P(0) = {x1,...xN} náhodných chromozomů

Iterace:

spočítej fitness všech

vytvoř populaci P(t+1) selekcí

reprodukce ruletou - naškálujeme jedince na ruletu podle fitness a otočíme ruletou N-krát

elitismus - S nejlepších jedinců kopírujeme vždy

proveď křížení

náhodně se spárují a zkříží podle zadané pravděpodobnosti

jednobodové

vícebodové

mutuj chromozómy

náhodná změna bitů podle zadané pravděpodobnosti

skonči pokud: najdeme hledaného jedince nebo fitness nejlepšího neroste

Schema - abstraktní "šablona" genomu, ternarni retezec delky m, krome 1/0 jeste * (wildcard)

může popisovat část chromozomu zaručující vysokou fitness

řád schématu o(H) - počet pevných pozic

délka schématu δ(H) - vzálenost mezi první a poslední pevnou pozicí

fitness schématu f(H) - průměrná fitness odp. řetězců v populaci

❢ Věta o schematech - v populaci během GA (exponenciálně) roste počet schémat, která jsou krátká, mají nízký řád a mají nadprůměrnou fitness

Idea důkazu: Díváme se postupně pro všechny genetické operátory, na čem závisí očekávaná četnost schématu v další populaci - ukazuje se, že právě na délce atd.