講義/Baum-Welch Algorithm

出典: Fukudat.com

Hidden Markov Models (HMM)の学習アルゴリズムとして有名な Baum-Welch Algorithm を解説する．

1 準備

1.1 カギ括弧表記法

n個組みを表す便利な表記方法として，

$\left[a_k\right]_{k=i}^{j} \equiv (a_{i}, a_{i+1}, \ldots, a_{j})$
$\left[a(k)\right]_{k=i}^{j} \equiv (a(i), a(i+1), \ldots, a(j))$

を導入する．添字の" $k=$ "は，明らかな場合は省略することもある．

1.2 再帰的分解

条件付確率 (conditional probability) と再帰的分解 (recursive factorization) を用いる．再帰的分解とは，複数の事象 (event) の同時確率 (joint probability) は 1つの事象のそれ以前に起こった事象を条件とする条件付確率の積で表されるというもので，例えば， $A$ , $B$ , $C$ をそれぞれ事象として，

$Pr(A \cap B \cap C) = Pr(A) Pr(B \mid A) Pr(C \mid A \cap B)$

である．

上で定義したカギ括弧表記法を用いると，離散確率変数 $X(n)$ の系列の同時確率分布は，

$Pr\left(\left[ X(k) \right]_0^N = \left[ x_k \right]_0^N \right) = Pr(X(0)=x_0) \cdot \prod_{n=1}^{N} Pr\left( X(n) = x_n \mid \left[ X(k) \right]_0^{n-1} = \left[ x_k \right]_0^{n-1} \right)$

と表記できる．

2 Hidden Markov Chain

有限状態のMarkov Chainを考える．

$\bold{S}$ を状態の有限集合とする．状態数を $M$ とする(つまり $|\bold S|=M$ )．簡単のため，状態を $1$ から $M$ の整数で表現する．（つまり， $\bold{S} = \{1, 2, \ldots, M\}$ ．）

つぎに， $(S(t) : t \in [0..N])$ を確率変数の時系列とし，すべての $t$ において $Pr(S(t) \in \bold{S}) = 1$ であるとする．つまり， $S(t)$ は $\bold{S}$ に限定されている．

$0$ から $N$ までの確率変数について，再帰的分解を適用すると，

$Pr\left( \left[ S(k) \right]_0^N = \left[ s_k \right]_0^N \right) = Pr\left( S(0) = s_0 \right) \cdot \prod_{t=1}^{N} Pr\left( S(t) = s_t \mid \left[ S(k) \right]_0^{t-1} = \left[ s_k \right]_0^{t-1} \right)$ . . . (1)

となる．

この事象系列がMarkov Chainであるためには，この条件付確率は直前の確率変数だけの関数でなければならない．このため，式(1)は次の様に簡略化される．

$Pr\left( \left[ S(k) \right]_0^N = \left[ s_k \right]_0^N \right) = Pr\left( S(0) = s_0 \right) \cdot \prod_{t=1}^{N} Pr\left( S(t) = s_t \mid S(t-1) = s_{t-1} \right)$ . . . (2)

ここで状態遷移確率は定常的であり，時間に依存しないと仮定する．すなわち，任意の $t$ について

$Pr(S(t)=j \mid S(t-1)=i) = Pr(S(1)=j \mid S(0)=i) \quad\stackrel{\rm{def}}{=}\quad p_{ij}$

である．

つぎに $Y(t)$ $(t \in [1..N])$ を別の確率変数の系列とする（観測 (observation) と呼ぶ）． $Y(t)$ は有限の範囲に限定されているとし，時刻 $0$ から $T$ までの連続した観測が得られるものとする． (一般の場合に拡張することは可能だが，複雑になるのでここでは扱わない）．

観測 $Y(t)$ はその時点の状態 $S(t)$ だけに依存すると仮定して， $T+1$ 個の状態と $T$ 個の観測の同時確率分布を分解すると，

$Pr\left( \left[ S(t) \right]_0^T = \left[ s_t \right]_0^T \wedge \left[ Y(t) \right]_1^T = \left[ y_t \right]_1^T \right) =$
　　 $Pr\left( S(0) = s_0 \right) \cdot \prod_{t=1}^{T} Pr\left( S(t) = s_t \mid S(t-1) = s_{t-1} \right) \cdot \prod_{t=1}^{T} Pr\left( Y(t) = y_t \mid S(t) = s_t \right)$ . . . (3)

表記をさらに簡単にするために，次の記号を導入する．

$\begin{cases} f(y \mid s) & \stackrel{\rm{def}}{=}\quad Pr\left( Y(t) = y \mid S(t) = s\right) \\ \bar{s} & \stackrel{\rm{def}}{=}\quad \left[ s_t \right]_0^T \\ \bar{y} & \stackrel{\rm{def}}{=}\quad \left[ y_t \right]_1^T \\ p(\bar{s}, \bar{y}) & \stackrel{\rm{def}}{=}\quad Pr\left( \left[ S(t) \right]_0^T = \bar{s} \wedge \left[ Y(t) \right]_1^T = \bar{y} \right) \\ \end{cases}$

これを使って式(3)を書き換えると，

$Pr\left([S(\tau)]_0^T = \bar{s} \wedge \left[ Y(t) \right]_{1}^{T} = \bar{y} \right) = p(\bar{s}, \bar{y}) = p_{s_0} \cdot \prod_{t=1}^{T} p_{s_{t-1} s_{t}} f(y_t \mid s_t)$ . . . (4)

を得る．この式(4)はモデルにおける，これ以上分解することのできない最小の事象に対する確率を与える式である．すなわち，モデル上で表現することのできる任意のイベントは，この確率の和として表現することが可能である．

もちろん，この確率は次のモデルパラメータ $\lambda$ の関数である．

$\lambda \quad \stackrel{\rm{def}}{=} \quad \left.\begin{cases} p_s, & 1 \le s \le M \\ p_{s_1s_2}, & 1 \le s_1, s_2 \le M \\ f(y \mid s), & 1 \le y \le Y,\, 1 \le s \le M \\ \end{cases} \right\}$

