有限状態トランスデューサ

外部ビデオ
外部ビデオ
	有限状態トランスデューサー //カールスルーエ工科大学、YouTube ビデオ

有限状態トランスデューサ（FST ）は、チューリングマシンの用語に従って、入力テープと出力テープという2つのメモリテープを持つ有限状態マシンです。これは、テープが1つしかない通常の有限状態オートマトンとは対照的です。FSTは、2つのシンボルセット間をマッピングする有限状態オートマトン（FSA）の一種です。^[1] FSTはFSAよりも一般的です。FSAは受け入れられる文字列のセットを定義することによって形式言語を定義しますが、FSTは文字列のセット間の関係を定義します。

FST は、入力テープ上の文字列のセットを読み取り、出力テープ上に関係のセットを生成します。FST は、セット内の文字列間の翻訳者または関係者と考えることができます。

形態素解析では、たとえば文字列を FST に入力すると、FST は形態素の文字列を出力します。

概要

オートマトンが文字列を認識するのは、そのテープの内容を入力とみなした場合です。言い換えると、オートマトンが文字列を集合 {0,1} にマッピングする関数を計算するということです。あるいは、オートマトンが文字列を生成するとも言えます。これは、そのテープを出力テープとみなすことを意味します。この見方では、オートマトンが生成する形式言語は文字列の集合です。オートマトンに関するこの 2 つの見方は同等です。つまり、オートマトンが計算する関数は、まさにそれが生成する文字列の集合の指示関数です。有限オートマトンによって生成される言語のクラスは、正規言語のクラスとして知られています。

トランスデューサの 2 つのテープは、通常、入力テープと出力テープとして考えられます。この見方では、トランスデューサは、入力テープ上の文字列を受け入れ、出力テープ上に別の文字列を生成することによって、入力テープの内容を出力テープに変換(つまり、翻訳) すると言われています。トランスデューサは、これを非決定的に実行し、各入力文字列に対して複数の出力を生成する場合があります。トランスデューサは、特定の入力文字列に対して出力を生成しない場合もあります。その場合、トランスデューサは入力を拒否すると言われています。一般に、トランスデューサは、 2 つの形式言語間の関係を計算します。

各文字列間有限状態トランスデューサは、入力アルファベット Σ を出力アルファベット Γ に関連付けます。有限状態トランスデューサとして実装できる Σ*×Γ* 上の関係Rは、有理関係と呼ばれます。部分関数である有理関係、つまり Σ* からのすべての入力文字列を最大で 1 つの Γ* に関連付ける有理関係は、有理関数と呼ばれます。

有限状態トランスデューサは、自然言語処理の研究や応用において、音韻解析や形態論解析によく使用されます。この分野の先駆者としては、ロナルド・カプラン、ラウリ・カルトゥネン、マーティン・ケイ、キモ・コスケンニエミなどがいます。^[2]^[^{非一次資料が必要}^] トランスデューサの一般的な使用方法は、いわゆる「カスケード」で、さまざまな操作のトランスデューサが、合成演算子 (以下で定義) を繰り返し適用することで 1 つのトランスデューサに結合されます。

正式な建設

正式には、有限トランスデューサTは、次の6 組 ( $Q 、Σ、Γ、 I 、 F 、δ$ ) です。

$Q は$ 有限集合、つまり状態の集合です。
$Σ は$ 入力アルファベットと呼ばれる有限集合です。
$Γ は$ 有限集合であり、出力アルファベットと呼ばれます。
$I は$ 初期状態の集合である $Q$ のサブセットです。
$F は$ 最終状態の集合である $Q$ のサブセットであり、
$\delta \subseteq Q\times (\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})\times Q$ （ここでεは空の文字列）は遷移関係である。

( Q , δ ) をラベル付き有向グラフ、つまりTの遷移グラフとして見ることができます。頂点の集合はQであり、頂点qから頂点rに向かうラベル付きエッジがあることを意味します。また、 a はそのエッジの入力ラベル、b はそのエッジの出力ラベルであるとも言えます。 $(q,a,b,r)\in \delta$

