Soutěž v závislostní syntaktické analýze hindštiny, bengálštiny a telugštiny. Něco jako CoNLL-X a 2007 shared task, ale pro indické jazyky. Tentokrát nezkouším jen DZ Parser, ale hlasující kombinaci tří parserů: Malt parseru, MST parseru a DZ parseru.

• Napsat článek.
• Rozchodit podporu clusteru v makefilech, abych nemusel MST parser pouštět ručně zvlášť.
• Vyzkoušet neprojektivní parsing MST parserem.
• Zjistit, jaká je úspěšnost naivního parseru, který pověsí poslední uzel na kořen a všechny předcházející uzly na poslední. Přinejmenším v telugských dtest datech takových případů vidím spoustu.
• Zjistit, proč je tolik chyb v syntaktickém značkování, a vylepšit ho. Třeba pomocí nějakého toolkitu pro strojové učení (Mallet apod.) Uvědomit si, že na jednom slovesu zřejmě nemohou viset dvě káčka se stejnými čísly (karma-karta). Taky že většina sloves asi vyžaduje k1.
• Vybrat SVN repozitář, do kterého tyto pokusy budu archivovat, vybrat soubory, které tam patří (Makefile, specifické skripty, vstupní data, soubory s vyhodnocením…) a dát je tam.
• Vyhodnotit křivku učení.
• Vyhodnotit požadavky na procesor, paměť a disk (je třeba nejdříve rozchodit skript).
• Více si pohrát s rysy.
• Více si pohrát s konfigurací Malt parseru.
• Frekvenční slovníky, abych si trochu udělal představu o častých slovech, případně o jejich syntaktických zvláštnostech.
• Konverze z wx do původních indických písem a do jejich vědecké transliterace kvůli příkladům v článku.
• Průzkum dat: jak dlouhé jsou věty? Indové v dokumentaci nějaká čísla uvádějí, ale tam se slova počítají včetně záložek a možná i včetně interpunkce, takže neodpovídají počtu uzlů, které vidím v treebanku.

Jak je zvykem, máme k dispozici data pro (d)trénink, dtest a etest (ta poslední jsou slepá, aspoň zatím). Každý datový soubor je k dispozici jednak s automaticky doplněnou (a zjednoznačněnou) morfologií (lemma, značka POS, morfologické kategorie), jednak bez ní (tj. na morfologické rovině pouze slovní tvar a značka chunku, ta by ale zřejmě měla být přiřazená ručně). Každý z uvedených souborů je ještě k dispozici jednak ve formátu CoNLL 2006, jednak v SSF (Shakti Standard Format, pro Indy je domovský, takže by stálo za to zjistit, zda se z něj převodem do CoNLL něco neztrácí).

Následující statistiky pocházejí ze souborů pro dtrénink s automatickou morfologií:

Statistiky v tabulce byly získány následujícím příkazem:

$TOOLS/conll_pocet_hodnot_sloupec.pl 4 < hi/dtrain.mconll

V telugských stromech jsem vypozoroval extrémní důsledek slovosledu SOV: poměrně často se stává, že poslední slovo věty visí na kořeni (typicky je to zřejmě sloveso) a většina ostatních slov visí na něm. Pro hindštinu a bengálštinu už to neplatí. Následující tabulka ukazuje podíl uzlů v jednotlivých datových souborech, které visely “naivně telugsky” (tj. pokud šlo o poslední uzel, visel na kořeni, jinak na posledním uzlu). Vzhledem k tomu, že na telugštině jinak dosahuju nejnižší úspěšnosti, by se tohle mělo nějak využít.

Takhle se z morfologických indických dat vyrobí soubor pro Tred, který obsahuje indické písmo místo WX:

cat hi/dtest.rmconll | conll_wc2utf.pl -l hi | $TOOLS/conll2csts.pl -y 2006 -l hi | perl -pe 's/<t>\S+\t/<t>/; s/\t.*?</</;' | cstsfs.pl > hi/dtest.fs

Důležitou součástí výše uvedeného příkazu je perlový kód, který maže tabulátory ze značek, jinak se na výsledek nedá v Tredu koukat. Tady je varianta pro výstup parseru:

cat hi/dtest.voted.rconll | conll_wc2utf.pl -l hi | $TOOLS/conll2csts.pl -y 2006 -l hi | perl -pe 's/<t>\S+\t/<t>/; s/\t.*?</</;' | cstsfs.pl > hi/dtest.voted.fs

A takhle spojíme vzorovou anotaci s výstupem parseru, abychom viděli chyby:

conll_pokusy.pl -l hi -t -g hi/dtest.mconll -s hi/dtest.voted.rconll | cstsfs.pl -s dzchyby > hi/dtest.voted.fs