このため，以後は適時 $\lambda$ を関数の引数に使用する．なお，

$p_s$ ... (初期)状態が $s$ である確率
$p_{s_1 s_2}$ ... 状態 $s_1$ から状態 $s_2$ に遷移する確率
$f(y \mid s)$ ... 状態 $s$ で観測 $y$ が観測される確率

という意味である．

状態 $S(t)$ は直接観測できないが， $Y(t)$ は観測できると考えて議論するのが，Hidden Markov Model (HMM) である．

3 各種事象の生起確率の計算

ある $T$ 個の観測からなる観測系列 $\bar{y}$ が観測される確率は，

$p(\bar{y};\, \lambda) \quad \stackrel{\rm{def}}{=} \quad \sum_{\bar{s}} p(\bar{s}, \bar{y};\, \lambda)$

と書ける．この確率は，ある観測系列 $\bar{y}$ が得られたときのモデルパラメータ $\lambda$ の尤度 (likelihood) でもある．

ある $T$ 個の観測からなる観測系列 $\bar{y}$ が観測されたときに，ある時刻 $\tau$ における状態の確率分布

$Pr\left(S(\tau) = s \mid \left[ Y(t) \right]_{1}^{T} = \left[ y_t \right]_{1}^{T} \right)$

を推定したい．条件付確率の定義より，

$Pr\left(S(\tau) = s \mid \left[ Y(t) \right]_{1}^{T} = \left[ y_t \right]_{1}^{T} \right) = \frac{ Pr\left(S(\tau) = s \wedge \left[ Y(t) \right]_{1}^{T} = \left[ y_t \right]_{1}^{T} \right) }{ Pr\left(\left[ Y(t) \right]_{1}^{T} = \left[ y_t \right]_{1}^{T} \right) }$

であるから，条件付確率を求めることは，同時確率を求めることと等価である．

この同時確率を

$\gamma_{\tau}(s) \quad\stackrel{\rm{def}}{=}\quad Pr\left(S(\tau) = s \wedge \left[ Y(t) \right]_{1}^{T} = \left[ y_t \right]_{1}^{T} \right)$

と置く．ここで時刻 $\tau$ 前後で分解すると，

$\gamma_{\tau}(s) = Pr\left(\left[ Y(t) \right]_{1}^{\tau} = \left[ y_t \right]_{1}^{\tau} \wedge S(\tau) = s \right) \cdot Pr\left(\left[ Y(t) \right]_{\tau+1}^{T} = \left[ y_t \right]_{\tau+1}^{T} \mid \left[ Y(t) \right]_{1}^{\tau} = \left[ y_t \right]_{1}^{\tau} \wedge S(\tau) = s \right)$

であるが， Markov性の仮定から， $[S(t)]_{\tau+1}^{T}$ の確率分布は $S(\tau)$ 以前の履歴とは独立（無関係）であり，したがって $[Y(t)]_{\tau+1}^{T}$ の確率分布も同様である．このことから右辺の第2項にある $Y$ の条件は取り除くことができ，

$\gamma_{\tau}(s) = Pr\left(\left[ Y(t) \right]_{1}^{\tau} = \left[ y_t \right]_{1}^{\tau} \wedge S(\tau) = s \right) \cdot Pr\left(\left[ Y(t) \right]_{\tau+1}^{T} = \left[ y_t \right]_{\tau+1}^{T} \mid S(\tau) = s \right)$

を得る．