注: この有限トランスデューサーの定義は、文字トランスデューサーとも呼ばれます(Roche および Schabes 1997)。代替の定義も可能ですが、すべてこの定義に従ったトランスデューサーに変換できます。

拡張遷移関係 を、次の最小の集合として定義します。 $\delta ^{*}$

$\delta \subseteq \delta ^{*}$ ;
$(q,\epsilon ,\epsilon ,q)\in \delta ^{*}$ すべてに対して; そして $q\in Q$
いつでも、そしてその時。 $(q,x,y,r)\in \delta ^{*}$ $(r,a,b,s)\in \delta$ $(q,xa,yb,s)\in \delta ^{*}$

拡張遷移関係は、本質的には、エッジラベルを考慮するように拡張された遷移グラフの反射推移閉包です。の要素はパスと呼ばれます。パスのエッジラベルは、その構成遷移のエッジラベルを順番に連結することによって取得されます。 $\delta ^{*}$

トランスデューサTの動作は、次のように定義される有理関係 [ T ] です。およびが存在し、となる場合のみです。つまり、入力ラベルがxで出力ラベルがyである初期状態から最終状態へのパスが存在する場合、T は文字列を文字列に変換します。 $x[T]y$ $i\in I$ $f\in F$ $(i,x,y,f)\in \delta ^{*}$ $x\in \Sigma ^{*}$ $y\in \Gamma ^{*}$

重み付きオートマトン

有限状態トランスデューサは重み付けすることができ、各遷移には入力ラベルと出力ラベルに加えて重みが付けられます。重みセットK上の重み付き有限状態トランスデューサ (WFST) は、重みなしのものと同様に、8 組 $T =(Q 、Σ、Γ、 I 、 F 、 E 、 λ 、 ρ)$ として定義できます。ここで、

$Q 、Σ、Γ、 I 、 F$ は上記のように定義されます。
$E\subseteq Q\times (\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})\times Q\times K$ （ここでεは空の文字列）は遷移の有限集合である。
$\lambda :I\rightarrow K$ 初期状態を重みにマッピングします。
$\rho :F\rightarrow K$ 最終状態を重みにマッピングします。

WFST に対する特定の操作を明確に定義するには、重みの集合が半環を形成することを要求すると便利です。^[3]実際に使用される 2 つの典型的な半環は、対数半環と熱帯半環です。非決定性オートマトンでは、ブール半環に重みがあるとみなすことができます。^[4]

ストキャスティック FST

確率的 FST (確率的 FST または統計的 FST とも呼ばれる) は、おそらく加重 FST の一種です。^{[引用が必要]}

有限状態トランスデューサの操作

有限オートマトンで定義された次の操作は有限トランスデューサにも適用されます。

和集合。トランスデューサ $T$ と $S$ が与えられたとき、またはの場合にのみとなるトランスデューサが存在する。 $T\cup S$ $x[T\cup S]y$ $x[T]y$ $x[S]y$
連結。トランスデューサ $T$ と $S$ が与えられたとき、トランスデューサが存在し、かつが存在する場合に限り、 $T\cdot S$ $x[T\cdot S]y$ $x_{1},x_{2},y_{1},y_{2}$ $x=x_{1}x_{2},y=y_{1}y_{2},x_{1}[T]y_{1}$ $x_{2}[S]y_{2}.$
クリーネ閉包。トランスデューサ $T$ が与えられたとき、以下の特性を持つトランスデューサが存在する可能性がある。 ^[5] $T^{*}$

( k1 )または( k2 )によって強制されない限り成立しない。

x[T^{*}]y

合成。アルファベット Σ と Γ 上のトランスデューサ $T$ とアルファベット Γ と Δ 上のトランスデューサ $S$ が与えられたとき、となる文字列が存在する場合のみ、となるΣ と Δ 上のトランスデューサが存在する。この操作は重み付きの場合にも拡張される。^[6] $T\circ S$ $x[T\circ S]z$ $y\in \Gamma ^{*}$ $x[T]y$ $y[S]z$

