有限状態トランスデューサ (FST) を用いた音声言語処理
塚田 元
tsukada@cslab.kecl.ntt.co.jp

NTT コミュニケーション科学基礎研究所
2002 年 12 月 20 日

Copyright(C) NTT, 2002

あらすじ

• 重み付き有限状態トランスデューサ (Weighted Finite StateTransducer) の定式化
• WFST の基本演算• 音声認識の定式化

1

Copyright(C) NTT, 2002

シンボル

シンボル＋遷移確率

入力・出力シンボル

入力・出力シンボル＋重み?

種々の有限状態機械?

有限状態オートマトン(Finite State Automaton)
確率的 FSA (Probabilistic FSA)
決定的 PFSA = Markov Model

非決定的 PFSA = Hidden Markov Model
有限状態トランスデューサ(Finite State Transducer)
重み付き FST(Weighted FST)

2

Copyright(C) NTT, 2002

有限状態オートマトン (FSA) – 定義 –A = (Σ, Q, E, I, F )• Σ: アルファベット• Q: 状態の有限集合• E : Q × (Σ ∪ {}) × Q: 遷移の有限集合• I ⊆ Q: 初期状態の集合• F ⊆ Q: 最終状態の集合

全ての FSA は決定的でかつ状態数最小の等価な FSA に変換可能．

3Copyright(C) NTT, 2002

1aaεcb63

非決定的 FSA の例
25dd44Copyright(C) NTT, 2002

1,2aab25 の消去結果
bc36dd45Copyright(C) NTT, 2002

1,2ab2,5決定化の結果

bc36dd46Copyright(C) NTT, 2002

1,2ab2,5最小化の結果

bc3,6d47Copyright(C) NTT, 2002

重み付き有限状態トランスデューサ (WFST) –定義–
A = (Σ, ∆, Q, K, E, I, F )• Σ: 入力アルファベット• ∆: 出力アルファベット• Q: 状態の有限集合• K: 重みの半環• E : Q × (Σ ∪ {}) × (∆ ∪ {}) × K × Q: 遷移の有限集合• λ : I → K: 初期状態重み関数• ρ : F → K ： 最終状態重み関数• I ⊆ Q: 初期状態の集合• F ⊆ Q: 最終状態の集合

8

Copyright(C) NTT, 2002

半環 (semiring)

確率値
log 確率値

半環の種類[−∞, +∞][−∞, 0][0, 1]

集合

longest common
prefixminmax+⊕

連結++×⊗

∞+∞

−∞00

0011

半環 (K, ⊕, ⊗, 0, 1): 逆元なしの環 (ring)

tropicalΣ∗ ∪ {∞}(Viterbi 近似)

string9

Copyright(C) NTT, 2002

演算: 合成 (composition)
入力
二つのトランスデューサ T1 , T2

z [T1 ](x, z) ⊗ [T2 ](z, y)

出力
以下の式を満たす T1 ◦ T2[T1 ◦ T2 ](x, y) =10

Copyright(C) NTT, 2002

a:a/0.2

例: ⊗ が + の半環

T10T1 ◦ T2

2

T2

0

a:x/0.3

b:y/0.3
1,12,1

1

c:z/0.1

c:z/0.4

y:y/0.2

b:b/0.2

演算: 合成 (composition)

1,0c:c/0.3

a:x/0.5

1b:y/0.1

0,011Copyright(C) NTT, 2002

演算: 決定化 (determinization)

入力： WFST
出力： １つの初期状態をもち、１つの入力アルファベットに対して、１つの状態から高々１つの遷移をもつ WFST。

• 半環の条件： weekly left divisible• 必ずしも全ての WFST が決定化できるわけではない。
• 非循環は決定化可能であることの十分条件。

12

Copyright(C) NTT, 2002

01

b:a/0.3
a:ε/0.2
a:a/0.1
3

決定化の入力b:a/0.5

c:c/0.42

4

d:c/0.6

d:ε/0.6

5

13

Copyright(C) NTT, 2002

(0,(ε,0))(2,(ε,0))決定化の出力b:aa/0.6

b:a/0.3

a:ε/0.1(3,(a,0))(1,(a,0.1)) c:ac/0.4 (4,(ε,0))(q,u)∈S

d:c/0.6(5,(ε,0))

d:ε/0.6q  ∈T rans(q,a) u ⊗ δ(q, a, q )状態： (元の状態, (未出力記号, 未出力重み)) の集合
出力関数： δ  (S, a) =遷移関数：

T rans (S, a) = (q,u)∈S q ∈T rans(q,a) {(q  , δ  (S, a)−1 (u ⊗ δ(q, a, q  )))}

14

Copyright(C) NTT, 2002

入力： WFST

演算： pushing

出力： 可能な限り出力アルファベットを早期に出力し、重みについても極力初期状態に引き寄せた WFST。(或る種の正規化手法)• 条件： weekly divisible semiring, zero-sum free semiring/machine

15Copyright(C) NTT, 2002

(ε,0)
a:ε/0.1
a:a/1.1(ε,0.6)(c,0.6)

pushing の例
b:a/0.3
b:ac/0.9

c:ac/0.4

b:aa/0.6
b:ac/0.2
(a,1)
c:c/0