$\begin{cases} \alpha_{\tau}(s) & \stackrel{\rm{def}}{=}\quad Pr\left(\left[ Y(t) \right]_{1}^{\tau} = \left[ y_t \right]_{1}^{\tau} \wedge S(\tau) = s \right) \\ \beta_{\tau}(s) & \stackrel{\rm{def}}{=}\quad Pr\left(\left[ Y(t) \right]_{\tau+1}^{T} = \left[ y_t \right]_{\tau+1}^{T} \mid S(\tau) = s \right) \\ \end{cases}$

と置くと，

$\gamma_{\tau}(s) = \alpha_{\tau}(s) \cdot \beta_{\tau}(s)$

である．

ここで， $\alpha_{\tau}(s)$ を再帰分解すると，

$\alpha_{\tau}(s) = \sum_{\sigma} Pr\left( [Y(t)]_1^{\tau-1} = [y_t]_1^{\tau-1} \wedge S(\tau-1)=\sigma \right) \cdot Pr\left(Y(\tau)=y_{\tau} \wedge S(\tau) = s \mid [Y(t)]_1^{\tau-1} = [y_t]_1^{\tau-1} \wedge S(\tau-1)=\sigma \right)$

再び Markov性の仮定から，第2項の $Y$ に関する条件を消去して，

$\alpha_{\tau}(s) = \sum_{\sigma} Pr\left( [Y(t)]_1^{\tau-1} = [y_t]_1^{\tau-1} \wedge S(\tau-1)=\sigma \right) \cdot Pr\left(Y(\tau)=y_{\tau} \wedge S(\tau) = s \mid S(\tau-1)=\sigma \right)$

この第1項は $\alpha_{\tau-1}(\sigma)$ で，第2項は $p_{\sigma s} \cdot f(y_\tau \mid s)$ であるから，結局次の漸化式を得る．

$\alpha_{\tau}(s) = \sum_{\sigma} \alpha_{\tau-1}(\sigma) \cdot p_{\sigma s} \cdot f(y_\tau \mid s)$

同様に， $\beta_{\tau}(s)$ に関しては

$\beta_{\tau}(s) = \sum_{\sigma} p_{s \sigma} \cdot f(y_{\tau+1} \mid \sigma) \cdot \beta_{\tau+1}(\sigma)$

を得る． $p(\bar{y};\, \lambda)=\sum_{\sigma} \alpha_T(\sigma)$ であるから，結局 $\bar{y}$ を観測したとき，時刻 $\tau$ の状態が $s_{\tau}$ である確率は

$Pr(s_{\tau} \mid \bar{y}) \equiv Pr( S(\tau) = s_{\tau} \mid [Y(t)]_1^T = [y]_1^T ) = \frac{\alpha_{\tau}(s_{\tau}) \beta_{\tau}(s_{\tau})}{\sum_{\sigma} \alpha_T(\sigma)}$

一旦各状態について $\alpha$ , $\beta$ を求めてしまえば，色々な事象の確率を計算することが可能となる．例えば， $\bar{y}$ を観測して $S(t) = \sigma$ かつ $S(t+1)=s$ である確率は，

$\begin{align} Pr(S(t) = \sigma \wedge S(t+1)=s \wedge [Y(\tau)]_1^T=[y]_1^T ) & = \alpha_t(\sigma) p_{\sigma s} f(y_{t+1}|s) \beta_{t+1}(s)\\ & \equiv \gamma_t(\sigma, s) \end{align}$

4 Algorithm

$\lambda$ を乱数または一様分布で初期化し，収束するまでEステップ，Mステップを繰り返す．

4.1 Eステップ

現在の $\lambda$ を使って以下の期待値を求める．

$\left\{ \begin{align} \alpha_1(j) & = p_j f(y_1|j) \\ \alpha_{t+1}(j) & = \sum_{i} \alpha_t(i) p_{ij} f(y_{t+1}|j) \end{align} \right.$
$\left\{ \begin{align} \beta_T(i) & = 1 \\ \beta_t(i) & = \sum_j p_{ij} f(y_{t+1}|j) \beta_{t+1}(j) \end{align} \right.$
$\left\{ \begin{align} \gamma_t(i) & = \alpha_t(i) \beta_t(i) \\ \gamma_t(i, j) & = \alpha_t(i) p_{ij} f(y_{t+1}|j) \beta_{t+1}(j) \end{align} \right.$

4.2 Mステップ

$\lambda$ を更新する．

$\left\{ \begin{align} p_i & = \gamma_1(i) \\ p_{ij} & = \frac{\sum_{t=1}^{T-1}\gamma_t(i,j)}{\sum_{t=1}^{T-1}\gamma_t(i)} \\ f(k|j) & = \frac{\sum_{t\ \text{s.t.}\ Y(t)=k}^{T}\gamma_t(j) }{\sum_{t=1}^{T}\gamma_t(j)} \end{align} \right.$