Víceznačnost, granularita
Redundance
Word Sense Disambiguation
Algoritmy WSD
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
4. března 2013
Víceznačnost, granularita Redundance Word Sense Disambiguation Algoritmy WSD
Víceznačnost, granularita
Redundance
Word Sense Disambiguation
Algoritmy WSD
Víceznačnost, granularita
Redundance
Word Sense Disambiguation
Algoritmy WSD
Je víceznačnost problém v N LP?
rychlý =4> fast auto car
rychlé auto =4> fast car
vysoký =4> high škola school
vysoká škola =4> university?
Víceznačnost, granularita
Redundance
Word Sense Disambiguation
Algoritmy WSD
Granularita významu (sense): kočka
• 2. malá n. středně velká šelma s hustým kožichem; zool. rod Felis
• 1. malá kočkovitá šelma, chovaná v domácnostech
• 3. samice kočkovité šelmy vůbec
• 4. ob. kožišina na límci, kolem krku n. ramen
• 6. věc připomínající někt. vlastnost kočky
• 5. kocovina (Haš.)
• 7. druh důtek
Víceznačnost, granularita Redundance Word Sense Disambiguation Algoritmy WSD
Jak stanovit kriteria pro „tu správnou" granularitu?
podle syntaktických kritérií:
• Lord zanechaly závěti všechen svůj majetek místnímu sirotčinci.
• Student zanechal studia podáním písemné žádosti.
Víceznačnost, granularita
Redundance
Word Sense Disambiguation
Algoritmy WSD
Jak stanovit kriteria pro „tu správnou" granularitu?
podle sémantických kritérií:
• abstraktní x konkrétní
• životný x neživotný
• člověk x zvíře
• emoce
• doména
Frekvence užívání slova v daném významu
holub a opilý živý tulák, Mizerná pouliční kočka je zkoumavě pozorovala, Jako by si spojoval esba Lukáš Fibrich (21. 3. </p><p> Město pro  kocku   Asi málokdo by hledal nej větší'světové
hledal nej větší'světově muzeum věnovaně kočkám právě na Borneu v Malajsii. Pokud někdy ilajsii. Pokud někdy náhodou navštívíte město  Kočka   , pak si tuhle atrakci rozhodně nenechte , bude obrovské sousoší tvořené několika kočkami , Vydáte-li se procházkou po nábřeží řeky směrem, záhy narazíte na další kočičí sochy. Kočkami - těmi umělými i těmi živými - je město . Důvod je jednoduchý - Kuching je město kockám zaslíbené. </pxp> NEOBVYKLÉ MUZEUM </p
mívají krásné husté a delší vlasy, Jako kočky předou, když je budete hladit, česat, mírně smyslem pro humor obklopují se zvěří - psi, kočky , drobné šelmy, tak se staňte znalci tohoto dáte za pravdu, že letušky byly opravdu kočky , U American Airlines nic takového nečekejte děkuji Katko za prima plavečky, já budu kočka , jako vždy super obchůdek, jen chválím
Víceznačnost, granularita Redundance Word Sense Disambiguation Algoritmy WSD
Redundance v přirozeném jazyce
Tto vtě určtě porozumte přestože nní správná.
Studentky se na semináři nudily. Myslete dopředu na finanční zajištění vlastního pohřbu. Ušetříte tím starosti svým blízkým.
Víceznačnost, granularita
Redundance
Word Sense Disambiguation
Algoritmy WSD
Redundance v přirozeném jazyce
na úrovni hlásek (některé hláskové sekvence se v daném jazyce nevyskytují)
• na syntaktické úrovni (shoda prísudku s podmětem)
• na úrovni významů (pleonasmy, tautologie)
□
Víceznačnost, granularita Redundance Word Sense Disambiguation Algoritmy WSD
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		
o	'—Word Sense Disambiguation		
o	i	""""■"bl"	
oó	—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.
Víceznačnost, granularita Redundance Word Sense Disambiguation Algoritmy WSD
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
Word Sense Disambiguation: aplikace
o
CN
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)...
Víceznačnost, granularita Redundance Word Sense Disambiguation Algoritmy WSD
Word Sense Disambiguation: přístupy
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)
o
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.
Víceznačnost, granularita
Redundance
Word Sense Disambiguation
Algoritmy WSD
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í)?
Víceznačnost, granularita Redundance Word Sense Disambiguation Algoritmy WSD
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]
Víceznačnost, granularita
Redundance
Word Sense Disambiguation
Algoritmy WSD
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ácí (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á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 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.
Víceznačnost, granularita
Redundance
Word Sense Disambiguation
Algoritmy WSD
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ě}
Víceznačnost, granularita Redundance
Leskův algoritmus: naivní
Word Sense Disambiguation
Algoritmy WSD
{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}
Víceznačnost, granularita
Redundance
Word Sense Disambiguation
Algoritmy WSD
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 D3 D4 D5 De D7
{} {} {} {}
o
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
Víceznačnost, granularita
Redundance
Word Sense Disambiguation
Algoritmy WSD
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 |
o
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.
Víceznačnost, granularita
Redundance
Word Sense Disambiguation
Algoritmy WSD
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;): retům max{v{s;))
váha slova v{o) = /cf/ó
Víceznačnost, granularita
Redundance
Word Sense Disambiguation
Algoritmy WSD
Leskův algoritmus: jednoduchý
1. malá kočkovitá šelma, chovaná v domácnostech, na venkově zvi. pro hubení myší; kočka domácí (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.
Víceznačnost, granularita
Redundance
Word Sense Disambiguation
Algoritmy WSD
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
Víceznačnost, granularita
Redundance
Word Sense Disambiguation
Algoritmy WSD
□ Agirre, E. and Edmonds, P. (2006).
Word sense disambiguation: algorithms and applications. Text, speech, and language technology. Springer.
Hi 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.
Q Manning, C. D., Raghavan, P., and Schtze, H. (2008). Introduction to Information Retrieval. Cambridge University Press, New York, NY, USA.