Není pravda, že ze značky POS jednoznačně vyplývá značka chunku. Proto bych měl parserům poskytnout obě značky, může jim to pomoct. Např. v bengálské větě “(3) তবে / tabé সুদীপ / sudípa ওকে / óké একদিন / ékadina আড়ালে / áđa়াlé ডেকে / đéké বলেছিল / baléčhila কৌতূহল / kautúhala দেখালে / dékhálé তুমি / tumi উঁচুতে / um̃čuté উঠতে / uţhaté অনিমেষ / animéša” jsou slova “déké” a “dékhálé” značena jako “VGNF|VM” (zřejmě gerundium), zatímco “baléčhila” a “uthaté” jsou “VGF|VM”. Pokud parser u všech vidí jen “VM”, pak není divu, že v té větě nasekal několik divokých chyb.

V hindštině se často na chybách podílí uzel NULL. Spočítat, kolik takových uzlů ve kterém jazyce je.

Přinejmenším častá slova by měla být pro parsery viditelná jako samostatný rys uzlu. Např. hindské “कि / ki” (“že”) se mi zavěsilo špatně a kdo ví, jestli to není jen proto, že parser viděl pouze značku “CC”. Podobně “तो / tó” má taky značku “CC”, ale jeho zavěšování asi bude o dost jiné.

Úspěšnost přes 85 % je poměrně vysoká a je těžké v těch občasných chybách vysledovat nějaké pravidlo. Přinejmenším v hindštině se mi ale zdá, že často jde o chyby se slovesy či spojkami (koordinace sloves) a často na velkou vzdálenost.

Je potřeba přinejmenším Malt parseru, ale pokud to jde, tak i MST parseru předhodit podrobnější rysy, aby parser mohl pracovat zvlášť např. s lemmatem a zvlášť s pádem a sám se rozhodnout, ve kterém případě mu co pomáhá víc.

První výsledky DZ Parseru na vývojových datech:
hi: A 1250 - G 554 - P 0.4432
bn: A 811 - G 408 - P 0.5031
te: A 675 - G 249 - P 0.3689

Fuj!

Když jsem vynechal morfologii, tj. použil jsem pouze slovní druh, je to lepší (jednak data nejsou tak řídká, jednak morfologie byla označkovaná automaticky, tj. s chybami, zatímco slovní druhy jsou vyznačené ručně):

hi: A 1250 - G 775 - P 0.6200
bn: A 811 - G 576 - P 0.7102
te: A 675 - G 476 - P 0.7052

Malt Parser na stejné úloze:
java -Xmx2g -jar ../../../malt-1.3/malt.jar -c malt -i hindi_training.ssf.conll -m learn
java -Xmx2g -jar ../../../malt-1.3/malt.jar -c malt -i hindi_developmet.ssf.conll -o out.conll -m parse
$TOOLS/eval07.pl -g hindi_developmet.ssf.conll -s out.conll | more

hi: bez značek 0.8184 (1023/1250), se značkami 0.5520
bn: bez značek 0.8471 ( 687/ 811), se značkami 0.6042
te: bez značek 0.8089 ( 546/ 675), se značkami 0.4474

MST Parser na stejné úloze:
Přinejmenším pro hindštinu potřebuje větší paměť (-Xmx4000m stačilo, výchozích 1800 ne).

hi: bez značek 0.8032 (1004/1250), se značkami 0.5480
bn: bez značek 0.8200 ( 665/ 811), se značkami 0.6091
te: bez značek 0.7763 ( 524/ 675), se značkami 0.4667

Postřehy:
- Kvůli DZ Parseru je nutné něco udělat proti převádění velkých písmen na malá. U zvolené transliterace z indických písem totiž velikost písmen hraje roli.
- Data jsou příliš malá, takže je potřeba nějak prořezat informaci ve značkách.
- Parser, který pustím na soutěžní testovací data, bych měl určitě natrénovat na sjednocení trénovacích a vývojových dat! V tomhle množství je každá stovka vět dobrá!
- Otázka je, zda po nás organizátoři chtějí také odhadnout značky závislostí. Asi jo.
- Hindská (a pravděpodobně i ostatní) data obsahují neprojektivity, takže parsery, které to umí (Malt i MST) bych měl pouštět v neprojektivním režimu.

Otázky:
- Jaké je složení morfologických značek? Co je pád, například?
- Jaká je míra neprojektivity?
- Jaká je průměrná délka věty?
- Jak moc se jednotlivé parsery liší v odpovědích?

Úkoly:
- Uklidit si na disku, vyrobit si makefile.

Pozor!
Když volám Malt parser ze složky s daty, nenajde cestu ke svému souboru s definicemi rysů a má mnohem menší úspěšnost (s výjimkou telugštiny, kde je z nějakého důvodu úspěšnost stejná).

Hlasování parserů nad formátem CoNLL.

- Načíst větu postupně ze 3 otevřených souborů s výstupy 3 parserů.
- Už při načítání výstupy slít, takže u každého slova mám 3 odkazy na rodiče podle 3 parserů.

Současně si vybudovat i síť opačných odkazů, od rodičů k dětem.

