Konečný převodník

Konečný převodník (anglicky finite-state transducer, FST) je konečný automat se dvěma paměťovými páskami podle terminologie používané pro Turingovy stroje: vstupní páskou a výstupní páskou. Tím se odlišuje od obyčejného konečného automatu, který má jen jednu pásku. Konečný převodník je typem konečného automatu, který provádí převod mezi dvěma množinami symbolů. Konečné převodníky lze považovat za zobecnění konečných automatů; zatímco konečný automat definuje formální jazyk určením množiny přijímaných řetězců, konečný převodník definuje relaci mezi množinami řetězců.

Konečný převodník čte řetězce ze vstupní pásky a generuje množinu relací na výstupní pásce. Na konečný převodník lze pohlížet jako na překladač nebo zařízení pro určení vztahů mezi množinami řetězců.

Při morfologické analýze může být vstupem konečného převodníku řetězec symbolů, a konečný převodník produkuje řetězec morfémů.

Úvod

Pokud chápeme obsah vstupní pásky jako vstup automatu, pak říkáme, že automat přijímá řetězec. Jinými slovy, automat počítá funkci, která přiřazuje řetězcům hodnoty {0,1}. Alternativně můžeme říct, že automat generuje řetězec, pokud pohlížíme na jeho pásku jako na výstup. Při tomto přístupu automat generuje formální jazyk, který je sadou řetězců. Oba pohledy na automat jsou ekvivalentní: funkce, kterou automat počítá, je právě charakteristická funkce množiny řetězců, které generuje. Třída jazyků generovaných konečnými automaty se nazývá regulární jazyky.

Na dvě pásky převodníku obvykle pohlížíme jako na vstupní pásku a výstupní pásku. Při tomto přístupu převodník převádí (překládá) obsah své vstupní pásky na výstupní pásku, načtením řetězce ze vstupní pásky a vygenerováním jiného řetězce na výstupní pásku. Převodník může pracovat nedeterministicky, a může produkovat více než jeden výstup pro každý vstupní řetězec. Převodník může také neprodukovat žádný výstup pro daný vstupní řetězec, čemuž říkáme, že daný vstup odmítá. Obecně převodník počítá relaci mezi dvěma formálními jazyky.

Každý konečný převodník, který převádí jeden řetězec na druhý, ukazuje souvislost vstupní abecedy Σ s výstupní abecedou Γ. Relace R na Σ*×Γ*, které lze implementovat jako konečné převodníky se nazývají racionální relace. Racionální relace, které jsou zobrazeními (tj. přiřazují každému vstupnímu řetězci z Σ* nejvýše jeden řetězec z Γ*, se nazývají racionální funkce.

Konečné převodníky se často používají pro fonologickou a morfologickou analýzu při výzkumu i v aplikacích v oblasti zpracování přirozeného jazyka. K průkopníkům v této oblasti patří Ronald Kaplan, Lauri Karttunen, Martin Kay a Kimmo Koskenniemi. Obvyklým způsobem použití převodníků je tak zvaná „kaskáda“, kdy se převodníky pro různé operace kombinují do jediného převodníku opakovanou aplikací operátoru skládání relací (definovaného níže).

Formalní konstrukce

Formálně je konečný převodník T šestice (Q, Σ, Γ, I, F, δ) taková, že:

• Q je konečná množina stavů;
• Σ je konečná množina nazývaná vstupní abeceda;
• Γ je konečná množina nazývaná výstupní abeceda;
• I je podmnožina množiny Q, množina počátečních stavů;
• F je podmnožina Q, množina koncových stavů; a
• $\delta \subseteq Q\times (\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})\times Q$ je přechodová relace (ε je prázdný řetězec).

Na (Q, δ) můžeme nahlížet jako na orientovaný graf, nazývaný přechodový graf T: množina vrcholů je Q a $(q,a,b,r)\in \delta$ znamená, že existuje označená hrana jdoucí z vrcholu q do vrcholu r. Přitom a je vstupní návěstí a b výstupní návěstí této hrany.

