K čemu potřebujeme strojové učení? Proč vývojáři nenaprogramují v umělé inteligenci rovnou optimální postupy vedoucí k nejlepším řešením? (Mimochodem v 60. letech 20. století si mnozí vědci mysleli, že to bude brzy možné.)

• nemohou předvídat/brát v potaz všechny situace, v nichž se agent může ocitnout;
• nemohou předvídat budoucí změny podmínek a zadání, k nimž u většiny úloh UI dochází, protože se týkají situací v reálném světě, který se vyvíjí;
• mnohdy optimální algoritmy (při omezeném času a výpočetní kapacitě) pro řešení úloh nejsou známy, a v UI je to dokonce typické. Exemplárními případy je rozpoznávání obličejů, analýza řeči, nebo agenty hrající strategické hry, 

Symbolem dominance strojového učení nad jinými přístupy v UI je drtivé vítězství stroje AlphaZero v šachách nad dosud nejsilnějším programem Stockfish v roce 2017. Stockfish je založen na klasickém "minimaxu" a alfa-beta ořezávání a hraje spíše "mechanicky", využívá standardní zahájení, koncovky a postupy. Naproti tomu AlphaZero se naučil za několik hodin hrát zcela sám bez pomoci lidských expertů, a jeho herní styl připomíná lidského velmistra, ovšem na daleko vyšší úrovni.

Typy učení

• Učení s učitelem - k dispozici je množina tréninkových dat - vzorových zadání úlohy, spolu se vzorovým řešením ke každému zadání.
• Zpětnovazební (posilující) učení - nejsou poskytnuta detailní řešení tréninkových úloh, pouze hodnocení správně/chybně, nebo odměna/trest.
• Učení bez učitele - nejsou k dispozici žádná data o správných řešeních, agent většinou vychází ze vzájemných podobností vzorových úloh (typická úloha je rozdělení tréninkové množiny do kategorií).

V dalším se zaměříme na učení s učitelem. Tréninková data budou ve formě množiny {(x₁, y₁), (x₂, y₂), ... , (x_N, y_N)}, kde x_i je zadání/vstup popsané vektorem atributů (číselných/logických/textových aj. hodnot) a y_i je obdobně zadané řešení/výstup. Agent se má naučit přiřazovat zadáním správná řešení, tedy najít funkci (hypotézu) h tak, že h(x_i) = y_i pro všechna 1 ≤ i ≤ N. Samozřejmě bychom rádi, aby po natrénování uměl zobecňovat - najít správná řešení i pro podobné vstupy, které ale nebyly v tréninkové množině.

Rozhodovací stromy

Jsou založeny na postupném vyhodnocení podmínek týkajících se vstupních atributů. Například pokud se rozhodujeme, zda zůstaneme v restauraci, do které jsme právě vešli, bereme v úvahu atributy jako počet hostů, odhadovanou čekací dobu, ceny, očekávanou kvalitu, zda venku prší apod. Každou z podmínek vyhodnotíme do dvou nebo nejvýše několika málo případů (ceny: nízké/střední/vysoké/astronomické). Každá podmínka je uzel v rozhodovacím stromu, její vyhodnocení jsou hrany do dceřiných uzlů. V listech stromu jsou pak výstupy/řešení úlohy (zůstat v restauraci / odejít).

Každý strom tudíž představuje jednu možnou hypotézu. Jak nyní na základě tréninkové množiny sestavit nejlepší strom? Chceme přirozeně, aby byl co nejmenší, kvůli úspoře paměti i času při jeho průchodech, a současně aby hypotéza bylo pokud možno platná pro celou tréninkovou množinu. 

• Začínáme s nejvíce informativními atributy, které co nejlépe rozdělí tréninkovou množinu s ohledem na správné výstupy. Atributy vybíráme pomocí entropie.
• Pokud je strom příliš velký, můžeme ho prořezávat odstraněním irelevantních podmínek, které nejsou pro výsledek podstatné (pro výběr auta nebude hrát roli, zda je mokré či suché).
• Dodatečné problémy mohou být způsobeny např. chybějícími daty (hodnoty některých atributů občas nejsou známy), mnohahodnotovými nebo těžce porovnatelnými atributy ("každý pes jiná ves") atd.

