Učení, rozhodovací stromy, neuronové sítě Aleš Horák E-mail: hales@fi.muni.cz http://nlp.fi.muni.cz/uui/ Obsah: 9 Učení • Rozhodovací stromy • Hodnocení úspěšnosti učícího algoritmu Neuronové sítě Úvod do umělé inteligence 10/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 V X ■ II XV X XX i v I / I I X | X V X V V I x\ o 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 SliDo Úvod do umělé inteligence 10/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 10/12 3/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 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 7/40 Obsah • Učící se agent • Komponenta učení 9 Induktivní učení Q Rozhodovací stromy • Atributová reprezentace příkladů • Rozhodovací stromy • Učení ve formě rozhodovacích stromů ^■ŕ^B I I /~\ f*\ /~\ /"\ ľ"\ ■ || f~\ /-\ ŕ"* ✓""N -f— I II ^» I | Ir"* ^"V I y-W" ^"V y i "|~ ľ"V"^ I I • Induktivní učení - shrnutí • Počítačový model neuronu e Struktury neuronových sítí Úvod do umělé inteligence 10/12 8/40 Rozhodovací stromy Atributová reprezentace príkladu 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 A 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 10/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: Štamgastů? nikdo OdhadCekání? Ano Úvod do umělé inteligence 10/12 10 / 40 Rozhodovací stromy Vyjadřovací síla rozhodovacích stromů Vyjadřovací síla rozhoc ovacích stromu rozhodovací stromy vyjádří libovolnou Booleovskou funkci vstupních atributů —y odpovídá výrokové logice _ Vs počkat?(s) (Pi(s) V P2(s) V ... V Pn(s)), I kde P,(s) = (/\i(s) = i/i A ... A /4m(s) = \/m) J Úvod do umělé inteligence 10/12 11 / 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) = (Ai(s) = Ví A ... A /lm(s) = Vm) 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 11 / 40 Rozhodovací stromy Vyjadřovací síla rozhodovacích stromu Vyjadřovací síla rozhodovacích stromu 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) 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 11 / 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 12 / 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 12 / 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 12 / 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 12 / 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 12 / 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 12 / 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 12 / 40 Rozhodovací stromy Učení ve formě rozhodovacích stromu Učení ve formě rozhodovacích stromu o 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 13 / 40 Rozhodovací stromy Učení ve formě rozhodovacích stromu Učení ve formě rozhodovacích stromu o 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 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 10/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 10/12 15 / 40 Výběr atributu - míra informace Rozhodovací stromy Učení ve formě rozhodovacích stromů 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(w) log2 P(ví) tato míra se také nazývá entropie Úvod do umělé inteligence 10/12 15 / 40 Výběr atributu - míra informace Rozhodovací stromy Učení ve formě rozhodovacích stromů 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(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: '((iso* m)) = "iso lQg2 m ~ m 1°š2 m = 0.08 bitů Úvod do umělé inteligence 10/12 15 / 40 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ů / 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 je p n 6, takže potřebujeme 1 bit LI Úvod do umělé inteligence 10/12 16 / 40 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ů Ii -j^hj)) bitů 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 výběr atributu - kolik informace nám dá test na hodnotu atributu A? Úvod do umělé inteligence 10/12 16 / 40 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ů Ii -j^hj)) bitů 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 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 16 / 40 Rozhodovací stromy Učení ve formě rozhodovacích stromu Použití míry informace pro výběr atributu oooooo oooooo mexicfca^-^pizzerie/ \ asijská ^~---^j3ufet 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 /((^f^:, j^.)) bitů pro klasifikaci nového příkladu Pi+rij i (i pi n i očekávaný počet bitů celkem je Remainder(A) = J2i ' \\p.+n-' p+n výsledný zisk atributu A je Gain(A) = /((^^, j^)) — Remainder(A) Úvod do umělé inteligence 10/12 17 / 40 Rozhodovací stromy Učení ve formě 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 ■ f \ nikdo ^---Mst pln, nejlépe tak, ze kazda potrebuje mene informace) i!. nechť Ei má p; pozitivních a n, negativních příkladů je potřeba /((^f^:, j^.)) bitů pro klasifikaci nového příkladu očekávaný počet bitů celkem je Remainder(A) = • ľ p+n V \ P/+/7/ ' P/+/1 výsledný zisk atributu /4 je Ga/A7(/4) = /((-^-, -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 17 / 40 Rozhodovací stromy Učení ve formě 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 ■ f \ nikdo ^---Mst pln, nejlépe tak, ze kazda potrebuje mene informace) i!. nechť Ei má p; pozitivních a n, negativních příkladů je potřeba /((^f^:, j^.)) bitů pro klasifikaci nového příkladu očekávaný počet bitů celkem je Remainder(A) = • ľ p+n V \ P/+/7/ ' P/+/1 výsledný zisk atributu A je Ga/A7(/4) = /((^^, ^^)) — 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 17 / 40 Rozhodovací stromy Učení ve formě 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 ■ f \ nikdo ^---Mst pln, nejlépe tak, ze kazda potrebuje mene informace) i!. nechť Ei má p; pozitivních a n, negativních příkladů je potřeba /((^f^:, j^.)) bitů pro klasifikaci nového příkladu očekávaný počet bitů celkem je Remainder(A) = • ľ p+n V \ P/+/7/ ' P/+/1 výsledný zisk atributu A je Ga/A7(/4) = /((^^, ^^)) — 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 /A = v,-) obsahuje klasifikací do tříd ci,Ck /?eroa/ncfer(y4) = P(^) • /«P(c,-1),P(c,-*)» =>► Ga/A?(yA) = /((P(^i),PK))) - Remainder(A) Úvod do umělé inteligence 10/12 17 / 40 Rozhodovací stromy Učení ve formě 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 18 / 40 Rozhodovací stromy Učení ve formě 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 18 / 40 Rozhodovací stromy Učení ve formě rozhodovacích stromu Algoritmus IDT - učení formou rozhodovacích stromu function InduceTree( attributes , examples) if length (examples) = 0 then return None single_class ^— all_same_class(exa/77p/es) # V příklady stejné třídy if single_class is not None then return Ieaf_tree(s/77g7e_c/ass) attribute ^— choose_attribute(ařřr/6i7ř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/7?p/es)) tree ^— new_decÍSÍOn_tree(ařřr/6i7ře) # nový (pod)strom s testem na atribut foreach value G get_attribute_values( attr/bivte) do val_examples ^— [ e for e G examples if attr_val(e, attribute) = value subtree ^— I nduceTree(attributes - 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 19 / 40 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 20 / 40 Hodnocení úspěšnosti učícího algoritmu • Učící se agent • Komponenta učení • Induktivní učení • 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í I\l /4-v 9 Počítačový model neuronu • Struktury neuronových sítí Úvod do umělé inteligence 10/12 21 / 40 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 22 / 40 Hodnocení úspěšnosti učícího algoritmu Hodnocení úspěšnosti učícího algoritmu dopředu — použít věty Teorie kompu- . , .. ^ , , r~> , 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 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 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 velikosti trénovací sady na úspěšnosti :siiDoJ 40 60 80 velikost trénovací sady 100 Úvod do umělé inteligence 10/12 22 / 40 H Hodnocení úspěšnosti učícího algoritmu ř ú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 realizovatelná nadbytečná nerealizovatelná ^ # příkladů Uvod do umělé inteligence 10/12 23 / 40 Hodnocení úspěšnosti učícího algoritmu Induktivní učení - shrnutí Induktivní učení - shrnutí e 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 24 / 40 Neuronové sítě Neuron • Učící se agent • Komponenta učení • Induktivní učení • Atributová reprezentace příkladů 9 Rozhodovací stromy • Učení ve formě rozhodovacích stromů • Induktivní učení - shrnutí euronove site • Počítačový model neuronu • Struktury neuronových sítí Úvod do umělé inteligence 10/12 25 / 40 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 sirem signálu Nervová vlákna Synapse 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 [y 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-, ad=~i 2. aplikuje aktivační funkci g 3. tím získá výstup a,- prahová váha 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 W0 = l.5 W0 = 0.5 Hq = -0.5 W2 = 1 H 2 - 1 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řiklad sítě s před nim 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 • 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 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í ^ výstupní jednotky J1 jednotky výstup perceptronu 1 O.S 0.6 04 02 0 Úvod do umělé inteligence 10/12 32 / 40 Vyjadřovací síla perceptronu Neuronové sítě Jednovrstvá sít - perceptron 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ít - 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ít - 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 °jl = Errx^ = Errx^j{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 Učení perceptronu pokrač. Neuronové sítě Jednovrstvá síť - perceptron 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 KM) 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ě 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 A/ kde A; = Errt x g^/r?,) Úvod do umělé inteligence 10/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; = Err j x g^/r?,) • skryté vrstvy - zpětné šíření (back-propagation) chyby z výstupní vrstvy WkJ <- WkJ + axakxAj kde Aj = gf(inj) E; ^ ,-A; Úvod do umělé inteligence 10/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^/r?,) • skryté vrstvy - zpětné šíření (back-propagation) chyby z výstupní vrstvy WkJ <- WkJ + axakxAj kde Aj = gf(inj) E; ^ ,-A; problémy učení: - dosažení lokálního minima chyby - příliš pomalá konvergence - přílišné upnutí na příklady —>► 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