Pravidlové algoritmy ML Matematické algoritmy ML Slabiny WSD Měření kvality WSD Formalismy pro reprezentaci 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 29. října 2012 Pravidlové algoritmy ML Matematické algoritmy ML Slabiny WSD Měření kvality WSD Formalismy pro reprezentaci 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ů Pravidlové algoritmy ML Matematické algoritmy ML Slabiny WSD Měření kvality WSD Formalismy pro reprezentaci 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) Pravidlové algoritmy ML Matematické algoritmy ML Slabiny WSD Měření kvality WSD Formalismy pro reprezentaci 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 Ol CN '—Pravidlové algoritmy ML Ó i—1 i žij.vman? q„b? hybí,™=? m*^™:' Ol — Rozhodovací strom O CN „Matematické" algoritmy zde uvedené jsou každý úplně jiný, spíš jde o reprezentanty různých skupin algoritmů. Pravidlové algoritmy ML Matematické algoritmy ML Slabiny WSD Měření kvality WSD Formalismy pro reprezentaci 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ů Pravidlové algoritmy ML Matematické algoritmy ML Slabiny WSD Měření kvality WSD Formalismy pro reprezentaci 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 Pravidlové algoritmy ML Matematické algoritmy ML Slabiny WSD Měření kvality WSD Formalismy pro reprezentaci 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ý 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) = \. Pravidlové algoritmy ML Matematické algoritmy ML Slabiny WSD Měření kvality WSD Formalismy pro reprezentaci Naivní Bayes pro velkého černého býložravce pŕri/- p \ _ p(c)p(f1,...,f„|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 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 Pravidlové algoritmy ML Matematické algoritmy ML Slabiny WSD Měření kvality WSD Formalismy pro reprezentaci Shrnutí: 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ů Pravidlové algoritmy ML Matematické algoritmy ML Slabiny WSD Měření kvality WSD Formalismy pro 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í Pravidlové algoritmy ML Matematické algoritmy ML Slabiny WSD Měření kvality WSD Formalismy pro reprezentaci 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, [Véronis, 2004]) Pravidlové algoritmy ML Matematické algoritmy ML Slabiny WSD Měření kvality WSD Formalismy pro 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 cn L-Slabiny WSD ó I cn —Word Sense Disambiguation: shrnutí o cn 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. Pravidlové algoritmy ML Matematické algoritmy ML Slabiny WSD Měření kvality WSD Formalismy pro reprezentaci 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 PLIN021 Sémantická analýza v praxi '—Měření kvality WSD -Word Sense Disambiguation: měření kvality 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 Ol CN '—Měření kvality WSD ľdnku19>8Vn«v*l-l1-51-31S.m™ 2007 -2010) Ó i—1 i Ol —Word Sense Disambiguation: měření kvality •J--'"1'1*1"'™"—id i—1 O CN Cokoli ze Senseval/Semeval je inpirací pro BP nebo referát. Pravidlové algoritmy ML Matematické algoritmy ML Slabiny WSD Měření kvality WSD Formalismy pro reprezentaci Formalismy pro reprezentaci znalostí WSD je zajímavá a „klasická" disciplína, řada vědců ale WSD odmítá kvůli uvedeným slabinám. Navíc, WSD je kvantitativní analýza, neříká nic o významu. Při studiu významu se chceme posunout dál, skutečně k jádru věci. Chceme pracovat nejen se slovy, ale i se znalostmi: jazykovými i obecnými... PLIN021 Sémantická analýza v praxi 10-29 '—Formalismy pro reprezentaci znalostí 2012- '—Formalismy pro reprezentaci znalostí Může to vypadat, že dost bylo matematiky. Na chvíli si od ní odpočineme a osvěžíme termíny z lingvistiky. Časem se k matematice zase vrátíme. Pravidlové algoritmy ML Matematické algoritmy ML Slabiny WSD Měření kvality WSD Formalismy pro reprezentaci Sémantické rysy (semantic features) matka = FEMALE + ADULT + HAS CHILD batole = HUMAN - ADULT • sémantické rysy jsou „atomy" významu • sémantické rysy jsou distinktivní rysy • význam je definován pomocí s. rysů a pravdivostních podmínek [Croft and Cruse, 2004] Pravidlové algoritmy ML Matematické algoritmy ML Slabiny WSD Měření kvality WSD Formalismy pro reprezentaci Sémantické rysy: synonymie výraz fit procházet rysy MOTION MOTION ON FOOT ON FOOT SELF-PROPELLED SELF-PROPELLED MEDIUM VELOCITY MEDIUM VELOCITY Pravidlové algoritmy ML Matematické algoritmy ML Slabiny WSD Měření kvality WSD Formalismy pro reprezentaci Sémantické rysy: antonymie výraz fit běžet rysy MOTION MOTION ON FOOT ON FOOT SELF-PROPELLED SELF-PROPELLED MEDIUM VELOCITY HIGH VELOCITY Pravidlové algoritmy ML Matematické algoritmy ML Slabiny WSD Měření kvality WSD Formalisi Sémantické rysy: problém s antonymií výraz fit letět střemhlav rysy MOTION MOTION ON FOOT ON WINGS SELF-PROPELLED GRAVITY-PROPELLED MEDIUM VELOCITY HIGH VELOCITY PLIN021 Sémantická analýza v praxi oj '—Sémantické rysy ó *7 I cn —Sémantické rysy: problém s antonymií o cn antonymie nebo raději obecně opozitnost? Pravidlové algoritmy ML Matematické algoritmy ML Slabiny WSD Měření kvality WSD Formalismy pro reprezentaci Sémantické rysy: problém s antonymií výraz fit loudat se rysy MOTION MOTION ON FOOT ON FOOT SELF-PROPELLED SELF-PROPELLED MEDIUM VELOCITY LOW VELOCITY PLIN021 Sémantická analýza v praxi Ol '—Sémantické rysy 1 J* CN Ó LED SELF^PROPELLED 2012-1 '—Sémantické rysy: problém s antonymií Sémantické rysy (jako všechny ostatní teorie) mohou být užitečné. Pří jejich formálním uchopení narazíme na problémy: kolik rysů má každý výraz? Jak poznáme, které jsou podstatné a které ne? Trošku to připomíná problém, jak najít vhodnou otázku ve hře Myslím si zvíře... Pravidlové algoritmy ML Matematické algoritmy ML Slabiny WSD Měření kvality WSD Formalismy pro i Výběrová omezení (selectional restrictions) slouží pro desambiguaci závislosti větných členů [Allen, 1995, kap. 10.1] • Koupila jsem si pletenou čepici a šálu. • Koupila jsem si nealkoholické pivo a křupky. pletená šála - OK, nealkoholické křupky - NOT OK Pravidlové algoritmy ML Matematické algoritmy ML Slabiny WSD Měření kvality WSD Formalismy pro re Výběrová omezení (selectional restrictions) slouží pro desambiguaci závislosti vetných členu [Alien, 1995, kap. 10.1] Rodinné domy postaví malé stavební firmy. AGENT = rodinné domy THEME = malé stavební firmy AGENT = malé stavební firmy THEME = rodinné domy (AGENT postavit PERSON | INSTITUTION) (THEME postavit BUILDING) rodinné malé stavební Pravidlové algoritmy ML Matematické algoritmy ML Slabiny WSD Měření kvality WSD Formalismy pro reprezentaci i Allen, J. (1995). Natural Language Understanding (2nd ed.). Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, USA. i Croft, W. and Cruse, D. (2004). Cognitive linguistics. Cambridge textbooks in linguistics. Cambridge University Press. □ Veronis, J. (2004). Hyperlex: Lexical cartography for information retrieval. In Computer Speech and Language: Special Issue on Word Sense Disambiguation, page 23.