有限状態変換器

フリー百科事典ウィキペディアより
ナビゲーションにジャンプ 検索にジャンプ

有限状態変換器( FST ) は、チューリング マシンの用語である入力テープと出力テープに従って、 2 つのメモリテープを備えた有限状態マシンです。これは、単一のテープを持つ通常の有限状態オートマトンとは対照的です。FST は、2 セットのシンボル間でマッピングを行う有限状態オートマトン (FSA) の一種です。[1] FST は FSA よりも一般的です。FSA は、受け入れられる文字列のセットを定義することによって形式言語を定義しますが、FST は文字列のセット間の関係を定義します。

FST は入力テープの一連の文字列を読み取り、出力テープに一連の関係を生成します。FST は、セット内のストリング間のトランスレーターまたはリレーターと考えることができます。

形態学的解析では、例として文字列を FST に入力すると、FST は形態素の列を出力します。

概要

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

テープの内容を入力として見ると、オートマトンは文字列を認識する言えますつまり、オートマトンは、文字列をセット {0,1} にマップする関数を計算します。あるいは、オートマトンが文字列を生成すると言えます。つまり、そのテープを出力テープとして見ることを意味します。このビューでは、オートマトンは一連の文字列である形式言語を生成します。オートマトンの 2 つのビューは同等です。オートマトンが計算する関数は、まさにそれが生成する文字列のセットの指標関数です。有限オートマトンによって生成される言語のクラスは、正規言語のクラスとして知られています。

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

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

有限状態トランスデューサは、自然言語処理の研究およびアプリケーションにおける音韻分析および形態分析によく使用されます。この分野のパイオニアには、ロナルド・カプランラウリ・カートチューネンマーティン・ケイ、キモ・コスケニエミが含まれます。[2] [非主要ソースが必要] トランスデューサを使用する一般的な方法は、いわゆる「カスケード」であり、合成演算子 (以下で定義) を繰り返し適用することによって、さまざまな操作用のトランスデューサが単一のトランスデューサに結合されます。

正式な建設

正式には、有限変換器Tは次のような 6 タプル ( Q、Σ、Γ、IF、δ ) です。

  • Q状態の集合である有限集合です。
  • Σは入力文字と呼ばれる有限集合です。
  • Γは出力アルファベットと呼ばれる有限集合です。
  • IQのサブセットであり、初期状態のセットです。
  • Fは、最終状態の集合であるQのサブセットです。
  • (ε は空の文字列) は遷移関係です。

( Q , δ ) は、 Tの遷移グラフとして知られるラベル付き有向グラフとして表示できます。頂点のセットはQであり、 は、頂点qから頂点rに向かうラベル付きエッジがあることを意味します。また、 a入力ラベルbはそのエッジの出力ラベルとも言います。

注: この有限変換器の定義は、文字変換器とも呼ばれます (Roche and Schabes 1997)。別の定義も可能ですが、すべてこの定義に従って変換器に変換できます。

拡張遷移関係を定義する 次のような最小のセットとして:

  • ;
  • すべてのために;
  • いつでもそれから.

拡張された遷移関係は、基本的に、エッジ ラベルを考慮して拡張された遷移グラフの再帰的遷移閉包です。の要素パスとして知られていますパスのエッジ ラベルは、パスを構成する遷移のエッジ ラベルを順番に連結することによって取得されます。

変換器T動作は、次のように定義された有理関係 [ T ] です。 存在する場合のみそのような. つまり、Tは文字列を変換します。文字列に入力ラベルがxで出力ラベルがyの初期状態から最終状態へのパスが存在する場合

加重オートマトン

有限状態変換器は重み付けできます。この場合、入力ラベルと出力ラベルに加えて、各遷移に重みが付けられます。一連のKの重みに対する重み付き有限状態トランスデューサ (WFST) は、8 タプルT =( Q , Σ, Γ, I , F , E , λ , ρ )として、重み付けされていないトランスデューサと同様に定義できます

  • Q、Σ、Γ、IFは上記のように定義されます。
  • (ここで、ε空の文字列です) は遷移の有限集合です。
  • 初期状態を重みにマッピングします。
  • 最終状態を重みにマップします。

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

確率的 FST

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

有限状態変換器の操作

有限オートマトンで定義された次の操作は、有限変換器にも適用されます。

  • ユニオン変換器TSが与えられると、変換器が存在します。そのような場合に限りまた.
  • 連結変換器TSが与えられると、変換器が存在します。そのような存在する場合のみ
  • クリーネ閉鎖変換器Tが与えられると、変換器が存在する可能性があります次の特性を持つ: [5]
;

 

 

 

 

( k1 )

もしも、 それから;

 

 

 

 

( k2 )

( k1 ) または ( k2 )によって義務付けられない限り、保持されません
  • 構成アルファベット Σ と Γ 上の変換器Tと、アルファベット Γ と Δ 上の変換器Sが与えられた場合、変換器が存在します。であるような Σ と Δ文字列が存在する場合のみそのような. この操作は重み付けされた場合に拡張されます。[6]
この定義は、数学で関係合成に使用されるのと同じ表記法を使用します。しかし、リレーション合成の従来の読み方は逆です。2 つのリレーションTSが与えられた場合、あるy存在するとき
  • オートマトンへの投影。2 つの投影関数があります。入力テープを保持し、出力テープを保存します。最初の投影、は次のように定義されます。