Poznámka: Tato definice konečného převodníku se také nazývá písmenový převodník (Roche a Schabes 1997); existují alternativní definice, ale všechny mohou být převedeny na převodníky, jako je tento.

Definujeme rozšířenou přechodovou relaci $\delta ^{*}$ jako nejmenší množinu takovou, že:

• $\delta \subseteq \delta ^{*}$;
• $(q,\epsilon ,\epsilon ,q)\in \delta ^{*}$ pro všechny $q\in Q$; a
• když $(q,x,y,r)\in \delta ^{*}$ a $(r,a,b,s)\in \delta$ pak $(q,xa,yb,s)\in \delta ^{*}$.

Rozšířená přechodová relace je v zásadě reflexivní a tranzitivní uzávěr přechodového grafu, který byl rozšířen o návěstí hran. Prvky $\delta ^{*}$ se nazývají cesty. Návěstí cesty se získá zřetězením návěstí jednotlivých hran v tom pořadí, v jaké se procházely.

Chování převodníku T je racionální relace [T] definovaná takto: $x[T]y$ právě tehdy, když existuje $i\in I$ a $f\in F$ tak, že $(i,x,y,f)\in \delta ^{*}$. To znamená, že T převádí řetězec $x\in \Sigma ^{*}$ na řetězec $y\in \Gamma ^{*}$, pokud existuje cesta z počátečního stavu do koncového stavu, jejíž vstupní návěstí je x, a výstupní návěstí y.

Vážený konečný převodník

Konečné převodníky lze rozšířit o váhy tak, že každému přechodu je přiřazeno nejen vstupní a výstupní návěstí, ale také váha. Vážený konečný převodník (anglicky Weighted Finite State Transducer, WFST) s množinou vah K lze definovat obdobně jako převodník bez vah – jako osmici T=(Q, Σ, Γ, I, F, E, λ, ρ), kde:

• Q, Σ, Γ, I, F jsou definovány jako výše;
• $E\subseteq Q\times (\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})\times Q\times K$ (kde ε je prázdný řetězec) je konečná množina přechodů;
• $\lambda :I\rightarrow K$ přiřazuje váhy počátečním stavům;
• $\rho :F\rightarrow K$ přiřazuje váhy koncovým stavům.

Aby byly určité operace na vážených konečných převodnících dobře definované, je vhodné vyžadovat, aby množina vah tvořila polookruh. Dva typické polookruhy používané v praxi jsou logaritmický polookruh a tropický polookruh: automaty bez vah mohou být považovány za automaty, jejichž váhy jsou v Booleovském polookruhu.

Stochastické konečné převodníky

Stochastické konečné převodníky (nazývané také pravděpodobnostní konečné převodníky nebo statistické konečné převodníky) jsou podle všeho tvarem vážených konečných převodníků.^[zdroj?]

Operace na konečných převodnících

Následující operace definované na konečných automatech lze také aplikovat na konečné převodníky:

• Sjednocení. Jsou-li dány převodníky T a S, existuje převodník $T\cup S$ tak, že $x[T\cup S]y$ právě tehdy, když $x[T]y$ nebo $x[S]y$.
• Zřetězení. Jsou-li dány převodníky T a S, existuje převodník $T\cdot S$ tak, že $x[T\cdot S]y$ právě tehdy, když existuje $x_{1},x_{2},y_{1},y_{2}$ s $x=x_{1}x_{2},y=y_{1}y_{2},x_{1}[T]y_{1}$ a $x_{2}[S]y_{2}.$
• Kleeneho uzávěr. Je-li dán převodník T, existuje převodník $T^{*}$ s následujícími vlastnostmi:

$\epsilon [T^{*}]\epsilon$,

(k1)

pokud $w[T^{*}]y$ a $x[T]z$, pak $wx[T^{*}]yz$;

(k2)

přičemž $x[T^{*}]y$ neplatí, pokud není zaručeno (k1) nebo (k2).

• Skládání relací. Je-li dán převodník T na abecedách Σ a Γ a převodník S na abecedách Γ a Δ, existuje převodník $T\circ S$ na Σ a Δ takový, že $x[T\circ S]z$ právě tehdy, když existuje řetězec $y\in \Gamma ^{*}$ tak, že $x[T]y$ a $y[S]z$. Tuto operaci lze rozšířit na vážené konečné převodníky.

