Word Sense Disambiguation Algoritmy WS D Strojové učení 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 8. října 2012 Word Sense Disambiguation Algoritmy WSD Strojové učení Word Sense Disambiguation Algoritmy WSD Strojové učení Word Sense Disambiguation Algoritmy WSD Strojové učení Word Sense Disambiguation Lexikální desambiguace: nalezení významu slova v daném kontextu. Pro člověka podvědomé, pro počítače „AI complete". WSD = „.. .the problem of computationally determining which "sense" of a word is activated by the use of the word in a particular context." [Agirre and Edmonds, 2006] klasifikační úloha: • jednotlivé významy tvoří třídy • podle kontextu se rozhodujeme, do kterých tříd slovo na vstupu patří předpoklady: významy jsou diskrétní a jejich konečný počet, máme nějaký inventář významů PLIN021 Sémantická analýza v praxi Pn äl^ík* advILmí n aíít*L AI Mm l«ť 00 o '—Word Sense Disambiguation í.í:'í;™ľ.d"ľ.SKi'ar''''1'"""' L2-10- '—Word Sense Disambiguation o cn AI complete = aby bylo možné vyřešit tuto úlohu, je potřeba vyřešit všechny. Výraz „AI complete" je asociací s „NP complete". Jde o třídu těžkých problémů teoretické informatiky. Těžký znamená neřešitelný v polynomiálním čase. Příklad NP-úplného problému je batoh: mám batoh o objemu x, hodnotící funkci dobře zaplněného batohu f (definovanou jakkoli, ale samozřejmě objektivně) a věci, které chci dát do batohu. Obecně je objem věcí v součtu větší než x. Jak dobře zaplnit batoh, tj. jak maximalizovat f? V praxi se při balení batohu spokojíme s dobrým výsledkem, přestože možná existuje lepší, ale ujel by nám vlak, než bychom na něj přišli. Pokud se nespokojíme s přibližným výsledkem, musíme zkusit všechny možnosti. Word Sense Disambiguation Algoritmy WSD Strojové učení Word Sense Disambiguation: aplikace • strojový překlad - machine translation (MT) • inteligentní vyhledávání - information retrieval (IR) • inteligentní korektor překlepů PLIN021 Sémantická analýza v praxi '—Word Sense Disambiguation o cn i—i o cn Word Sense Disambiguation: aplikace Ukázky toho, když počítačový program předpokládá jiný význam? Všichni známe strojově přeloženou Wikipedii, kde byl např. Ludvík dodávka Beethoven (ad 1). Známe také situaci, kdy hledáme na Google nějaký mnohoznačný termín a většinu stránek ignorujeme (můžeme zkusit hledat „evropský los", ad 2). Kdybychom tak měli korektor, který by odhalil chyby typu „Palivo z potopené Concordie budou přečerpávat do speciálních palivových lidí." (ad 3)... Word Sense Disambiguation Algoritmy WS D Word Sense Disambiguation: přístupy Strojové učení zpravidla ignorují teoretické, psychologické, logické aj. aspekty významu • hloubkové (zahrnující znalosti o jazyce i o světě) • povrchové přístupy (bez dalších znalostí, počítají s okolím) PLIN021 Sémantická analýza v praxi '—Word Sense Disambiguation '—Word Sense Disambiguation: přístupy o cn V současnosti mají vrch povrchové přístupy, protože jsou lepší než nic a relativně levné. Hloubkové přístupy nejsou funkční, protože si žádají zpracovat a formalizovat příliš mnoho dat, což je zdlouhavé a drahé. Hloubkové přístupy jsou funkční v omezených doménách, protože tam je „svět" malý a experty se vyplatí platit. Word Sense Disambiguation Algoritmy WS D Strojové učení Word Sense Disambiguation: přístupy historický přístup („expertní"): v jakých kontextech může slovo nabývat jakých významů? kohoutek • botanika: rostlina • chovatelství: lopatková kost • technické vybavení budov: ruční uzávěr PLIN021 Sémantická analýza v praxi '—Word Sense Disambiguation '—Word Sense Disambiguation: přístupy Expertní přístup je příliš náročný: kdo dokáže najít a vyjmenovat všechny možné kontexty (které navíc stále přibývají)? Word Sense Disambiguation Algoritmy WSD Strojové učení Algoritmy založené na znalostech historický start: strojově čitelné slovníky (Machine Readable Dictionaries) reprezentant: Leskův algoritmus (1986) = slovo w, jehož okolí sdílí nejvíc slov s definicí (nebo s příklady užití) /tého významu, má význam s; [Kilgarriff and Rosenzweig, 2000] Word Sense Disambiguation Algoritmy WS D Strojové učení Naivní Leskův algoritmus: kočka (SSJČ) 1. malá kočkovitá šelma, chovaná v domácnostech, na venkově zvi. pro hubení myší; kočka domáci (zool.); šedivá, černá, tříbarevná k.; hladká srst kočky; k. mňouká, přede; k. číhá na myš; k. chytá ptáky; angorská k.; být falešný, úlisný jako k.; přen. expr. je to k. falešník; to děvče je k. lichotné, úlisné; [x] jsou na sebe jako pes a k. nenávidí se... 2. malá n. středně velká šelma s hustým kožichem; zool. rod Felis: k. plavá; k. divoká; k. domáci 3. samice kočkovité šelmy vůbec; rysí k.; lví k.; expr. každá kočkovitá šelma vůbec (tygr, levhart aj.) 4. ob. kožišina na límci, kolem krku n. ramen 5. kocovina (Haš.) 6. věc připomínající někt. vlastnost u kočky: bot. velký trs ostřic vystupující z rašeliniště (na blatech); tech. pojízdný vozík jeřábu se zdvihacím ústrojím 7. druh důtek; devítiocasá k. Word Sense Disambiguation Algoritmy WS D Strojové učení Naivní Leskův algoritmus: vstup Aminokyselina DL-methionin okyseluje moč, čímž chrání močové ústrojí psů i koček (důležitá vlastnost zvláště u kasírovaných jedinců). {aminokyselina, DL-methionin, okyselovat, moč, čímž, chránit, močový, ústrojí, pes, i, důležitý, vlastnost, zvláště, u, kastrovaný, jedinec} {aminokyselina, což, DL-methionin, důležitý, chránit, i, jedinec, kastrovaný, moč, močový, okyselovat, pes, u, ústrojí, vlastnost, zvláště} Word Sense Disambiguation Algoritmy WS D Strojové učení Leskův algoritmus: naivní {aminokyselina, což, DL-methionin, důležitý, chránit, i, jedinec, kastrovaný, moč, močový, okyselovat, pes, u, ústrojí, vlastnost, zvláště} 1: {a, angorský, být, černý, číhat, děvče, domácí, domácnost, expresivně, falešník, falešný, hladký, hubení, chovaný, chytat, jako, kočkovitý, lichotný, malý, mňoukat, myš, na, nenávidět, pes, pro, přeneseně, příst, pták, se, srst, šedivý, šelma, to, tříbarevný, úlisný, v, venkov, zoologicky, zvláště} 2: {divoký, domácí, Felis, hustý, kožich, malý, nebo, plavý, rod, s, středně, šelma, velký, zoologicky} 6: {bláto, botanicky, jeřáb, na, některý, ostřice, pojízdný, připomínající, rašeliniště, s, technicky, trs, u, ústrojí, věc, velký, vozík, vlastnost, vystupující, z, zdvihací} 7: {devítiocasá, druh, důtky} Word Sense Disambiguation Algoritmy WS D Strojové učení Leskův algoritmus: naivní {aminokyselina, což, DL-methionin, důležitý, chránit, i, jedinec, kastrovaný, moč, močový, okyselovat, pes, u, ústrojí, vlastnost, zvláště} Di = {pes,zvláště} D2 D7 {} {} {} {} PLIN021 Sémantická analýza v praxi '—Algoritmy WSD -Leskův algoritmus: naivní o cn Naivní L. algoritmus určil, že význam slova kočka v uvedené větě je 6. Je to spíš náhoda podpořená tím, že u významů 1 a 6 v SSJČ také nejvíc textu. Jakou roli hrají v určení významu slova spojky a předložky? Jak odfiltrovat z definic a příkladů užití slova, která v určení významu slova nehrají roli? viz dál Word Sense Disambiguation Algoritmy WS D Strojové učení Inverzní četnost v dokumentu [Manning et al., 2008] Term frequency tf - četnost znaku í v určitém dokumentu Počet dokumentů N Document frequency dft - počet dokumentů, ve kterých se vyskytuje í Inverse document frequency idft = log Příklad: mějme dokumenty: {Máma mele maso}, {Ema maso solí, z masa bude oběd}, {Máma má Emu}, {Ema má mámu i oběd} A/ = 4 A/ = 4 dft(maso) = 2 dft(Ema) = 3 idft(maso) = log | idft(Ema) = log | PLIN021 Sémantická analýza v praxi '—Algoritmy WSD '—Inverzní četnost v dokumentu [Manning et al., 2008] o cn Proč nepočítáme s frekvencí znaku tf? V krátkých dokumentech je tf nižší než v dlouhých, neznamená to ale, že je tam t méně důležité. Co vyjadřuje idftl Čím běžněji se slovo vyskytuje, tím je idft nižší. Co když je df — 0? Používá se zvýšení jmenovatele (přičte se 1, aby ve jmenovateli nebyla 0). K čemu se používá tf? Dohromady s idft se používá při výpočtu míry (váhy) TF-IDF (počítá se jako násobek tf x idft. Čím vyšší TF-IDF nějaké slovo v souboru dokumentů má, tím víc se předpokládá, že má vyšší relevanci. Word Sense Disambiguation Algoritmy WS D Strojové učení Leskův algoritmus: jednoduchý pro každý význam s; slova w. nastav váhu v na 0: v{s;) := 0 najdi množinu slov O v okolí slova w pro každé slovo oj z okolí O pro každý význam s; pokud se oj nachází v definici n. př. užití D; přičti v(o) k v(s;): v(s;) := v(s;) + v(o) vyber s; s nejvyšším v(s;): return max(v(si)) váha slova v(o) = idf0 Word Sense Disambiguation Algoritmy WS D Strojové učení Leskův algoritmus: jednoduchý 1. malá kočkovitá šelma, chovaná v domácnostech, na venkově zvi. pro hubení myší; kočka domáci (zool.); šedivá, černá, tříbarevná k.; hladká srst kočky; k. mňouká, přede; k. se plíží, číhá na myš; k. chytá ptáky; angorská k.; být falešný, úlisný jako k.; přen. expr. je to k. falešník; to děvče je k. lichotné, úlisné; [x] jsou na sebe jako pes a k. nenávidí se... 2. malá n. středně velká šelma s hustým kožichem; zool. rod Felis: k. plavá; k. divoká; k. domácí 3. samice kočkovité šelmy vůbec; rysí k.; lví k.; expr. každá kočkovitá šelma vůbec (tygr, levhart aj.) 4. ob. kožišina na límci, kolem krku n. ramen 5. kocovina (Haš.) 6. věc připomínající někt. vlastnost kočky: bot. velký trs ostřic vystupující z rašeliniště (na blatech); tech. pojízdný vozík jeřábu se zdvihacím ústrojím 7. druh důtek; devítiocasá k. Word Sense Disambiguation Algoritmy WS D Strojové učení Leskův algoritmus: jednoduchý Aminokyselina DL-methionin okyseluje moč, čímž chrání močové ústrojí psů i koček (důležitá vlastnost zvláště u kasírovaných jedinců). i D; v{sí) 1 Di = {pes(l,525),zvláště(l,83)} 3,355 2 D2 = {} 0 3 D3 = {} 0 4 D4 = {} 0 5 D5 = {} 0 6 D6 = {u(0,363),vlastnost(l,79),ústrojí(2,32)} 3,173 7 D7 = {} 0 Word Sense Disambiguation Algoritmy WS D Strojové učení 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. PLIN021 Sémantická analýza v praxi BSSSSSKÄBSS: 00 I_. . _ . 'uľ'ľ'JIľ'ľb.l k*.- „- ii o —Strojové uceni □..,«»,.!j,b.,k>», "ľ i .ír;:ľ"L,.„ cn —Algoritmy strojového učení ^„,a-'„a,z„„'.,..,„z, ľ~) Typickí baby strajavíba bíímjsau któdkiíníú cn Definice ML může vypadat podivně, je to ale tím, že je těžké říct, co je to učení. Strojové učení a „lidské" učení má společné rysy - má určitý cíl, opakování, v jeho průběhu by mělo docházet ke zlepšení ... Word Sense Disambiguation Algoritmy WSD Strojové učení Další informace (nejen) o strojovém učení www.coursera.org Word Sense Disambiguation Algoritmy WS D Strojové učení □ Agirre, E. and Edmonds, P. (2006). Word sense disambiguation: algorithms and applications. Text, speech, and language technology. Springer. II Kilgarriff, A. and Rosenzweig, J. (2000). English senseval: Report and results. In Proceedings of the 2nd International Conference on Language Resources and Evaluation, pages 1239-1244. 1 Manning, C. D., Raghavan, P., and Schtze, H. (2008). Introduction to Information Retrieval. Cambridge University Press, New York, NY, USA.