{{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á.
== 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 ==
{{TODO}}
== Učení založené na příkladech ==
{{TODO}}
== Bayesovské učení ==
{{TODO}}
== Support Vector Machines ==
{{TODO}}
[[Category:Matematická lingvistika]]
