1. No category

音声言語処理特論
第３回 連続音声認識アルゴリズム 山本一公
連続音声認識
•  前回の話 –  テンプレートは単語単位 –  入力発声も単語単位 –  入力発声特徴時系列をN単語のテンプレートとマッチングして、最も
累積距離の小さいテンプレートを認識結果の単語として選ぶ •  タスクを大きくする –  １発声に複数の単語が含まれる –  その場合にすべての発声パターンを事前にテンプレート化することは
現実的ではない •  例えば5,000語語彙のn単語連鎖の可能なパターンは5,000n個 –  ２単語連鎖で25,000,000個、３単語連鎖で1.25x1011個のパターン –  認識単位（単語、音節、音素）を接続しながら認識していく必要がある •  如何に効率よく計算するか
音声言語処理特論　第3回
2
前回の復習
Fは(1,1)から(I,J)へ 至る経路
D( A, B) = min
F
整合窓
標
準
Cx = ( I , J )
bJ
j =i+r
warping function
bj
b2
b1
1
2 1
w(k ) = i(k ) − i(k − 1) + j (k ) − j (k − 1)
C = (i, j )
ー
：
・対称形
∑ w(k ) ⋅ d (i(k ), j (k ))
∑ w(k )
C2
C4
C3
⎧ D(i − 1, j ) + d (i, j )
⎫
⎪
⎪
D(i, j ) = min ⎨ D(i, j − 1) + d (i, j )
⎬
⎪ D(i − 1, j − 1) + 2d (i, j )⎪
⎩
⎭
j =i−r
C5
C1 = (1,1)
a1 a2
ai
入力パターン：Ａ
aI
・非対称形
1
1
1
w(k ) = i (k ) − i (k − 1)
音声言語処理特論　第3回
3
DPマッチングのポイント
•  ある格子点において、 ①  その格子点にたどり着いた時の最小累積距離 ②  最小距離になるとき、どっちの方向からその格子点にたどり着いた
のか この2点だけを記憶する –  結果として得られる、出発点から到着点までの最短経路がその格子
点を通るかどうかは分からないが、「仮に通るとすれば」、出発点から
その格子点までの最短距離と、その格子点から到着点までの最短距
離の合計になるはずである –  その格子点にたどり着くための経路は何種類もあるが、直前に通る
格子点だけを考えればよい。 •  全ての格子点について、「最短経路がそこを通るかもしれない」と
思って、そこに至る最短経路を計算しておく –  開始点から順番に計算していくと、最短経路が計算される！
音声言語処理特論　第3回
4
DPマッチングのやり方（１）
1
2 1
b5
b4
b3
g(2,2)=min{ d(a2,b2)+g(1,2),
d(a2,b2)+g(2,1),
2 ×d(a2,b2)+g(1,1) }
b2
b(2,2)=argmin{ d(a2,b2)+g(1,2),
d(a2,b2)+g(2,1),
2 ×d(a2,b2)+g(1,1) }
b1
a1
a2
a3
a4
a5
音声言語処理特論　第3回
a6
a7
←DP距離
（累積距離）
←バック
ポインタ
（どっちから
来たか）
5
DPマッチングのやり方（２）
1
2 1
g(7,5) ←DP距離
b(7,5) ←バック
ポインタ
b5
b4
b3
b2
b1
a1
a2
a3
a4
a5
音声言語処理特論　第3回
a6
a7
6
DPマッチングのやり方（３）
1
2 1
g(7,5) ←DP距離
b(7,5) ←バック
ポインタ
b5
b4
b3
バックトレース
b2
b1
a1
a2
a3
a4
a5
音声言語処理特論　第3回
a6
a7
7
DPマッチングのやり方（４）
•  バックトレースの結果から 入力
a1 a2 a3 a4 a5 a6 a7
パターン
標準
b1
b2
b3
b4
b5
パターン
このようなフレームの対応のときに最小距離
となることが分かる
音声言語処理特論　第3回
8
DPパス
•  ある格子点に至る経路を制限するためのもの ・対称形
1
2 1
・非対称形
1
1
1
•  上に行き続けたり、横に行き続けたりできる –  そんな極端なフレーム対応になることは少ない –  不都合な場合が多い •  そうできないようにしたい！
音声言語処理特論　第3回
9
傾斜制限付きDPパスの例
•  整合窓の範囲を変える（傾斜制限）
1
2
2
(i,j)
1
2
j
1
1
(i,j)
1
1
i
1
(i,j)
1
1
1
g( i-2, j-1) + 2･d(i-1, j) + d(i, j)
g(i, j) = min g( i-1, j-1) + 2･d(i, j)
g( i-1, j-2) + 2･d(i, j-1) + d(i, j)
g( i-2, j-1) + d(i-1, j) + d(i, j)
g(i, j) = min g( i-1, j-1) + d(i, j)
g( i-1, j-2) + d(i, j)
フレームスキップを 含む場合
g( i-2, j-1) + d(i, j)
g(i, j) = min g( i-1, j-1) + d(i, j)
g( i-1, j-2) + d(i, j-1) + d(i, j)
音声言語処理特論　第3回
10
傾斜制限の例
•  フレーム数が少ないので極端だが……
傾き２と1/2の
傾斜制限
1
2
b5
2
1
2
b4
b3
この範囲内のみで 経路を取る
b2
b1
a1
a2
a3
a4
a5
音声言語処理特論　第3回
a6
a7
11
計算順序（１）
音声言語処理特論　第3回
12
計算順序（２）
音声言語処理特論　第3回
13
計算順序（３）
・非対称形
•  後者であれば 1
1
1
–  入力が１フレーム進むごとに計算を進めることができる •  時間同期処理になる •  入力が終了してない段階（例えば、音声の発声途中）で、認識処
理を進めることができる •  DPパスを上記非対称型のようにしておくと、１フレーム毎に距離
が重み１で加算されるようになり、重みの累計は入力フレーム数
となるため、パスの長さによる正規化が不要に –  バックポインタが必要ない場合（例えば、孤立単語認識で
あれば、認識のために必要なのは最小累積距離のみ）は、
１つ前のフレームの累積距離計算の結果だけを記憶して
おけば、それより前はいらない •  メモリの使用量が少なくて済む
音声言語処理特論　第3回
14
DPマッチングの原理（再掲）
D( A, B) = min
F
整合窓
標
準
Cx = ( I , J )
bJ
j =i+r
warping function
bj
C = (i, j )
・非対称形
b2
b1
C2
C4
C3
j =i−r
C5
1
2 1
w(k ) = i(k ) − i(k − 1) + j (k ) − j (k − 1)
ー
：
・対称形
∑ w(k ) ⋅ d (i(k ), j (k ))
∑ w(k )
1
1
1
w(k ) = i (k ) − i (k − 1)
C1 = (1,1)
a1 a2
ai
入力パターン：Ａ
aI
⎧D(i − 1, j ) ⎫
⎪
⎪
D(i, j ) = min⎨D(i − 1, j − 1) ⎬ + d (i, j )
⎪D(i − 1, j − 2)⎪
⎩
⎭
音声言語処理特論　第3回
15
連続単語認識
音声言語処理特論　第3回
16
連続単語認識の模式図
•  単語数（桁
数）は不明 •  単語の境界も
不明 •  これらを変化
させて、最適
解（累積距離
が最小となる
解）を探し出
す必要がある
音声言語処理特論　第3回
17
最適解を得るために
•  全ての可能性を考慮する必要がある –  全ての可能性を考慮しなければ、その時点で最適解とは言えない •  全ての可能性とは？ –  任意の単語順（今回は文法制約を考えない） –  任意の単語数（桁数） –  任意のフレームが単語の始まりである可能性 •  その前のフレームが単語の終わりになる、ということ •  任意の時間位置に任意の単語が出現できると考えなければいけない •  効率良く計算するためにはどうすれば良いか？ –  可能性を漏らさず計算 –  重複しないように計算
音声言語処理特論　第3回
18
２段DP法（１）
•  DPマッチングを２段階で行う方法 •  １段目 –  任意の開始・終了位置に任意の単語が出現すると考えて、
可能なパターンの全てを計算する •  前々回やった、DPマッチング •  多少、効率を上げるための工夫が入る •  ２段目 –  １段目で計算した部分パターンの距離を組み合わせて、
全体で距離が最小になるようにする •  この考え方がDPマッチングの考え方に他ならない
音声言語処理特論　第3回
19
２段DP法（２）
•  １段目の処理 –  入力音声の時刻 s から時刻 t までとの距離が最小になる
単語 w(s,t) –  そのときの距離の最小値 D(s,t) –  全ての(s,t)の組み合わせを計算する必要がある •  全ての始端・終端の組み合わせでそれぞれDPマッチング •  似たような区間で、似たような計算をたくさんすることになる •  重複計算になるのを避けたい –  片端点（終端点）フリーDPマッチング
音声言語処理特論　第3回
20
片端点フリーDPマッチング（１）
•  端点（終端）を固定しないDPマッチング (s,t)=(2,6)でマッチング
終端
b5
標
準
1
2 1
b4
ー b3
b2
始端
b1
入力パターン
a1
a2
a3
a4
a5
音声言語処理特論　第3回
a6
a7
a8
21
片端点フリーDPマッチング（２）
•  終端はいくらでも後ろに延ばせる (s,t)=(2,7)でマッチング
(s,t)=(2,6)で計算してある！
b5
標
準
1
2 1
終端
b4
ー b3
新しく計算するのは ここだけ！
b2
始端
b1
入力パターン
a1
a2
a3
a4
a5
音声言語処理特論　第3回
a6
a7
a8
22
２段DP法（３）
•  ２段目の処理 –  １段目で計算した距離を用いて、入力音声全体における累積距離を最小
にする単語系列を求める DTd = min {D(1, m1 ) + D(m1 + 1, m2 ) + ! + D(mk + 1, T )}
{m j }, k
ただし 1 ≤ m1 < m2 < ! < mk < T
–  これは、DPによって次の漸化式のように計算できる D0 = 0
Dn = min {Dm −1 + D(m, n )}
m =1,!, n
•  nフレーム目が単語の終端になると仮定 •  m-­‐1(<n)フレーム目が単語の終端となる場合の、m-­‐1フレーム目までの累積
最小距離は計算済み •  現在の単語がmフレーム目からnフレーム目までにあるとして、累積最小距離
を計算する •  n=1,…,Tで全て計算する 音声言語処理特論　第3回
23
２段DP法（４）
•  １段目はDPマッチング、２段目もDP（動的計画法）による計算
となるため、２段DP法と呼ばれる –  全ての可能性を漏らさず考慮するため、最適解が必ず求まる –  D(s,t)に対応するw(s,t)をバックポインタを含めて記憶しておく必要が
ある •  片端点フリーDPで１段目の重複計算を多少避けているとは
いえ、明らかに効率が悪い –  １段目で D(s,t) を計算するとき、s が１フレーム変わると距離計算を最
初からやり直すので、まだ重複している部分がある
音声言語処理特論　第3回
24
レベルビルディング法（１）
•  連続する単語の数（桁数）を順次１つずつ増やしながら、入力音声
と連続単語系列との距離を求め、最適な単語系列を得る方法 •  まず、入力が１単語（１桁）であるとして、DPマッチングを行う •  その結果を覚えておいて、それを利用することで２桁目を計算する •  さらにその結果を覚えておいて、それを利用することで３桁目を計
算する •  …… •  桁数指定の計算が可能 •  桁ごとの結果が全て得られる
音声言語処理特論　第3回
25
レベルビルディング法（２）
•  １段目 各入力フレームで、最小距離とその距離に
なる単語（標準パターン）を覚えておく （そのフレームで単語が終わると仮定する）
b5
標
準
1段目の認識結果
1
2 1
b4
ー 実際は、 標準パターン長が パターン毎に異なる ことに注意！
b3
b2
b1
始端
入力パターン
a1
a2
a3
a4
a5
音声言語処理特論　第3回
a6
a7
26
レベルビルディング法（３）
•  ２段目 各入力フレームで、最小距離とその距離に
各入力フレームで、 最小距離とその単語（標準パターン） なる単語（標準パターン）を覚えておく （そのフレームで単語が終わると仮定する）
を覚えておく
b5
標
準
２段目の認識結果
1
2 1
b4
ー 実際は、 標準パターン長が パターン毎に異なる ことに注意！
b3
b2
b1
１段目の 結果
入力パターン
a1
a2
a3
a4
a5
音声言語処理特論　第3回
a6
a7
27
レベルビルディング法（４）
•  ３段目 各入力フレームで、最小距離とその距離に
各入力フレームで、 最小距離とその単語（標準パターン） なる単語（標準パターン）を覚えておく （そのフレームで単語が終わると仮定する）
を覚えておく
b5
標
準
３段目の認識結果
1
2 1
b4
ー 実際は、 標準パターン長が パターン毎に異なる ことに注意！
b3
b2
b1
２段目の 結果
入力パターン
a1
a2
a3
a4
a5
音声言語処理特論　第3回
a6
a7
28
レベルビルディング法（５）
•  傾斜制限が付いている場合は計算しない領域が出てくる 音声言語処理特論　第3回
29
レベルビルディング法（６）
•  １桁ずつ増やしていく –  「建て増し」していく ⇒ レベルビルディング •  １桁目は片端点フリーDPマッチング、２桁目以降は両端点フ
リーDPマッチングとなる –  計算量の削減が図れる •  桁が増える度に、入力音声全体（全フレーム）に渡る走査が
必要になる –  実時間向きではない（時間同期アルゴリズムではない）
音声言語処理特論　第3回
30
レベルビルディング法（７）
•  アルゴリズム 1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
1
桁数 𝑥=1,2,…,𝑋 テンプレート 入力フレーム 𝑖=1,2,…,𝐼 接続時の DPパス
標準パターン 𝑛=1,2,…,𝑁 Dxn (i,1) = Dx −1 (i − 1) + d n (i,1)
標準パターンフレーム 𝑗=2,3,…,𝐽𝑛 n
1
Dxn (i − 1, k ) + d n (i, j )
Dx (i, j ) = min
1
⎧ j
k
1
n
n
⎪
Dx (i, J )
Dx (i ) = min
k = ⎨ j − 1
n
⎪ j − 2 テンプレー内の
DPパス
DX (I )
からバックトレース ⎩
音声言語処理特論　第3回
31
クロックワイズＤＰ法（１）
•  基本的な原理はレベルビルディング法と同じ •  レベルビルディング法のアルゴリズムの一番外側のループは桁数（桁数
を１から順に増やす） •  その内側に入力のフレームのループがある（フレームを１つずつ進める。
ここは時間同期になっている） •  このループの順序を入れ替える！それだけ！ –  一番外側のループが入力フレームになるので、時間同期アルゴリズムに大
変身！ •  フレーム間距離を重複して計算しなくなるので、レベルビルディング法に
比して計算効率が良くなる –  レベルビルディング法では、桁が変わるともう一度計算してしまう •  各時刻（フレーム）ごとに桁毎の累積距離を別々に覚えておく必要がある
ので、メモリ使用量は増える
音声言語処理特論　第3回
32
クロックワイズＤＰ法（２）
•  アルゴリズム 1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
1
入力フレーム 𝑖=1,2,…,𝐼 テンプレート 桁数 𝑥=1,2,…,𝑋 接続時の DPパス
標準パターン 𝑛=1,2,…,𝑁 Dxn (i,1) = Dx −1 (i − 1) + d n (i,1)
標準パターンフレーム 𝑗=2,3,…,𝐽𝑛 n
1
Dxn (i − 1, k ) + d n (i, j )
Dx (i, j ) = min
1
⎧ j
k
1
n
n
⎪
Dx (i, J )
Dx (i ) = min
k = ⎨ j − 1
n
⎪ j − 2 テンプレー内の
DPパス
DX (I )
からバックトレース ⎩
音声言語処理特論　第3回
33
One-­‐pass DP法（１）
•  さらに簡略化 •  クロックワイズDPでは、各時刻（フレーム）ごとに桁毎の累積距離
を別々に覚えておく必要がある •  これをやめる •  全ての桁数の中で、累積距離が最も小さいものだけを覚えておく •  任意桁の結果の中で、累積距離が最も小さい結果だけが求まる •  使用するメモリ量が減る •  桁別の計算が必要なくなるため、計算量も減る •  桁別の結果を得ることはできなくなる –  桁数の制御そのものが難しくなる
音声言語処理特論　第3回
34
One-­‐pass DP法（２）
•  接続点で累積距離が最小になる単語（赤で示されているも
の）だけを残す
1
テンプレート 接続時の DPパス
音声言語処理特論　第3回
35
One-­‐pass DP法（３）
X のループがない！
•  アルゴリズム 1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
1
入力フレーム 𝑖=1,2,…,𝐼 テンプレート 標準パターン 𝑛=1,2,…,𝑁 接続時の DPパス
D n (i,1) = D(i − 1) + d n (i,1)
標準パターンフレーム 𝑗=2,3,…,𝐽𝑛 D n (i, j ) = min D n (i − 1, k ) + d n (i, j )
k
n
n
1
nˆ = arg min D (i, J )
1
⎧ j
n
1
⎪
nˆ
nˆ
D(i ) = D (i, J )
k = ⎨ j − 1
⎪ j − 2 テンプレー内の
DPパス
D(I ) からバックトレース ⎩
音声言語処理特論　第3回
36
計算量比較
アルゴリズム 局所距離計算 累積距離計算
メモリ量
重複計算が 多くなる
(1/2)・I・J・X・NX (1/2)・I・J・X・NX
直接解法 ２段DP I・N・J・(3/4)J
I・N・J・(3/4)J
3・I・X
計算量が多い
レベル ビルディング
I・N・J・X
I・N・J・X
3・I
実時間処理 できない
クロックワイズ
I・N・J
I・N・J・X
One Pass DP
I・N・J
I・N・J
• 
• 
• 
• 
• 
(3・I+4・N・J)・X メモリ量が多い
3・I+4・N・J
桁数別でない
I ： 入力パターン長 J ： （平均）標準パターン長 N ： 標準パターン数（単語数） X ： 桁数 「直接解法」は X 単語並べた標準パターンを作って、 直接的にDPマッチングで求める場合
音声言語処理特論　第3回
37
連続DP法（１）
•  ワードスポッティング –  入力音声フレーム中から、単語や音節・音素を探し出す –  キーワードを発話中から見つけ出す •  「沖縄」「航空券」「二枚」がキーワード –  あまり高度でない対話システムで使われる •  キーワードが分かるだけで、大雑把な意味理解は可能。意外と普
通に対話できてしまう –  助詞の使い分けができない外国人とでもちゃんと会話できるよね 音声言語処理特論　第3回
38
連続DP法（２）
•  キーワードがどこにあるか分からないのだが、そも
そも発話中にあるかないかすら分からない •  任意区間のマッチングによって求まる累積距離が、
あらかじめ設定した閾値を下回っていればその区間
にキーワードが存在すると判定する •  端点フリーのDPマッチングを入力の始端フレームか
ら連続的に行っていく ⇒ 連続（conKnuous）DP
音声言語処理特論　第3回
39
連続DP法（３）
⎡ g (i − 2, j − 1) + 2d (i − 1, j ) + d (i, j ) (a )⎤
累積距離 g (i, j ) = min ⎢⎢ g (i − 1, j − 1) + 2d (i, j )
(b) ⎥⎥
⎢⎣ g (i − 1, j − 2 ) + 2d (i, j − 1) + d (i, j ) (c) ⎥⎦
⎧c(i − 2, j − 1) + 3 if (a )
⎪
DPパスの長さ c(i, j ) = ⎨c(i − 1, j − 1) + 2 if (b)
⎪c(i − 1, j − 2 ) + 3 if (c)
⎩
音声言語処理特論　第3回
40
連続DP法（４）
•  入力音声の i フレームが単語 w の終端になる場合の最小
累積距離 –  DPパスの長さが一定ではないので、長さで割って距離を正規化する Dw (i ) =
g (i, J w )
ただしJ wは単語wの標準パターン長
c(i, J w )
–  この値が閾値を下回るか否かにより単語の存在非存在を判定 •  そんなに多くないキーワードの検出のためのもの –  キーワードをワードスポッティングした後に、それを核としてその周辺
を音声認識する手法（島駆動型; Island driven）もあるが、単語境界が
あまり厳密に検出できないので、統合が難しく、性能はあまり良くなら
ない 音声言語処理特論　第3回
41