Tato definice používá notaci používanou v matematice pro skládání relací. Nicméně obvyklé chápání skládání relací je jiné: jsou-li dány dvě relace T a S, $(x,z)\in T\circ S$, když existuje nějaké y tak, že $(x,y)\in S$ a $(y,z)\in T.$

• Projekce automatu. Existují dvě projekční funkce: $\pi _{1}$ zachovává vstupní pásku a $\pi _{2}$ zachovává výstupní pásku. První projekce $\pi _{1}$ je definována takto:

Je-li dán převodník T, existuje konečný automat $\pi _{1}T$ tak, že $\pi _{1}T$ přijme x právě tehdy, když existuje řetězec y pro který $x[T]y.$

Druhá projekce $\pi _{2}$ je definovaná obdobně.

• Determinizace. Je-li dán převodník T, chceme vytvořit ekvivalentní převodník, které má jedinečná/jednoznačná počáteční stav a tak, že žádné dva přechody ponechává jakýkoli stav sdílí stejný vstupní návěstí. Pomocí podmnožinové konstrukce lze tuto vlastnost rozšířit na konečné převodníky i na vážené konečné převodníky, které se ale někdy nemusí zastavit; skutečně, některé nedeterministické převodníky nepřipouštějí ekvivalentní deterministické převodníky. Byly navrženy různé charakterizace determinizovatelných převodníků spolu s efektivními algoritmy, jak je testovat: spoléhají na vlastnosti polookruhu používaného ve váženém případě, i na obecné vlastnosti struktury převodníku (tzv. twins property).
• Ukládání (anglicky pushing)^[ujasnit] vah pro vážené konečné převodníky.
• Minimalizace vážených konečných převodníků.
• Odstranění epsilon přechodů.

Další vlastnosti konečných převodníků

• Je rozhodnutelné, zda relace [T] převodníku T je prázdná.
• Je rozhodnutelné, zda existuje řetězec y tak, že x[T]y pro daný řetězec x.
• Je nerozhodnutelné, zda dva převodníky jsou ekvivalentní. Ekvivalence je ale rozhodnutelná ve speciálním případě, když relace [T] převodníku T je zobrazení.
• Pokud definujeme abecedu návěstí $L=(\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})$, konečné převodníky jsou izomorfní s nedeterministickými konečnými automaty s abecedou $L$, takže mohou být determinizovány (převedeny na deterministický konečný automat nad abecedou $L=[(\Sigma \cup \{\epsilon \})\times \Gamma ]\cup [\Sigma \times (\Gamma \cup \{\epsilon \})]$) a následně minimalizovány, čímž se minimalizuje počet stavů.^[zdroj?]

Aplikace

Kontextová přepisovací pravidla tvaru a → b / c _ d, používaná v lingvistice pro modelování fonologických pravidel a posouvání hlásek jsou výpočetně ekvivalentní s konečnými převodníky za předpokladu, že jejich aplikace není rekurzivní, tj. není povoleno, aby pravidla přepisovala stejný podřetězec opakovaně.

Vážené konečné převodníky se používají pro zpracování přirozeného jazyka, včetně strojového překladu a pro strojové učení. Jednou z komponent knihovny OpenGrm je implementace morfologického značkování.

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Finite-state transducer na anglické Wikipedii.

Literatura

