Day02::音声認識(2),動的計画法

Day2

音声認識本の続き
DPという言葉が出てきたのでDPの問題をといた

まえのひ

fgjiutx.hatenablog.com

音声認識の方法

一言に音声認識といっても，単語の認識なのか，それとも文章(単語列)の認識なのかによって適用されるアルゴリズムが異なります．

離散単語認識では，予め決められた語彙のうちから発声された単語が何なのかを当てるタスクです．単語間の前後関係の考慮が不必要なのでアルゴリズムは比較的単純で済む場合が多いです．

対して，連続的な単語列の認識では，単語間の前後関係¹を把握する必要があります．連続的な場合においては，電話番号や郵便番号などといった限られた語彙間の推移を有限状態オートマトンなどで推定するような比較的単純なタスクである連続音声認識と，膨大な語彙の文を認識させる文認識へと細分化されます．

加えて，語彙の発声は個人差が大きく存在します．なので特定の話者のデータで学習を行えばその話者に対する精度ばかりが高くなります．これは特定話者音声認識とよばれ，ディクテーションなどの用途に特化していると言えます．対して話者が不特定の場合は，不特定話者音声認識と呼ばれます．

特徴量の量子化

音声認識の分野では度々単語間の類似度を図るために，特徴ベクトル間の距離(=類似度合い)を測定したい場合があります．その際に，特徴ベクトル間類似度の計測が実数値を取るような高次元のベクトルでは，計算量が嵩むようなものが存在すします．そこで，計算資源を節約するために，ベクトル量子化と呼ばれるアルゴリズムを適用します．ベクトル量子化では，特徴量ベクトルの取りうる空間を重複の無いように分割し，各々の空間に対して離散的な何かしらのシンボルを付与することで高次元の特徴ベクトルではなく，シンボルを記憶するだけで済み，計算量の大幅な削減が見込めます．もちろん，計算量を向上する代わりに実際の距離とは乖離が生じますが，この劣化は量子化ひずみとも呼ばれます．

空間分割のためのアルゴリズムとしては$k-$meansアルゴリズムなどが採用されています．そのアルゴリズムで得られたセントロイド(早い話が重心)はコードベクトル，その点に割り当てた一意な符号をコードワードなどと呼ばれます．

DPマッチング

離散単語の認識を考えます．まずは，特定話者が語彙の各々を発生して音声認識の標準パターンを作成していると仮定した場合を考えましょう．

この場合の認識タスクは，可変長の入力データと，同じく可変長の単語の標準データとの間の類似度の計算に相当します．固定長の場合には各々の要素間の距離を測ることで簡単に達成できますが，可変長の場合には，フレーム間をどのように対応付けるべきかが認識する上では非常に重要となります．ただ単に全通りを探索するとなると，組み合わせは$N^M$となり全く現実的ではありません．

そこで計算量を削減するために考案されたのがDPマッチングです²．

DPマッチングでは，まず単語列をベクトル量子化をします．そうすることで，2つの単語間の距離は予め保存しておいたフレーム間を参照するだけで済みます．

入力単語列$A=\{a_1,a_2,...,a_N\}$と,標準パターン$B=\{b_1,b_2,...,b_M\}$および任意のA,Bの元の間の距離$d(a_i,b_j)$が分かっている際，DPマッチングは，以下のような座標系における点$c_1=(1,1)$から点$c_k=(i_k,j_k)$までの距離の累積和を$g(c_k)$とした際に，点$c_K=(a_N,b_M)$までの累積和を最小化させる効率的なアルゴリズムです．

また，音声の性質に対して，このDP平面上の座標の増加は時間の経過に等しいことから，逆方向にDP平面状を進むことはありませんし，途中の音韻を抜き去ることは別の単語となる可能性があるためあまり考えられないでしょう．すなわち，以下の単調連続性の制約を課すことができます． $$ i_{k+1}=i_k\textrm{or}i_k+1,j_{k+1}=j_k\textrm{or}j_k+1 $$ ここで，累積和をマンハッタン距離 $$ w_k=(i_k-i_{k-1})+(j_k-j_{k-1}) $$ を用いて $$ g(c_K)=\frac{1}{N+M}\sum_{k=1}^{K}d(c_k)w_k $$ のように定めれば，その最小距離は， $$ g(c_k)=\min[g(i,j-1)+d(i,j),g(i-1,j-1)+2d(i,j),g(i-1,j)+d(i,j)] $$ と，再帰的に定めることができます．これは，単純な配列を保持しておけば簡単な動的計画法で解くことができてその計算量は$3NM$程度で済みます．これを用いて単純な単語の語彙の間では，動的計画法を用いて大幅に計算量を抑えて音声認識を取らせる方法がとられていました．