d:c/0.6
d:ε/0
d:ε/0.6d:ε/0π∈P ath(q,F in) out(π)(ε,0)• 最終状態まで至る全てのパスにおいて、出力列の『(longestcommon preﬁx, 出力重みの和)』を、各状態に保持。
• 各状態の値： distance(q) =• 出力関数：out (e) = distance(src(e))−1 (out(e) ⊗ distance(dest(e)))

16

Copyright(C) NTT, 2002

演算： 最小化 (minimization)
入力： 決定的な WFST
出力： 状態数が最小の決定的 WFST

• pushing により正規化• 通常の FSA の最小化アルゴリズムを適用

17

Copyright(C) NTT, 2002

0a:a/1.1

0a:a/1.1

c:c/0

c:c/02,332

最小化の例
b:ac/0.9

b:ac/0.2

1b:ac/0.9

b:ac/0.2

1

d:ε/0

d:ε/0

d:ε/0

4

418

Copyright(C) NTT, 2002

oacoustic
observation

Hcpphones

Lw
words

音声認識のモデル化
C

context-dependent
phones• argmaxw P (w|o) = argmaxw P (o|w)P (w) =argmaxw P (o|c)P (c|p)P (p|w)P (w)Gwwords• 各々の P (x|y) を WFST によりモデル化。o を入力としたときH ◦ C ◦ L ◦ G が出力する最も尤もらしい w を求める問題として定式化。
• メモリと計算時間のトレードオフにより、静的に合成(composition) しておく範囲を選択できる。

• 木構造辞書により音響・言語尤度を共有化する技術の一般化とみなせる。静的に合成しておく範囲を増やすことで、サーチエラーを減らすことができる。

19

Copyright(C) NTT, 2002

trigram の例
aba:a/P(a|c)

c

ε:ε/b(bc)c:c/P(c|ab)bc

a:a/P(a) εb:b/P(b)c:c/P(c|b)ε:ε/b(ca) ε:ε/b(c) c:c/P(c)b:b/P(b|ca)
ε:ε/b(ab)b:b/P(b|a)ε:ε/b(b)a ε:ε/b(a)bca

a:a/P(a|bc)

20Copyright(C) NTT, 2002

i:ε/0.5
i:駅/1g:ε/1

発音辞書の例

e:ε/0.5
k:ε/1

E:ε/1

e:ε/1o:英語/121

Copyright(C) NTT, 2002

ε, ∗x/ε_x:xy/ε_x:yx/x_y:xy, yy/x_ε:yx/ε_ε:xy, ε

y/y_ε:yx/y_y:xx, yy, xy/x_x:yy/x_y:y y/y_y:y y/y_x:yx/y_x:xTriphone トランスデューサの例

x/ε_y:xx/x_x:xx, xy/ε_y:yy/ε_ε:yx/y_ε:xx/x_ε:xx, ε22

Copyright(C) NTT, 2002

実用上の工夫• 言語モデルのネットワークサイズを爆発させないために、 を普通の記号として扱う。

k i t a #1
来た北• 決定化が可能になるように、仮想的な音素を導入し同音異義語を無くす。

k i t a #2

この仮想記号を出力するような自己ループを H や C に付け加える。

23

Copyright(C) NTT, 2002

H ◦ min(det(C ◦ L ◦ G))

H ◦C ◦L◦GGL

C

H

ネットワーク

1,742,876

2,068,728

4,413,443

159,427

129,370

795

33,767

状態数4,618,082

5,925,541

9,264,432

517,597

149,693

39,21050,672遷移数

講演音声の認識実験 – ネットワークサイズ –min(det(H ◦ min(det(C ◦ L ◦ G))))※ min は pushing を含む。

24

Copyright(C) NTT, 2002

講演音声の認識実験 – サーチエラーと探索効率 –• 認識対象： 日本語話し言葉コーパス テストセット (4 講演)• 認識結果： 単語誤り率 (処理時間 RTF)

51.8

(3.0)

(17.5)

35.2

36.5

51.2

(3.0)

(4.1)

(21.8)

尤度幅 100

H ◦C ◦L◦G

38.5(2.2)

尤度幅 90H ◦ min(det(C ◦ L ◦ G))

36.8

ネットワークmin(det(H ◦ min(det(C ◦ L ◦ G))))

音声認識実験は、Daniel Willett 氏の作成したデコーダ、MIT の FST ツールを用いて、堀 貴明氏に実施いただいた。

25

Copyright(C) NTT, 2002

まとめ

• 音響モデルから言語モデルまでを融合したモデルがひとつのWFST として実現可能になり、大語彙連続音声認識に適用されるようになってきた。

• 従来の探索手法に比べ、サーチエラーを減らすことが可能。
今後の研究課題• ネットワークサイズの縮小化• 本手法と相性のよい近似手法• パラメータおよび構造の学習• 全体最適化• より高度な言語処理 (トピック抽出、要約、機械翻訳など) との融合

26

Copyright(C) NTT, 2002

参考文献

基本演算
Roche and Schabes eds, Finite-State Language Processing, The MITPress, 1997.

Mohri, Finite-State Transducers in Language and Speech Processing,Computational Linguistics, 23(2), 1997.
Mohri, Minimization Algorithms for Sequential Transducers,
Theoretical Computer Science, 234, 2000.

大語彙連続音声認識
Mohri, Pereira, and Riley, Weighted Finite-State Transducers inSpeech Recognition. Computer Speech and Language, 16(1), 2002.

チュートリアルMohri and Riley, Weighted Finite-State Transducers in Speech
Recognition, ICSLP’02

27

Copyright(C) NTT, 2002