Differences
This shows you the differences between two versions of the page.
| — |
user:ptacek:eugene-charniak-recent-advances-in-nl-parsing-a-mt [2006/03/28 16:18] (current) |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| + | ====== Context Free Grammar ====== | ||
| + | da se do CNF - Chomskeho normalni forma\\ | ||
| + | A -> BC\\ | ||
| + | B -> terminal\\ | ||
| + | S1 -> Λ\\ | ||
| + | |||
| + | ===== CKY ===== | ||
| + | na diagonalu si napis posloupnost terminalu a preved je na neterminaly\\ | ||
| + | potom postupuj po diagonalach vys a vys, do kazdeho policka prijdou vsechny moznosti, ktere jsou odvodit z dvojic policek: | ||
| + | < | ||
| + | 1 2 3 4 ? | ||
| + | 1 | ||
| + | 2 | ||
| + | 3 | ||
| + | 4 | ||
| + | </ | ||
| + | |||
| + | slozitost θ(|G|N< | ||
| + | |||
| + | ===== Chart parsing ===== | ||
| + | |||
| + | taky horni trojuhelnik nad diagonalou. navic ?zasobnik Agenda, na pocatku v ni terminaly, | ||
| + | pak je supej do policek a pokud muzes pouzit nejaky pravidlo, tak ho uzi a vysledek zase supej do Agendy. | ||
| + | |||
| + | Resi problem CKY s unary rules (jako S->VP) a ani cykly v G nevadi (S-> | ||
| + | |||
| + | ====== PCFG ====== | ||
| + | Probabilistic, | ||
| + | do cell si pisu soucin komponenty*P(pravidla) | ||
| + | |||
| + | pocitam nejpravdepodobnejsi parse, takze kdyz vice moznosti, tak si staci pamatovat tu vetsi pst | ||
| + | |||
| + | tahle pravdepodobnosti verze Chart parsingu se asi menuje VITERBI (nerozumnel jsem presne) | ||