Koncový snímač - Finite-state transducer

Převodník konečných stavu ( FST ) je konečný automat se dvěma paměťovými pásky , po terminologie pro Turing stroje : vstupní pásky a výstupní pásku. To kontrastuje s obyčejným automatem s konečným stavem , který má jedinou pásku. FST je typ automatu konečných stavů (FSA), který mapuje mezi dvěma sadami symbolů. FST je obecnější než FSA. FSA definuje formální jazyk definováním sady přijatých řetězců, zatímco FST definuje vztahy mezi sadami řetězců.

FST načte sadu řetězců na vstupní pásce a vygeneruje sadu vztahů na výstupní pásce. FST lze považovat za překladač nebo relater mezi řetězci v sadě.

Při morfologické analýze by příkladem bylo vložení řetězce písmen do FST, FST by pak vydal řetězec morfémů .

Přehled

Externí video
Koncové měniče // Karlsruhe Institute of Technology , video z YouTube

O automatu lze říci, že rozpoznává řetězec, pokud jako vstup vidíme obsah jeho pásky. Jinými slovy, automat vypočítá funkci, která mapuje řetězce do množiny {0,1}. Alternativně můžeme říci, že automat generuje řetězce, což znamená prohlížení jeho pásky jako výstupní pásky. V tomto pohledu automat generuje formální jazyk , což je sada řetězců. Dva pohledy na automaty jsou ekvivalentní: funkce, kterou automat vypočítá, je přesně indikátorovou funkcí sady řetězců, které generuje. Třída jazyků generovaných konečnými automaty je známá jako třída regulárních jazyků .

Dvě pásky snímače jsou obvykle považovány za vstupní a výstupní pásku. V tomto pohledu se říká, že převodník převádí (tj. Překládá) obsah své vstupní pásky na svou výstupní pásku přijetím řetězce na jeho vstupní pásce a generováním dalšího řetězce na jeho výstupní pásce. Může tak činit nedeterministicky a může produkovat více než jeden výstup pro každý vstupní řetězec. Převodník může také produkovat žádný výstup pro daný vstupní řetězec, v takovém případě se říká, že odmítá vstup. Převodník obecně vypočítává vztah mezi dvěma formálními jazyky.

Každý převodník konečných stavů mezi řetězci a řetězcem spojuje vstupní abecedu Σ s výstupní abecedou Γ. Vztahy R na Σ* × Γ*, které lze implementovat jako převodníky konečného stavu, se nazývají racionální vztahy . Racionální vztahy, které jsou dílčími funkcemi , tj. Které se týkají každého vstupního řetězce od Σ* maximálně do jednoho Γ*, se nazývají racionální funkce .

Převodníky konečného stavu se často používají pro fonologickou a morfologickou analýzu ve výzkumu a aplikacích zpracování přirozeného jazyka . Mezi průkopníky v této oblasti patří Ronald Kaplan , Lauri Karttunen , Martin Kay a Kimmo Koskenniemi . Běžný způsob použití snímačů je v takzvané "kaskádě", kde jsou snímače pro různé operace kombinovány do jednoho snímače opakovanou aplikací operátoru kompozice (definováno níže).

Formální konstrukce

Formálně je konečným převodníkem T 6-tice ( Q , Σ, Γ, I , F , δ ) tak, že:

• Q je konečná množina , 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 z Q , souboru počátečních stavů ;
• F je podmnožina Q , množina konečných stavů ; a
• ${\ Displaystyle \ delta \ subseteq Q \ times (\ Sigma \ cup \ {\ epsilon \}) \ times (\ Gamma \ cup \ {\ epsilon \}) \ times Q}$(kde ε je prázdný řetězec ) je přechodový vztah .

Můžeme zobrazit ( Q , ó ) jako značeného orientovaný graf , známý jako přechodné grafu z T : sada vrcholů je Q , a znamená, že je značený hranou směřující od vrcholu q na vrcholu r . Jsme také, že je vstupní štítku a b na výstupu štítku od uvedené hrany. ${\ Displaystyle (q, a, b, r) \ v \ delta}$

POZNÁMKA: Tato definice konečného měniče se také nazývá písmenný převodník (Roche a Schabes 1997); jsou možné alternativní definice, ale všechny lze převést na převodníky podle tohoto.

Definujte rozšířený přechodový vztah jako nejmenší sadu tak, že: ${\ displaystyle \ delta ^{*}}$

• ${\ Displaystyle \ delta \ subseteq \ delta ^{*}}$;
• ${\ Displaystyle (q, \ epsilon, \ epsilon, q) \ v \ delta ^{*}}$pro všechny ; a${\ displaystyle q \ v Q}$
• kdykoli a potom .${\ Displaystyle (q, x, y, r) \ v \ delta ^{*}}$${\ Displaystyle (r, a, b, s) \ v \ delta}$${\ Displaystyle (q, xa, yb, s) \ v \ delta ^{*}}$

