{{predmet|Úvod do strojového učení (v počítačové lingvistice)|Markéta Vidová-Hladká]],<br/>[[Pavel Schlesinger]],<br/>[[Kiril Ribarov|PFL054}}
== Úvod ==
Učení v našem smyslu je ''získávání zkušeností'', ''učení se novým poznatkům''. Stroj je počítač, který umí jenom počítat. Formálně:
* Počítač se učí řešit úlohu třídy <math>T</math> se zkušeností <math>E</math> a úspěšností měřenou kritériem <math>P</math>, jestliže se jeho úspěšnost zkušeností zvyšuje.
Např.: <math>T</math> = parsing, <math>E</math> = treebank, <math>P</math> počet správně určených hran.
Zkušenost je '''přímá''' (přímo uvést, které postupy jsou povolené a které ne) a '''nepřímá''' (udává "dobré" postupy na základě trénovacích dat). Získávání zkušenosti může být '''řízené''' (s učitelem, kdy <math>E</math> = trénovací data), '''semi-supervised''' (kdy systém generuje postupy a něco je známkuje) nebo '''neřízené'''. Trénovací data by měla být vybraná s ohledem na testovací data.
Pro řízené strojové učení máme '''trénovací data''': <math>X = x_1, x_2, \dots x_n</math> s výstupními hodnotami <math>Y</math> a hledáme '''cílovou funkci''' <math>c:X\to Y, c(x_i) = y_i</math>. Hledáme ji nad '''prostorem hypotéz''' (modelem) <math>H</math>; tj. hledáme <math>h\in H: h(x_i) = c(x_i)\ \forall i\in 1,\dots n</math>.
=== Několik konceptů ===
''Postup učení jako '' '''vyhledávání''': Máme množinu ''možných'' hypotéz, v ní podmnožinu hypotéz ''konzistentních'' s trénovacími daty a v této podmnožině se někde nachází ''optimální'' hypotéza. Pomocí stroj. učení se jí přibližujeme, od ''startovací'' hypotézy se postupně dostaneme do něčeho, co je konzistentní s trénovacími daty, ale ne nutně k optimu.
''Vstupní hodnoty'' <math>X</math> prostoru hypotéz jsou buď '''reálné, diskrétní, nebo kategoriální'''. Výstupní hodnoty taktéž, potom je pro reálné hodnoty strojové učení '''regresí''', kdežto pro kategoriální '''klasifikací'''.
''Trénování'' je možné:
* '''dávkově''' (všechna trénovací data najednou)
* '''inkrementálně''' (dostávám instance jednu po druhé, mám náhodný výběr s návratem, postupně bez návratu (?))
* '''online''' (dostávám trénovací instance jednu po druhé, až když jsou k dispozici)
'''Bias''' je nějaký apriorní předpoklad. Může být dvojitého typu:
* '''absolutní''' -- hledaná hypotéza je prvkem prohledávané množiny (?)
* '''preferenční''' -- preferují se hypotézy vyhovující nějakému kritériu (např. Occamově břitvě)
Se '''šumem''' v datech se musí počítat, vzniká kvůli chybě měření nebo chybě modelu. Data musí ale být konzistentní (?).
'''Occamova břitva''' je kritérium jednoduchosti: vybrat nejjednodušší hypotézu, která pasuje na trénovací data (nabízí-li se víc možností).
'''Testování hypotéz''' -- úspěšnost hypotézy na trénovacích datech je odhadem její úspěšnosti na testovacích datech (+ intervaly spolehlivosti (?)). Problém je '''přetrénování''': při příliš velkém množství trénovacích dat klesá chyba na trénovacích, ale roste chyba na testovacích datech. K zjištění očekávané úspěšnosti na testovacích datech se může používat i '''křížová validace''': rozdělím trénovací data na podmnožiny a potom vždycky natrénuju na jedné podmnožině a testuju úspěšnost na zbytku dat; nakonec spočítám průměrnou chybu.
Teoretické aspekty:
* Lze určit hranice pro velikost prostoru hypotéz, přesnost aproximace, pravděpodobnost vydání úspěšné hypotézy a nutnou velikost trénování?
* Kolik trénovacích příkladů je třeba, aby učení s vysokou pravděpodobností konvergovalo k úspěšné hypotéze?
* Jaká je výpočetní složitost učení, které je úspěšné?
* Kolik případů bude klasifikováno špatně, než systém dojde ke správné hypotéze?
* '''Naučitelnost''': Požadujeme, aby se systém s velkou pravděpodobností naučil hypotézu, která je přibližně správná.
=== Testování úspěšnosti algoritmů ===
Máme několik měr, které se všechny vztahují k následující tabulce:
{|align="right" border="1" cellspacing="0"
|+ Tabulka pro posuzování úspěšnosti algoritmů ('''confusion matrix''')
! Testovací data !! Reálná hodnota: 1 !! Reálná hodnota: 0
|-
! Klasifikace: 1
| tp || fp
|-
! Klasifikace: 0
| fn || tn
|}
* '''Accuracy''' je čistě poměr správně klasifikovaných a všech testovacích instancí, tj. <math>A = \frac{tp + tn}{tp + fp + tn + fn}</math>
* '''Precision''': <math>P = \frac{tp}{tp + fp}</math> a '''recall''': <math>R = \frac{tp}{tp + fn}</math> se vždycky uvádějí dohromady
== Uspořádání hypotéz ==
Vytvoření boolovské funkce z množiny trénovacích příkladů. Hypotézu tu reprezentujeme jako <math>n</math>-tici "povolených" hodnot proměnných z trénovacích příkladů, přičemž pro hypotézu může být hodnotou:
* Specifická hodnota dané proměnné (tj. povolená je jedna hodnota)
* "?" (tj. na hodnotě této proměnné nezáleží, povolené je všechno)
* "<math>\emptyset</math>" (tj. nevyhovuje žádná hodnota této proměnné)
Pokud instance <math>x</math> vyhovuje všemi svými hodnotami proměnných povoleným hodnotám pro hypotézu <math>h</math>, potom <math>h(x) = 1</math>, tj. hypotéza <math>h</math> klasifikuje <math>x</math> jako '''pozitivní příklad'''.
Potom '''nejobecnější hypotéza''' je taková, která cokoliv klasifikuje jako pozitivní případ, tj. <math>(?, ?, ?, \dots, ?)</math> a '''nejspecifičtější hypotéza''' taková, která vše klasifikuje jako negativní, tj. <math>(\emptyset, \emptyset,\dots,\emptyset)</math>.
V tomto případě máme dán popis instancí <math>X</math>, tj. možné hodnoty proměnných, potom prostor všech možných hypotéz <math>H</math>, cílovou funkci <math>c: X\to \{0,1\}</math> a trénovací data (pozitivní i negativní příklady <math>D = (<x_1, c(x_1)>, <x_2, c(x_2)>,\dots)</math>. Hledáme takovou hypotézu, která by odpovídala cílové funkci na všech trénovacích příkladech: <math>h\in H: \forall x\in X: h(x) = c(x)</math>.Hypotéza, která je "vhodně dobrou" aproximací cílové funkce nad trénovacími daty, bude i "vhodně dobrou" aproximací nad ostatními daty.
=== Definice ===
Pro prohledávání hypotéz máme vodítko: ''uspořádání podle specifičnosti''.
* Řekneme, že příklad <math>x\in X</math> '''vyhovuje''' hypotéze <math>h\in H</math>, právě když <math>h(x) = 1</math>.
* Hypotéza <math>h\in H</math> je '''obecnější než''' hypotéza <math>j \in H</math> (<math>h \geq_{g} j</math>), právě když <math>\forall x\in X: j(x) = 1\Rightarrow h(x) = 1</math> (můžeme říct, že <math>j</math> je '''specifičtější než''' <math>h</math>).
* Hypotéza <math>h\in H</math> je '''striktně obecnější než''' <math>j \in H</math> (<math>h >_{g} j</math>), pokud <math>h</math> je obecnější než <math>j</math>, ale <math>j</math> není obecnější než <math>h</math>.
* Relace <math>\geq_{g}</math> je částečné uspořádání nad prostorem <math>H</math>.
Další definice:
* Hypotéza <math>h</math> '''pokrývá''' pozitivní příklad <math>x\in X</math>, právě když správně klasifikuje jako pozitivní.
* Hypotéza <math>h</math> '''je konzistentní s''' trénovacími daty <math>D</math>, právě když <math>h(x) = c(x)\ \forall <x,c(x)>\in D</math>.
* '''Prostor možností (version space)''' <math>VS_{H,D}</math> vzhledem k prostoru hypotéz <math>H</math> je podmnožina hypotéz konzistentních s trénovacími daty <math>D</math>.
* '''Hranice obecnosti (general boundary)''' <math>G</math> vzhledem k <math>H</math> a <math>D</math> je množina nejobecnějších hypotéz z <math>H</math> konzistentních s <math>D</math>. Proti tomu '''Hranice specifičnosti (specific boundary)''' <math>S</math> vzhledem k <math>H</math> a <math>D</math> je množina nejspecifičtějších hypotéz z <math>H</math> konzistentních s <math>D</math>.
=== Algoritmus Find-S ===
Nalezne nejspecifičtější hypotézu, která ještě vyhovuje trénovacím datům.
# Vezmi nejspecifičtější hypotézu <math>h\in H</math>
# <math>\forall x</math> pozitivní trénovací příklad a <math>\forall a_i</math> atribut reprezentace <math>h</math>: pokud hodnota <math>a_i</math> u <math>x</math> neodpovídá <math>h</math>, nahraď hodnotu <math>a_i</math> v <math>h</math> nejbližší obecnou hodnotou, která odpovídá <math>x</math>
# Po projití všech pozitivních příkladů vrať upravené <math>h</math>
Find-S vrátí nejspecifičtější hypotézu konzistentní s pozitivními trénovacími příklady. Za předpokladů, že prohledávaný soubor hypotéz obsahuje cílovou funkci <math>c</math> a trénovací data neobsahují chyby, bude nalezená hypotéza konzistentní i s negativními trénovacími příklady, tj. s celými trénovacími daty.
Je-li víc správných hypotéz, nalezneme takto jen jednu z nich, navíc neodhalíme nekonzistenci trénovacích dat.Nemusí existovat ani jen jedna nejspecifičtější hypotéza. Problém nalezení všech konzistentních hypotéz řeší algoritmus Candidate-Elimination.
=== Algoritmus Candidate-Elimination ===
Algoritmus pracuje s prostorem možností, určeným hranicí obecnosti a hranicí specifičnosti. To je možné proto, že platí následující věta:
'''Věta o reprezentaci prostoru možností''': <math>VS_{H,D} = \{h\in H: \exists s\in S, \exists g\in G: (g\geq_g h\geq_g s)\}</math>.
Postup algoritmu:
# Do <math>G, S</math> přiřaď množinu nejobecnějších, resp. nejspecifičtějších hypotéz z <math>H</math>
# Postupuj přes trénovací příklady <math>d\in D</math>:
# Je-li příklad <math>d\in D</math> pozitivní:
## Odstraň z <math>G</math> hypotézy nekonzistentní s <math>d</math>.
## Každou s <math>d</math> nekonzistentní hypotézu z <math>S</math> odstraň a přidej do <math>S</math> její minimální zobecnění konzistentní s <math>d</math>, pro které existuje nějaká obecnější hypotéza v <math>G</math>. Odstraň pak z <math>S</math> hypotézy, které jsou obecnější než jiné hypotézy v <math>S</math>.
# Je-li příklad <math>d\in D</math> negativní:
## Odstraň z <math>S</math> hypotézy nekonzistentní s <math>d</math>.
## Každou s <math>d</math> nekonzistentní hypotézu z <math>G</math> odstraň a přidej do <math>G</math> její minimální specializaci konzistentní s <math>d</math>, pro kterou existuje nějaká specifičtější hypotéza v <math>S</math>. Odstraň pak z <math>G</math> hypotézy, které jsou specifičtější než jiné hypotézy v <math>G</math>.
# Na konci vrať <math>G, S</math> jako reprezentaci prostoru možností.
Pokud chci uznávat dva atributy a ne jeden nebo všechny, můžu si zvětšit prostor hypotéz na množinu všech podmnožin množiny instancí <math>X</math>. Potom můžeme použít CE algoritmus, ale systém není schopen klasifikovat instance "za hranicí" trénovacích dat (?).
== Induktivní předpoklad ==
Abychom zachytili strategii, podle které systém generalizuje za hranici trénovacích dat při klasifikaci nových instancí, definujeme induktivní předpoklad:
* <math>(D_c\wedge x_i)\vdash L(x_i, D_c)</math>, tj. klasifikace instance <math>x_i</math> algoritmem <math>L</math> natrénovaným na <math>D_c</math> je '''induktivně odvoditelná''' z oné instance a trénovacích dat.
* '''Induktivní předpoklad (inductive bias)''' algoritmu <math>L</math> je minimální množina tvrzení <math>B</math> taková, že pro libovolnou cílovou funkci <math>c</math> a odp. trénovací data <math>D_c</math> platí: <math>\forall x_i \in X: (B\wedge D_c\wedge x_i)\vdash L(x_i, D_c)</math>, tj. klasifikace <math>x_i</math> algoritmem <math>L</math> natrénovaným na <math>D_c</math> je dokazatelná z instance, trénovacích dat a induktivního předpokladu.
Induktivní předpoklad algoritmu CE je <math>B = \{c\in H\}</math>, tj. cílová funkce je obsažena v prostoru hypotéz. Potom totiž platí i <math>c\in VS_{H,D}</math> a <math>\forall h\in VS_{H,D}: h(x_i) = L(x_i,D_c)</math>, tj. i <math>c(x_i)=L(x_i, D_c)</math>
Např. algoritmus ROTE-LEARNER, který jen skladuje v paměti trénovací příklady a pak vydává výsledek jen tehdy, je-li reálný příklad ekvivalentní nektrému z nich, má prázdný induktivní předpoklad.
Proti tomu Find-S předpokládá, <math>c \in H</math> a navíc, že všechny příklady jsou negativní, pokud jejich protějšek nepřináší novou znalost (?).
Induktivní učící systém, který používá CE a prostor hypotéz <math>H</math> je ekvivalentní deduktivnímu učícímu systému, který používá dokazování logických vět a induktivní předpoklad "<math>H</math> obsahuje cílovou funkci".
== Rozhodovací stromy ==
Jsou induktivní algoritmy, vytvořené ke klasifikaci instancí, popisují pomocí ''"disjunkce konjunkcí"''. Můžeme je použít, když instance jsou popsány atributy a hodnotami a cílová funkce je ''diskrétní''. V trénovacích datech můžou být i chyby nebo nevyplněné atributy, není to až tak citlivé.
Cílová funkce je tu reprezentována právě '''rozhodovacím stromem''' (sekvencí rozhodnutí <tt>if-then-else</tt>), klasifikace se pak provádí průchodem stromem od kořene k listům, kdy se testuje hodnota jednoho atributu instance pro každý uzel, každá hrana odpovídá jedné hodnotě. Každý uzel pak určuje klasifikaci instance.
=== ID3 algoritmus ===
Je algoritmus, který vytváří rozhodovací stromy na základě trénovacích dat. Postupuje ''top-down'' -- konstruuje strom od kořene. V každém uzlu si klade otázku: ''Který atribut je nejlepší pro tento uzel?'' a řeší ji statistickým testem na základě max. entropie. Počet větví vedoucích z uzlu je počet možných hodnot atributu, takže ho známe hned po vytvoření uzlu. Trénovací data jsou při vytváření dělena podle atributů v daném uzlu.
Pracuje rekurzivně:
# Vyřeší singulární případy:
## Všechna trénovací data jsou pozitivní případy / negativní případy: vytvoří jednouzlové stromy s ''(+)'' nebo ''(-)''.
## Nemáme (už) žádné atributy: vytvoří jednouzlový strom s ''(nejčastější hodnota cíl. funkce v trénovacích datech)''.
# Vybere atribut <math>A</math>, který nejlépe klasifikuje trénovací data a:
## Pro každou jeho možnou hodnotu udělá poduzel, rozdělí trénovací data podle těchto hodnot.
## Máme-li pro danou hodnotu atributu trénovací data, volá se rekurzivně (na danou část trénovacích dat a atributy s vynechaným <math>A</math>).
## Pokud nejsou trénovací data, vloží list s ''(nejčstější hodnota cíl. funkce v trénovacích datech)''.
# Vrátí výsledný (pod)strom.
Prochází se celý hypothesis space, ale hladovým způsobem bez backtrackingu. Výstupem je 1 rozhodovací strom, tj. jedna hypotéza.
Výběr nejlepšího atributu probíhá na základě '''entropie (zisku informace)'''. Který atribut má nejvyšší zisk informace, ten je vybrán. Platí: <math>G(D,A) = H(D) - \sum_{v\in\mathrm{values}(A)}(\frac{|D_v|}{|D|}\cdot H(D_v))</math>, kde:
* <math>G(D,A)</math> je zisk informace pro data <math>D</math> a atribut <math>A</math>,
* <math>H(D)</math> je entropie dat <math>D</math> vzhledem k cílové funkci,
* <math>D_v</math> jsou data, která mají hodnotu atributu <math>A</math> rovnou <math>v</math>.
=== Vylepšení ID3 ===
Jedním z možných problémů je '''overfitting'''. Řekneme, že hypotéza <math>h\in H</math> ''overfituje'' trénovací data, pokud existuje alternativní hypotéza <math>h'\in H</math> taková, že <math>h</math> má menší chybu než <math>h'</math> na trénovacích datech, ale na celé distribuci instancí je to naopak.
Vyvarovat se overfittingu lze buď '''prořezáváním (pruning)''', nebo použitím '''heldout dat''' pro validaci při trénování. Pruning je vyříznutí nějakého podstromu. Prořezávat můžeme, pokud je přesnost obecnější hypotézy vyšší než nějaké speciálnější. Postup:
# Vyhodit podstrom.
# Dát místo něj jeden uzel s ''(nejčastější hodnota na trénovacích datech)'' pro podmnožinu odpovídající vyhazovanému podstromu.
Máme víc možností prořezávání, počítáme přesnost a podle toho se rozhodujeme -- je nutné taky vědět, kdy s tím přestat, nutné testovat.
Strategie '''rule-post-pruning''' spočívá v následujícím postupu:
# Vytvoření rozhodovacího stromu.
# Jeho převedení na pravdila (počet pravidel = počet listů), kdy 1 pravidlo je 1 cesta od listu ke kořeni.
# Pro každé pravidlo zahodit ty podmínky, jejichž vyhozením se přesnost pravidla zlepší.
# Pravidla setřídit podle přesnosti na trénovacích datech, reálná data klasifikovat použitím pravidel v tomto pořadí.
Proti prořezávání nad stromem nemusíme vyhazovat jen z konce stromu, máme jemnější rozlišení.
Pokud je některý atribut <math>A</math> '''spojitý''' (ale cílové ohodnocení stále diskrétní), můžeme ho převést na diskrétní <math>A_{C}</math>: najdeme konstantu <math>C</math> a potom: <math>A < C \Rightarrow A_{C} = 0</math>, <math>A \geq C \Rightarrow A_{C} = 1</math>. Nejlepší <math>C</math> můžeme najít opět pomocí zisku informace:
# Zjistíme "přelomové" body, tj. vedle sebe stojící hodnoty, které jsou hodnoceny rozdílně.
# Kandidáti na <math>C</math> pak jsou průměry takových to vedle sebe stojících hodnot.
# Spočítáme <math>\overline{C} = \mathrm{argmax}_{C} G(A_{C},D)</math>.
Má-li atribut více hodnot (např. nějaké datum), zisk informace ho bude preferovat, což často vede k vytvoření stromu hloubky 1, který funguje jen na trénovací data. Musíme pak změnit test výběru atributů, místo zisku informace používáme '''ziskový poměr (gain ratio)''':
* Rozštěpení informace (split information): <math>SI(D,A) = \sum_{v\in\mathrm{values}(A)}\frac{|D_v|}{|D|}\log_2(\frac{|D_v|}{|D|})</math>
* Ziskový poměr: <math>GR(D,A) = \frac{G(D,A)}{SI(D,A)}</math>, kde <math>G(D,A)</math> je zisk informace pro trénovací data <math>D</math> a atribut <math>A</math>
Jsou i jiné způsoby, jak toho dosáhnout.
Pokud jsou některé atributy důležitější než jiné, zavádí se '''cena atributu (cost of the attribute)'''. Taky se musí vytvořit jiné kritérium, alternativní k zisku informace. Jsou i jiné alternativní způsoby výběru nejlepšího atributu, např. '''distance-based measure''', kdy se vybírá atribut, který dělí data co nejrovnoměrněji podle nějaké metriky. Změna výběru atributů nemá na stromy takový vliv jako prořezávání.
== Učení založené na příkladech ==
{{TODO}}
== Bayesovské učení ==
{{TODO}}
== Support Vector Machines ==
{{TODO}}
[[Category:Matematická lingvistika]]