- Abychom zajistili, že graf, který vybudujeme, bude strom, nedovolíme v každém kroku přidat libovolný uzel.

Místo toho se budeme snažit postupovat od kořene k listům.

- Budeme udržovat dvě skupiny uzlů, hotové a čekající.

Hotové uzly jsou už zařazené do stromu, čekající ještě ne.

- Na začátku je hotový pouze kořen stromu.
- U všech čekajících uzlů provést hlasování o jejich rodiči.

Každý parser disponuje tolika hlasy, jaká byla jeho úspěšnost na vývojových datech.
Vítězný rodič v tuto chvíli ještě nemusí být hotový.

- Nyní opakovaně procházet čekající uzly.

Ty, jejichž vítězný rodič už je hotový, přidat do stromu.
To celé opakovat, dokud je možné přidat nějaký čekající uzel.

- Je možné, že vítězní rodiče některých čekajících uzlů tvoří cyklus, a proto se do stromu zatím nedostaly.
- V tom případě najít uzel, u kterého napácháme nejméně škody tím, že ho pověsíme na jiného než vítězného rodiče.

(Tohle je podobný princip, jaký používá i Ryan McDonald uvnitř MST parseru, ne?)
Musí to být rodič, který je už hotový, ale při splnění této podmínky má nejvyšší možný počet hlasů.
Asi se teoreticky může stát, že žádný parser nedal hlas žádné hraně, která by zrušila cyklus, v tom případě budeme
muset prostě nějaký uzel vylosovat.
Po přidání tohoto rodiče do stromu bude možné přidat i celou jeho skupinku (cyklus).
Potom totéž postupně uděláme i s ostatními cykly.

- Paralelně je nutné ještě rozhodnout o syntaktické značce pro danou závislost.

Tady použijeme opět vážené hlasování jednotlivých parserů.
Mohli bychom výsledek také ovlivňovat tím, který parser vyhrál hlasování o zavěšení uzlu, ale to by bylo komplikované.

- Na standardní výstup vypsat větu ve formátu CoNLL, ale s novými hodnotami HEAD a DEPREL.

Porovnání úspěšností parserů nad jednotlivými jazyky:

Úspěšnost nalezení rodiče, bez syntaktické značky (Malt:MST:DZ)

hi:8184:8032:6200 1:0.98:0.76
bn:8471:8200:7102 1:0.97:0.84
te:8089:7763:7052 1:0.96:0.87

Úspěšnost přiřazení syntaktické značky (Malt:MST:DZ)

hi:5728:5824:3776 1:1.02:0.66
bn:6215:6289:5376 1:1.01:0.87
te:4904:5111:4267 1:1.04:0.87

Když použiju část informace z morfologie, DZ Parser si vede mnohem lépe! (Na hindštině asi 74% místo 62.)
Bohužel se ukazuje, že to platí pouze pro hindštinu. Bengálština i telugština se výrazně zhorší.
Otázka je, jestli by si lépe vedly i Malt parser a MST parser, ale to vyzkouším až později.
Pozoruhodné je, že zhoršený DZ Parser zlepšuje výsledek hlasování, na kterém se podílí!

Nové váhy parserů při hlasování (20.10.2009 13:26, DZ parser teď na všechno používá pád a záložku, Malt parser používá POSTAG s pádem a záložkou pro hindštinu, jinde používá CPOSTAG, MST Parser používá všude POSTAG s pádem a záložkou):

unlabeled MST:MALT:DZ
hi 8616:8584:7512
bn 8570:8471:5438
te 7985:8089:4578

labels MST:MALT:DZ
hi 6816:6704:5960
bn 6967:6215:5314
te 5526:4904:4400

21:57 lrc-two:/ha/work/people/zeman/icon-parsing/work> cat hi/dtrain.conll hi/dtest.conll | $TOOLS/neproj.pl
slov = 15025
neproj = 275
podil = 0.0183028286189684
vet = 1651
neproj = 230
podil = 0.13930950938825
22:05 lrc-two:/ha/work/people/zeman/icon-parsing/work> cat bn/dtrain.conll bn/dtest.conll | $TOOLS/neproj.pl
slov = 7260
neproj = 70
podil = 0.00964187327823691
vet = 1130
neproj = 62
podil = 0.0548672566371681
22:05 lrc-two:/ha/work/people/zeman/icon-parsing/work> cat te/dtrain.conll te/dtest.conll | $TOOLS/neproj.pl
slov = 6169
neproj = 28
podil = 0.00453882314799805
vet = 1606
neproj = 21
podil = 0.0130759651307597

Předběžný pokus s neprojektivní analýzou hindštiny Malt parserem ukazuje zřetelné zhoršení:

Labeled   attachment score: 641 / 1250 * 100 = 51.28 %
Unlabeled attachment score: 947 / 1250 * 100 = 75.76 %
Label accuracy score:       685 / 1250 * 100 = 54.80 %