Rozšířený přechodový vztah je v podstatě reflexivní tranzitivní uzavření přechodového grafu, který byl rozšířen tak, aby zohledňoval popisky hran. Prvky jsou známé jako cesty . Okrajové štítky cesty se získají zřetězením okrajových štítků jeho přechodů v pořadí. ${\ displaystyle \ delta ^{*}}$

Chování převodníku T je racionální vztah [ T ] je definována následujícím způsobem: v případě, a pouze tehdy, pokud existuje , a takové, že . To znamená, že T převádí řetězec na řetězec, pokud existuje cesta z počátečního stavu do konečného stavu, jehož vstupní popisek je x a jehož výstupní štítek je y . ${\ Displaystyle x [T] y}$ ${\ displaystyle i \ in I}$${\ displaystyle f \ v F}$${\ Displaystyle (i, x, y, f) \ v \ delta ^{*}}$${\ displaystyle x \ in \ Sigma ^{*}}$${\ displaystyle y \ in \ Gamma ^{*}}$

Vážené automaty

Převaděče konečného stavu mohou být váženy, přičemž každý přechod je kromě vstupních a výstupních štítků označen ještě jednou hmotností. Vážený převodník konečného stavu (WFST) přes sadu K závaží lze definovat podobně jako nevážený jako 8-tice T = ( Q , Σ, Γ, I , F , E , λ , ρ ) , kde:

• Q , Σ, Γ, I , F jsou definovány výše;
• ${\ Displaystyle E \ subseteq Q \ times (\ Sigma \ cup \ {\ epsilon \}) \ times (\ Gamma \ cup \ {\ epsilon \}) \ times Q \ times K}$(kde ε je prázdný řetězec ) je konečná sada přechodů;
• ${\ Displaystyle \ lambda: I \ rightarrow K}$ mapuje počáteční stavy na váhy;
• ${\ Displaystyle \ rho: F \ rightarrow K}$ mapuje konečné stavy na váhy.

Aby byly určité operace na WFST dobře definovány, je vhodné požadovat sadu váh k vytvoření semiring . V praxi se používají dvě typická semirings - logování semestru a tropické semiring : nedeterministické automaty mohou být považovány za váhy s booleovským semiringem .

Stochastic FST

Stochastické FST (také známé jako pravděpodobnostní FST nebo statistické FST) jsou pravděpodobně formou vážených FST.

Operace na převodnících konečného stavu

Následující operace definované na konečných automatech platí také pro konečné snímače:

• Unie . Vzhledem k tomu, že převodníky T a S existují, existuje takový převodník , že pokud a pouze pokud nebo .${\ Displaystyle T \ cup S}$${\ Displaystyle x [T \ cup S] y}$${\ Displaystyle x [T] y}$${\ Displaystyle x [S] y}$
• Zřetězení . Vzhledem k tomu, že převodníky T a S existují, existuje takový převodník , že pokud a pouze pokud existují s a${\ Displaystyle T \ cdot S}$${\ Displaystyle x [T \ cdot S] y}$${\ displaystyle x_ {1}, x_ {2}, y_ {1}, y_ {2}}$${\ Displaystyle x = x_ {1} x_ {2}, y = y_ {1} y_ {2}, x_ {1} [T] y_ {1}}$${\ Displaystyle x_ {2} [S] y_ {2}.}$
• Kleene uzavření . Vzhledem k převodníku T existuje převodník s následujícími vlastnostmi:${\ displaystyle T^{*}}$

${\ Displaystyle \ epsilon [T^{*}] \ epsilon}$;

( k1 )

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

( k2 )

a neplatí, pokud to není nařízeno ( k1 ) nebo ( k2 ).${\ Displaystyle x [T^{*}] y}$

• Složení . Vzhledem k tomu, že převodník T na abecedách Σ a Γ a měnič S na abecedách Γ a Δ, existuje převodník na Σ a Δ takový, že právě tehdy, když existuje řetězec takový, že a . Tato operace se vztahuje na vážený případ.${\ Displaystyle T \ circ S}$${\ Displaystyle x [T \ circ S] z}$${\ displaystyle y \ in \ Gamma ^{*}}$${\ Displaystyle x [T] y}$${\ Displaystyle y [S] z}$

Tato definice používá stejný zápis, jaký se používá v matematice pro sestavování vztahů . Konvenční čtení pro relační kompozici je však opačné: vzhledem ke dvěma vztahům T a S , pokud existují nějaké y takové, že a${\ Displaystyle (x, z) \ in T \ circle S}$${\ displaystyle (x, y) \ v S}$${\ Displaystyle (y, z) \ v T.}$

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

