Algoritmy strojového učení Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové“ systémy ML PLIN021 Sémantická analýza v praxi OP VK Mezi bohemistikou a informatikou www.projekt-inova.cz Zuzana Nevěřilová xpopelk@fi.muni.cz Centrum zpracování přirozeného jazyka, B203 Fakulta informatiky, Masarykova univerzita 11. března 2013 Algoritmy strojového učení Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové“ systémy ML Algoritmy strojového učení Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové“ systémy ML Algoritmy strojového učení Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové“ systémy ML Word Sense Desambiguation úkolem WSD je zjistit, jaký význam (z inventáře významů) má slovo ve vstupním textu minule jsme mluvili o metodách založených na znalostech (Leskův algoritmus pracující se slovníkovými definicemi a příklady užití) Algoritmy strojového učení Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové“ systémy ML Algoritmy strojového učení Strojové učení (machine learning, ML) = algoritmy a techniky, které způsobí změnu stavu počítačového systému tak, že zefektivní schopnost přizpůsobení se . . . Učím se, že pokud je blízko „kočka“ i „pes“, má „kočka“ význam 1. . . • s učitelem – pro zadaný vstup máme i správný výstup (trénovací data) • bez učitele – pro zadaný vstup neznáme správný výstup • kombinace – pro část vstupu máme i správný výstup Typické úlohy strojového učení jsou klasifikační úlohy. Algoritmy strojového učení Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové“ systémy ML Algoritmy strojového učení • „pravidlové“ • rozhodovací seznamy • rozhodovací stromy • „matematické“ • pravděpodobnostní: naivní Bayesovský (Duda et Hart, 1973) • maximální entropie: (Berger, 1996) • podobnostní: k-NN ve vektorovém prostoru (Ng et Lee, 1996) • „promluvové“ • předpoklad one sense per discourse (Gale 1992) • předpoklad one sense per collocation (Yarowsky, 1995) Algoritmy strojového učení Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové“ systémy ML Rozhodovací seznam if (zvíře má chobot) then output(slon) if (zvíře má pruhy) then output(zebra) if (zvíře má ploutve & zvíře není ryba) then output(žralok) Algoritmy strojového učení Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové“ systémy ML Rozhodovací strom savec? žije ve vodě? žije v moři? žije v řece? žije na souši? býložravec? masožravec? Rozhodovací strom savec? žije ve vodě? žije v moři? žije v řece? žije na souši? býložravec? masožravec? 2013-03-11 PLIN021 Sémantická analýza v praxi Pravidlové algoritmy ML Rozhodovací strom Seznam je jednodušší na implementaci, ale vidíme, že strom je přehlednější při stejné i vyšší složitosti. Častěji pracujeme se stromy. Rozhodovací strom savec? žije ve vodě? žije v moři? žije v řece? žije na souši? býložravec? masožravec? 2013-03-11 PLIN021 Sémantická analýza v praxi Pravidlové algoritmy ML Rozhodovací strom V této hře jsou Myslím si zvíře aspekty: • Jak poznám z množiny otázek O = {o1, o2, . . . , on}, kde oi je např. „Má zvíře srst?“, o jaké zvíře jde? Redukcí. Pokud odpověď na oi je „ne“, vyloučím ze správných odpovědí všechna zvířata zj , která mají srst. Podobně pro další otázky, dokud nezůstane (ideálně) 1 zvíře. • Jaká je strategie kladení otázek? Cílem je minimalizovat n. Prostředkem k dosažení tohoto cíle je neklást otázky, které dělí množinu možných zvířat stejným způsobem. Např. otázky „Má zvíře srst?“ a „Má zvíře 4 nohy?“ dělí Z na dvě téměř stejné části. Na celou hru můžeme pohlížet jako na množinu zvířat (která známe) a rozhodovací strom, který nás „dovede“ k myšlenému zvířeti. Algoritmy strojového učení Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové“ systémy ML Algoritmy strojového učení • „pravidlové“ • rozhodovací seznamy • rozhodovací stromy • „matematické“ • pravděpodobnostní: naivní Bayesovský (Duda et Hart, 1973) • maximální entropie: (Berger, 1996) • podobnostní: k-NN ve vektorovém prostoru (Ng et Lee, 1996) • „promluvové“ • předpoklad one sense per discourse (Gale 1992) • předpoklad one sense per collocation (Yarowsky, 1995) Algoritmy strojového učení • „pravidlové“ • rozhodovací seznamy • rozhodovací stromy • „matematické“ • pravděpodobnostní: naivní Bayesovský (Duda et Hart, 1973) • maximální entropie: (Berger, 1996) • podobnostní: k-NN ve vektorovém prostoru (Ng et Lee, 1996) • „promluvové“ • předpoklad one sense per discourse (Gale 1992) • předpoklad one sense per collocation (Yarowsky, 1995) 2013-03-11 PLIN021 Sémantická analýza v praxi Pravidlové algoritmy ML Algoritmy strojového učení „Matematické“ algoritmy zde uvedené jsou každý úplně jiný, spíš jde o reprezentanty různých skupin algoritmů. Algoritmy strojového učení Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové“ systémy ML Naivní Bayesovský klasifikátor Naivní Bayesovský alg. předpokládá nezávislost znaků (což nemusí být správně), ale je rychlý. P(C|F1, . . . , Fn) = P(C)·P(F1,...,Fn|C) P(F1,...,Fn) zvíře velikost barva potrava slon velký šedý býložravec slon střední šedý býložravec kráva velká černá býložravec kráva velká strakatá býložravec kráva malá strakatá býložravec kráva velká bílá býložravec vlk velký černý masožravec vlk malý šedý masožravec Algoritmy strojového učení Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové“ systémy ML Naivní Bayes pro velkého černého býložravce zvíře velikost barva potrava slon velký šedý býložravec slon střední šedý býložravec kráva velká černá býložravec kráva velká strakatá býložravec kráva malá strakatá býložravec kráva velká bílá býložravec vlk velký černý masožravec vlk malý šedý masožravec Na základě těchto dat můžeme vypočítat, že zvíře, které vidíme, bude: na 25 % slon, na 50 % kráva a na 25 % vlk, tj. P(slon) = 2 8 , P(kráva) = 4 8 a P(vlk) = 2 8 . Podmíněné pravděpodobnosti jsou P(černá barva|slon) = 0, P(černá barva|kráva) = 1 4 , P(černá barva|vlk) = 1 2 . Algoritmy strojového učení Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové“ systémy ML Naivní Bayes pro velkého černého býložravce P(C|F1, . . . , Fn) = P(C)·P(F1,...,Fn|C) P(F1,...,Fn) P(slon) = 2 8 , P(kráva) = 4 8, P(vlk) = 2 8, P(černý|slon) = 0, P(černý|kráva) = 1 4 , P(černý|vlk) = 1 2 , P(velký|slon) = 1 2 , P(velký|kráva) = 3 4 , P(velký|vlk) = 1 2 , P(býložravec|slon) = 2 2 , P(býložravec|kráva) = 4 4 , P(býložravec|vlk) = 0 P(slon|velký, černý, býložravec) = P(slon)P(velký|slon) · P(černý|slon) · P(býložravý|slon) = 0.25 · 0.25 · 0 · 1 = 0 P(kráva|velký, černý, býložravec) = P(kráva)P(velký|kráva) · P(černý|kráva) · P(býložravý|kráva) = 0.5 · 0.75 · 0.25 · 1 = 0.09375 P(kráva|velký, černý, býložravec) = P(vlk)P(velký|vlk) · P(černý|vlk) · P(býložravý|vlk) = Algoritmy strojového učení Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové“ systémy ML Algoritmy strojového učení • „pravidlové“ • rozhodovací seznamy • rozhodovací stromy • „matematické“ • pravděpodobnostní: naivní Bayesovský (Duda et Hart, 1973) • maximální entropie: (Berger, 1996) • podobnostní: k-NN ve vektorovém prostoru (Ng et Lee, 1996) • „promluvové“ • předpoklad one sense per discourse (Gale 1992) • předpoklad one sense per collocation (Yarowsky, 1995) Algoritmy strojového učení Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové“ systémy ML Algoritmus strojového učení [Yarowsky, 1995] hledáme význam s slova w • 1. vezmi všechny výskyty slova w z korpusu včetně jejich kontextů • 2. pro každý možný význam slova, vytvoř malou sadu příkladů (buď ručně, nebo pomocí kolokací) • 3. vytvoř rozhodovací seznam s pravděpodobnostmi pro další slova, která se vyskytují v kontextech • 4. aplikuj tento seznam na celý korpus (s prahem pro pravděpodobnost) • 5. nově zařazená slova obsahují další slova v kontextech • 6. algoritmus můžeme upravit pomocí zařazení předpokladu one-sense-per-discourse • 7. opakuj kroky 3–6 • 8. jakmile množiny přestanou narůstat, zastav • 9. systém je nyní natrénovaný i na jiný korpus! Algoritmy strojového učení Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové“ systémy ML Algoritmus strojového učení závisí na: • první volbě kolokací • způsobu určení pravděpodobnosti: typicky log likelihood log P(senseA,collocateA) P(senseB,collocateA) • prahu pro pravděpodobnost • správnosti předpokladu one-sense-per-discourse Algoritmy strojového učení Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové“ systémy ML Yarowsky, D. (1995). Unsupervised word sense disambiguation rivaling supervised methods. In Proceedings of the 33rd annual meeting on Association for Computational Linguistics, ACL ’95, pages 189–196, Stroudsburg, PA, USA. Association for Computational Linguistics.