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 Neuronové sítě Úvod do umělé inteligence 10/12 1/40 Strojové učení Učení Úvod do umělé inteligence 10/12 2/40 Učení Strojové učení Úvod do umělé inteligence 10/12 2/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 úkol indukce: najdi hypotézu h takovou, že h « f pomocí sady trénovacích příkladů +1 Úvod do umělé inteligence 10/12 3/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íš f na všech příkladech Úvod do umělé inteligence 10/12 4/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íš f na všech příkladech např. hledání křivky: fM x Úvod do umělé inteligence 10/12 4/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íš f na všech příkladech např. hledání křivky: fM x Úvod do umělé inteligence 10/12 4/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íš f na všech příkladech např. hledání křivky: fM Úvod do umělé inteligence 10/12 4/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íš f na všech příkladech např. hledání křivky: fM Úvod do umělé inteligence 10/12 4/40 Učení Induktivní učení Metoda induktivního učení zkonstruuj/uprav h, aby souhlasila s ř na trénovacích příkladech h je konzistentní souhlasíš f na všech příkladech např. hledání křivky: Úvod do umělé inteligence 10/12 4/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íš 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 4/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 10/12 5/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 10/12 5/40 Učení Hodnocení úspěšnosti učícího algoritmu Hodnocení úspěšnosti učícího algoritmu jak můžeme zjistit, zda h « f? Úvod do umělé inteligence 10/12 6/40 Učení Hodnocení úspěšnosti učícího algoritmu Hodnocení úspěšnosti učícího algoritmu dopředu — použít věty Teorie kompu- . , .. ^ , , ro / tačního učení jak muzeme zjistit, zda h « r r ( v , . . .. , po naučeni — kontrolou na jme trenovaci sadě Úvod do umělé inteligence 10/12 6/40 Učení 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 dopředu — použít věty Teorie kompu- tačního učení po naučení — kontrolou na jiné trénovací sadě křivka učení - závislost úspěšnosti na velikosti trénovací sady liDoJ 40 60 80 velikost trénovací sady 100 Úvod do umělé inteligence 10/12 6/40 Učení Hodnocení úspěšnosti učícího algoritmu Hodnocení úspěšnosti učícího algoritmu - pokrač. tvar křivky učení závisí na o 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 9 naopak nadbytečné expresivite např. množství nerelevantních atributů % správnosti i 1 - realizovatelná nadbytečná nerealizovatelná ► # příkladů Úvod do umělé inteligence 10/12 7/40 • 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í) 9 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 8/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 10/12 9/40 Výkonnostnj standard Kritika zpětná vazl>a Senzory ^ Komponenta učení cíle učení zmeny znalosti Výkonnostní komponenta Generátor problémů Agent experimenty Akční prvky O (O 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 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 13 / 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: Štamgastů? nikdo OdhadCekání? Ano Úvod do umělé inteligence 10/12 14 / 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) = (Al(s) = Ví A ... A Am{s) = Vm) J Úvod do umělé inteligence 10/12 15 / 40 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) = (>4i(s) = l/i A ... A /lm(s) = \/m) i pro libovolnou Booleovskou funkci —± řádek v pravdivostní tabulce = cesta ve stromu (od kořene k listu) T T F F A T F T F B A xor B F T T F Úvod do umělé inteligence 10/12 15 / 40 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)), kde P/(s) = (>Ai(s) = V1 A ... A Am(s) = Vm) i pro libovolnou Booleovskou funkci —± řádek v pravdivostní tabulce = cesta ve stromu (od kořene k listu) 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 10/12 15 / 40 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? Úvod do umělé inteligence 10/12 16 / 40 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 Úvod do umělé inteligence 10/12 16 / 40 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 Úvod do umělé inteligence 10/12 16 / 40 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ů Úvod do umělé inteligence 10/12 16 / 40 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? Úvod do umělé inteligence 10/12 16 / 40 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) Úvod do umělé inteligence 10/12 16 / 40 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) Úvod do umělé inteligence 10/12 16 / 40 Rozhodovací stromy Učení formou rozhodovacích stromu Učení formou 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 10/12 17 / 40 Rozhodovací stromy Učení formou rozhodovacích stromu Učení formou 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í o 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í ■ algoritmus IDT, Induction of Decision Trees Úvod do umělé inteligence 10/12 17 / 40 Výběr atributu Rozhodovací stromy Učení formou 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 10/12 18 / 40 Rozhodovací stromy Učení formou 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íra: 1 bit = odpověď na Booleovskou otázku s pravděpodobností odpovědi (P(T) = §,P(F) = \) Úvod do umělé inteligence 10/12 19 / 40 Rozhodovací stromy Učení formou 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íra: 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(w) log2 P(vi) tato míra se také nazývá entropie Úvod do umělé inteligence 10/12 19 / 40 Rozhodovací stromy Učení formou 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íra: 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(vn)» = E"=i-P(yi) !og2 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: '((iuô' m)) = ~m lQg2 m~ m log2 m = °-08 bitů Úvod do umělé inteligence 10/12 19 / 40 Rozhodovací stromy Učení formou 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ů / n p+n> p+n bitů je potřeba pro klasifikaci nového příkladu např. pro Xi,..., X12 z volby čekání na stůl ]e p n 6, takže potřebujeme 1 bit Úvod do umělé inteligence 10/12 20 / 40 Rozhodovací stromy Učení formou 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ů =^ K(p+ň' Ď+ň)) ^ítů Je potíebz 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 výběr atributu - kolik informace nám dá test na hodnotu atributu A? Úvod do umělé inteligence 10/12 20 / 40 Rozhodovací stromy Učení formou 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ů =^ K(p+ň' Ď+ň)) ^ítů Je potíebz 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 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 20 / 40 Rozhodovací stromy Učení formou 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 oooooo je potřeba /((—r—, —r-)) bitů pro klasifikaci nového příkladu mexicfca^-^pizzerie/ \ asijská ^~"-—^j3ufet nechť Ei má p; pozitivních a n, negativních příkladů Pi n, Pi+rii' p,-neočekávaný počet bitů celkem je Remainder(A) = J2i ' \\p.+n.i p.+n výsledný zisk atributu A je Gain(A) = /((^^, — Remainder(A) Pi+rij i (/ p; n i Úvod do umělé inteligence 10/12 21 / 40 Rozhodovací stromy Učení formou rozhodovacích stromu Použití míry informace pro výběr atributu oooooo oooooo atribut A rozdělí sadu příkladů E na podmnožiny E; (' \ S .1 V I V I f , V I ■ f V ■ C \ nikdo ^---Mst pln, nejlépe tak, ze kazda potrebuje mene informace) i!. nechť E\ má p; pozitivních a n, negativních příkladů je potřeba /((^^:, ^J2^.)) bitů pro klasifikaci nového příkladu očekávaný počet bitů celkem je Remainder(Ä) = J2i ^x^" ' ^ p+n \ \ Pi+ni ' p,+n výsledný zisk atributu A je Gain(A) = /((-^-, —7-)) Remainder(A) p+n ' p+n výběr atributu = nalezení atributu s nejvyšší hodnotou Gain(A) Úvod do umělé inteligence 10/12 21 / 40 Rozhodovací stromy Učení formou rozhodovacích stromu Použití míry informace pro výběr atributu oooooo oooooo atribut A rozdělí sadu příkladů E na podmnožiny E; (' \ S .1 V I V I f , V I ■ f V ■ C \ nikdo ^---Mst pln, nejlépe tak, ze kazda potrebuje mene informace) i!. nechť E\ má p; pozitivních a n, negativních příkladů je potřeba /((^^:, ^J2^.)) bitů pro klasifikaci nového příkladu očekávaný počet bitů celkem je Remainder(Ä) = J2i ^x^" ' ^ p+n \ \ Pi+ni ' p,+n výsledný zisk atributu A je Gain(A) = /((^^, j^)) — Remainder(A) výběr atributu = nalezení atributu s nejvyšší hodnotou Gain(A) Gain(Stamgastul) « 0.541 bitů Gain(Typl) — 0 bitů I Úvod do umělé inteligence 10/12 21 / 40 Rozhodovací stromy Učení formou rozhodovacích stromu Použití míry informace pro výběr atributu oooooo oooooo atribut A rozdělí sadu příkladů E na podmnožiny E; (' \ S .1 V I V I f , V I ■ f V ■ C \ nikdo ^---Mst pln, nejlépe tak, ze kazda potrebuje mene informace) i!. nechť E\ má p; pozitivních a n, negativních příkladů je potřeba /((^^:, ^J2^.)) bitů pro klasifikaci nového příkladu očekávaný počet bitů celkem je Remainder(Ä) = J2i ^x^" ' ^ p+n \ \ Pi+ni ' p,+n výsledný zisk atributu A je Gain(A) = /((^^, j^)) — Remainder(A) výběr atributu = nalezení atributu s nejvyšší hodnotou Gain(A) Gain(Stamgastul) « 0.541 bitů Gain(Typl) — 0 bitů I obecně: E\ (pro /4 = vf) obsahuje klasifikací do tříd ci, /?eroa/nc/er(y4) = ■ /«P(q,i), P(q,*)» =>> Ga/a?(>A) = /((P(^i),PK))) - Remainder(A) Úvod do umělé inteligence 10/12 21 / 40 Rozhodovací stromy Učení formou rozhodovacích stromu 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 10/12 22 / 40 Rozhodovací stromy Učení formou rozhodovacích stromu 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 10/12 22 / 40 Rozhodovací stromy Učení formou 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 23 / 40 Rozhodovací stromy Učení formou 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 24 / 40 Neuronové sítě Neuron • Induktivní učení • Hodnocení úspěšnosti učícího algoritmu • Učící se agent • Komponenta učení • Učení - shrnutí i—i i i / , • Atributová reprezentace příkladů • Rozhodovací stromy • Učení formou rozhodovacích stromů q N euronove site • Počítačový model neuronu • Struktury neuronových sítí Úvod do umělé inteligence 10/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 10/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 - jsou propojeny vazbami (links) (units) - vazba z jednotky j do / propaguje aktivaci aj jednotky j - každá vazba má číselnou váhu Wjj (síla+znaménko) vstupní aktivační výstupní vazby funkce vazby Úvod do umělé inteligence 10/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 - jsou propojeny vazbami (links) (units) - vazba z jednotky j do / propaguje aktivaci aj jednotky j - každá vazba má číselnou váhu Wjj (síla+znaménko) funkce jednotky /: _; prahová váha 1. spočítá váženou /2 vstupů = in, °o~í v. w ^giii^j 2. aplikuje aktivační funkci g 3. tím získá výstup a,- a. 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 27 / 40 Neuronové sítě Aktivační funkce 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 10/12 28 / 40 Neuronové sítě Aktivační funkce 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(ini) prahová funkce sigmoida 1/(1 + e_x) je derivovatelná - důležité pro učení b) 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 28 / 40 Neuronové sítě Logické funkce pomocí neuronové jednotky Logické funkce pomocí neuronové jednotky Wb=-l-5 Wo = -0-5 W0 = Q.5 W2 = í W2 = l 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 10/12 29 / 40 • 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 30 / 40 Neuronové sítě Struktury neuronových sítí Příklad sítě s pře dní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(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 10/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 výstupní jednotky výstup perceptronu 1 0.8 0.6 04 02 0 Úvod do umělé inteligence 10/12 32 / 40 Neuronové sítě Jednovrstvá síť - perceptron Vyjadřovací síla perceptronu perceptron může reprezentovat hodně Booleovských funkcí - AND, OR, NOT, majoritní funkci QTj Wjxj > n/2, Wj = 1), ... reprezentuje lineární separator (nadrovina) v prostoru vstupu: Úvod do umělé inteligence 10/12 33 / 40 lu Neuronové sítě Jednovrstvá síť - perceptron čení perceptron u 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 10/12 34 / 40 lu Neuronové sítě Jednovrstvá síť - perceptron čení perceptron u 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 Úvod do umělé inteligence 10/12 34 / 40 lu Neuronové sítě Jednovrstvá síť - perceptron čení perceptron u 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 Úvod do umělé inteligence 10/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 5 0-9 ä I as t 0.7 g 0.6 i-. £ 0.5 0,4 Perceptron Rozhodovací strom —i-1-1-1-1-1-1-1-1-1 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 i i Z 0.9 ] I 0.8 H B t 0-7 H -s > 0.6 ] 0.5 ■ 0.4 Rozhodovací strom Perceptron J -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 35 / 40 ■ icevrstve neuronové site Neuronové sítě Vícevrstvé neuronové sítě označení MLP, multi-layer perceptron vrstvy jsou obvykle úplně propojené počet skrytých jednotek je obvykle volen experimentálně Úvod do umělé inteligence 10/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í např. dvě "opačné" skryté jednotky vytvoří hřbet dva hřbety vytvoří homoli Úvod do umělé inteligence 10/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 Aj kde A/ = Errt x gř(irij) Úvod do umělé inteligence 10/12 38 / 40 Neuronové sítě Vícevrstvé neuronové sítě Učení vícevrstvých síti pravidla pro úpravu vah: • výstupní vrstva - stejně jako u perceptronu Wjj <- Wjj + a x ay x A/ kde A; = Errt x gř(irij) 9 skryté vrstvy - zpětné šíření (back-propagation) chyby z výstupní vrstvy WkJ ► neschopnost generalizovat Úvod do umělé inteligence 10/12 38 / 40 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 velikost trénovací sady Úvod do umělé inteligence 10/12 39 / 40 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, . .. Úvod do umělé inteligence 10/12 40 / 40 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í Úvod do umělé inteligence 10/12 40 / 40