Učení, rozhodovací stromy, neuronové sítě Aleš Horák E-mail: hales@fi.muni.cz http://nlp.fi.muni.cz/uui/ Obsah: • Učení • Rozhodovací stromy • Hodnocení úspěšnosti učícího algoritmu Neuronové sítě Úvod do umělé inteligence 11/12 1/40 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 o učení je klíčové pro neznámé prostředí (kde návrhář 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 SliDo Úvod do umělé inteligence 11/12 2/40 Výkonnostní standard Senzory zpětná vazba Komponenta učení cíle učení zmeny znalosti Výkonnostní komponenta Generátor problémů experimenty O 00 (D o. Agent Akční prvky Úvod do umělé inteligence 11/12 3/40 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 vyvodí nové pravidlo, že takové přejíždění 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 Výkonnostní standard Kritika zpětná vazl>a Senzory Komponenta učení cíle učení zmeny znalost Výkonnostní komponenta Generátor problémů Agent o w (D Q. Úvod do umělé inteligence 11/12 3/40 Komponenta učení 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 Úvod do umělé inteligence 11/12 4/40 Komponenta učení 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í • posílené (reinforcement learning) - nejobecnější, agent se učí podle odměn/pokut Úvod do umělé inteligence 11/12 4/40 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 11/12 5/40 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í s f na všech příkladech Úvod do umělé inteligence 11/12 6/40 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í s f na všech příkladech např. hledání křivky: fM x Úvod do umělé inteligence 11/12 6/40 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í s f na všech příkladech např. hledání křivky: fM x Úvod do umělé inteligence 11/12 6/40 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í s f na všech příkladech např. hledání křivky: fM Úvod do umělé inteligence 11/12 6/40 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í s f na všech příkladech např. hledání křivky: fM Úvod do umělé inteligence 11/12 6/40 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í s f na všech příkladech např. hledání křivky: Úvod do umělé inteligence 11/12 6/40 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í s 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 11/12 6/40 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 Úvod do umělé inteligence 11/12 7/40 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 a) f(x) b) f(x) -> x ■> x 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 Úvod do umělé inteligence 11/12 7/40 Rozhodovací stromy • Učící se agent • Komponenta učení • Induktivní učení Q Rozhodovací stromy • Atributová reprezentace příkladů • Rozhodovací stromy • Učení ve formě rozhodovacích stromů • Induktivní učení - shrnutí • Počítačový model neuronu • Struktury neuronových sítí Úvod do umělé inteligence 11/12 8/40 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? /Wt 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 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 11/12 9/40 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: nikdo Štamgastů? částľ^ plno OdhadCekání? >60 30-60, Alternativa? Hlad? Ne \ Ano Ne/ \^Ano Rezervace? Pá/So? A Alternativa? \Ano Ne^/\^Ano Ne/ /\ Ano Bar? A 1 N 1 A 1 Déšť? Úvod do umělé inteligence 11/12 10 / 40 Rozhodovací stromy Vyjadřovací síla rozhodovacích stromů Vyjadřovací síla rozhoc ovací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 P„(s)), kde P,(s) = (/\i(s) = Ví A ... A Am(s) = Vm) Úvod do umělé inteligence 11/12 11 / 40 Rozhodovací stromy Vyjadřovací síla rozhodovacích stromů 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 P„(s)), I _kde P,(s) = (yAi(s) = Vi A ... A Am(s) = Vm) J pro libovolnou Booleovskou funkci —>► řádek v pravdivostní tabulce = cesta ve stromu (od kořene k listu) Úvod do umělé inteligence 11/12 11 / 40 Rozhodovací stromy Vyjadřovací síla rozhodovacích stromů 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)), kde P/(s) = (>Ai(s) = V1 A ... A /lm(s) = \/m) _ _ _ ^ pro libovolnou Booleovskou funkci —>► řádek v pravdivostní tabulce = cesta ve stromu (od kořene k listu) A B T T T F F T 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 Úvod do umělé inteligence 11/12 11 / 40 Prostor hypotéz Rozhodovací stromy 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? Úvod do umělé inteligence 11/12 12 / 40 Prostor hypotéz Rozhodovací stromy 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 Úvod do umělé inteligence 11/12 12 / 40 Prostor hypotéz Rozhodovací stromy 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 Úvod do umělé inteligence 11/12 12 / 40 Prostor hypotéz Rozhodovací stromy 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ů Úvod do umělé inteligence 11/12 12 / 40 Prostor hypotéz Rozhodovací stromy 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? Úvod do umělé inteligence 11/12 12 / 40 Prostor hypotéz Rozhodovací stromy 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) Úvod do umělé inteligence 11/12 12 / 40 Prostor hypotéz Rozhodovací stromy 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) Úvod do umělé inteligence 11/12 12 / 40 Rozhodovací stromy Učení ve formě rozhodovacích stromů 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í Úvod do umělé inteligence 11/12 13 / 40 Rozhodovací stromy Učení ve formě rozhodovacích stromů 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 11/12 13 / 40 Výběr atributu Rozhodovací stromy Učení ve formě rozhodovacích stromů dobrý atribut = rozdělí příklady na podmnožiny, které jsou (nejlépe) "všechny pozitivní" nebo "všechny negativní" OOOOOO OOOOOO Štamgastů? je lepší volba atributu <— dává lepší informaci o vlastní klasifikaci příkladů Úvod do umělé inteligence 11/12 14 / 40 Rozhodovací stromy Učení ve formě rozhodovacích stromů 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) = \) Úvod do umělé inteligence 11/12 15 / 40 Rozhodovací stromy Učení ve formě rozhodovacích stromů 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á /«p(ví), ..., p(vn))) = Er=i-p(yi) iog2 p{ví) tato míra se také nazývá entropie Úvod do umělé inteligence 11/12 15 / 40 Rozhodovací stromy Učení ve formě rozhodovacích stromů 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((PM,..., P(v„))) = E"=i-P(vi) log2 P(ví) 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: '((iso* m)) = -les '°g2 xéo - m lQg2 m = °-08 bitů Úvod do umělé inteligence 11/12 15 / 40 Rozhodovací stromy Učení ve formě rozhodovacích stromů 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ů =^ '((^+7;? p+ň)) ^itů Je potřeba pro klasifikaci nového příkladu např. pro Xi,..., X12 z volby čekání na stůl je p = n = 6, takže potřebujeme 1 bit j Úvod do umělé inteligence 11/12 16 / 40 Rozhodovací stromy Učení ve formě rozhodovacích stromů 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ů =^ K(~ň!tňi Ď+í?)) ^ítů Je potíebz 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 - /co///c informace nám dá test na hodnotu atributu A? Úvod do umělé inteligence 11/12 16 / 40 Rozhodovací stromy Učení ve formě rozhodovacích stromů 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ů =^ K(~ň!tňi Ď+í?)) ^ítů Je potíebz 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 - /co///c 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 11/12 16 / 40 Rozhodovací stromy Učení ve formě rozhodovacích stromů Použití míry informace pro výběr atributu atribut A rozdělí sadu příkladů E na podmnožiny E; ssssss I I J | Štamgastů? | / ■ I S .1 V I V I S . V I ■ S V ■ f \ nkdo^^äsL plno r (nejlépe tak, ze kazda potrebuje mene informace) „ •••• nechť Ei má p; pozitivních a n, negativních příkladů je potřeba /((^p^, ^+7^)) bitů pro klasifikaci nového příkladu _ Pi+ni \(l Pi n; očekávaný počet bitů celkem je Remainder(A) = J2i ^+77 ' '\\p.+A7.1 p.+n. výsledný zisk atributu A je Gain(A) = /((^^, j^)) — Remainder(A) Úvod do umělé inteligence 11/12 17 / 40 Rozhodovací stromy Učení ve formě rozhodovacích stromů 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) nechť Ei má p; pozitivních a n, negativních příkladů je potřeba /((^p^, ^+7^)) bitů pro klasifikaci nového příkladu očekávaný počet bitů celkem je Remainder(Ä) = J2i ' ' mexickáMizené/ \ asijská ^"~~~»^bijfet výsledný zisk atributu A je Gain(A) = / n P+A7' p+A7 P+A7 ' V\p,+A7/ ' P/+/1 Remainder(A) výběr atributu = nalezení atributu s nejvyšší hodnotou Gain(A) Úvod do umělé inteligence 11/12 17 / 40 Rozhodovací stromy Učení ve formě rozhodovacích stromů 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) plno mexická^---^pizierie/ \ asijská^^^^bufet nechť Ei má p; pozitivních a n, negativních příkladů je potřeba /((^j^, ^+7^)) bitů pro klasifikaci nového příkladu _ Pi+n-, n; očekávaný počet bitů celkem je Remainder(A) = p+n . VXp+A7., +n ■ / výsledný zisk atributu A je Gain(A) = / n P+A7' p+A7 Remainder(Ä) výběr atributu = nalezení atributu s nejvyšší hodnotou Gain(A) Gain(Stamgastul) « 0.541 bitů Gain(Typl) — 0 bitů j Úvod do umělé inteligence 11/12 17 / 40 Rozhodovací stromy Učení ve formě rozhodovacích stromů 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) nechť Ei má p; pozitivních a n, negativních příkladů je potřeba /((^j^, ^+7^)) bitů pro klasifikaci nového příkladu plno mex\d^á^--^p\zzeňe/ \ asijská^^-^tiufet _ Pi+n-, n; očekávaný počet bitů celkem je Remainder(A) = p+n . VXp+A7., +n ■ / výsledný zisk atributu A je Gain(A) = / n P+A7' p+A7 Remainder(Ä) výběr atributu = nalezení atributu s nejvyšší hodnotou Gain(A) Gain(Stamgastul) « 0.541 bitů Gain(Typl) — 0 bitů j obecně: E; (pro A — v i) obsahuje klasifikací do tříd ci, /?eroa/nc/er(y4) = ■ /«P(q,i), P(q,*)» =>> Ga/a?(>A) = /((P(vi),PK))) - Remainder(A) Úvod do umělé inteligence 11/12 17 / 40 Rozhodovací stromy Učení ve formě rozhodovacích stromů Algoritmus IDT - příklad 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", "plno"), ("cen", "$"), ("déšť", "ne"), ("rez", "ne"), ("typ", "asijská") ]), ... ] Úvod do umělé inteligence 11/12 18 / 40 Rozhodovací stromy Učení ve formě rozhodovacích stromů Algoritmus IDT - příklad 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", "plno"), ("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 nečekat Úvod do umělé inteligence 11/12 18 / 40 Rozhodovací stromy Učení ve formě rozhodovacích stromů 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 leaf_tree( single.class ) attribute ^— choose_attribute( ařír/bi/řes, 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(exa/77p/es)) tree ^— new_decÍSÍOn_tree(ařřr/6i7ře) # nový (pod)strom s testem na atribut foreach value G get_attribute_values ( attribute) do vaLexamples ^— [ e for e G examples if attr_val(e, attribute) = value subtree ^— lnduceTree(aříributes - attribute , vaLexamples) if subtree is None then subtree ^— leaf_tree(get_example_classes(va/_exa/77p/es)) add_tree_branch(va/L/e, subtree) return tree Úvod do umělé inteligence 11/12 19 / 40 Rozhodovací stromy Učení ve formě rozhodovacích stromů IDT - výsledný rozhodovací strom rozhodovací strom naučený z 12-ti příkladů: Štamgastů? Úvod do umělé inteligence 11/12 20 / 40 Obsah Hodnocení úspěšnosti učícího algoritmu • Učící se agent • Komponenta učení • Induktivní učení 9 Atributová reprezentace příkladů • Rozhodovací stromy • Učení ve formě rozhodovacích stromů Q Hodnocení úspěšnosti učícího algoritmu • Induktivní učení - shrnutí • Počítačový model neuronu • Struktury neuronových sítí Úvod do umělé inteligence 11/12 21 / 40 Hodnocení úspěšnosti učícího algoritmu Hodnocení úspěšnosti učícího algoritmu ak můžeme zjistit, zda h « f? Úvod do umělé inteligence 11/12 22 / 40 Hodnocení úspěšnosti učícího algoritmu Hodnocení úspěšnosti učícího algoritmu dopředu — použít věty Teorie kom- jak můžeme zjistit, zda putačního učení po naučení — kontrolou na jiné trénovací sadě Úvod do umělé inteligence 11/12 22 / 40 Hodnocení úspěšnosti učícího algoritmu Hodnocení úspěšnosti učícího algoritmu jak můžeme zjistit, zda h « f? 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 CSliDo) dopředu — použít věty Teorie kom- putačního učení po naučení — kontrolou na jiné trénovací sadě křivka učení - závislost velikosti trénovací sady na úspěšnosti 40 60 80 velikost trénovací sady 100 Úvod do umělé inteligence 11/12 22 / 40 Hodnocení úspěšnosti učícího algoritmu cení ú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ů Úvod do umělé inteligence 11/12 23 / 40 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 ©) 9 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 o 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 11/12 24 / 40 Neuronové sítě Neuron • Učící se agent • Komponenta učení • Induktivní učení • Atributová reprezentace příkladů • Rozhodovací stromy • Učení ve formě rozhodovacích stromů II ' ' V X XI • Induktivní učení - shrnutí Q N euronove site 9 Počítačový model neuronu • Struktury neuronových sítí Úvod do umělé inteligence 11/12 25 / 40 mozek - 10 neuronů > 20 typů, 10 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 11/12 26 / 40 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 (units) - jsou propojeny vazbami (links) - vazba z jednotky j do / propaguje aktivaci aj jednotky j - každá vazba má číselnou váhu Wjj (síla+znaménko) jednotka í vstupní vazby aktivační funkce výstupní vazby Úvod do umělé inteligence 11/12 27 / 40 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 (units) funkce jednotky : 1. spočítá váženou vstupů = in i 2. aplikuje aktivační funkci g 3. tím získá výstup a, a,- = g{im) = g(^2 wJ,i3j) jsou propojeny vazbami (links) vazba z jednotky j do / propaguje aktivaci aj jednotky j každá vazba má číselnou váhu Wjj (síla+znaménko) prahová váha vstupní vstupní aktivační výstup vazby funkce funkce výstupní vazby Úvod do umělé inteligence 11/12 27 / 40 Akt ivační funkce Neuronové sítě Aktivační funkce účel aktivační funkce: 9 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í Úvod do umělé inteligence 11/12 28 / 40 Akt ivační funkce Neuronové sítě Aktivační funkce účel aktivační funkce: 9 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í napr. a) g(ifh) +1 t prahová funkce m i b) g(ini) sigmoida 1/(1 + e x) je derivovatelná - důležité pro učení změny prahové váhy Wqj nastavují nulovou pozicí - nastavují práh aktivace Úvod do umělé inteligence 11/12 28 / 40 Neuronové sítě Logické funkce pomocí neuronové jednotky Logické funkce pomocí neuronové jednotky Wh = 1-5 Wo = 0-5 Wo = -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 Úvod do umělé inteligence 11/12 29 / 40 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ěť 9 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 W j£ Úvod do umělé inteligence 11/12 30 / 40 Neuronové sítě Struktury neuronových sítí Příklad sítě s p vsiupem 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(W3i5 ' g{Wli3 ' 31 + 1/16,3 ' 32) + 1/1/4,5 • g{W1A • 31 + 1/1/2,4 • 32)) Úvod do umělé inteligence 11/12 31 / 40 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 0.4 0.2 0 Úvod do umělé inteligence 11/12 32 / 40 Neuronové sítě Jednovrstvá síť - perceptron Vyjadřovací síla perceptron u perceptron může reprezentovat hodně Booleovských funkcí - AND, OR, NOT, majoritní funkci (J2j WjXj > n/2, Wj = 1), ... reprezentuje lineární separator (nadrovina) v prostoru vstupu: Úvod do umělé inteligence 11/12 33 / 40 Učení perceptronu Neuronové sítě Jednovrstvá síť - perceptron 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ě Úvod do umělé inteligence 11/12 34 / 40 Učení perceptronu Neuronové sítě Jednovrstvá síť - perceptron 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 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 Úvod do umělé inteligence 11/12 34 / 40 Učení perceptronu Neuronové sítě Jednovrstvá síť - perceptron 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 E pro příklad se vstupem x a požadovaným (=správným) výstupem y je E = |E/r2 = |(y — /7w(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 m = E"xm = Errxm(y-w^ = ~Err x g'{in) x *j 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 Úvod do umělé inteligence 11/12 34 / 40 Neuronové sítě Jednovrstvá síť - 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 i B 0.9 I as i 0.7 ■8 g 0.6 i-i 0.4 x xx xx x * * Kx x Perceptron Rozhodovací strom x 0 10 20 30 40 50 60 70 SO 90 100 velikost trétiovací sady b) učení čekání na volný stůl v restauraci 1 I 0.9 ■ 1 0.8 H 2 -8 > 0.6 -I ■■ca | 0.5 W 0.4 Rozhodovací strom Perceptron T-1-1-1 0 10 20 30 40 50 60 70 SO 90 100 velikost trénovací sady Úvod do umělé inteligence 11/12 35 / 40 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 11/12 36 / 40 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í napr. dvě "opačné" skryté jednotky vytvoří hřbet dva hřbety vytvoří homoli kw(xvx2) 0.8 : 0.6 : 0.4 ; 0.2 ; o : playground.tensorflow.org csiíDo) Úvod do umělé inteligence 11/12 37 / 40 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 ay x A/ kde A/ = Errt x gř(irij) Úvod do umělé inteligence 11/12 38 / 40 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 ay x A/ kde A; = Errt x gř(irij) • skryté vrstvy - zpětné šíření (back-propagation) chyby z výstupní vrstvy WkJ