[ Skip to the content ]

Institute of Formal and Applied Linguistics Wiki

[ Back to the navigation ]

You are here: start » user » zeman » morpho-challenge-2008

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision 		Previous revision
Last revision Both sides next revision
user:zeman:morpho-challenge-2008 [2008/08/01 12:52]
zeman Přehled již provedených pokusů. 		user:zeman:morpho-challenge-2008 [2008/08/01 22:35]
zeman Abrupt, abruptly, abruptness vysvětleno, byť uspokojivě nevyřešeno.
Line 153: Line 153:
  
 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. 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.
 +
  
 ==== Nejpřísnější segmentace ==== ==== Nejpřísnější segmentace ====
Line 159: Line 160:
  
 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. 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.
 +
 +==== 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: F kleslo.
 +
 +=== 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í, 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.
  
 ===== Zbývá udělat ===== ===== Zbývá udělat =====
Line 165: Line 190:
   * 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.   * 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 trénovacími daty.   * Vymyslet způsob, jak využít četnosti slovních tvarů, které jsme dostali s trénovacími daty.
 +
  
 ===== 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ředponě. 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ředponě.
- 
-Algoritmus 3 (předpony + kmeny + přípony) nedělá to, co má. Jaktože nepoznal vzor //abrupt - abruptly - abruptness//, když všechna tato slova jsou v datech a //-ly// i //-ness// jsou běžné koncovky? 
  
 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ží.

[ Back to the navigation ] [ Back to the content ]