Vzhledem k převodníku T existuje konečný automat , který akceptuje x právě tehdy, pokud existuje řetězec y, pro který${\ displaystyle \ pi _ {1} T}$${\ displaystyle \ pi _ {1} T}$${\ Displaystyle x [T] y.}$

Druhá projekce je definována podobně.${\ displaystyle \ pi _ {2}}$

• Determinizace . Vzhledem k převodníku T chceme vytvořit ekvivalentní převodník, který má jedinečný počáteční stav a takový, aby žádné dva přechody opouštějící jakýkoli stav nesdílely stejnou vstupní značku. Konstrukci výkonové sady lze rozšířit na snímače nebo dokonce vážené snímače, ale někdy se nezastaví; některé nedeterministické snímače nepřiznávají ekvivalentní deterministické snímače. Byly navrženy charakteristiky determinovatelných měničů spolu s účinnými algoritmy pro jejich testování: spoléhají se na semiring použitý ve váženém případě a také na obecnou vlastnost na struktuře převodníku (vlastnost dvojčat ).
• Váha tlačící na vážené pouzdro.
• Minimalizace pro vážený případ.
• Odstranění epsilonových přechodů .

Další vlastnosti převodníků s konečným stavem

• Lze rozhodnout, zda je vztah [ T ] snímače T prázdný.
• Je rozhodnutelné, zda existuje řetězec y takový, že x [ T ] y pro daný řetězec x .
• Je nerozhodné, zda jsou dva měniče ekvivalentní. Ekvivalence je však rozhodnutelná ve zvláštním případě, kde vztah [ T ] snímače T je (částečná) funkce.
• Pokud definujeme abecedu štítků , převodníky konečného stavu jsou izomorfní vůči NDFA nad abecedou , a proto mohou být determinovány (přeměněny na deterministické konečné automaty nad abecedou ) a následně minimalizovány tak, aby měly minimální počet stavů.${\ Displaystyle L = (\ Sigma \ cup \ {\ epsilon \}) \ times (\ Gamma \ cup \ {\ epsilon \})}$${\ displaystyle L}$${\ Displaystyle L = [(\ Sigma \ cup \ {\ epsilon \}) \ times \ Gamma] \ cup [\ Sigma \ times (\ Gamma \ cup \ {\ epsilon \})]}}$

Aplikace

Kontextově citlivá přepisovací pravidla formy a → b / c _ d , používaná v lingvistice k modelování fonologických pravidel a zvukové změny , jsou výpočetně ekvivalentní převodníkům s konečným stavem za předpokladu, že aplikace je nerekurzivní, tj. Pravidlo nesmí přepisovat stejný podřetězec dvakrát.

Vážení FST našli uplatnění ve zpracování přirozeného jazyka , včetně strojového překladu , a ve strojovém učení . Implementaci pro označování části řeči lze najít jako jednu součást knihovny OpenGrm.

Viz také

• Mealy machine
• Mooreův stroj
• Morfologický slovník
• foma (software)
• Převodník stromů

Poznámky

Reference

externí odkazy

• OpenFst , open-source knihovna pro operace FST.
• Stuttgart Finite State Transducer Tools , další open-source sada nástrojů FST
• java FST Framework , open-source java FST Framework schopný zpracovávat textový formát OpenFst.
• Vcsn , platforma s otevřeným zdrojovým kódem (C ++ a IPython) pro vážené automaty a racionální výrazy.
• Morfologie konečného stavu-Kniha XFST/ LEXC, popis implementace převodníků konečného stavu společnosti Xerox určených pro lingvistické aplikace.
• FOMA , open-source implementace většiny schopností implementace Xerox XFST/ LEXC.

Další čtení

• Jurafsky, Daniel ; James H. Martin (2000). Zpracování řeči a jazyka . Sál Prentice. s.  71 –83. ISBN 0-13-095069-6.
• Kornai, Andras (1999). Rozšířené konečné jazykové modely . Cambridge University Press. ISBN 0-521-63198-X.
• Roche, Emmanuel; Yves Schabes (1997). Jazykové zpracování konečného stavu . Stiskněte MIT. s.  1 –65. ISBN 0-262-18182-7.
• Beesley, Kenneth R .; Lauri Karttunen (2003). Morfologie konečného stavu . Centrum pro studium jazyka a informací. ISBN 1-57586-434-7.
• Roark, Brian; Richard Sproat (2007). Výpočtové přístupy k morfologii a syntaxi . Oxford University Press. ISBN 978-0-19-927478-9.
• Berstel, Jean (1979). Převody a bezkontextové jazyky . Teubner Verlag.. Zdarma verze PDF