HMMの最尤推定

※ かなり導出部分を省略しています。導出は適宜HMMの最尤推定の計算過程を参照してください。

隠れマルコフモデルは、一般に以下の式で表されます。

$p(\mathbf{X}, \mathbf{Z} | \boldsymbol{\theta})=p\left(\mathbf{z}_{1} | \boldsymbol{\pi}\right)\left[\prod_{n=2}^{N} p\left(\mathbf{z}_{n} | \mathbf{z}_{n-1}, \mathbf{A}\right)\right] \prod_{m=1}^{N} p\left(\mathbf{x}_{m} | \mathbf{z}_{m}, \boldsymbol{\phi}\right)\qquad (13.10)$

$\mathbf{X} = \{\mathbf{x}_1,\ldots,\mathbf{x}_N\}$ :
$\mathbf{Z} = \{\mathbf{z}_1,\ldots,\mathbf{z}_N\}$
$\boldsymbol{\theta}=\{\boldsymbol{\pi}, \mathbf{A}, \boldsymbol{\phi}\}$

※ 一般に放出確率 $p\left(\mathbf{x}_{n} | \mathbf{z}_{n}, \boldsymbol{\phi}\right)$ は、二値のベクトル $\mathbf{z}_n$ の $K$ 個の可能な状態に対応した $K$ 個の要素を持つベクトルからなる任意の分布

$p\left(\mathbf{x}_{n} | \mathbf{z}_{n}, \phi\right)=\prod_{k=1}^{K} p\left(\mathbf{x}_{n} | \phi_{k}\right)^{z_{n k}}\qquad (13.9)$

を考えることも可能ですが、今回は下記の離散多項分布を考えます。

Name	Probability	Conditional Distribution
initial state	$\pi_{k} \equiv p\left(z_{1 k}=1\right)$	$p\left(\mathbf{z}_{1} \mid \boldsymbol{\pi}\right)=\prod_{k=1}^{K} \pi_{k}^{z_{1 k}}\quad (13.8)$
transition probability	$A_{j k} \equiv p\left(z_{n k}=1\mid z_{n-1, j}=1\right)$	$p\left(\mathbf{z}_{n} \mid \mathbf{z}_{n-1}, \mathbf{A}\right)=\prod_{k=1}^{K} \prod_{j=1}^{K} A_{j k}^{z_{n-1, j} z_{n k}}\quad (13.7)$
emission probability	$\phi_{i k}\equiv p\left(x_{n i}=1 \mid z_{n k}=1\right)$	$p(\mathbf{x}_n \mid \mathbf{z}_n, \boldsymbol{\phi})=\prod_{i=1}^{D} \prod_{k=1}^{K} \phi_{i k}^{x_{ni} z_{nk}}\quad (13.22)$

尤度関数

ここで、データ集合 $\mathbf{X}$ が観測された際に、上記の同時分布を潜在変数 $\mathbf{Z}$ について周辺化することで、尤度関数は以下のように記述されます。

$p(\mathbf{X} | \boldsymbol{\theta})=\sum_{\mathbf{Z}} p(\mathbf{X}, \mathbf{Z} | \boldsymbol{\theta})\qquad (13.11)$

しかし、この尤度関数は $n$ について分解できない（ $\mathbf{z}_n$ ）ごとに和を取れないので、条件付き独立の性質を活かして尤度関数の対数の期待値を最大化するBaum-Welch algorithm (EM algorithm)を用います。

Baum-Welch (EM)

パラメータ $\boldsymbol{\theta}^{\text {old }}$ を用いて $p\left(\mathbf{Z} | \mathbf{X}, \boldsymbol{\theta}^{\text {old }}\right)$ を最大化する。
対数尤度関数の期待値 $Q\left(\boldsymbol{\theta}, \boldsymbol{\theta}^{\text {old }}\right)$ を求める。
$Q\left(\boldsymbol{\theta}, \boldsymbol{\theta}^{\text {old }}\right)$ を最大化するパラメータに更新する。 $\boldsymbol{\theta}\rightarrow\boldsymbol{\theta}^{\text {old }}$
1に戻る。

$Q\left(\boldsymbol{\theta}, \boldsymbol{\theta}^{\text {old }}\right)=\sum_{\mathbf{Z}} p\left(\mathbf{Z} | \mathbf{X}, \boldsymbol{\theta}^{\text {old }}\right) \ln p(\mathbf{X}, \mathbf{Z} | \boldsymbol{\theta})\qquad (13.12)$