Jak poznáme, které atributy jsou více informativní než jiné? Výpočet informačního zisku atributu je popsán v prezentaci MFF UK a v monografii [5]. Výpočet si předvedeme na příkladu atributu Patrons v prezentaci. 

Atribut Patrons je aplikován na boolovskou proměnnou Wait ("budeme čekat?") v posledním sloupci tabulky, která má 6 hodnot pozitivních (p=6) a 6 negativních (n=6). Její entropie tedy je

B(p/(p+n)) = B(6/12) = –0,5*log₂(0,5) – (1–0,5)*log₂(1–0,5) = – 0,5 * (-1) - 0,5 * (–1) = 1

Počty pozitivních a negativních výsledků pro jednotlivé hodnoty atributu Patrons jsou (viz slajd č. 5 v prezentaci):

1. None: p₁ = 0, n₁ = 2
2. Some: p₂ = 4, n₂ = 0
3. Full: p₃ = 2, n₃ = 4

Očekávaná entropie po testu atributu po dosazení do vzorce:

Remainder(Patrons) = Σ_k=1,2,3 B(p_k /(p_k +n_k)) * (p_k +n_k)/(p+n) = B(0/2) * 2/12 + B(4/4) * 4/12 + B(2/6) * 6/12 = 0 + 0 + B(1/3) * 1/2 = 0,459

Platí totiž, že B(0) = B(1) = 0; při výpočtu se objeví 0 * log₂0 = 0 * –∞, což lze vypočíst limitou lim(0 * log₂0) = 0. Intuitivně je to dáno tím, že jde o entropii náhodných jevů, jejichž výsledek je vždy negativní (None), resp. vždy pozitivní (Some). Takový jev tedy vlastně vůbec není náhodný a jeho entropie = míra nejistoty je nulová. Výpočet B(1/3) se provede stejně jako v předchozím odstavci, kde jsme počítali B(6/12).

Výsledný informační zisk atributu

Gain(Patrons) = B(p/(p+n)) - Remainder(Patrons) = 1 - 0,459 = 0,541.

Regresní modely

Co když jsou vstupní i výstupní atributy spojité a jejich dělení do malého počtu kategorií nedává smysl? Pak budou prostor hypotéz tvořit spojité funkce mapující vektor vstupů na vektor výstupů. Hledáme takovou, která vstupy na výstupy mapuje "co nejlépe". Bohužel neexistuje (a nemůže existovat) žádné jednoznačné kritérium, co znamená "co nejlépe". Často se pracuje např. s kvadratickou chybou (požadovaný minus skutečný výstup, to celé na druhou), kterou rozhodovací funkce udělá v součtu na všech tréninkových vzorech. 

Jelikož hledání spojitých funkcí může být docela složité, začneme s lineárními funkcemi, pro něž existují známé a ověřené metody. Ty umožní jednoznačně najít nejlepší hypotézu - funkci h s nejmenší kvadratickou chybou.

Pro složitější úlohy ale často lineární hypotézy nestačí - nejsou dost přesné, nepostihují dobře charakter problému (příkladem je už problém XOR). V tom případě hledáme co nejlepší hypotézu heuristicky - zvolíme nějaký tvar funkce a manipulujeme s jejími parametry tak, aby chyba pokud možno klesala. Často se používají gradientní metody.

Neparametrické modely

použijeme v případě, že tréninková množina není příliš veliká, takže není nutno ji modelovat pomocí nějaké funkce - hypotézy. Namísto toho můžeme, při řešení nového zadání, hledat v tréninkové množině "co nejpodobnější" případy, a z jejich vzorových řešení nějak slepíme odpověď. A samozřejmě si na to vezmeme vhodný matematický aparát.