Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Last revision Both sides next revision | ||
user:zeman:morpho-challenge-2008 [2008/07/28 15:27] zeman Návod na vyhodnocování. |
user:zeman:morpho-challenge-2008 [2008/08/01 22:35] zeman Abrupt, abruptly, abruptness vysvětleno, byť uspokojivě nevyřešeno. |
||
---|---|---|---|
Line 44: | Line 44: | ||
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): | 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): | ||
< | < | ||
- | kmkon2vzor.pl < en.kmkon > en.vzor | + | kmkon2vzor.pl < en.kmkon > en.nefiltr |
- | vzorfiltr.pl < en.vzor > en1.vzor</ | + | vzorfiltr.pl |
Skript '' | Skript '' | ||
+ | |||
+ | |||
+ | |||
===== Morfematická segmentace ===== | ===== Morfematická segmentace ===== | ||
Line 62: | Line 65: | ||
end</ | end</ | ||
+ | V úvahu přichází několik stupňů přísnosti při aplikaci vzorů na morfematickou segmentaci: | ||
+ | - Slovo rozdělit pouze v případě, že toto dělení bylo viděno v trénovacích datech a proniklo filtrem mezi výsledné vzory. Jinými slovy, kmen i koncovka musí být známé a navíc musely být viděny spolu. | ||
+ | - Kmen a koncovka nemusely být viděny přímo spolu. Stačí, když byl kmen viděn s N jinými koncovkami, které se s hledanou koncovkou společně vyskytují alespoň v jednom vzoru. | ||
+ | - Další možnost by byla snažit se zjistit, zda slovo může náležet ke vzoru, který připouští danou koncovku. I když náš systém toto slovo zařadil k jinému slovu. Např. nejpřísnější metoda nerozdělila " | ||
+ | - Kmen i koncovka musí být známé, ale nemusely být viděny spolu. | ||
+ | - Známá je koncovka, kmen známý být nemusí. | ||
+ | - Známý je kmen, koncovka známá být nemusí. | ||
+ | - Známý je kmen nebo koncovka, ale ne nutně obojí. | ||
+ | Poslední tři body neumím uspořádat podle přísnosti, | ||
===== Úprava výstupu před odesláním ===== | ===== Úprava výstupu před odesláním ===== | ||
Line 78: | Line 90: | ||
$MC/ | $MC/ | ||
$MC/ | $MC/ | ||
+ | |||
+ | ===== Skórování ===== | ||
+ | |||
+ | Organizátoři poskytli program '' | ||
+ | |||
+ | Co ještě potřebujeme: | ||
+ | |||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | |||
+ | Jaký je tedy úplný postup při vyhodnocování? | ||
+ | |||
+ | - Stáhnout program '' | ||
+ | - Stáhnout program '' | ||
+ | - Pro jazyk, který chceme vyhodnocovat, | ||
+ | - Pro jazyk, který chceme vyhodnocovat, | ||
+ | - Z výstupu analyzátoru, | ||
+ | - Nejdříve vytvoříme seznam relevantních slov, tedy takových, která se vyskytují ve vzorových analýzách, | ||
+ | - Potom náhodně vybereme 100 relevantních slov z výstupu našeho analyzátoru. < | ||
+ | - Nyní již máme pohromadě všechny soubory potřebné jako vstupy pro vyhodnocovací program a můžeme spustit vyhodnocování: | ||
+ | < | ||
+ | |||
+ | < | ||
+ | $MC/ | ||
+ | $MC/ | ||
+ | |||
+ | ===== Vyhodnocení ===== | ||
+ | |||
+ | 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 | | ||
===== Zpracování převrácených slov a hledání předpon ===== | ===== Zpracování převrácených slov a hledání předpon ===== | ||
Line 94: | Line 144: | ||
end</ | end</ | ||
- | ===== Zbývá udělat | + | ===== Záznamy pokusů |
- | * Vyzkoušet skórování. | + | ==== Převrácená slova a předpony |
- | * Pustit celý algoritmus na převrácená slova a získat | + | |
- | * Zkusit rozpoznat složená slova, resp. složené kmeny. Pouze jednoduchý přístup, snažit se najít uvnitř kmenu jiný existující kmen tak, aby to, co zbyde, byl také existující kmen nebo složenina. | + | |
- | * Vymyslet způsob, jak využít četnosti slovních tvarů, které jsme dostali s& | + | |
- | * Odeslat výsledky Mikkovi. | + | |
- | ===== Skórování ===== | + | První pokus se ještě dostal do oficiálního vyhodnocení, |
- | Organizátoři poskytli program '' | + | ==== Pomlčka odděluje morfémy ==== |
- | Co ještě potřebujeme: | + | 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. |
- | * '' | ||
- | * '' | ||
- | * '' | ||
- | * '' | ||
- | Jaký je tedy úplný postup | + | ==== Nejpřísnější segmentace ==== |
+ | |||
+ | 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í, | ||
+ | |||
+ | ==== Mazání vzorů, které mají více koncovek než kmenů, a přepracovaný algoritmus slévání podmnožin ==== | ||
+ | |||
+ | Vzor pro slova abrupt, abruptly, abruptness nepřežil, protože se do slovníku kvůli překlepu připletlo | ||
+ | |||
+ | === Nový algoritmus pro prořezávání podmnožin === | ||
+ | |||
+ | 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í, | ||
+ | |||
+ | Složitost algoritmu je v nejhorším případě O((n**2)*k), | ||
+ | |||
+ | Nový dynamický: | ||
+ | 1. Projít všechny množiny. | ||
+ | 2. Pro každou zkoumat 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 " | ||
+ | |||
+ | 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. | ||
+ | |||
+ | ===== Zbývá udělat ===== | ||
+ | |||
+ | * Pustit celý algoritmus na převrácená slova a získat předpony. | ||
+ | * Zkusit rozpoznat složená slova, resp. složené kmeny. Pouze jednoduchý přístup, snažit se najít uvnitř kmenu jiný existující kmen tak, aby to, co zbyde, byl také existující kmen nebo složenina. | ||
+ | * Vymyslet způsob, jak využít četnosti slovních tvarů, které jsme dostali s& | ||
- | - Stáhnout program '' | ||
- | - Stáhnout program '' | ||
- | - Pro jazyk, který chceme vyhodnocovat, | ||
- | - Pro jazyk, který chceme vyhodnocovat, | ||
- | - Z výstupu analyzátoru, | ||
- | - Nejdříve vytvoříme seznam relevantních slov, tedy takových, která se vyskytují ve vzorových analýzách, | ||
- | - Potom náhodně vybereme 100 relevantních slov z výstupu našeho analyzátoru. < | ||
- | - Nyní již máme pohromadě všechny soubory potřebné jako vstupy pro vyhodnocovací program a můžeme spustit vyhodnocování: | ||
- | < | ||
===== Postřehy ===== | ===== Postřehy ===== | ||
Line 133: | Line 200: | ||
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, | 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, | ||
- | Algoritmus 3 (předpony + kmeny + přípony) nedělá to, co má. Jaktože nepoznal | + | Č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í |
+ | |||
+ | Vzhledem ke způsobu vyhodnocení, | ||
+ | |||
+ | 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 " | ||
+ | |||
+ | Třetina slov v angličtině neprojde filtrováním vzorů. Na vstupu mám 385 tisíc slov, na výstupu 122 tisíc segmentací. (Ve skutečnosti jsem jich asi odfiltroval víc, protože na výstupu navíc mohou být i taková slova, která jsem vůbec neviděl. Můžou se tam dostat při slučování vzorů s nadmnožinami.) Otázka je, jak přesně k tomu došlo. Kdybych věděl, kde se slova ztrácejí, možná by mě napadlo, jak je neztratit úplně. To bych ale musel rozvinout ladění, abych dokázal stopovat slovo během celého procesu filtrování. |