Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
user:zeman:morpho-challenge-2008 [2008/07/31 13:32] zeman Výsledky. |
user:zeman:morpho-challenge-2008 [2008/08/01 22:33] zeman Nové slévání podmnožin. |
||
---|---|---|---|
Line 47: | Line 47: | ||
vzorfiltr.pl -okm en.kmeny.txt -okonc en.koncovky.txt < en.nefiltr > en.vzor</ | vzorfiltr.pl -okm en.kmeny.txt -okonc en.koncovky.txt < en.nefiltr > en.vzor</ | ||
Skript '' | Skript '' | ||
+ | |||
+ | |||
+ | |||
===== Morfematická segmentace ===== | ===== Morfematická segmentace ===== | ||
Line 61: | Line 64: | ||
$MC/ | $MC/ | ||
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 77: | 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í ===== | ===== Vyhodnocení ===== | ||
Line 104: | 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 při vyhodnocování? | + | ==== Nejpřísnější segmentace ==== |
- | - Stáhnout program '' | + | 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 |
- | - 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í: | + | |
- | < | + | |
- | < | + | Dvě třetiny vzorů nepřežijí filtrování, |
- | $MC/ | + | |
- | $MC/ | + | ==== 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 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: | ||
+ | |||
+ | === 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& | ||
===== Postřehy ===== | ===== Postřehy ===== | ||
Předpony, zdá se, fungují, ale na rozdíl od přípon by to tu nechtělo dávat společná písmena ke kmeni, nýbrž k& | Předpony, zdá se, fungují, ale na rozdíl od přípon by to tu nechtělo dávat společná písmena ke kmeni, nýbrž k& | ||
+ | |||
+ | Algoritmus 3 (předpony + kmeny + přípony) nedělá to, co má. Jaktože nepoznal vzor //abrupt - abruptly - abruptness//, | ||
Jednopísmenné předpony jsou problém. Nemůžu je úplně zakázat (české //o-, u-//), ale ve výstupu se mi nezdravě množí. | Jednopísmenné předpony jsou problém. Nemůžu je úplně zakázat (české //o-, u-//), ale ve výstupu se mi nezdravě množí. | ||
Line 147: | Line 201: | ||
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í. |