変換器Tが与えられると、有限オートマトンが存在します。そのような文字列yが存在する場合にのみxを受け入れます
2番目の投影、も同様に定義されます。
  • 決定化トランスデューサTが与えられた場合、一意の初期状態を持ち、どの状態からの 2 つの遷移も同じ入力ラベルを共有しないような同等のトランスデューサを構築したいと考えています。パワーセットの構造は、トランスデューサや加重トランスデューサにまで拡張できますが、停止しない場合があります。実際、一部の非決定論的トランスデューサは、同等の決定論的トランスデューサを認めていません。[7] 決定可能な変換器の特徴付けは、それらをテストするための効率的なアルゴリズムと共に提案されています[8] : [9]それらは、重み付けされたケースで使用されるセミリングと、変換器の構造に関する一般的な特性に依存しています (双子のプロパティ)。
  • 加重ケースの重量プッシュ。[10]
  • 加重ケースの最小化。[11]
  • イプシロン遷移の削除

有限状態変換器のその他の特性

  • 変換器Tの関係 [ T ]が空かどうか決定可能です。
  • 与えられた文字列xに対してx [ T ] yとなるような文字列yが存在するかどうかは決定可能です。
  • 2 つの変換器が同等かどうかは判断できません。[12]ただし、変換器Tの関係 [ T ] が(部分) 関数であるという特別な場合には、等価性は決定可能です。
  • ラベルのアルファベットを定義する場合、有限状態変換器は、アルファベット上でNDFAと同型です。、したがって決定化される可能性があります(アルファベット上の決定論的有限オートマトンに変わります)、その後、最小数の状態になるように最小化されます。[引用が必要]

アプリケーション

FST は、コンパイラの字句解析フェーズで使用され、セマンティック値を検出されたトークンに関連付けます。[13]

ab / c _ dという形式の文脈依存の書き換え規則は、言語学で音韻規則音の変化をモデル化するために使用されますが、適用が非再帰的である場合、つまり規則が書き換えを許可されていない場合、有限状態変換器と計算上同等です。同じ部分文字列を 2 回。[14]

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

も参照

注意事項

  1. ^ ダニエル・ジュラフスキー (2009). 音声および言語処理ピアソン。ISBN 9789332518414.
  2. ^ コスケニエミ 1983
  3. ^ ベルステル、ジャン。ロイテナウアー、クリストフ (2011)。適用のある非可換有理級数数学とその応用の百科事典。巻。137. ケンブリッジ:ケンブリッジ大学出版局p。16.ISBN _ 978-0-521-19022-0. Zbl  1250.68007 .
  4. ^ ロテール、M. (2005). 単語に組み合わせ論を適用数学とその応用の百科事典。巻。105. Jean Berstel、Dominique Perrin、Maxime Crochemore、Eric Laporte、Mehryar Mohri、Nadia Pisanti、Marie-France Sagot、Gesine ReinertSophie Schbath、Michael Waterman、Philippe Jacquet、Wojciech Szpankowski、Dominique Poulalhon、Gilles Schaeffer による共同作業ロマン・コルパコフ、グレゴリー・クチェロフ、ジャン=ポール・アリューシュ、ヴァレリー・ベルテケンブリッジ:ケンブリッジ大学出版局p。 211 . ISBN 0-521-84802-4. Zbl  1133.68067 .
  5. ^ ボイジェロット、バーナード。レゲイ、アクセル。ウォルパー、ピエール(2003)。「大規模なトランスデューサの反復」。コンピュータ支援検証コンピュータ サイエンスの講義ノート。巻。2725. スプリンガー ベルリン ハイデルベルク。pp.223–235。ドイ: 10.1007/978-3-540-45069-6_24 . eISSN 1611-3349ISBN  978-3-540-40524-5. ISSN  0302-9743
  6. ^ 毛利 2004 , pp. 3–5
  7. ^ 「トランスデューサの決定」 .
  8. ^ 毛利 2004 pp.5-6
  9. ^ Allauzen & Mohri 2003
  10. ^ 毛利 2004 , pp. 7–9
  11. ^ 毛利 2004 pp.9-11
  12. ^ グリフィス 1968
  13. ^ チャールズ・N・フィッシャー。ロン・K・サイトロン; リチャード・J・ルブラン・ジュニア(2010)。「スキャン - 理論と実践」. コンパイラの作成. アディソン・ウェズリー。ISBN 978-0-13-606705-4.
  14. ^ 「音韻規則システムの正規モデル」(PDF) . 2010 年 10 月 11 日にオリジナル(PDF)からアーカイブされました2012年8 月 25 日閲覧
  15. ^ ケビン・ナイトとジョナサン・メイ (2009). 「自然言語処理における加重オートマトンの応用」。マンフレッド・ドロステで。ヴェルナー・クイッチ; ハイコ・フォーグラー(編)。加重オートマトンのハンドブックスプリンガー サイエンス & ビジネス メディア。ISBN 978-3-642-01492-5.{{cite book}}: CS1 maint: uses authors parameter (link)
  16. ^ 「加重変換器による学習」(PDF) . 20174 月 29 日閲覧
  17. ^ OpenGrm

参考文献

外部リンク

さらに読む