隠れマルコフモデルと潜在変数の話

初めまして、データ分析部の中野です。

今回は音声認識や自然言語処理、文字認識などで使用される隠れマルコフモデルの話をしていきたいと思います。特に、モデル内で導入される潜在変数の推定について説明していきます。

隠れマルコフモデルは、時系列データの混合分布推定に用いられるモデルです。与えられた時系列データが複数のグループから構成され、それぞれどのような特徴があるかを推定します。また、各グループ間の遷移の様子を確率で表現することもできます。

まず、例として隠れマルコフモデルを文字認識で使用する場合について説明していきます。文字認識で使用する場合は、ペンの動きの系列をグループに分けることで推定を行います。ここでペンの動きとは、ペンの平面移動の方向を表します。各時刻におけるペン先の座標を取得することで、現在の時刻の座標とひとつ前の時刻の座標との差分を計算し、ペンの動きの方向を取得して特徴量として扱います。
漢字の「会」と「合」を例に挙げて、ペンの動きからどのように推定されるかを説明します。括弧は紙面に接していない部分の動きを表しているとします。

「会」という文字の場合は

左下⇒(右上)⇒右下⇒(左)⇒右⇒(左下)⇒右⇒(左)⇒左下⇒右⇒(左上)⇒右下

「合」という文字の場合は

左下⇒(右上)⇒右下⇒(左)⇒右⇒(左下)⇒下⇒(上)⇒右⇒下⇒(左)⇒右

というように方向ごとのグループに分かれることがイメージできるかと思います。この2つの文字では4画目以降が違っていて、4画目が右であれば「会」、下であれば「合」と判別されます。このときのペンの方向を時系列で表現すると次の図のようなイメージになります。

cha

thetaは角度を表し、平均的に0°の値を観測しているときは水平右、平均的に45°の値であれば右上、平均的に-45°の値であれば右下の方向に動いているという解釈ができます。

このように隠れマルコフモデルを用いた文字認識では、ペンが動く方法を考慮することでどんな文字なのかを推定することができます。

さて、隠れマルコフモデルでは各グループの特徴とグループ間の遷移の様子を表現できると述べましたが、それだけでなく各データがどのグループに属しているかも推定することができます。これは潜在変数といわれる観測されない変数を導入することで表現でき、隠れマルコフモデルの特徴の一つです。上の例で挙げた文字認識では、潜在変数を導入し各方向ごとにグループ分けすることで書き順を表現し文字を推定しています。また、自然言語処理では潜在変数を用いることで各単語がどのような品詞であるかを推定します。

以下、その潜在変数についてどのように推定していくかを見ていきましょう。
サンプルとして、混合されたポアソン分布を用います。(環境はRです)

 N <- 500
 K <- 4
 prms <- c(1, 4, 7, 10)
 transit <- rbind(c(0.95, 0, 0.025, 0.025),
                 c(0.025, 0.95, 0, 0.025),
                 c(0.025, 0.025, 0.95, 0),
                 c(0, 0.025, 0.025, 0.95))
 z <- rep(1,N)
 for(i in 2:N) z[i] <- which(rmultinom(1, 1, prob = transit[z[i-1], ]) == 1)
 x <- rpois(N, prms[z])

観測値の系列と潜在変数の系列については次のようになっています。4つのグループからなる混合されたポアソン分布で、潜在変数の数字がグループを表します。

late_2Rplot01

潜在変数の変化と観測値の変化に対応が見られることがわかると思います。

潜在変数の推定にはViterbiアルゴリズムというアルゴリズムを用います。このアルゴリズムは観測された系列について、最も尤もらしい並びを探すアルゴリズムとして知られています。隠れマルコフモデルの場合は、観測値を元に、分布や遷移確率の情報を用いて、背後の潜在変数の系列を推定します。

viterbi

具体的には、2つのステップからなる計算を行うことで最適な経路(潜在変数の値の時間軸に沿った変化)を探索していきます。

