Zkoumání kontextu Odbočka k lineární algebře Kontextové vektory Odbočka k teorii množin Matematický model výzi 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 10. května 2012 Zkoumání kontextu Odbočka k lineární algebře Kontextové vektory Odbočka k teorii množin Matematický model výzi Zkoumání kontextu Odbočka k lineární algebře Kontextové vektory Odbočka k teorii množin Matematický model významu Zkoumání kontextu Odbočka k lineární algebře Kontextové vektory Odbočka k teorii množin Matematický Kontextové vektory [Schütze, 1998] Významy jsou spojeny vztahy. Zdá se, že některé významy jsou „víc spojeny" než jiné. Např. „pták" je víc spojený s „peří" než se „strom". Problémem WSD je inventář významů, jeho kvalita, granularita a aktuálnost. Inventářům se můžeme vyhnout, pokud potřebujeme „pouze" zjistit, která slova jsou použita ve stejném významu, aniž bychom věděli, jaký význam to je. Algoritmus rozlišení kontextových skupin (context group discrimination) Výsledkem jsou výskyty víceznačného slova v různých shlucích. Každé slovo, kontext i shluk jsou reprezentovány vektorem v mnoharozměrném vektorovém prostoru. Zkoumání kontextu Odbočka k lineární algebře Kontextové vektory Odbočka k teorii množin Matematický model výzi Vektor, prostor, vzdálenost vektor: • velikost (stejně jako číslo) • směr (na rozdíl od čísla) zobrazuje se jako šipka (o určité délce a určitým směrem) ©Matematika polopatě 2006-2011 Zkoumání kontextu Odbočka k lineární algebře Kontextové vektory Odbočka k teorii množin Matematický model výzi Vektor, prostor, vzdálenost vektor: • u vektoru není definováno, kde začíná • důležitý je skutečně jen směr a délka • můžeme proto kreslit vektory začínající od nuly (přesněji z bodu 0) 2 -_-_i-_-_iF_______ 1 0 Ä' /'A ■ / , -1 -1 G @Matematika polopatě 2006-2011 PLIN021 Sémantická analýza v praxi '—Odbočka k lineární algebře o 1—1 I bodu 0) 2006-3011 12-05- '—Vektor, prostor, vzdálenost o cn tzn. vektor je množina Zkoumání kontextu Odbočka k lineární algebře Kontextové vektory Odbočka k teorii množin Matematický mi Vektor, prostor, vzdálenost vektor: • se označuje malým písmenem (typicky u nebo v) • se zapisuje jako n-tice v = (xi,x2,... ,x„) • xi,... ,x„ jsou souřadnice šipky (konce vektoru), kdyby začínal v bodě 0 0 _ JT 1 C 2 ,3 4 ©Matematika 2006-2011 polopatě PLIN021 Sémantická analýza v praxi '—Odbočka k lineární algebře '—Vektor, prostor, vzdálenost vektor na obrázku je v = (1,1) Zkoumání kontextu Odbočka k lineární algebře Kontextové vektory Odbočka k teorii množin Matematický model výzi Vektor, prostor, vzdálenost prostor: • „místo", kam umísťujeme vektory • prostor má dimenzi • dimenze je n z předchozího snímku PLIN021 Sémantická analýza v praxi 2 '—Odbočka k lineární algebře lÓ ° I cn —Vektor, prostor, vzdálenost o cn Jednorozměrný prostor je např. škála na teploměru, dvourozměrný prostor je ten, který byl na obrázcích, trojrozměrný se ještě dá nakreslit pomocí perspektivy. Vícerozměrné prostory si nemůžeme představit, ale nevadí to, pokud rozumíme tomu, co je vektor - n-tice čísel vyjadřující směr a vzdálenost od bodu 0. Zkoumání kontextu Odbočka k lineární algebře Kontextové vektory Odbočka k teorii množin Matematický mi Vektor, prostor, vzdálenost velikost vektoru: • velikost vektoru v je vzdálenost mezi jeho začátkem a koncem • vzdálenost můžeme počítat několika způsoby • nejkratší spojnice v rovině se nazývá euklidovská vzdálenost (počítáme Pythagorovou větou) • jiný způsob výpočtu vzdálenosti je např. Manhattanská vzdálenost ©Matematika polopatě 2006-2011 0 01 O cn PLIN021 Sémantická analýza v praxi '—Odbočka k lineární algebře '—Vektor, prostor, vzdálenost 3 Manhattanská vzdálenost je dobrý příklad toho, že vzdálenost není vždy euklidovská (a že je to pro nás dokonce mnohdy přirozené). Představme si, že síť v souřadném systému (šedé čárkované čáry) je mapa Manhattanu. Čáry jsou ulice, bílé čtverce jsou bloky domů. Jaká ja nejkratší vzdálenost mezi křižovatkami A a B? Blokem domů samozřejmě procházet nemůžeme, je to tedy 2. M. vzdálenost v našem případě neslouží pro nic jiného než pro ilustraci toho, že termín vzdálenost není tak jednoznačný, jak bychom si možná mysleli. Proto pro tu „naši" vzdálenost používáme přesný termín euklidovská vzdálenost. Zkoumání kontextu Odbočka k lineární algebře Kontextové vektory Odbočka k teorii množin Matematický model výzi Vektor, prostor, vzdálenost velikost vektoru v = (xi,X2) se značí \ v\ Pythagorova věta: a2 + b2 = c2 I v\ vW + (*2)2 velikost vektoru v = (xi, X2,..., x„) v n-rozměrném prostoru W\ = V(xi)2 + --- + (Xn)2 = V ;=0 @Matematika polopatě 2006-2011 PLIN021 Sémantická analýza v praxi '—Odbočka k lineární algebře mm o if) §•—. j. |. B O cň '—Vektor, prostor, vzdálenost ■0* ©Matematika i.i.bpatí 5006-5011 o cn velikost uje odmocnina z 2 Zkoumání kontextu Odbočka k lineární algebře Kontextové vektory Odbočka k teorii množin Matematický model výzi Vektor, prostor, vzdálenost Dva vektory u = (xi,..., x„) a v (yi, • • • ,Yn) svírají úhel a cos a = kde u ■ v = xiyi +x2y2 H-----hxnyn n ;'=1 2 i i 1 U / !B - "1 1 A ---1--- 0 □ 1 1 1 2 3 ©Matematika polopatě 2006-2011 PLIN021 Sémantická analýza v praxi 2 '—Odbočka k lineární algebře lÓ ° I cn —Vektor, prostor, vzdálenost o V dalším nás bude úhel zajímat m Zkoumání kontextu Odbočka k lineární algebře Kontextové vektory Odbočka k teorii množin Matematický Vektor jako reprezentant výskytu slova v doméně Mějme n domén d; G V\i = 1,..., n (např. zoologie, vaření, atmosféra, vojenské letectví). Každé slovo w je reprezentováno vektorem v = (xi,X2,... ,xn). Vyskytuje-li se slovo w v textech z domény d;, pak x; přiřadíme četnost w v doméně d\. Četnost můžeme vyjádřit více způsoby (které už známe z WSD): • počet výskytů w • počet dokumentů, ve kterých se w vyskytuje • 0 pokude se w v d; nevyskytuje, jinak 1 Zkoumání kontextu Odbočka k lineární algebře Kontextové vektory Odbočka k teorii množin Matematický Vektor jako reprezentant výskytu slova v doméně Mějme 4 domény d; G V\i vojenské letectví). ,4 (zoologie, vaření, atmosféra, Každé slovo w je reprezentováno vektorem v = (xi, x2, X3, X4). Získáme potom vektory: \/i (buňka) = (10,0,0,5) i/2(tkáň) = (9,0,0,0) \v2\ i/3(let) = (4,0,l,10) ^(množství) = (4,5,4, 5) | V41 vs(pára) = (0,6,5,1) |i/5| V100 + 25 = 11,18 VŠI = 9 V16 + 1+ 100 = 10,81 V16 + 25 + 16 + 25 = 9,06 V36 + 25 + 1 = 7, 87 Zkoumání kontextu Odbočka k lineární algebře Kontextové vektory Odbočka k teorii množin Matematický Vektor jako reprezentant výskytu slova v doméně vi (buňka) = (10,0,0,5) kil = 11,18 1/2 (tkáň) = (9,0,0,0) = 9 i^(let) = (4,0,1,10) = 10,81 \/4 (množství) = (4,5,4,5) l^l = 9,06 vs(pára) = (0,6,5,1) l"5l = 7,87 aro-Wi/, — arrrnc vlv2 — arrrnc 10 9+° °+° °+5 0 — arccos^i, v2) — arccos j^pj^j — arccos-n 189-— arccos 1qq062 = arccos 0,89 = 27° a VI 1/2 V3 1/4 V5 VI 0 27° 42,2° 50° 86,6° V2 27° 0 68° 63,9° 90° V3 42,2° 68° 0 44,4° 80° l/4 50° 63,9° 44,4° 0 40° V5 86,6° 90° 80° 40° 0 Zkoumání kontextu Odbočka k lineární algebře Kontextové vektory Odbočka k teorii množin Matematický model výzi Kontextové vektory [Schütze, 1998] Algoritmus: 1. vytvoř matici spoluvýskytů 2. spočítej kontextový vektor pro každý kontext 3. sdruž kontextové vektory do shluků [Král, 2006] Zkoumání kontextu Odbočka k lineární algebře Kontextové vektory Odbočka k teorii množin Matematický model výzi Kontextové vektory [Schütze, 1998] Slova „matice" se není třeba děsit. Pokud zapíšeme naše výše uvedené vektory \/i (buňka) = (10,0,0,5) i/2 (tkáň) = (9,0,0,0) i/3(let) = (4,0,l,10) i/4(množství) = (4,5,4,5) i/5(pára) = (0,6,5,1) do tabulky, získáme právě matici spoluvýskytů: 1/1/ zoologie vaření atmosféra vojenské letectví buňka 10 0 0 5 tkáň 9 0 0 0 let 4 0 1 10 množství 4 5 4 5 pára 0 6 5 1 PLIN021 Sémantická analýza v praxi '—Kontextové vektory -Kontextové vektory [Schütze, 1998] Matice je jednoduše řečeno tabulka, která vyjadřuje souvislost toho, co na řádcích, s tím, co je ve sloupcích. Zkoumání kontextu Odbočka k lineární algebře Kontextové vektory Odbočka k teorii množin Matematický Kontextové vektory: matice spoluvýskytů Matice spoluvýskytů je tabulka, kde řádky odpovídají znakům a sloupce dimenzím. Čísla v buňkách odpovídají počtu spoluvýskytů znaku a dimenze v tomtéž kontextu. Jaká slova vybrat jako znaky? Ideálně všechna, většina z nich nebude mít žádný vliv (v buňkách budou nuly) a budeme je moci vypustit. Atmosféra Havárie Atmosphere Crash ránafbang 0 4 ráno/moniing 6 0 ozvai/resound 1 5 ocekávai/expect 2 2 Zkoumání kontextu Odbočka k lineární algebře Kontextové vektory Odbočka k teorii množin Matematický model výzi Kontextové vektory: výpočet Kontextový vektor získáme jako průměrný vektor všech výskytů všech slov v daném kontextu. ■É A Atmosféra Havárie Asmosphere Crash rána/bang 0 4 ránoJmoming 6 0 ozvat/resound 1 5 očekávat/expect 2 2 ',Ván'a Po siSíce se ozvala rana. ozvat i očekávat Nad ránem očekáváme srážky, ráno \-i-1-1—H-I- Atmosféra Po srážce se ozvala(l,5) rána(0'4)+(6'0) = (3,2). (l25l+í3221 = (2 3l) Nad ránem(6,0) očekáváme(2,2) srážky. (6'0)+(2'2) = (4,1) Zkoumání kontextu Odbočka k lineární algebře Kontextové vektory Odbočka k teorii množin Matematický model výzi Kontextové vektory: shlukování (klastrování) 1. Vyber k centroidů (těžišť) 2. Každý kontextový vektor přiřaď k nejbližšímu centroidů 3. Centroid přepočítej podle přítomných vektorů 4. Opakuj kroky 2-3, dokud se shluky neustálí Výsledek pro slovo srážka: Cluster: ozbrojený daň mzda teplota oblačnost zahynout voják vlak armed tax wage temperature cloudiness deaden soldier train 1 0.07 0.01 0.01 0.01 0.00 0.02 0.04 0.01 2 0,01 0.16 0.20 0.01 0.00 o.ot 0.01 0.00 3 0.02 0.01 0.01 0.12 0.08 0.01 0.01 0,00 4 0,03 0.01 0.01 0.01 0.00 0.08 0.02 0.04 □ Zkoumání kontextu Odbočka k lineární algebře Kontextové vektory Odbočka k teorii množin Matematický Množina, n-tice, relace, zobrazení, funkce Množina A = {xi,... ,x„} soubor prvků. Množina je určena svými prvky. Množiny mohou být prvky jiných množin. Součin A x B je množina (uspořádaných) dvojic. A x B = {{a,b)\a G A, b G B} N-tice (xi,... ,xn) je prvek součinu A\ x • • • x An, kde x; G A; Relace R je podmnožina součinu A\ x • • • x An Funkce je relace f c A x B, kde pro x G A existuje právě jedno y G 6 takové, že (x,y) G f. Zobrazení je obecnější než funkce. Funkce je zobrazení do množiny čísel. Zkoumání kontextu Odbočka k lineární algebře Kontextové vektory Odbočka k teorii množin Matematický Matematický model významu [Widdows, 2003] přesné vymezení toho, co je kontext prostory W (words), C (lexicon of meanings), C (contexts) korespondence (w, c) —> I kontextové skupiny: homonyma jsou v disjunktních kontextových skupinách, víceznačná slova jsou v překrývajících se k. skupinách Matematický model významu [Widcows. 2003] PLIN021 Sémantická analýza v praxi 2 '—Matematický model významu ,«»,»(..*),c0«™ cŇ '—Matematický model významu [Widdows, 2003] o cn Disjunktní množiny - takové, které nesdílejí žádný prvek (průnik takových množin je prázdná množina). Překrývající se množiny - mají některé prvky společné (průnik takových množin je neprázdný). Proč je řeč o „skupinách" a ne „množinách"? Nevíme jistě, jestli významy tvoří množiny. Co je množina? Skupina prvků, které mají určité společné vlastnosti. Exaktní, obecně platná definice neexistuje, ale ono to nevadí. Každý prvek bud' v množině je, nebo v ní není. U významů by se nám lehce mohlo stát, že bychom se neshodli na příslušnosti nějakého významu do nějaké množiny kontextů. Proto mluvíme pro jistotu o kontextových skupinách. Zkoumání kontextu Odbočka k lineární algebře Kontextové vektory Odbočka k teorii množin Matematický Matematický model významu: motivace Soutěže jako SENSEVAL ukázaly, že úspěch či neúspěch WSD záleží na tom, jak těžké víceznačnosti jsou. Co to ale znamená? Někdy mají potíže s rozeznáním významu i lidé, jak to pak mají zvládnout počítače? Problém je jednak granularita, jednak kontext. Ve většině přístupů je totiž kontext definován vágně. Zkoumání kontextu Odbočka k lineární algebře Kontextové vektory Odbočka k teorii množin Matematický mi Matematický model významu: prostory W (words) C (lexicon of meanings) C (contexts) slova, části složených slov, víceslovné výrazy tradiční slovníky, ontológie, taxonomie, významy z trénovacích dat věty, kolokace, domény Zkoumání kontextu Odbočka k lineární algebře Kontextové vektory Odbočka k teorii množin Matematický model výzi Matematický model významu: tradiční WSD tradiční WSD: (w, c) G W x C zobrazení: 4> : (w, c) —> C ověření oproti „zlatému standardu" (tj. manuálním anotacím) všechny významy slova: S(w) = {4>(w, c)|Vc G C} C C úkol WSD je extrapolace (zobecnění) 4> (známe hodnotu (w,C2)) Zkoumání kontextu Odbočka k lineární algebře Kontextové vektory Odbočka k teorii množin Matematický model výzi Matematický model významu: synonymie slova w\, W2 6 W jsou synonyma právě, když 4>(wi, c) = 4>{w2, c) zobrazení z W do L není injektivní úplná synonymie: (w2, c) pro všechna c £ C Zkoumání kontextu Odbočka k lineární algebře Kontextové vektory Odbočka k teorii množin Matematický Matematický model významu: odposlouchávání Odposlouchávání (eavesdropping) v neznámých datech: přiřazení významu nejen z kontextu c G C, ale z libovolné podmnožiny C. Označme Cs kontexty, které jsou relevantní pro w. Pak přiřazení významu je zobrazení ■ {w, c,Cs) ->• C Jak zjistit Csl Pomocí podobností spočítaných na korpusu. Zkoumání kontextu Odbočka k lineární algebře Kontextové vektory Odbočka k teorii množin Matematický m Matematický model významu: kontextové skupiny Jak vlastně vypadá množina Cl Podmnožina promluvy.........................obsahující slovo w Kolik kontextu potřebujeme pro určení významu wl Záleží případ od případu. Tradiční přístup ke kontextu je c = (1/1/1,..., wn), tj. zobrazení W je však širší, obsahuje „meta" informace, obecně nepopsa(tel)né slovy, např.: „v lékařském kontextu operace vždy znamená chirurgický zákrok, na rozdíl od vojenské nebo matematické operace" Zkoumání kontextu Odbočka k lineární algebře Kontextové vektory Odbočka k teorii množin Matematický Matematický model významu: kontextové skupiny Vztah mezi významy a kontexty je monotónní, tj. jsou-li dva významy velmi různé, jsou velmi různé i kontexty, ve kterých se slovo objevuje. Nabízí se tedy popsat vztah mezi významy a kontexty bez ohledu na to, jak nějaký konkrétní kontext vypadá. Kontextová skupina slova w s významem / obsahuje přesně ty jazykové situace, ve kterých má slovo w význam /. C/, = {c G C|0(srážka, c) = /}, kde / má význam „autonehoda" a Ch je kontext „havárie". Kontext je inverzní zobrazení k přiřazení významu