Podobnost kontextů ve velkých textových korpusech
PA154 Jazykové modelování (9.1)
Pavel Rychlý
pary@fi.muni.cz
April 27, 2021
Významy
Slovo (a jeho některé části) jsou základními nositeli významu
■ slovo bez kontextu - žádný význam, mnoho potenciálních významů
■ stejné slovo v různých kontextech - různé významy
■ slovo v podobných kontextech - stejný význam
■ co to je kontext?
PA154 Jazykové modelování (9.1)
Podobnost kontextů ve velkých textových korpusech 2/17
Co to je kontext?
Kontext jsou slova v okolí klíčového slova.
■ Jaké okolí?:
► následující slovo
► předcházející slovo
► okno, +1 až +5
► okno, -5 až -1
■ Ne všechna slova v okolí jsou důležitá.
■ Jak určíme důležitost?
► nejčastější kolokace - ale to je "the"
► (statisticky) nejvýznamnější - jaký vzorec?
PA154 Jazykové modelování (9.1)
Podobnost kontextů ve velkých textových korpusech 3/17
Word Sketch
Jednostránkový souhrn chování slova
research as noun 251537>; ▼ ^ i
usually in plurals [99.1%, percentile 21.9)								
=•: t	1 x			:•: I	í X			X
modifier			modifies				subject_of	
scientific			grant				aim	
recent	***		project ♦**				focus	
cancer	*»•		laboratory				investigate	
empirical	***		institute				show	
market	*»•		finding				examine	
further	***		contract ♦**				indicate	
Cray	*»•		programme				suggest	
medical	***		council				reveal explore	•«
historical			fellow		•••			»•
applied			centre		...		concentrate	
PA154 Jazykové r			modelování (9.1)	Podobnost kontextů ve velkých textových korpusech				4
/17
Word Sketch
Jak jej lze vytvořit
■ Velký vyvážený korpus
■ Vyhledáme závislé prvky (subjects, objects, heads, modifiers etc)
■ Seznam kolokací pro každou gramatickou relaci
■ Statistika pro třídění každého seznamu
Z Word Sketch můžeme vytvořit thesaurus.
PA154 Jazykové modelování (9.1)
Podobnost kontextů ve velkých textových korpusech 5/17
Grammatical Relations Definition
■ plain text file
■ a set of queries for each GR
■ queries contain labels for keyword and collocate
■ processing options
PA154 Jazykové modelování (9.1)
Podobnost kontextů ve velkých textových korpu
Definice gramatických relací
# Modifier5 and 'modify* gramrels definition *DUAL
=modif ier/modify 2:"AJ." 1:"N.•
# fand/or; gramrel definition =and/or
*SYMMETRIC
[word=nandn|word=nor"] 2: [] & l.tag = 2.tag
# (adverb3 gramrel definition =adverb
1: [] 2:"AV." 2:"AV." 1: []
PA154 Jazykové modelování (9.1)
Podobnost kontextů ve velkých textových korpusech 7/17
Koeficient výnačnosti
počty výskytů (wordi^gramrel, word^)
í11	1/1/1,/?, 1/1/2	II II	Wl,/?, 1/1/2	11 1
	1/1/1,/?,*	1	*,*, 1/1/2	)
