音声情報処理 DPマッチング 最小距離の求め方

DPマッチング

DPマッチングは、音声認識におけるパターン認識手法の一つであり、特に孤立単語認識で用いられます。この手法は、以下の特徴を持っています。

距離尺度に基づいたパターン認識：音声パターン間の距離を計算し、その最小化を目指すアプローチです。
孤立発声された単語を対象とする：連続した音声ではなく、個別の単語や短いフレーズの認識に適しています。
DPマッチングでは、動的計画法(Dynamic Programming：DP)を用いて、パターンの時間軸を非線形に伸縮させながら、パターン間の距離の最小値を計算します。具体的には、比較する二つの音声パターンを時間軸上で調整し、対応が最も良くなるように伸縮させます。このとき、各時刻におけるパターン間の距離を累積し、その総和が最小となる経路を探索します。

この方法により、話者の速度や抑揚の違いなど、発声時間のばらつきを吸収することができます。すなわち、同じ単語であっても発声時間が異なる場合に、それらを正しく比較・認識することが可能となります。

DPマッチングの主な利点は、計算の効率性と実装の容易さです。そのため、簡易な音声認識システムや限定された語彙の認識に広く利用されています。しかし、話者依存性が高いことや、大規模な語彙を扱う際の計算量の増大といった課題もあります。

---

実際にDPマッチングを用いてパターン認識を行ってみましょう

問題1

特徴パターンが１次元で、Y=(4,2,3,7,5)，R=(3,5,2,4)のとき，
フレーム間距離が式1で得られるとして、図1のアルゴリズムに従ってパターン間の距離を求めよ。その時のフレームの対応付けは？

---

式1

d(i,j)=|y_i - r_i|

---

図1

---

解1

以下の図を埋めていき求める。
Yが入力パターンでRが参照パターンである
入力パターンは左からY(1)=4,Y(2)=2...,Y(i)
参照パターンは下からR(1)=3,R(2)=5...,R(j)
g(i,j)が格子点(i,j)までの最小累積距離

Step1:g(1,)を埋める。

g(1,1) = d(1,1) = |4-3| = 1
それ以外は∞である。

Step2:d(i,j)を求める

g(i,j)を求めるための準備としてd(i,j)を求める。
d(i,j)の値はマスの右上にメモしておくと良い

Step3:g(i, j)を求めていく
DPのパスが図1の時，g(i, j)(i > 1)は以下の式で表せる

g(i,j) = \min \begin{Bmatrix} 
g(i-1,j) \\
g(i-1,j-1) \\
g(i-1,j-2)
\end{Bmatrix} + d(i,j)

イメージ:g(3,3)のとき

DPパスが図1の通り以下のものであるため、これをイメージしながら計算する。

g(3,3)においては以下図のようになり、

1,4,2の中で一番小さい1とd(3,3)の1を足して1+1=2となる。

同様にしていき，結果以下図になる。

• g(2,)は、j = 1,2,3 → g(2,j)=g(1,1)+d(2,j)となり、j>3 → g(2,j)=∞となる
• g(,1)は必ずg(i,1)=g(i-1,1)+d(i,1)となるので、先に埋めていると楽

Step4:仕上げ

全てのg(i,j)を求めることができたので、パターン間距離とフレームの対応付けを求める。
最終的な距離が最小となる経路は以下図のようになる。

パターン間距離

D(Y,R) = \frac{g(I,J)}{I} \\\\\
= \frac{最短距離時のg(5,j)}{入力パターン総数} = \frac{4}{5}

フレーム対応付け

問題2

問題1と同様の時に、DPパスが図2の場合のパターン間の距離とその時のフレームの対応付けを求めよ。

---

図2

解2

基本は解1と同様に進めるがDPパスが対象型DPパスであることに注意する。

Step1:g(1,)を埋める。

g(1,1) = 2d(1,1) = 2 x |4-3| = 2
それ以外は∞である。

g(1,1) = 2d(1,1) x2を忘れない！！

Step2:d(i,j)を求める

g(i,j)を求めるための準備としてd(i,j)を求める。
d(i,j)の値はマスの右上にメモしておくと良い

Step3:g(i, j)を求めていく

DPのパスが図1の時，g(i, j)(i > 1)は以下の式で表せる

g(i,j) = \min \begin{Bmatrix} 
g(i-1,j) + d(i,j)\\
g(i-1,j-1) + 2d(i,j)\\
g(i,j-1)+ d(i,j)
\end{Bmatrix}

イメージ:g(2,2)のとき

DPパスが図2の通り以下のものであるため、これをイメージしながら計算する。

g(2,2)においては以下図のようになり、

右からくるのは、∞ + 3 = ∞
斜め下からくるのは、2 + 2x3 = 8
下からくるのは、3 + 3 = 6
で最小はしたからくる6であるため、g(2,2) = 6

同様にしていき，結果以下図になる。

Step4:仕上げ

全てのg(i,j)を求めることができたので、パターン間距離とフレームの対応付けを求める。
最終的な距離が最小となる経路は以下図のようになる。

パターン間距離

D(Y,R) = \frac{g(I,J)}{I} \\\\\
= \frac{最短距離時のg(5,j)}{入力パターン総数} = \frac{7}{5}

フレーム対応付け