この定義は、数学で関係合成に使用されるのと同じ表記法を使用しています。ただし、関係合成の従来の読み方は逆です。2つの関係

T

と

S

が与えられ、

yが

存在し、かつ

(x,z)\in T\circ S

(x,y)\in S

(y,z)\in T.

オートマトンへの投影。投影関数には、入力テープの保存と出力テープの保存の 2 つがあります。最初の投影は次のように定義されます。 $\pi _{1}$ $\pi _{2}$ $\pi _{1}$

変換器

Tが与えられたとき、文字列

yが存在する場合にのみxを受け入れるような有限オートマトンが存在する。

\pi _{1}T

\pi _{1}T

x[T]y.

2 番目の投影も同様に定義されます。

\pi _{2}

決定化。トランスデューサ $T$ が与えられたとき、一意の初期状態を持ち、どの状態から出る 2 つの遷移も同じ入力ラベルを共有しないような等価なトランスデューサを構築したい。べき集合の構築はトランスデューサ、さらには重み付きトランスデューサに拡張できるが、停止に失敗することがある。実際、非決定性トランスデューサの中には、等価な決定性トランスデューサを受け入れないものがある。^{[7]決定可能なトランスデューサの} 特徴付けは、それらをテストするための効率的なアルゴリズムとともに提案されている^{[8] 。}^[9]これらは、重み付きの場合に使用される半環と、トランスデューサの構造に関する一般的な特性 (双子特性) に依存している。
重み付けされたケースの重み付けプッシュ。^[10]
重み付きケースの最小化。^[11]
イプシロン遷移の除去。

有限状態トランスデューサの追加特性

トランスデューサTの関係[ T ]が空であるかどうかを決定できます。
与えられた文字列xに対してx [ T ] yとなる文字列yが存在するかどうかは決定可能である。
2つの変換器が同等であるかどうかは決定できない。^[12]ただし、変換器Tの関係[ T ]が（部分）関数である特殊なケースでは同等性が決定可能である。
ラベルのアルファベットを定義すると、有限状態トランスデューサはアルファベット上のNDFAと同型であり、したがって決定化（アルファベット上の決定論的有限オートマトンに変換）され、その後、状態数が最小になるように最小化される。^[^要出典^] $L=(\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})$ $L$ $L=[(\Sigma \cup \{\epsilon \})\times \Gamma ]\cup [\Sigma \times (\Gamma \cup \{\epsilon \})]$

アプリケーション

FSTはコンパイラの字句解析フェーズで、発見されたトークンに意味値を関連付けるために使用されます。 ^[13]

言語学で音韻規則や音の変化をモデル化するために使われるa → b / c_d形式の文脈依存書き換え規則は、適用が非再帰的、つまり規則が同じ部分文字列を2回書き換えることが許されていない限り、有限状態トランスデューサと計算上は同等である。^[14]

重み付きFSTは、機械翻訳を含む自然言語処理や機械学習に応用されています。^[15]^[16]品詞タグ付けの実装は、 OpenGrm ^[17]ライブラリの1つのコンポーネントとして見つけることができます。

参照

注記