14 + log2 —^
M/l,/?,*
2-   l/l/i,/?, 1/1/2
*,*, 1/1/2
PA154 Jazykové modelování (9.1)
Podobnost kontextů ve velkých textových korpusech
Koeficient podobnosti
porovnání profilů slov w\ a 1/1/2 pouze důležité (význačné) kontexty jaký je překryv
počty (wordi, (gramrel, wordi)) a (i/i/orč/2, (gramrel, wordi))
^2(tuPi,tupj)e{tupwlr]tupsW2} A$i + ASj - (AS; - ASj)2/50
S/rn(1/1/1. wt) —
tu p, G {tupWl U tupW2 }
AS;
PA154 Jazykové modelování (9.1)
Podobnost kontextů ve velkých textových korpusech 9/17
Velikosti dat
Velikosti korpusů, jejich slovníků a počty slov v kontextech
Korpus	Velikost	Slov	Lemat	Různé k.	Všechny k.
BNC	lllm	776k	722k	23m	63m
SYN2000	114m	l,65m	776k	19m	58m
OEC	l,12g	3,67m	3,12m	84m	569m
Itwac	l,92g	6,32m	4,76m	67 m	587m
Velikosti slovníků i počty různých kontextů rostou sublineárně s velikostí korpusu.
PA154 Jazykové modelování (9.1)
Podobnost kontextů ve velkých textových korpusech 10/17
Velikost matice
■ Podobnost všech dvojic lemmat
■ Matice velikosti A/2, kde N je 700k - 5m
■ Počet prvků v radech tera (1012)
■ Matice je naštěstí velice řídká
■ Většina hodnot je 0 nebo "skoro" 0
■ Dokonce většina celých řádků/sloupců je prázdných
PA154 Jazykové modelování (9.1)
Podobnost kontextů ve velkých textových korpusech 11/17
Praktické velikosti dat
■ Výpočet pouze pro slova s minimální četností
■ Lépe limitovat počty kontextů než prostých výskytů
■ Z kontextů brát pouze statisticky významné
Korpus	MIN	Lemmat	KWIC	CTX
BNC	1	152k	5.7m	608k
BNC	20	68k	5.6m	588k
OEC	2	269k	27.5m	994k
OEC	20	128k	27.3m	981k
OEC	200	48 k	26.7m	965k
Itwac	20	137k	24.8m	l.lm
PA154 Jazykové modelování (9.1)
Podobnost kontextů ve velkých textových korpusech 12/17
Praktické velikosti dat
■ Matice velikosti A/2, kde N je 50k - 200k
■ Počet prvků v řádech giga (1010)
■ Hodnota každého prvku vznikne aplikací funkce podobnosti na vektory délky K = 500k - lm.
■ Přímočarý algoritmus pro výpočet celé matice má časovou složitost 0(N2K).
■ Složitost je polynomiální, ale algoritmus je prakticky nepoužitelný pro dané rozsahy hodnot.
■ Odhadované doby výpočtu jsou v měsících až letech.
■ Heuristiky snižují velikosti N a K na úkor přesnosti výsledných hodnot.
■ Doba výpočtu je potom v řádech dnů s chybou 1-4%.
PA154 Jazykové modelování (9.1)
Podobnost kontextů ve velkých textových korpusech 13/17
Efektivní algoritmus
■ I menší matice je velice řídká
■ Není potřeba počítat podobnost pro slova, která nemají nic společného,
■ tedy nemají žádný společný kontext.
■ Hlavní cyklus algoritmu tedy nevedeme přes slova, ale přes kontexty.
PA154 Jazykové modelování (9.1)
Podobnost kontextů ve velkých textových korpusech 14/17
Efektivní algoritmus
■ Vstup: seznam všech možných slov v kontextech, (w, r, w'), s četnostmi výskytů v korpusu
■ Výstup: matice podobností slov sim(w\, 1/1/2)
for (r, w') in CONTEXTS:
WLIST = set of all w where (w, r, w') exists for wľ in WLIST: for W2 in WLIST:
s/m( 1/1/1,1/1/2)+ = f (frequencies)
PA154 Jazykové modelování (9.1)
Podobnost kontextů ve velkých textových korpusech 15/17
Optimalizace
Pokud |IM./S7~| > 10000, daný kontext přeskočíme.
Matici sim(w\, 1/1/2) během výpočtu nedržíme celou v paměti.
Opakovaný běh hlavního cyklu pro omezený rozsah w\.
Místo sim(w\, 1/1/2)+ = x generujeme na výstup (1/1/1,1/1/2, x).
Výstupní seznam potom setřídíme a sčítáme jednotlivé x.
Využití TMMS (Two Phase Multi-way Merge Sort) s průběžným sčítáním.
Místo několika stovek GB třídíme jednotky GB.
PA154 Jazykové modelování (9.1)
Podobnost kontextů ve velkých textových korpusech 16/17
Výsledky
■ Algoritmus je řádově rychlejší než přímočarý algoritmus. (18 dnů x 2
hodiny)
Korpus	MIN	Lemmat	KWIC	CTX	čas
BNC	1	152k	5.7m	608k	13m 9s
BNC	20	68k	5.6m	588k	9m 30s
OEC	2	269k	27.5m	994k	lh 40m
OEC	20	128k	27.3m	981k	lh 27m
OEC	200	48k	26.7m	965k	lh 10m
Itwac	20	137k	24.8m	l.lm	lh 16m
■ Bez omezení přesnosti.
■ Možnost snadné paralelizace.
PA154 Jazykové modelování (9.1)
Podobnost kontextů ve velkých textových korpusech 17/17