一つ目のステップでは、初期の観測値からある時刻の観測値に至るまでの経路について調べていきます。このステップでは、再帰的にひとつ前の時刻から尤度が最も高くなる経路とその尤度を保存します。こうすることで、計算量を減らし高速で計算することを可能にしています。上の図のように各時刻、各潜在変数ごとに再帰的に尤度を計算していき、最後の観測値まで計算します。

二つ目のステップでは、最後の観測値において最も尤度の高かった潜在変数から鎖を後戻りするように経路をたどっていきます。これが最も尤もらしい経路であり、これにより、潜在変数の列を推定することができます。

上記の流れを式で表現すると次のようになります。以下、x_{n}を観測値、z_{n}を潜在変数、p(x_{n}|z_{n})を分布の密度関数、p(z_{n}|z_{n-1})を推移確率、w(z_n)を尤度、Z_{n,k} を経路、k_{n} は推定される潜在変数の系列とする。

ステップ1
w(z_1) = \log p(z_1) + \log p(x_1 | z_1 )                初期状態の計算
w(z_{n})=\log p(x_{n}|z_{n})+\max_{z_{n-1}}\left[ \log p(z_{n}|z_{n-1})+w(z_{n-1}) \right]   尤度の再帰的計算
Z_{n,k}=argmax_{z_{n-1}}\left[ \log p(z_{n}=k|z_{n-1})+w( z_{n-1} )\right]          経路の保存

ステップ2
k_N =argmax_{z_N} w(z_N)  最も尤度の高い状態
k_n= Z_{ n+1 , k_{n+1} }     潜在変数の系列の探索

 

ではRを使って潜在変数を推定してみましょう。今回は”HiddenMarkov”というパッケージを用いて以下のように行いました。

 install.packages("HiddenMarkov")
 library(HiddenMarkov)
 model <- dthmm(x,
                Pi = transit,
                delta = c(1, 0, 0, 0),
                distn = "pois",
                pm=list(lambda=prms))
 latent_variable <- Viterbi(model)

また実用的なものとして書いたわけではないですが、推定を行う関数をRで直接記述しました。参考程度にご覧ください。(下のコードでは7行目以降for文を多用していますが、パッケージではapply関数を使用しているため、パッケージの関数の方が概ね2倍程計算が速いです)

Viterbi_pois <- function(x, prms, trans){
   N <- length(x)
   K <- ncol(trans)
   z <- matrix(0, N, K)
   best_logp <- matrix(-Inf, N, K)
   best_logp[1, 1] <- 0 + log(dpois(x[1], prms[1])
   for(t in 2:N){
      for(k in 1:K){
         for(j in 1:K){
            tmp_logp <- best_logp[t-1, j] + log(trans[j, k]) + log(dpois(x[t], lambda = prms[k]))
            if(tmp_logp > best_logp[t, k]){
               z[t, k] <- j
               best_logp[t, k] <- tmp_logp
            }
          }
      }
   }
   best_z <- rep(1, N)
   best_z[N] <- which.max(best_logp[N, ])
   for(t in 1:(N-1)){
      best_z[N-t] <- z[N-t+1, best_z[N-t+1]]
   }
   return(best_z)
}

本来は分布のパラメータや推移確率も推定の対象ですが、今回はViterbiアルゴリズムがうまく推定できることをみるために分布のパラメータや推移確率を既知、潜在変数を未知として潜在変数の推定を行っています。Viterbiアルゴリズムで推定された潜在変数を用意した潜在変数と比較してみると、うまく推定できていることがわかります(赤が推定した潜在変数列)。

report1

実際の分析では、グループがいくつあるのかを決めることから始まり、各グループの特徴や推移確率を全て推定しなければなりませんが、観測されない潜在変数を扱うことで各変数についての情報をより詳しく表現することができます。

潜在変数というものを用いることで、本来は観測されない値を表現していくことができます。隠れマルコフモデルでは背後の状態を潜在変数として表現していますが、そのほかに潜在変数を用いたモデルの例としては因子分析などがあり、因子分析ではテスト結果から学力を表現することや、陸上競技の結果から運動能力などを表現することができます。このように本来観測されない値を数値で表現することでモデルの表現の幅が広がり、より高度な分析につながっていきます。