Stránky soutěže jsou na http://www.cis.hut.fi/morphochallenge2008/. E-mailová adresa organizátorů je morphochallenge2007@james.hut.fi. Poznámky k mému loňskému řešení jsou na stránce Morpho Challenge 2007.
Data mám v ~/data/morphochallenge/2008
. Programy mám v ~/projekty/morphochallenge
(odkaz na data vede i odsud). Původně byly v ~/zapoctaky/konc
.
setenv MC /home/zeman/projekty/morphochallenge
Organizátoři používají trochu zvláštní kódování, navíc pro každý jazyk jiné. Napsal jsem si skript, který převede data od organizátorů do UTF-8. Bude umět i převod opačným směrem, což bude potřeba, až budu organizátorům posílat výsledky.
cd ~/data/morphochallenge/2008 gunzip -c wordlist.ara.gz | $MC/mc_convert.pl -f ar > wordlist.ar.txt gunzip -c wordlist.eng.gz | $MC/mc_convert.pl -f en > wordlist.en.txt gunzip -c wordlist.fin.gz | $MC/mc_convert.pl -f fi > wordlist.fi.txt gunzip -c wordlist.ger.gz | $MC/mc_convert.pl -f de > wordlist.de.txt gunzip -c wordlist.tur.gz | $MC/mc_convert.pl -f tr > wordlist.tr.txt
Můj skript pro automatické rozsekání slov na kmeny a koncovky předpokládá, že vstup je textový korpus ve formátu CSTS. Nejprve tedy musíme trénovací seznamy slov a jejich četností převést do tohoto formátu.
cd $MC foreach l (ar de en fi tr) mc2csts.pl < data/2008/wordlist.$l.txt -l $l > data/2008/$l.csts end
Pro některé jazyky (zejména pro finštinu) trvá zpracování déle, než by se chtělo čekat, a vyplatí se tedy úlohy odeslat na cluster:
# lrc cd $MC foreach l (ar de en fi tr) qsub.csh mc_jazyk.csh $l end
Během trénování pro každý jazyk l vzniknou následující soubory:
l.csts
… vstupní seznam slovních tvarů převedený do CSTSl.kmkon
… první rozdělení na kmeny a koncovky. Každý slovní tvar byl rozdělen na dvě části všemi možnými způsoby a výsledky byly seskupeny podle kmenů (stejná levá část).l.nefiltr
… převedeno do podoby vzorů, na každém řádku jeden vzor. Vzor je popsán seznamem koncovek, které byly nalezeny se stejnými kmeny. Dotyčný seznam kmenů následuje za seznamem koncovek. Seznam vzorů zatím neprošel žádným filtrováním.l.vzor
… přefiltrovaný a upravený seznam vzorů. Údaje o každém vzoru jsou rozložené na několik řádků a doplněné českými komentáři, aby byl seznam čitelný pro člověka.l.kmeny.txt
a l.koncovky.txt
… seznam všech kmenů a koncovek, které přežily filtrování a figurují v závěrečném seznamu vzorů. Tyto strojově čitelné seznamy se dají využít při pozdější segmentaci nových slov.Seznam vzorů se buduje takto (práce je rozdělena do několika kroků, protože zpracování velkých dat trvá dlouho a při opravě nějaké drobnosti u filtrování vzorů nechceme muset opakovat i první dva kroky):
csts2kmkon.pl < en.csts > en.kmkon kmkon2vzor.pl < en.kmkon > en.nefiltr vzorfiltr.pl -okm en.kmeny.txt -okonc en.koncovky.txt < en.nefiltr > en.vzor
Skript vzorfiltr.pl
jako vedlejší účinek vedle standardního výstupu tiše vyrobí soubory kmeny.txt
a koncovky.txt
.
Mám natrénovaný seznam vzorů, resp. seznam kmenů a koncovek. Segmentace ve skutečnosti znamená najít takové dělení slova na dvě části, aby první část odpovídala známému kmenu a druhá část známé koncovce.
Slovo umím rozložit na právě dva morfémy (kmen a koncovka) nebo nechat nerozložené. Při přiřazování slov ke vzorům se přednostně zjišťuje, zda známe přímo danou dvojici kmen-koncovka. Pokud žádnou takovou dvojici nenajdeme, zjišťujeme, zda rozpoznáme alespoň koncovky (aniž bychom znali kmen).
Rozklad slov na základě již vybudovaného seznamu vzorů se provede takto:
mchallenge.pl kmeny.txt koncovky.txt < wordlist.eng > en.dz.txt
cd $MC/data/2008 foreach l (ar de en fi tr) $MC/mchallenge.pl $l.kmeny.txt $l.koncovky.txt < wordlist.$l.txt > $l.dz.txt end
V úvahu přichází několik stupňů přísnosti při aplikaci vzorů na morfematickou segmentaci:
Poslední tři body neumím uspořádat podle přísnosti, ale všechny tři jsou méně přísné než první dva body. Můj přístup z roku 2007 a oficiálně vyhodnocená metoda 1 z roku 2008 zkouší nejdřív bod 2, a pokud selže, tak bod 5. I když by popis na začátku této kapitoly mohl napovídat, že začínám podle bodu 1, není tomu tak.
Ve výstupních souborech musí být první slovo (tvar, který jsme měli rozebrat) identické s řetězcem, který jsme od organizátorů dostali, tedy také v původním kódování. Zbytek řádku mohou být více méně libovolné řetězce, kterými si označujeme morfémy. Mohli bychom výstupy prohnat převodem kódování inverzním k tomu, který jsme na začátku dělali se vstupem. O něco bezpečnější se zdá žádné překódování neprovádět a pouze nahradit první slovo kopií prvního slova ze vstupu (vstupní a výstupní soubor mají stejný počet řádků, což se dá snadno ověřit). Má to ale háček. Původní texty obsahují ne-ASCII znaky, které jsou pak vesměs zakódované v ISO Latin 1. Uvnitř Perlu budou tyto znaky reprezentované jako UTF-8. Pokud pak na výstupu zvolíme UTF-8, bude se výstupní slovo lišit od vstupního. Pokud zvolíme ISO Latin 1, budou v pytli morfémy (možná jde nejen o estetickou chybu, ale i o věcnou, protože např. v arabštině by to mohlo dopadnout tak, že většina morfémů se převede na řetězce otazníků). Takže nakonec bude možná přece jen lepší překódovat celé výstupní soubory do těch příšerných kódování, která používají organizátoři.
cd ~/data/morphochallenge/2008 $MC/mc_convert.pl -t ar < ar.dz.txt | gzip -c > wordlist.ara.dz.gz $MC/mc_convert.pl -t de < de.dz.txt | gzip -c > wordlist.ger.dz.gz $MC/mc_convert.pl -t en < en.dz.txt | gzip -c > wordlist.eng.dz.gz $MC/mc_convert.pl -t fi < fi.dz.txt | gzip -c > wordlist.fin.dz.gz $MC/mc_convert.pl -t tr < tr.dz.txt | gzip -c > wordlist.tur.dz.gz $MC/mc_convert.pl -t ar < ar.dz3.txt | gzip -c > wordlist.ara.dz3.gz $MC/mc_convert.pl -t de < de.dz3.txt | gzip -c > wordlist.ger.dz3.gz $MC/mc_convert.pl -t en < en.dz3.txt | gzip -c > wordlist.eng.dz3.gz $MC/mc_convert.pl -t fi < fi.dz3.txt | gzip -c > wordlist.fin.dz3.gz $MC/mc_convert.pl -t tr < tr.dz3.txt | gzip -c > wordlist.tur.dz3.gz
Organizátoři poskytli program eval_morphemes.pl
. Pokyny pro správné vyhodnocování sepsali na stránce http://www.cis.hut.fi/morphochallenge2008/evaluation.shtml. Napsal jsem si kvůli tomu Makefile
, který je ve složce s daty a níže popsaný postup se z něj dá vyčíst.
Co ještě potřebujeme:
wordpairs_goldstd
… vzorek dvojic slov ze zlatého standardu. Získá se programem sample_word_pairs.pl
.wordpairs_proposed
… vzorek dvojic slov z výstupu analyzátoru. Získá se programem sample_word_pairs.pl
.morphemeanalyses_goldstd
… vzorové analýzy slov (zlatý standard)morphemeanalyses_proposed
… výstup analyzátoruJaký je tedy úplný postup při vyhodnocování?
eval_morphemes.pl
z webu http://www.cis.hut.fi/morphochallenge2008/evaluation.shtml.sample_word_pairs.pl
z téhož webu.goldstdsample.ara
(pro arabštinu) a je k dispozici na adrese http://www.cis.hut.fi/morphochallenge2008/datasets.shtml#download.cut -f1 goldstdfile > relevantwordsfile
sample_word_pairs.pl -refwords relevantwordsfile < resultfile > wordpairsfile_result
eval_morphemes.pl -trace wordpairsfile_goldstd wordpairsfile_result goldstdfile resultfile
cut -f1 $MC/data/2008/goldstdsample.eng > $MC/data/2008/relevantwords.eng $MC/sample_word_pairs.pl -refwords $MC/data/2008/relevantwords.eng < $MC/data/2008/en.dz.txt > $MC/data/2008/wordpairs_result.eng $MC/eval_morphemes.pl -trace $MC/data/2008/samplepairs.goldstd.eng $MC/data/2008/wordpairs_result.eng $MC/data/2008/goldstdsample.eng $MC/data/2008/en.dz.txt
Moje vyhodnocení se bude lišit od oficiálních výsledků soutěže, protože mám k dispozici gold standard jen pro 500 slov z každého jazyka. Na prvním místě uvádím své výsledky, vpravo pak oficiální výsledky zveřejněné na stránkách soutěže.
Jazyk | F | P | R | Fo | Po | Ro |
en | 48.56 | 53.39 | 44.53 | 46.90 | 52.98 | 42.07 |
de | 27.67 | 30.28 | 25.47 | 36.98 | 53.12 | 28.37 |
fi | 30.97 | 47.44 | 22.99 | 30.33 | 58.51 | 20.47 |
tr | 32.68 | 59.46 | 22.53 | 29.23 | 65.81 | 18.79 |
ar | 15.78 | 79.86 | 8.76 | 21.86 | 77.24 | 12.73 |
# lrc cd $MC/data/2008 foreach l (ar de en fi tr) $MC/reverse.pl < $l.csts > $l.rev.csts qsub.csh $MC/mc_jazyk.csh $l.rev end
foreach l (ar de en fi tr) cat $l.rev.kmeny.txt | $MC/reverse_line.pl > $l.kmeny1.txt cat $l.rev.koncovky.txt | $MC/reverse_line.pl > $l.predpony.txt $MC/mchallenge3.pl $l.predpony.txt $l.kmeny1.txt $l.kmeny.txt $l.koncovky.txt < wordlist.$l.txt > $l.dz3.txt end
První pokus se ještě dostal do oficiálního vyhodnocení, ale bylo to zklamání. Od té doby jsem se na to nedíval.
Při segmentaci prostě v každém rozkladu navíc nahradím pomlčky mezerami, čímž se slovo může rozpadnout na větší počet morfémů (pokud pomlčka nebyla na začátku). V angličtině to zvedlo F o 2 body.
Museli jsme vidět kmen i koncovku ve stejném vzoru (tedy buď přímo v trénovacích datech, nebo se koncovka ke kmeni dostala slučováním podmnožin s nadmnožinami).
Dvě třetiny vzorů nepřežijí filtrování, takže spoustě slov nezbyde žádný vzor a tato slova se stanou nerozložitelnými. Drasticky klesla úplnost, takže tohle je asi spíš slepá ulička.
Vzor pro slova abrupt, abruptly, abruptness nepřežil, protože se do slovníku kvůli překlepu připletlo i slovo abrupty. Takový vzor měl jen dva kmeny (druhý byl explicit), neslil se s hlavním vzorem bez překlepu a zahynul, protože měl víc koncovek než kmenů. Zkusil jsem kvůli tomu dovolit, aby vzor měl až 5krát více koncovek než kmenů, protože toto pravidlo bylo stejně zavedeno kvůli mamutím vzorům, kde byl jeden kmen (první písmeno) a několik tisíc koncovek. Změna mě donutila kompletně přepracovat (zefektivnit) algoritmus slévání podmnožin, ale ovoce v podobě úspěšnosti nepřinesla: F kleslo.
Starý:
1. Množiny procházet od největších po nejmenší (využíváme tím toho, že během procházení se nalezené podmnožiny mažou, takže se zmenšuje prostor, který procházíme).
2. Pro každou množinu procházet nadmnožiny. V nejhorším případě všechny, ale pokud najdeme alespoň jednu nadmnožinu velikosti n, hledáme už jen další nadmnožiny stejné velikosti a neprocházíme větší množiny.
3. Zjištění, zda je množina A nadmnožinou množiny B, znamená projít všechny prvky množiny B a zeptat se, jestli jsou v hashi reprezentujícím množinu A.
Složitost algoritmu je v nejhorším případě O((n**2)*k), kde n je počet množin a k je maximální velikost množiny. Pro 69877 anglických vzorů o průměrné velikosti dejme tomu 4 by vycházelo 20 miliard dotazů na hash. Pro 248077 německých vzorů by při stejné průměrné velikosti vycházelo 246 miliard dotazů.
Nový dynamický:
1. Projít všechny množiny.
2. Pro každou zkoumat podmnožiny, které jsou menší o 1 (pokud v trénovacích datech nebyly, vytvoříme si je jen jako pomocný uzel). Těch má každá množina tolik, kolik má prvků (protože odebráním prvku vznikne podmnožina). Z podmnožiny si vytvořit zpětný odkaz na nadmnožinu. Pokud jsme podmnožinu vytvořili jako pomocný uzel, který doteď neexistoval ani jako pomocný (důležité!), rovnou rekurzivně najdeme i jeho podmnožiny.
3. Projít množiny podruhé, teď už od největších po nejmenší. Pro každou množinu procházíme do šířky strom jejích nadmnožin (máme na ně odkazy). U nadmnožin se díváme, zda o nich máme jen pomocný záznam, nebo zda jsme něco takového skutečně viděli v datech. Za “nalezenou” považujeme nadmnožinu, která byla v datech. Pokud nalezneme alespoň jednu nadmnožinu velikosti n, hledáme už jen další nadmnožiny stejné velikosti a neprocházíme větší množiny. Místo mazání množiny pouze měníme skutečný záznam na pomocný.
Složitost algoritmu: Vybudování grafu nadmnožin stojí O(n*k) kroků. Složitost procházení stromu je těžké odhadnout, protože nevíme, kolika způsoby půjde rozšířit každou množinu a v kolikátém patře se hledání zastaví. V nejhorším případě by to mohlo být ještě horší než n na druhou (protože jsme přidali pomocné záznamy pro množiny, které v datech nebyly), spíš si ale myslím, že typicky budeme procházet jen O(k) množin v nejbližším 1 až 2 patrech. Případně bychom mohli zkusit prostě hledání na několik nejbližších pater omezit.
Počítadlo zjistilo, že pro 69877 anglických vzorů graf množin obsahoval 455633 množin.
Pozor, při procházení zdola nahoru zřejmě také mnohokrát procházím tímtéž místem!
Po zabránění tomuto opakování mi počítadlo zjistilo, že pro 69877 anglických vzorů jsem celkem zkoušel 202302 nadmnožin.
Pravidlová metoda pro předpony funguje mnohem lépe než ta reverzní. Obě metody se ale také podstatně liší způsobem použití naučených předpon při segmentaci. Chtělo by to oba způsoby prohodit a ověřit, zda rozdíl v úspěšnosti netkví ve skutečnosti zde. Kromě toho upravit reverzní metodu tak, aby společné písmeno neputovalo ke kmeni, ale k předponě.
Jednopísmenné předpony jsou problém. Nemůžu je úplně zakázat (české o-, u-), ale ve výstupu se mi nezdravě množí.
Segmentaci dělám hladově, i když by to chtělo chart parser. Problém: máme 2 seznamy kmenů (jeden zbytky po předponách, druhý po příponách). Který seznam použít?
Četnost koncovek: u kolika slov (typů i výskytů) jsme viděli danou koncovku? Méně časté koncovky by měly mít ztížené uplatnění při segmentaci. Zatím ale nevím, jak jim ho ztížit jinak, než je úplně zakázat.
Vzhledem ke způsobu vyhodnocení, který používá Morpho Challenge, by to chtělo sjednotit označení koncovek. Např. když téměř stejnou sadu koncovek uvidíme jednou jako “a, y, e, u, o, ou” a jindy jako “na, ny, ně, nu, no, nou”. Nevím ale, jak to udělat.
Jak mám poznat podmnožinu, když se kvůli chybějícímu výskytu v trénovacích datech neposunulo písmeno? Například mám v němčině největší vzor “0,m,n,r,re,rem,ren,rer,res,s”. Všechny kmeny končí na “e”. Jak poznám, že kdybych toto “e” zahrnul do koncovek (“e,em,en,er,ere,erem,eren,erer,eres,es”), mohl bych do vzoru přilít jiný vzor, který je téměř jeho podmnožinou, akorát má navíc koncovku “0” (tedy bez toho “e”)? Další věc: jak poznám složené koncovky? Tady by zrovna správná segmentace byla “aggressiv+er+e”. Musel bych hledat podmnožinu množiny koncovek, která je v množině koncovek obsažena dvakrát, jednou s prefixem a podruhé bez. Hledání by muselo být fuzzy.
V němčině je problém s kódováním. Postupně zjišťuju, že zobrazení, které použili v Lipsku, není prosté. Nejdřív byl problém se slovem guerilla → gürilla, to je v němčině cizí. Jenže ono se to objevuje i u některých německých slov: dauer → daür, zuerst → zürst atd.