ここで、表記を簡単にするために、γ、ξを導入します。

$\begin{aligned} \gamma\left(\mathbf{z}_{n}\right) &=p\left(\mathbf{z}_{n} | \mathbf{X}, \boldsymbol{\theta}^{\text {old }}\right) &(13.13)\\ \xi\left(\mathbf{z}_{n-1}, \mathbf{z}_{n}\right) &=p\left(\mathbf{z}_{n-1}, \mathbf{z}_{n} | \mathbf{X}, \boldsymbol{\theta}^{\text {old }}\right) &(13.14) \end{aligned}$

なお、潜在変数が離散なので、以下のように記述し直せます。（ $\pi_{k},A_{j k},\phi_{j k}$ と同様。）

$\begin{aligned} \gamma\left(z_{n k}\right) &=\sum_{\mathbf{z}} \gamma(\mathbf{z}) z_{n k} &(13.15)\\ \xi\left(z_{n-1, j}, z_{n k}\right) &=\sum_{\mathbf{z}} \gamma(\mathbf{z}) z_{n-1, j} z_{n k} &(13.16)\end{aligned}$

これらを用いると、 $Q\left(\boldsymbol{\theta}, \boldsymbol{\theta}^{\mathrm{old}}\right)$ が以下のように書き下せます。（計算過程）

$\begin{aligned} Q\left(\boldsymbol{\theta}, \boldsymbol{\theta}^{\mathrm{old}}\right)=& \sum_{k=1}^{K} \gamma\left(z_{1 k}\right) \ln \pi_{k}+\sum_{n=2}^{N} \sum_{j=1}^{K} \sum_{k=1}^{K} \xi\left(z_{n-1, j}, z_{n k}\right) \ln A_{j k} \\ &+\sum_{n=1}^{N} \sum_{k=1}^{K}\gamma\left(z_{n k}\right) \sum_{i=1}^Dx_{ni} \ln \phi_{i k} \end{aligned}\qquad (13.17)$

Maximization step

※ 実際の計算の順番からは前後しますが、先にM stepを説明します。

上記の $Q\left(\boldsymbol{\theta}, \boldsymbol{\theta}^{\mathrm{old}}\right)$ を各パラメータ $\boldsymbol{\theta}$ に関して最大化するのは（別ブロックに別れているから）簡単で、それぞれ適当なラグランジュ乗数を導入することで、以下のように求まります。（計算過程）

$\begin{aligned} \pi_{k}&= \frac{\gamma\left(z_{1 k}\right)}{\sum_{j=1}^{K} \gamma\left(z_{1 j}\right)} & (13.18)\\ A_{j k}&= \frac{\sum_{n=2}^{N} \xi\left(z_{n-1, j}, z_{n k}\right)}{\sum_{l=1}^{K} \sum_{n=2}^{N} \xi\left(z_{n-1, j}, z_{n l}\right)} & (13.19)\\ \phi_{i k}&=\frac{\sum_{n=1}^{N} \gamma\left(z_{n k}\right) x_{n i}}{\sum_{n=1}^{N} \gamma\left(z_{n k}\right)} & (13.23) \end{aligned}$

Expectation step

M step で必要となる $\gamma,\xi$ は、条件付き独立性を用いることで効率的に計算することができます。

$\begin{aligned} \gamma\left(\mathbf{z}_{n}\right) &=p\left(\mathbf{z}_{n} | \mathbf{X}\right)=\frac{p\left(\mathbf{X} | \mathbf{z}_{n}\right) p\left(\mathbf{z}_{n}\right)}{p(\mathbf{X})}\quad (\because \text{Bayes' theorem}) &(13.32)\\ &=\frac{p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n}, \mathbf{z}_{n}\right) p\left(\mathbf{x}_{n+1}, \ldots, \mathbf{x}_{N} | \mathbf{z}_{n}\right)}{p(\mathbf{X})} \quad (\because \text{conditional independence})\\ &= \frac{\alpha\left(\mathbf{z}_{n}\right) \beta\left(\mathbf{z}_{n}\right)}{p(\mathbf{X})} & (13.33) \end{aligned}$

$\begin{aligned} \alpha\left(\mathbf{z}_{n}\right) & \equiv p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n}, \mathbf{z}_{n}\right) & (13.34)\\ \beta\left(\mathbf{z}_{n}\right) & \equiv p\left(\mathbf{x}_{n+1}, \ldots, \mathbf{x}_{N} | \mathbf{z}_{n}\right) & (13.35) \end{aligned}$

