イラストで学ぶ音声認識 改訂第2版 4. 有限状態オートマトン

イラストで学ぶ音声認識 改訂第2版 4. 有限状態オートマトン 4.1 有限状態オートマトンとは 4.2 有限状態オートマトンが表現する言語 4.3 さまざまな有限状態オートマトン 4.4 出力を生成する方法の違い 4.5 WFST の演算 1

4.1 有限状態オートマトンとは 有限状態オートマトン の定義 状態を持つ機械の振る舞いの論理的モデル 単純な有限状態オートマトンの形式的定義 : 入力記号の集合 : 状態の集合 : 初期状態の集合 : 最終状態の集合 : 状態遷移規則の集合 2

4.1 有限状態オートマトンとは 単純なオートマトンの例 入力記号列が特定の規則に従っているかどうかを，状態遷移に基づいて判定 する = {形容詞, 名詞, 助詞, 動詞} = {0, 1, 2, 3, 4} = {0} = {4} = {(0, 名詞, 1), (0, 形容詞, 2), ...} 3

4.1 有限状態オートマトンとは 決定性と非決定性 決定性オートマトン：現在の状態と入力記号から次状態が一つに定まる 非決定性オートマトン：上記条件で，次状態が一つに定まらない （同じ入力 記号で異なる状態に遷移可能な場合） 入力記号に空文字列 を含む場合は，必然的に非決定的になる 4

4.2 有限状態オートマトンが表現する言語 有限状態オートマトンで表現できる言語＝正規言語 正規言語の定義 空集合は正規言語である すべての に対して， は正規言語である と が正規言語であるとき，以下も正規言語である 連接 : 選択 : 繰り返し : これ以外のものは正規言語ではない 5

4.3 さまざまな有限状態オートマトン FSA (finite state acceptor) 入力された記号列が受理されるかどうかを判定する 構成要素： 6

4.3 さまざまな有限状態オートマトン WFSA (weighted finite state acceptor) 構成要素： （状態遷移に重みが加わる） : 重みの集合（ , など）, : 初期状態の重み, : 最終状態の重み 7

4.3 さまざまな有限状態オートマトン FST (finite state transducer) 構成要素： : 出力記号の集合 （状態遷移時に記号が出力される） 8

4.3 さまざまな有限状態オートマトン WFST (weighted finite state transducer) 構成要素： （状態遷移に重みと出力記号が加わる） 9

4.4 出力を生成する方法の違い オートマトンの型 ミーリ型：出力が状態遷移時に決まる ムーア型：出力が現在の状態で決まる ミーリ型とムーア型は相互に変換可能 この2つは等価な オートマトンです． 1:x 0:x 2:y 10

4.5 WFST の演算 オートマトンの有用な性質 決定化：非決定性オートマトンは，決定性オートマトンに変換可能 最小化：決定性オートマトンは，その機能を変えることなく，状態数最小の オートマトンに変換可能 WFST の有用な操作 合成：2つの WFST を合成して新しい WFST を作る 重み移動：状態間で重みを移動させて，計算を効率化する 11

4.5 WFST の演算 FSTの合成 2つのFST において， の出力が の入力となるとき，合成して ができる 12

4.5 WFST の演算 WFSTの合成における重みの扱い 重みが確率値の場合，通常の合成では掛け算をおこなう しかし音声認識における探索では，確率の対数の負数をとった値に対してビ タビアルゴリズムを適用する すなわち，確率の掛け算は足し算に，独立な確率の和は最小値演算になる 乗法演算が足し算，加法演算が最小値となる構造をTropical半環とよぶ． Tropical半環は通常の確率演算と同じ構造を持っているので，この構造で WFSTの合成をおこなうことができる 13

4.5 WFST の演算 決定化 単純に合成した WFST は多くの非決定性をもつので，探索の効率化のため遷 移を決定性に変換 14

4.5 WFST の演算 WFST の最小化手順 等価な状態を集合分割によって求める 15