Učení, rozhodovací stromy, neuronové sítě Aleš Horák E-mail: hales@fi.muni.cz http://nlp.f i.muni.cz/uui/ Obsah: ► Učení ► Rozhodovací stromy ► Hodnocení úspěšnosti učícího algoritmu ► Neuronové sítě Úvod do umělé inteligence 10/12 1/37 Učení Učení ► učení agenta - využití jeho vjemů z prostředí nejen pro vyvození další akce ► učení modifikuje rozhodovací systém agenta pro zlepšení jeho výkonnosti ►V X ■ II XV X XX i v I / I I X | X V X V V I x\ učeni je khcove pro neznáme prostredí (kde navrhar není vševědoucí) ► učení je také někdy vhodné jako metoda konstrukce systému - vystavit agenta realitě místo přepisování reality do pevných pravidel Úvod do umělé inteligence 10/12 2/37 Učení Učící se agent Učící se agent Výkonnostn^standard zpětná vazl>a Agent experimenty Akční prvky O (0 O. příklad automatického taxi: ► Výkonnostní komponenta - obsahuje znalosti a postupy pro výběr akcí pro vlastní řízení auta ► Kritika - sleduje reakce okolí na akce taxi. Např. při rychlém přejetí 3 podélných pruhů zaznamená a předá pohoršující reakce dalších řidičů ► Komponenta učení - z hlášení Kritiky IX s ■ I I V . I X V f V I V f vyvodí nove pravidlo, ze takové přejížděni je nevhodné, a modifikuje odpovídajícím způsobem Výkonnostní komponentu ► Generátor problémů - zjišťuje, které oblasti by mohly potřebovat vylepšení a navrhuje experimenty, jako je třeba brzdění na různých typech vozovky Úvod do umělé inteligence 10/12 3/37 Učení Komponenta učení Komponenta učení návrh komponenty učení závisí na několika atributech: - jaký typ výkonnostní komponenty je použit - která funkční část výkonnostní komponenty má být učena - jak je tato funkční část reprezentována - jaká zpětná vazba je k dispozici výkonnostní komponenta funkční část reprezentace zpětná vazba Alfa-beta prohledávání Logický agent Reflexní agent vyhodnocovací funkce určení akce váhy perceptronu vážená lineární f u n kce axiomy Result neuronová síť výhra/prohra výsledné skóre správná/špatná akce učení s dohledem (supervised learning) x bez dohledu (unsupervised learning) ► s dohledem - učení funkce z příkladů vstupů a výstupů ► bez dohledu - učení vzorů na vstupu vzhledem k reakcím prostředí ► zpětnovazební (reinforcement learning) - nejobecnější, agent se učí podle odměn/pokut Učení Induktivní učení Induktivní učení známé taky jako věda © nejjednodušší forma - učení funkce z příkladů (agent je tabula rasa) f je cílová funkce každý příklad je dvojice x, ^(x) např. 0 0 X X X +1 úkol indukce: najdi hypotézu h takovou, že h « f pomocí sady trénovacích příkladů Úvod do umělé inteligence 10/12 5/37 Učení Induktivní učení Metoda induktivního učení zkonstruuj/uprav h, aby souhlasila s f na trénovacích příkladech h je konzistentní ^ souhlasíš f na všech příkladech např. hledání křivky: pravidlo Ockhamovy břitvy- maximalizovat kombinaci konzistence a jednoduchosti (nejjednoduššíze správných je nejlepší) Úvod do umělé inteligence 10/12 6/37 Učení Induktivní učení Metoda induktivního učení pokrač. hodně záleží na prostoru hypotéz, jsou na něj protichůdné požadavky: - pokrýt co největší množství hledaných funkcí - udržet nízkou výpočetní složitost hypotézy 1-> x 1-> - stejná sada 7 bodů - nejmenší konzistentní polynom - polynom 6-tého stupně (7 parametrů) - může být výhodnější použít nekonzistentní přibližnou lineární funkci - přitom existuje konzistentní funkce ax + by + c sin x Rozhodovací stromy Atributová reprezentace příkladů Atributová reprezentace příkladů příklady popsané výčtem hodnot atributů (libovolných hodnot) např. rozhodování, zda počkat na uvolnění stolu v restauraci: Příklad Atributy počkat? Alt Bar Pá/So Hlad Stam Cen Déšť /?ez Typ CekD Xi A N N A část. $$$ N A mexická 0-10 x2 A N N A plno $ N N asijská 30-60 N x3 N A N N část. $ N N bufet 0-10 A x4 A N A A plno $ N N asijská 10-30 A x5 A N A N plno $$$ N A mexická >60 N x6 N A N A část. $$ A A pizzerie 0-10 A x7 N A N N nikdo $ A N bufet 0-10 N x8 N N N A část. $$ A A asijská 0-10 A x9 N A A N plno $ A N bufet >60 N Xio A A A A plno $$$ N A pizzerie 10-30 N Xn N N N N nikdo $ N N asijská 0-10 N X12 A A A A plno $ N N bufet 30-60 A Ohodnocení tvoří klasifikaci příkladů - pozitivní (A) a negativní (N) Úvod do umělé inteligence 10/12 8/37 Rozhodovací stromy Rozhodovací stromy Rozhodovací stromy jedna z možných reprezentací hypotéz - rozhodovací strom pro určení, jestli počkat na stůl: Úvod do umělé inteligence 10/12 9/37 Rozhodovací stromy Vyjadřovací síla rozhodovacích stromu Vyjadřovací síla rozhodovacích stromů rozhodovací stromy vyjádří libovolnou Booleovskou funkci vstupních atributů —>► odpovídá výrokové logice Vs počkat?(s) (Pi(s) V P2(s) V ... V Pn(s)), I _kde P,(s) = (yAi(s) = Vi A ... A /\m(s) = \/m) j pro libovolnou Booleovskou funkci —>► řádek v pravdivostní tabulce = cesta ve stromu (od kořene k listu) A B T T T F F F F triviálně pro libovolnou trénovací sadu existuje konzistentní rozhodovací strom s jednou cestou k listům pro každý příklad ale takový strom pravděpodobně nebude generalizovat na nové příklady chceme najít co možná kompaktní rozhodovací strom Rozhodovací stromy Prostor hypotéz Prostor hypotéz 1. vezměme pouze Booleovské atributy, bez dalšího omezení Kolik existuje různých rozhodovacích stromů s n Booleovskými atributy? = počet všech Booleovských funkcí nad těmito atributy = počet různých pravdivostních tabulek s 2n řádky = 22" např. pro 6 atributů existuje 18 446 744 073 709 551616 různých rozhodovacích stromů 2. když se omezíme pouze na konjunktivní hypotézy (Hlad A -iDéšť) Kolik existuje takových čistě konjunktivních hypotéz? každý atribut může být v pozitivní nebo negativní formě nebo nepoužit =4> 3n různých konjunktivních hypotéz (pro 6 atributů = 729) prostor hypotéz s větší expresivitou - zvyšuje šance, že najdeme přesné vyjádření cílové funkce - ALE zvyšuje i počet možných hypotéz, které jsou konzistentní s trénovací množinou =4> můžeme získat nižší kvalitu předpovědí (generalizace) Rozhodovací stromy Učení ve formě rozhodovacích stromu Učení ve formě rozhodovacích stromů ► triviální konstrukce rozhodovacího stromu ■ pro každý příklad v trénovací sadě přidej jednu cestu od kořene k listu ■ na stejných příkladech jako v trénovací sadě bude fungovat přesně ■ na nových příkladech se bude chovat náhodně - negeneralizuje vzory z příkladů, pouze kopíruje pozorování ► heuristická konstrukce kompaktního stromu ■ chceme najít nejmenší rozhodovací strom, který souhlasí s příklady ■ přesné nalezení nejmenšího stromu je ovšem příliš složité —>» heuristikou najdeme alespoň dostatečně malý ■ hlavní myšlenka - vybíráme atributy pro test v co nejlepším pořadí Úvod do umělé inteligence 10/12 12 / 37 Rozhodovací stromy Učení ve formě rozhodovacích stromu Výběr atributu dobrý atribut = rozdělí příklady na podmnožiny, které jsou (nejlépe) "všechny pozitivní" nebo "všechny negativní" OOOOOO OOOOOO Štamgastů? nikdo část. oooo mexická oo Štamgastů? je lepší volba atributu <— dává lepší informaci o vlastní klasifikaci příkladů Úvod do umělé inteligence 10/12 13 / 37 Rozhodovací stromy Učení ve formě rozhodovacích stromu Výběr atributu - míra informace informace - odpovídá na otázku čím méně dopředu vím o výsledku obsaženém v odpovědi —>► tím více informace je v ní obsaženo měřítko: 1 bit = odpověď na Booleovskou otázku s pravděpodobností odpovědi (P(T) = §,P(F) = \) n možných odpovědí (P(vi),..., P(vn)) —>> míra informace v odpovědi obsažená l«P(vi),..., P(v„)» = E/=i-P(ví) log2 P(Vi) tato míra se také nazývá entropie např. pro házení mincí: /((§, §)) = — \ log2 \ — \ log2 \ — \ + \ — 1 bit pro házení falešnou mincí, která dává na 99% vždy jednu stranu mince: '((iBň* ififi)) = -TBň lQg2 mi-mi lQg2 Tftň = °-08 bitů Úvod do umělé inteligence 10/12 14 / 37 Rozhodovací stromy Učení ve formě rozhodovacích stromu Použití míry informace pro výběr atributu předpokládejme, že máme p pozitivních a n negativních příkladů =^ '((tj+tjj ĎTn)) ^itů ie potřeba pro klasifikaci nového příkladu např. pro Xi,..., x12 z volby čekání na stůl je p = a? = 6, takže potřebujeme 1 bit výběr atributu - kolik informace nám dá test na hodnotu atributu A? = rozdíl odhadu odpovědi před a po testu atributu Úvod do umělé inteligence 10/12 15 / 37 Rozhodovací stromy Učení ve formě rozhodovacích stromu Použití míry informace pro výběr atributu atribut A rozdělí sadu příkladů E na podmnožiny E\ (nejlépe tak, že každá potřebuje méně informace) oooooo •••••• mexická_----^pizzerie/ \ asijská ~^taufet nechť Ei má p; pozitivních a n, negativních příkladů je potřeba /((^^r, bitů pro klasifikaci nového příkladu očekávaný počet bitů celkem je Remainder(A) = J2i ' '((;^+7T> výsledný zisk atributu A je Gain(A) = /((^^, ^^)) — Remainder(A) výběr atributu = nalezení atributu s nejvyšší hodnotou Gain(A) Gain(Stamgastul) « 0.541 bitů Gain(Typl) — 0 bitů obecně: E; (pro A — vf) obsahuje klasifikací do tříd ci,Ck Remainder(A) = P(vs) • /«P(c,-1),P(c,-*)» =>> Ga/a?(>A) = /((P(^i),P(v„))) - Remainder(A) j Úvod do umělé inteligence 10/12 16 / 37 Rozhodovací stromy Učení ve formě rozhodovacích stromu Algoritmus IDT - příklad , "plno"), ] attributes = { "hlad": ["ano", "ne"], "štam": ["nikdo", "část", "plno"], "cen": ["$", "$$", "$$$"], ... } examples = [ ("počkat", ("alt", "ano"), ("bar", "ne"), ("páso", "ne"), ("hlad", "ano"), ("štam", "část"), ("cen", "$$$"), ("déšť", "ne"), ("rez", "ano"), ("typ", "mexická") ]), ("nečekat", ("alt", "ano"), ("bar", "ne"), ("páso", "ne"), ("hlad", "ano"), ("štam" ("cen", "$"), ("déšť", "ne"), ("rez", "ne"), ("typ", "asijská") ]), PrintTree(lnduceTree( attributes, examples)) štam? = nikdo nečekat = část počkat = plno hlad? = ano cen? = $ páso? = ano počkat = ne nečekat = $$$ nečekat = ne Úvod do umělé inteligence 10/12 17 / 37 Rozhodovací stromy Učení ve formě rozhodovacích stromu Algoritmus IDT - učení formou rozhodovacích stromů function InduceTree( attributes , examples) if length (examples) = 0 then return None single_class ^— all_same_class(examples) # V příklady stejné třídy if single_class is not None then return Ieaf_tree(s/77g7e_c/ass) attribute ^— choose_attribute(attr/£>l/tes, examples) # podle míry informace if attribute is None then # žádný užitečný atribut, list s distribucí klasifikací return leaf_tree(get_example_classes(examples)) tree ^— new_decÍSÍOn_tree(ařřr/6i7ře) # nový (pod)strom s testem na atribut foreach value G get_attribute_values(aitr/bute) do val_examples ^— [ e for e G examples if attr_val(e, attribute) = value subtree ^— lnduceTree(aříributes - attribute , val_examples) if subtree is None then subtree ^— leaf_tree(get_example_classes(val_examples)) add_tree_branch(va/l/e, subtree) return tree Úvod do umělé inteligence 10/12 18 / 37 Rozhodovací stromy Učení ve formě rozhodovacích stromu IDT - výsledný rozhodovací strom rozhodovací strom naučený z 12-ti příkladů: Štamgastů? podstatně jednodušší než strom "z tabulky příkladů" Úvod do umělé inteligence 10/12 19 / 37 Hodnocení úspěšnosti učícího algoritmu Hodnocení úspěšnosti učícího jak můžeme zjistit, zda h « f? ( \ PO používaná metodologie (cross validation): 1. vezmeme velkou množinu příkladů 2. rozdělíme ji na 2 množiny - trénovací a testovací 3. aplikujeme učící algoritmus na trénovací sadu, získáme hypotézu h 4. změříme procento příkladů v testovací sadě, které jsou správně klasifikované hypotézou h 5. opakujeme kroky 2-4 pro různé velikosti trénovacích sad a pro náhodně vybrané trénovací sady algoritmu dopředu — použít věty Teorie kompu- tačního učení naučení — kontrolou na jiné trénovací sadě křivka učení - závislost velikosti trénovací sady na úspěšnosti 0.4 1-1-1-1-1-1 0 20 40 60 80 100 velikost trénovací sady Úvod do umělé inteligence 10/12 20 / 37 Hodnocení úspěšnosti učícího algoritmu Hodnocení úspěšnosti učícího algoritmu - pokrač. tvar křivky učení závisí na^ je hledaná funkce realizovatelná x nerealizovatelná funkce může být nerealizovatelná kvůli ■ chybějícím atributům ■ omezenému prostoru hypotéz ► naopak nadbytečné expresivite např. množství nerelevantních atributů % správnosti i realizovatelná nadbytečná nerealizovatelná ► # příkladů Hodnocení úspěšnosti učícího algoritmu Induktivní učení - shrnutí Induktivní učení - shrnutí ► učení je potřebné pro neznámé prostředí (a líné analytiky ©) ► učící se agent - výkonnostní komponenta a komponenta učení ► metoda učení závisí na typu výkonnostní komponenty, dostupné zpětné vazbě, typu a reprezentaci části, která se má učením zlepšit ► u učení s dohledem - cíl je najít nejjednodušší hypotézu přibližně konzistentní s trénovacími příklady ► učení formou rozhodovacích stromů používá míru informace ► kvalita učení - přesnost odhadu změřená na testovací sadě Úvod do umělé inteligence 10/12 22 / 37 Neuronové sítě Neuron Neuron mozek - 1011 neuronů > 20 typů, 1014 synapsí, lms-10ms cyklus nosiče informace - signály = "výkyvy" elektrických potenciálů (se šumem) neuron - mozková buňka, která má za úkol sběr, zpracování a ^ Tělo buňky, soma Úvod do umělé inteligence 10/12 23 / 37 Neuronové sítě Počítačový model neuronu Počítačový model neuronu 1943 - McCulloch & Pitts - matematický model neuronu spojené do neuronové sítě - schopnost tolerovat šum ve vstupu a učit se jednotky v neuronové síti - jsou propojeny vazbami (links) (units) _ vazba z jednotky j do / propaguje aktivaci a jednotky j - každá vazba má číselnou váhu Wjj (síla+znaménko) funkce jednotky /: 1. spočítá váženou vstupů = in-, <%=_jř 2. aplikuje aktivační funkci g Wj 3. tím získá výstup a,- a prahová váha ai=g(ini) a,- = g{im) = g(^2 WJ,i3j) vstupní vstupní aktivační výstup vazby funkce funkce výstupní vazby Úvod do umělé inteligence 10/12 24 / 37 Neuronové sítě Aktivační funkce Aktivační funkce účel aktivační funkce: ► jednotka má být aktivní +1) pro pozitivní příklady, jinak neaktivní « 0 ► aktivace musí být nelineární, jinak by celá síť byla lineární 4 b) gdm) +i napr a) lil. prahová funkce sigmoida 1/(1 + e_x) je derivovatelná - důležité pro učení ReLU {rectified linear unit) softplus log(l + ex) změny prahové váhy Wqj nastavují nulovou pozicí - nastavují práh aktivace Úvod do umělé inteligence 10/12 25 / 37 Neuronové sítě Logické funkce pomocí neuronové jednotky Logické funkce pomocí neuronové jednotky Wb = l-5 Wo = 0.5 Wq = -0.5 W2 = í W2 = í AND OR NOT jednotka McCulloch & Pitts sama umí implementovat základní Booleovské f u n kce =4> kombinacemi jednotek do sítě můžeme implementovat libovolnou Booleovskou funkci Neuronové sítě Struktury neuronových sítí Struktury neuronových sítí ► sítě s předním vstupem (feed-forward networks) ■ necyklické ■ implementují funkce ■ nemají vnitřní paměť ► rekurentní sítě (recurrent networks) ■ cyklické, vlastní výstup si berou opět na vstup ■ složitější a schopnější ■ výstup má (zpožděný) vliv na aktivaci = paměť ■ Hopfieldovy sítě - symetrické obousměrné vazby; fungují jako asociativní paměť ■ Boltzmannovy stroje - pravděpodobnostní aktivační funkce ■ Long Short Term Memory (LSTM) - spojují vzdálené závislosti v sekvenci vstupu www.asimovinstitute.org/neural-network-zoo * ¥ Úvod do umělé inteligence 10/12 27 / 37 Neuronové sítě Struktury neuronových sítí Příklad sítě s předním vstupem síť 5-ti jednotek - 2 vstupní jednotky, 1 skrytá vrstva (2 jednotky), 1 výstupní jednotka síť s předním vstupem = parametrizovaná nelineární funkce vstupu 35 = g{ 1/1/3,5 • 33 + H/4,5 • a4) = g(W3,5 • l/l/l,3 ' 31 + 1/1/2,3 ' 32) + 1/1/4,5 ' l/l/l,4 ' 31 + 1/1/2,4 • 32)) Úvod do umělé inteligence 10/12 28 / 37 Neuronové sítě Jednovrstvá síť - perceptron Jednovrstvá síť - perceptron perceptron - pro Booleovskou funkci 1 výstupní jednotka - pro složitější klasifikaci - více výstupních jednotek vstupní jednotky w výstupní jednotky výstup perceptronu 1 O.S 0.6 04 02 0 Úvod do umělé inteligence 10/12 29 / 37 Neuronové sítě Jednovrstvá sít - perceptron Vyjadřovací sila perceptronu perceptron může reprezentovat hodně Booleovských funkcí - AND, OR, NOT, majoritní funkci WjXj > n/2, Wj = 1), ... reprezentuje lineární separator (nadrovina) v prostoru vstupu: Neuronové sítě Jednovrstvá síť - perceptron Učení perceptronu výhoda perceptronu - existuje jednoduchý učící algoritmus pro libovolnou lineárně separabilní funkci učení perceptronu = upravování vah, aby se snížila chyba na trénovací sadě kvadratická chyba (ztráta, Loss) E pro příklad se vstupem x a požadovaným (=správným) výstupem y je E = |E/r2 = |(y — /?w(x))2, kde /?w(x) je výstup perceptronu váhy pro minimální chybu pak hledáme optimalizačním prohledáváním spojitého prostoru vah 9E_ = Errx^ = Errx^{y-WjXj)) =-Err x g'(in) x Xj pravidlo pro úpravu váhy Wj: 0 výstup /?w(x) je moc malý =^> váhy se musí zvýšit pro pozitivní příklady a snížit pro negativní úpravu vah provádíme po každém příkladu —>» opakovaně až do dosažení ukončovacího kritéria Neuronové sítě Jednovrstvá sít - perceptron Učení perceptronu pokrač. učící pravidlo pro perceptron konverguje ke správné funkci pro libovolnou lineárně separabilní množinu dat a) učení majoritní funkce 13 - 0.9 i as t 0.7 g 0.6 té °-5 0.4 x *x *x x * * Kx * Perceptron Rozhodovací strom t-1-r t-1-1-1-r 0 10 20 30 40 50 60 70 SO 90 100 velikost trénovací sady b) učení čekání na volný stůl v restauraci 1 I 0.9 ■ 1 0.8 1 2 t 0.7 ] g 0.6 ] i-i ^ 0.5 H 0.4 Rozhodovací strom Perceptron -----*N>.^'V^.^ < -1-1-1-1-1-1-1-1-1-1 0 10 20 30 40 50 60 70 SO 90 100 velikost trénovací sady Úvod do umělé inteligence 10/12 32 / 37 Neuronové sítě Vícevrstvé neuronové sítě Vícevrstvé neuronové sítě vrstvy jsou obvykle úplně propojené počet skrytých jednotek je obvykle volen experimentálně Úvod do umělé inteligence 10/12 33 / 37 Neuronové sítě Vícevrstvé neuronové sítě Vyjadřovací síla vícevrstvých sítí s jednou skrytou vrstvou - všechny spojité funkce se dvěma skrytými vrstvami - všechny funkce těžko se ovšem pro konkrétní síť zjišťuje její prostor reprezentovatelných funkcí např. dvě "opačné" skryté jednotky vytvoří hřbet dva hřbety vytvoří homoli Neuronové sítě Vícevrstvé neuronové sítě Učení vícevrstvých sítí pravidla pro úpravu vah: ► výstupní vrstva - stejně jako u perceptronu Wjj <- Wjj + a x aj x A; kde A; = Err-, x gř(irii) ► skryté vrstvy - zpětné šíření (back-propagation) chyby z výstupní vrstvy WkJ ► neschopnost generalizovat Úvod do umělé inteligence 10/12 35 / 37 Neuronové sítě Vícevrstvé neuronové sítě Učení vícevrstvých sítí pokrač. vícevrstvá síť se problém čekání na volný stůl v restauraci učí znatelně lip než perceptron 0 10 20 30 40 50 60 70 80 90 100 velikost trénovací sady Úvod do umělé inteligence 10/12 36 / 37 Neuronové sítě Neuronové sítě - shrnutí Neuronové sítě - shrnutí ► většina mozků má velké množství neuronů; každý neuron « lineární prahová jednotka (?) ► perceptrony (jednovrstvé sítě) mají nízkou vyjadřovací sílu ► vícevrstvé sítě jsou dostatečně silné; mohou být trénovány pomocí zpětného šíření chyby ► velké množství reálných aplikací- rozpoznávání řeči ■ rozpoznávání ručně psaného písma ■ řízení auta, . .. ► v posledních letech hluboké neuronové sítě - lépe generalizují