条件付き独立性を用いてそれぞれ変形すると、以下の再帰式を導くことができます。（計算過程）

$\begin{aligned} \alpha\left(\mathbf{z}_{n}\right) &=p\left(\mathbf{x}_{n} | \mathbf{z}_{n}\right) \sum_{\mathbf{z}_{n-1}} \alpha\left(\mathbf{z}_{n-1}\right) p\left(\mathbf{z}_{n} | \mathbf{z}_{n-1}\right) & (13.36)\\ \alpha\left(\mathbf{z}_{1}\right) &=p\left(\mathbf{x}_{1}, \mathbf{z}_{1}\right)=p\left(\mathbf{z}_{1}\right) p\left(\mathbf{x}_{1} | \mathbf{z}_{1}\right)=\prod_{k=1}^{K}\left\{\pi_{k} p\left(\mathbf{x}_{1} | \boldsymbol{\phi}_{k}\right)\right\}^{z_{1 k}} & (13.37)\\ \beta\left(\mathbf{z}_{n}\right) &=\sum_{\mathbf{z}_{n+1}} \beta\left(\mathbf{z}_{n+1}\right) p\left(\mathbf{x}_{n+1} | \mathbf{z}_{n+1}\right) p\left(\mathbf{z}_{n+1} | \mathbf{z}_{n}\right) & (13.38)\\ \beta\left(\mathbf{z}_{N}\right) &= \frac{\gamma\left(\mathbf{z}_N\right)p\left(\mathbf{X}\right)}{\alpha\left(\mathbf{z}_N\right)} = \frac{p\left(\mathbf{z}_{N} | \mathbf{X}\right)p(\mathbf{X})}{p\left(\mathbf{X}, \mathbf{z}_{N}\right)} = 1 & (13.30) \end{aligned}$

※ なお、ここで $\alpha$ の再起式をforward-algorithm、 $\beta$ の再起式をbackward-algorithmと呼ぶことがあります。

また、これらを用いて $\xi$ を記述することもでき、以下のように表せます。（計算過程）

$\xi\left(\mathbf{z}_{n-1}, \mathbf{z}_{n}\right)=\frac{\alpha\left(\mathbf{z}_{n-1}\right) p\left(\mathbf{x}_{n} | \mathbf{z}_{n}\right) p\left(\mathbf{z}_{n} | \mathbf{z}_{n-1}\right) \beta\left(\mathbf{z}_{n}\right)}{p(\mathbf{X})}\qquad (13.43)$

以上でBaum-Welchに必要な計算式が求まりました。

おまけ（尤度関数）

尤度関数は、アルゴリズムの停止条件に用いられるなど、値を求めることが非常に有用です。

求める際は、

$\gamma\left(\mathbf{z}_{n}\right)= \frac{\alpha\left(\mathbf{z}_{n}\right) \beta\left(\mathbf{z}_{n}\right)}{p(\mathbf{X})} \qquad (13.33)$

の両辺を $\mathbf{z}_n$ について周辺化すれば、左辺は

$\sum_{\mathbf{z}_{n}} \gamma\left(\mathbf{z}_{n}\right) = \sum_{\mathbf{z}_{n}}p\left(\mathbf{z}_{n} | \mathbf{X}\right) = 1$

となることが明らかなので、以下のように求まります。

$p(\mathbf{X})=\sum_{\mathbf{z}_{n}} \alpha\left(\mathbf{z}_{n}\right) \beta\left(\mathbf{z}_{n}\right)\qquad (13.41)$

また、上記の式は任意の $n$ について成立するので、 $n=N$ の場合を考えれば $\alpha$ のみを用いて求めることができます。

$p(\mathbf{X})=\sum_{\mathbf{z}_{N}} \alpha\left(\mathbf{z}_{N}\right)\qquad (13.42)$

HMMの最尤推定

尤度関数

Baum-Welch (EM)

Maximization step

Expectation step

おまけ（尤度関数）

Table of Contents

Published

Last Updated

Category

Tags

Contact

Other contents