^ Jurafsky, Daniel (2009).音声言語処理. ピアソン. ISBN 9789332518414。
^ コスケンニエミ 1983
^ Berstel, Jean; Reutenauer, Christophe (2011).非可換有理数級数とその応用. 数学とその応用百科事典. 第137巻. ケンブリッジ:ケンブリッジ大学出版局. p. 16. ISBN 978-0-521-19022-0.ZBL1250.68007 。
^ ロテール、M. (2005)。単語に組み合わせ論を応用。数学とその応用の百科事典。 Vol. 105. ジャン・ベルステル、ドミニク・ペラン、マキシム・クロシュモア、エリック・ラポルト、メリヤル・モーリ、ナディア・ピサンティ、マリー＝フランス・サゴ、ジェシーヌ・ライナート、ソフィー・シュバス、マイケル・ウォーターマン、フィリップ・ジャケ、ヴォイチェフ・シュパンコウスキー、ドミニク・ポラロン、ジル・シェーファーによる共同作品。ロマン・コルパコフグレゴリー・クチェロフ、ジャン＝ポール・アルーシュ、ヴァレリー・ベルテ。ケンブリッジ：ケンブリッジ大学出版局。 p. 211.ISBN 0-521-84802-4.ZBL1133.68067 。
^ Boigelot, Bernard; Legay, Axel; Wolper, Pierre (2003). 「大規模システムにおける反復トランスデューサ」。コンピュータ支援検証。コンピュータサイエンスの講義ノート。第 2725 巻。Springer Berlin Heidelberg。pp. 223–235。doi : 10.1007 / 978-3-540-45069-6_24。eISSN 1611-3349。ISBN 978-3-540-40524-5. ISSN 0302-9743.
^ 毛利 2004、3-5ページ
^ 「トランスデューサーの決定化」。
^ 毛利 2004、5-6 ページ
^ アラウゼン＆モーリ 2003
^ 毛利 2004、7-9ページ
^ 毛利 2004、9-11頁
^ グリフィス 1968
^ Charles N. Fischer、Ron K. Cytron、Richard J. LeBlanc, Jr. (2010)。「スキャン - 理論と実践」。コンパイラの作成。Addison- Wesley。ISBN 978-0-13-606705-4。
^ 「音韻規則システムの正規モデル」(PDF) 。 2010年10月11日時点のオリジナル(PDF)からアーカイブ。2012年8月25日閲覧。
^ Kevin Knight、Jonathan May (2009)。「自然言語 処理における重み付きオートマトン応用」。Manfred Droste、Werner Kuich、Heiko Vogler (編)。重み付きオートマトンハンドブック。Springer Science & Business Media。ISBN 978-3-642-01492-5。
^ 「重み付きトランスデューサーによる学習」(PDF) 。 2017年4月29日閲覧。
^ オープンGrm

参考文献

Allauzen, Cyril; Mohri, Mehryar (2003). 「双子特性をテストするための効率的なアルゴリズム」(PDF) . Journal of Automata, Languages and Combinatorics . 8 (2): 117–144.
Koskenniemi, Kimmo (1983)、「2 レベル形態論: 語形認識と生成の一般的な計算モデル」(PDF) 、ヘルシンキ大学一般言語学科、2018 年 12 月 21 日にオリジナル(PDF)からアーカイブ、 2010 年 1 月10 日に取得
Mohri, Mehryar (2004)。「重み付き有限状態トランスデューサアルゴリズム。概要」(PDF)。形式言語とアプリケーション。あいまいさとソフトコンピューティングの研究。第 148 巻。pp. 551–564。doi : 10.1007 / 978-3-540-39886-8_29。ISBN 978-3-642-53554-3。
Griffiths, TV (1968). 「Λ-Free 非決定性一般化マシンの等価性の問題の解決不能性」Journal of the ACM . 15 (3). ACM: 409–413. doi :10.1145/321466.321473.

外部リンク

OpenFst は、FST 操作用のオープンソースライブラリです。
有限状態形態論 - 書籍 Archived 2022-03-25 at the Wayback Machine XFST/LEXC は、言語アプリケーション向けの有限状態トランスデューサーのゼロックス実装の説明です。
ヘルシンキのオープンソース実装とゼロックスfstの拡張
FOMA は、Xerox XFST/LEXC 実装のほとんどの機能をオープンソースで実装したものです。
Stuttgart Finite State Transducer Tools、別のオープンソース FST ツールキット
Java FST Framework は、OpenFst テキスト形式を処理できるオープンソースの Java FST フレームワークです。
Vcsn は、重み付きオートマトンと有理数式のためのオープンソースプラットフォーム (C++ および IPython) であり、Wayback Machineで 2020-06-23 にアーカイブされています。

