WSD, pokračování Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové" systémy ML Slabiny WSD M PLIN021 Sémantická analýza v praxi OP VK Mezi bohemistikou a informatikou www. p roj e kt- i n o va. cz Zuzana Nevěřilová xpopelkOfi.muni.cz Centrum zpracování přirozeného jazyka, B203 Fakulta informatiky, Masarykova univerzita 28. března 2012 WSD, pokračování Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové" systémy ML Slabiny 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í) WSD, pokračování Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové" systémy ML Slabiny WSD M 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é" • one sense per discourse (Gale 1992) • one sense per collocation (Yarowsky, 1995) • redundance atributů o PLIN021 Sémantická analýza v praxi '—WSD, pokračování '—Algoritmy strojového učení o CN Nebudeme se tu nějak moc věnovat ML, ale přeci jen poskytnu povrchní přehled. S uvedenými termíny se totiž může počítačový lingvista poměrně často setkat, tak ať aspoň ví, na čem je. Pro lidi jsou typické (a intuitivní) spíš „pravidlové" systémy. Příkladem je hra Myslím si zvíře (protihráč se snaží zvíře z e Z uhádnout pomocí otázek, na které dostává odpovědi ano/ne). WSD, pokračování Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové" systémy ML Slabiny WSD M 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) WSD, pokračování Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové" systémy ML Slabiny WSD M Rozhodovací strom savec í žije ve vodě? žije na souši? žije v moři? žije v řece? býložravec? mäsožravec? PLIN021 Sémantická analýza v praxi 00 CN '—Pravidlové algoritmy ML 00 O i í? býk,žr,™=> maK,;r™c' Ol — Rozhodovací strom O CN 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. o PLIN021 Sémantická analýza v praxi '—Pravidlové algoritmy ML '—Rozhodovací strom o CN V této hře jsou 2 aspekty: • Jak poznám z množiny otázek O — {oi, 02,..., o„}, kde o-, je např. „Má zvíře srst?", o jaké zvíře jde? Redukcí. Pokud odpověď na o-, je „ne", vyloučím ze správných odpovědí všechna zvířata z,-, 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 vítěznému zvířeti. PLIN021 Sémantická analýza v praxi 00 CN '—Pravidlové algoritmy ML 00 O i í? býk,žr,™=> maK,;r™c' Ol — Rozhodovací strom O CN „Matematické" algoritmy zde uvedené jsou každý úplně jiný, spíš jde o reprezentanty různých skupin algoritmů. WSD, pokračování Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové" systémy ML Slabiny WSD M Naivní Bayesovský klasifikátor Naivní Bayesovský alg. předpokládá nezávislost znaků (což nemusí být správně), aleje rychlý. pŕri/- p \ _ p(c)p(f1,...,f„|c) r^L.|ri,..., rn) — p(fi,...,f„) 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ý mäsožravec vlk malý šedý mäsožravec WSD, pokračování Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové" systémy ML Slabiny WSD M Naivní Bayes pro velkého černého býložravce I 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ý mäsožravec vlk malý šedý mäsož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) = §, P(kráva) = | a P(vlk) = §. Podmíněné pravděpodobnosti jsou P(černá barva|slon) = 0, P(černá barva|kráva) = \, P(černá barva|vlk) = \. WSD, pokračování Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové" systémy ML Slabiny WSD M Naivní Bayes pro velkého černého býložravce II Podmíněné pravděpodobnosti jsou P(velkýjslon) = \, P(velký|kráva) = f, P(velký|vlk) = \. Podmíněné pravděpodobnosti jsou P(býložravec|slon) = |, P(býložravec|kráva) = |, P(býložravec|vlk) = 0. WSD, pokračování Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové" systémy ML Slabiny WSD M Naivní Bayes pro velkého černého býložravce I P(C\F, F ) - p(cyp(Fi,...,Fn\c) r^L.|ri,..., rn) — p(fi,...,f„) P(slon) = §, P(kráva) = f, P(vlk) = §, P(černý|slon) = 0, P(černýjkráva) = \, P(černýjvlk) = \, P(velkýjslon) = \, P(velký|kráva) = |, P(velký|vlk) = \, P(býložravec|slon) = |, P(býložravec|kráva) = |, 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 WSD, pokračování Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové" systémy ML Slabi Naivní Bayes pro velkého černého býložravce II P(kráva|velký, černý, býložravec) = P(vlk)P(velký|vlk) • P(černýjvlk) • P(býložravýjvlk) 0.25 0.5 0.5 0 = 0 WSD, pokračování Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové" systémy ML Slabiny WSD M 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é" • one sense per discourse (Gale 1992) • one sense per collocation (Yarowsky, 1995) • redundance atributů WSD, pokračování Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové" systémy ML Slabiny Algoritmus strojového učení [Yarowsky, 1995] I 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 WSD, pokračování Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové" systémy ML Slabiny WSD M Algoritmus strojového učení [Yarowsky, 1995] II • 8. jakmile množiny přestanou narůstat, zastav • 9. systém je nyní natrénovaný i na jiný korpus! WSD, pokračování Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové" systémy ML Slabiny WSD M Algoritmus strojového učení [Yarowsky, 1995] III kočičím emblémem. Na hlavu nespadla žádná kocka Vyjížděli jsme pro jistotu brzy, aby si náhodou kocky šťastně a já nechápala proč", protože vždy na kocky Pak za mnže a zase na nás. "Taky jdete na kočky vyťukávání čís la, aby se dozvěděla, co se těm kockám místo - místní benzinovou pumpu, jestli ty kočky nepřemístili jinam. "Nevíte, kde jsou ty kočky ty kočky, co měly být na výstavišti?" " Kočky ale nevím. U nás žádný plakát nevisel." " Kočky zaslechl a pridal se k hovoru. "Chcete vidět kočky plešatých, mouratých, černých, bílých a j iných koček se suďte l A ostatní se pridávali, brali kočky No a pan z posledního auta si vzal místo kočky " Jindy se s ní zkouším domluvit: "Hele, Kočko aby to dneska všechno dobre dopadlo..." Kočka Postupem času zjišťuji, že jsem se naučila brát Kočku tlapkách moji budoucnost ani věci příští. Kočka budoucnost ani věci příští. Kočka je zkrátka Kočka V některých domácnostech spolu kamarádí kocka volný čas, energii a peníze na záchranu psů, koček na fintění, protože to by mě nepustili v poledne neusmyslely, že se kolem nich nadával. Říkal, že nepatrí ani tak k falešným ľ" vyzvídala jsem. "Taky. Vypadá to mrtvě prihodilo. Dozvěděli jsme se akorát bolestivý nepřemístili jinam. "Nevíte, kde jsou ty , co měly být na výstavišti?" "Kočky? Zeptejte ? Zeptejte se kolegyně, já nedávno nastoupila se nevedoul" povzdechla jsem a zavrtěla 7" "Jste místní? AnoT chcemel Tam nahoře . "Chudinky, trápí je/' ozvala jsem se. pro sebe i pro sousedy, pro známě a příbuzně překvapenou Jarunu a odvezl ji k sobě do , dneska by se mi vážně hodilo, abys zůstala je Osobnost a kašle na můj osud. Trénuje jako zvířecího kamaráda, který nemá s mým je zkrátka Kočka. Ulevilo se mi tímto zjištěním . Ulevilo se mi tímto zjištěním. Cítím se a pes. V ]iných zase spolu žijímasochistka a dalších zvířat Proto tak obdivuji a (JpesJ in context(w)) then s(w,A)=l WSD, pokračování Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové" systémy ML Slabiny WSD M Algoritmus strojového učení [Yarowsky, 1995] IV if ('vlasy' in context(w)) then s(w,B)=l if ('prase' in context(w)) then s(w,A)=0.9 if ('prsa' in context(w)) then s(w,B)=l if ('oči' in context(w)) then s(w,B)=0.6 if ('člověk' in context(w)) then s(w,A)=0.8 ? 7 7 ? ? ??AAAAAAA , ? A aa A A 7 ? 7 ? ? ? A '? 7 ' ' 7 A PeASA A A ? 7 ? ? 7 A A A , ? ,77' A B ? ' ? ' ' ? 7 A A vlasy g ? d ? 7 ? ? 7 B 7 7-7? 7 B 7 7 7 if ('mazlit' in context(w)) then s(w,A)=0.7 WSD, pokračování Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové" systémy ML Slabiny WSD M Algoritmus strojového učení [Yarowsky, 1995] V if ('šaty' in context(w)) then s(w,B)=0.8 if ('boty' in context(w)) then s(w,B)=0.6 if ('kotě' in context(w)) then s(w,A)=0.8 ? 7 7 ? ? ? 7 7 ? ? ? , A A A A A A AA AAA ? A , , 7 A P^A A A r 7 A A A b ■ f ? f ? " A vlasy bb ? ? ' ? b b b 7 a 7 b ? ? 7 ? ? WSD, pokračování Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové" systémy ML Slabiny WSD M Algoritmus strojového učení: shrnutí 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! WSD, pokračování Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové" systémy ML Slabiny Algoritmus strojového učení závisí na: • první volbě kolokací • způsobu určení pravděpodobnosti: typicky log likelihood i P(senseA,collocateA) o P (sense B, colloca teA) • prahu pro pravděpodobnost • správnosti předpokladu one-sense-per-discourse WSD, pokračování Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové" systémy ML Slabiny WSD M Word Sense Disambiguation úkolem WSD je zjistit, jaký význam (z inventáře významů) má slovo ve vstupním textu ukázali jsme si dva reprezentanty metod pro WSD: Leskův algoritmus pracující se slovníkovými definicemi a příklady užití a Yarowského algoritmus strojového učení WSD, pokračovaní Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové" systémy ML Slabiny Word Sense Disambiguation: slabiny největší slabinou je inventář významů proto existují jednak snahy vytvořit dobré inventáře, jednak snahy úplně se inventářím vyhnout (Hyperlex) o PLIN021 Sémantická analýza v praxi '—Slabiny WSD '—Word Sense Disambiguation: slabiny o CN projekt HyperLex je dobrá inpirace pro BP nebo referát WSD, pokračovaní Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové" systémy ML Slabiny Word Sense Disambiguation: shrnutí • všechny algoritmy pro WSD pracují s kolokacemi • všechny pracují s určitým oknem, ve kterém kolokace sledují PLIN021 Sémantická analýza v praxi '—Slabiny WSD CN i—I O CN Word Sense Disambiguation: shrnutí Ono okno může zásadně ovlivňovat průběhy algoritmů. Není žádná „doporučená velikost" okna. Hlavním důvodem je to, co možná tušíme: různá slova mají různý „dopad" na význam promluvy. Sledováním velikosti a kvality tohoto okna (tj. kontextu) se budeme zabývat o něco později, až budeme znát také přístupy z úplně opačného konce. WSD, pokračování Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové" systémy ML Slabiny WSD M Word Sense Disambiguation: měření kvality soutěž SENSEVAL (www.senseval.org) • vyhodnocení systémů pro WSD • od roku 1998 (Senseval-1, -2, -3, Semeval-2007, -2010) • od Semeval-1 jsou úkoly různé (např. přiřazení emoce ke krátkému textu, detekce metonymie ...) • čeština (zatím) chybí • data z proběhlých kol jsou k dispozici o PLIN021 Sémantická analýza v praxi '—Měření kvality WSD '—Word Sense Disambiguation: měření kvality o CN Ne, že by bylo třeba se Senseval/Semeval účastnit. Je dobré podívat se na ručně anotovaná data (málokdy je máme). Mnoho prací se také na soutěže odvolává. PLIN021 Sémantická analýza v praxi saute SENSEVAL s.n»v>l 00 CN '—Měření kvality WSD ľdnku19>8Vn«v*l-l1-51-31S.m™ 2007 -2010) 00 O i . ätótinä [štím) chybí Ol —Word Sense Disambiguation: měření kvality i—1 O CN Cokoli ze Senseval/Semeval je inpirací pro BP nebo referát. WSD, pokračování Pravidlové algoritmy ML Matematické algoritmy ML „Promluvové" systémy ML Slabiny WSD M 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.