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 29. října 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? 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 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.