さらに読む

ジュラフスキー、ダニエル、ジェームズ・H・マーティン（2000年）。音声言語処理。プレンティス・ホール。pp.71-83。ISBN 0-13-095069-6。
コルナイ、アンドラーシュ(1999)。言語の拡張有限状態モデル。ケンブリッジ大学出版局。ISBN 0-521-63198-X。
ロッシュ、エマニュエル。イヴ・シャーベス (1997)。有限状態言語処理。 MITプレス。 1 ～ 65 ページ。ISBN 0-262-18182-7。
Beesley, Kenneth R.; Lauri Karttunen (2003)。有限状態形態論。言語情報研究センター。ISBN 1-57586-434-7。
ロアーク、ブライアン、リチャード・スプロート（2007年）。形態論と統語論への計算的アプローチ。オックスフォード大学出版局。ISBN 978-0-19-927478-9。
ジャン・ベルステル (1979)。変換と文脈自由言語。トイブナー・フェルラーク。. 無料PDF版

[1] Jurafsky, Daniel (2009).音声言語処理. ピアソン. ISBN 9789332518414。

[2] コスケンニエミ 1983

[BR16-3] Berstel, Jean; Reutenauer, Christophe (2011).非可換有理数級数とその応用. 数学とその応用百科事典. 第137巻. ケンブリッジ:ケンブリッジ大学出版局. p. 16. ISBN 978-0-521-19022-0.ZBL1250.68007 。

[Lot211-4] ロテール、M. (2005)。単語に組み合わせ論を応用。数学とその応用の百科事典。 Vol. 105. ジャン・ベルステル、ドミニク・ペラン、マキシム・クロシュモア、エリック・ラポルト、メリヤル・モーリ、ナディア・ピサンティ、マリー＝フランス・サゴ、ジェシーヌ・ライナート、ソフィー・シュバス、マイケル・ウォーターマン、フィリップ・ジャケ、ヴォイチェフ・シュパンコウスキー、ドミニク・ポラロン、ジル・シェーファーによる共同作品。ロマン・コルパコフグレゴリー・クチェロフ、ジャン＝ポール・アルーシュ、ヴァレリー・ベルテ。ケンブリッジ：ケンブリッジ大学出版局。 p. 211.ISBN 0-521-84802-4.ZBL1133.68067 。

[BoigelotLegayWolper2003-5] Boigelot, Bernard; Legay, Axel; Wolper, Pierre (2003). 「大規模システムにおける反復トランスデューサ」。コンピュータ支援検証。コンピュータサイエンスの講義ノート。第 2725 巻。Springer Berlin Heidelberg。pp. 223–235。doi : 10.1007 / 978-3-540-45069-6_24。eISSN 1611-3349。ISBN 978-3-540-40524-5. ISSN 0302-9743.

[6] 毛利 2004、3-5ページ

[7] 「トランスデューサーの決定化」。

[8] 毛利 2004、5-6 ページ

[9] アラウゼン＆モーリ 2003

[10] 毛利 2004、7-9ページ

[11] 毛利 2004、9-11頁

[12] グリフィス 1968

[13] Charles N. Fischer、Ron K. Cytron、Richard J. LeBlanc, Jr. (2010)。「スキャン - 理論と実践」。コンパイラの作成。Addison- Wesley。ISBN 978-0-13-606705-4。

[14] 「音韻規則システムの正規モデル」(PDF) 。 2010年10月11日時点のオリジナル(PDF)からアーカイブ。2012年8月25日閲覧。

[DrosteKuich2009-15] ^ Kevin Knight、Jonathan May (2009)。「自然言語 処理における重み付きオートマトン応用」。Manfred Droste、Werner Kuich、Heiko Vogler (編)。重み付きオートマトンハンドブック。Springer Science & Business Media。ISBN 978-3-642-01492-5。

[16] 「重み付きトランスデューサーによる学習」(PDF) 。 2017年4月29日閲覧。

[17] オープンGrm