• ALLAUZEN, Cyril; MOHRI, Mehryar, 2003. Efficient Algorithms for Testing the Twins Property. Journal of Automata, Languages and Combinatorics. Roč. 8, čís. 2, s. 117–144. Dostupné v archivu pořízeném dne 2012-03-18. 
• BEESLEY, Kenneth R.; KARTTUNEN, Lauri. Finite State Morphology. [s.l.]: Center for the Study of Language and Information, 2003. ISBN 1-57586-434-7. 
• BERSTEL, Jean; REUTENAUER, Christophe, 2011. Noncommutative rational series with applications. Cambridge: Cambridge University Press. (Encyclopedia of Mathematics and Its Applications). ISBN 978-0-521-19022-0. 
• BERSTEL, Jean. Transductions and Context-free Languages. [s.l.]: Teubner Verlag, 1979. Dostupné online. Volná PDF verze. 
• CORTES, Corinna; MOHRI, Mehryar. Learning with Weighted Transducers [online]. [cit. 2017-04-29]. Dostupné online. 
• GRIFFITHS, T. V., 1968. The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines. Journal of the ACM. ACM. Roč. 15, čís. 3, s. 409–413. Dostupné online. DOI 10.1145/321466.321473. 
• JURAFSKY, Daniel, 2009. Speech and Language Processing. [s.l.]: Pearson. ISBN 9789332518414. 
• JURAFSKY, Daniel; MARTIN, James H. Speech and Language Processing. [s.l.]: Prentice Hall, 2000. Dostupné online. ISBN 0-13-095069-6. S. 71–83. 
• KAPLAN, Ronald M.; KAY, Martin. Regular Models of Phonological Rule Systems [online]. [cit. 2012-08-25]. Dostupné v archivu pořízeném z originálu dne 2010-10-11. 
• KNIGHT, Kevin; MAY, Jonathan, 2009. Handbook of Weighted Automata. [s.l.]: Springer Science & Business Media. ISBN 978-3-642-01492-5. Kapitola Applications of Weighted Automata in Natural Language Processing. 
• KORNAI, Andras. Extended Finite State Models of Language. [s.l.]: Cambridge University Press, 1999. Dostupné online. ISBN 0-521-63198-X. 
• KOSKENNIEMI, Kimmo, 1983. Two-level morphology: A general computational model of word-form recognition and production. Helsinky: Department of General Linguistics, University of Helsinki. 160 s. Dostupné online. ISBN 951-45-3201-5. (anglicky)  Archivováno 21. 12. 2018 na Wayback Machine.
• LOTHAIRE, M., 2005. Applied combinatorics on words. Cambridge: Cambridge University Press. (Encyclopedia of Mathematics and Its Applications). Dostupné online. ISBN 0-521-84802-4. S. 211. 
• MOHRI, Mehryar, 2004. Weighted Finite-State Transducer Algorithms: An Overview. Formal Languages and Application. Roč. 148, čís. 620, s. 551–564. Dostupné online. DOI 10.1007/978-3-540-39886-8_29. 
• ROARK, Brian; SPROAT, Richard. Computational Approaches to Morphology and Syntax. [s.l.]: Oxford University Press, 2007. ISBN 0-19-927478-9. 
• ROCHE, Emmanuel; SCHABES, Yves, 1997. Finite-state language processing. [s.l.]: MIT Press. Dostupné online. ISBN 0-262-18182-7. S. 1–65. 
• VAN NOORD, Gertjan; GERDEMANN, Dale. Finite State Transducers with Predicates and Identities [online]. Dostupné online. 

Související články

• Mealyho automat
• Mooreův stroj
• Morfologický slovník
• Foma (software)
• Stromový převodník
• Dvouúrovňová morfologie

Externí odkazy

• OpenFst, knihovna s otevřeným zdrojovým textem pro práci s konečnými převodníky.
• Stuttgart Finite State Transducer Tools, sada nástrojů s otevřeným zdrojovým textem pro konečné převodníky
• java FST Framework, Java FST Framework s otevřeným zdrojovým textem schopný zpracovávat textový formát OpenFst.
• Vcsn Archivováno 23. 6. 2020 na Wayback Machine., platforma s otevřeným zdrojovým textem pro C++ & IPython pro vážené automaty a racionální výrazy.
• Finite State Morphology--The Book Archivováno 19. 9. 2020 na Wayback Machine. XFST/ LEXC, popis implementace konečných převodníků firmy Xerox určených pro lingvistické aplikace.
• FOMA, implementace s otevřeným zdrojovým textem většiny funkcionalit implementace XFST/LEXC firmy Xerox.

Autoritní data	GND: 4529256-5

Portály: Matematika