フォワード-バックワードアルゴリズム(α-βアルゴリズム)

はじめに

本記事では、モデルパラメータ ${\boldsymbol\theta}^{old}$ は一定なので、依存性は明記しません。
本記事は、隠れマルコフモデルの最尤推定の続きの記事であり、
HMMの最尤推定のEMアルゴリズムにおけるEステップの $\gamma(z_{nk})$ と $\xi(z_{n-1,j},z_{nk})$ を求めるのが主目的となります。

フォワード-バックワードアルゴリズム

隠れマルコフモデルは木構造を持ち、2段階のメッセージパッシングアルゴリズムによって、潜在変数の事後確率が効率的に求められます。
隠れマルコフモデルにおいては、これは特に、フォワード-バックワードアルゴリズム、あるいは、Baum-Welchアルゴリズムと呼ばれます。
基本アルゴリズムはいくつか変形版がありますが、ここでは $\alpha$ - $\beta$ アルゴリズムとして知られる、もっともよく使われるものに焦点を当てます。

隠れマルコフモデルの条件付き独立性

潜在変数の事後確率を求めるために必要なのは、
すべての $n$ における、 ${\bf z}_n$ の各々の値に対する $p({\bf x}_n|{\bf z}_n)$ です。

それでは、まず条件付き確率を書き下します。(式の説明はまとめて行います。)

$\begin{eqnarray} p({\bf X}|{\bf z}_n)&=&p({\bf x}_1,\ldots,{\bf x}_n|{\bf z}_n)p({\bf x}_{n+1},\ldots,{\bf x}_N|{\bf z}_n)\tag{1}\\ p({\bf x}_1,\ldots,{\bf x}_{n-1}|{\bf x}_n,{\bf z}_n)&=&p({\bf x}_1,\ldots,{\bf x}_{n-1}|{\bf z}_n)\tag{2}\\ p({\bf x}_1,\ldots,{\bf x}_{n-1}|{\bf z}_{n-1},{\bf z}_n)&=&p({\bf x}_1,\ldots,{\bf x}_{n-1}|{\bf z}_{n-1})\tag{3}\\ p({\bf x}_{n+1},\ldots,{\bf x}_N|{\bf z}_n,{\bf z}_{n+1})&=&p({\bf x}_{n+1},\ldots,{\bf x}_N|{\bf z}_{n+1})\tag{4}\\ p({\bf x}_{n+2},\ldots,{\bf x}_N|{\bf z}_{n+1},{\bf x}_{n+1})&=&p({\bf x}_{n+2},\ldots,{\bf x}_N|{\bf z}_{n+1})\tag{5}\\ p({\bf X}|{\bf z}_{n-1},{\bf z}_n)&=&p({\bf x}_1,\ldots,{\bf x}_{n-1}|{\bf z}_{n-1})p({\bf x}_n|{\bf z}_n)p({\bf x}_{n+1},\ldots,{\bf x}_N|{\bf z}_n)\tag{6}\\ p({\bf x}_{N+1}|{\bf X},{\bf z}_{N+1})&=&p({\bf x}_{N+1}|{\bf z}_{N+1})\tag{7}\\ p({\bf z}_{N+1}|{\bf z}_N,{\bf X})&=&p({\bf z}_{N+1}|{\bf z}_N)\tag{8} \end{eqnarray}$

条件付き独立の復習をしておきます。
$c$ が与えられた下で、 $a$ は $b$ に対して条件付き独立であるとき、以下の式が成り立ちます。

$\begin{eqnarray} p(a|b,c)=p(a|c)\tag{9} \end{eqnarray}$

また、 $c$ で条件付けれられた $a$ および $b$ の同時分布について考えると、条件付き独立性は、以下の形でも表せます。

$\begin{eqnarray} p(a,b|c)&=&p(a|b,c)p(b|c)\\ &=&p(a|c)p(b|c)\tag{10} \end{eqnarray}$

以下の式 $(1)$ から式 $(8)$ の説明用のグラフで、 $a,b,c$ に該当する集合を $A,B,C$ と表記します。

式 $(1)\ \ p({\bf X} | {\bf z}_n)=p({\bf x}_1,\ldots,{\bf x}_n | {\bf z}_n)p({\bf x}_{n+1},\ldots,{\bf x}_N | {\bf z}_n)$ の説明

f:id:olj611:20210923201803p:plain:w700
${\bf x}_1,\ldots,{\bf x}_n$ のどれかから ${\bf x}_{n+1},\ldots,{\bf x}_N$ のどれかへの経路は、すべて ${\bf z}_n$ を通り、
そこでhead-to-tailで観測されていると仮定されているため、
$\{{\bf x}_1,\ldots,{\bf x}_n\}\mathop{\perp\!\!\!\!\perp}{\bf x}_{n+1},\ldots,{\bf x}_N|{\bf z}_n$ であり、式 $(1)$ が成り立ちます。

式 $(2)\ \ p({\bf x}_1,\ldots,{\bf x}_{n-1} | {\bf x}_n,{\bf z}_n)=p({\bf x}_1,\ldots,{\bf x}_{n-1} | {\bf z}_n)$ の説明

f:id:olj611:20210923202015p:plain:w700
${\bf x}_1,\ldots,{\bf x}_{n-1}$ のどれかから ${\bf x}_n$ への経路は、すべて ${\bf z}_n$ を通り、
そこでhead-to-tailで観測されていると仮定されているため、
$\{{\bf x}_1,\ldots,{\bf x}_{n-1}\}\mathop{\perp\!\!\!\!\perp}{\bf x}_n|{\bf z}_n$ であり、式 $(2)$ が成り立ちます。

式 $(3)\ \ p({\bf x}_1,\ldots,{\bf x}_{n-1}|{\bf z}_{n-1},{\bf z}_n)=p({\bf x}_1,\ldots,{\bf x}_{n-1}|{\bf z}_{n-1})$ の説明

f:id:olj611:20210923202329p:plain:w700
${\bf x}_1,\ldots,{\bf x}_{n-1}$ のどれかから ${\bf z}_n$ への経路は、すべて ${\bf z}_{n-1}$ を通り、
そこでhead-to-tailまたはtail-to-tailで観測されていると仮定されているため、
$\{{\bf x}_1,\ldots,{\bf x}_{n-1}\}\mathop{\perp\!\!\!\!\perp}{\bf z}_n|{\bf z}_{n-1}$ であり、式 $(3)$ が成り立ちます。

式 $(4)\ \ p({\bf x}_{n+1},\ldots,{\bf x}_N|{\bf z}_n,{\bf z}_{n+1})=p({\bf x}_{n+1},\ldots,{\bf x}_N|{\bf z}_{n+1})$ の説明

f:id:olj611:20210923202918p:plain:w700
${\bf x}_{n+1},\ldots,{\bf x}_{N}$ のどれかから ${\bf z}_n$ への経路は、すべて ${\bf z}_{n+1}$ を通り、
そこでhead-to-tailで観測されていると仮定されているため、
$\{{\bf x}_{n+1},\ldots,{\bf x}_{N}\}\mathop{\perp\!\!\!\!\perp}{\bf z}_n|{\bf z}_{n+1}$ であり、式 $(4)$ が成り立ちます。

式 $(5)\ \ p({\bf x}_{n+2},\ldots,{\bf x}_N|{\bf z}_{n+1},{\bf x}_{n+1})=p({\bf x}_{n+2},\ldots,{\bf x}_N|{\bf z}_{n+1})$ の説明

f:id:olj611:20210923204523p:plain:w700
${\bf x}_{n+2},\ldots,{\bf x}_{N}$ のどれかから ${\bf x}_{n+1}$ への経路は、すべて ${\bf z}_{n+1}$ を通り、
そこでtail-to-tailで観測されていると仮定されているため、
$\{{\bf x}_{n+2},\ldots,{\bf x}_{N}\}\mathop{\perp\!\!\!\!\perp}{\bf x}_{n+1}|{\bf z}_{n+1}$ であり、式 $(5)$ が成り立ちます。

式 $(6)\ \ p({\bf X}|{\bf z}_{n-1},{\bf z}_n)=p({\bf x}_1,\ldots,{\bf x}_{n-1}|{\bf z}_{n-1})p({\bf x}_n|{\bf z}_n)p({\bf x}_{n+1},\ldots,{\bf x}_N|{\bf z}_n)$ の説明

f:id:olj611:20210923212429p:plain:w700
${\bf x}_{1},\ldots,{\bf x}_{n-1}$ のどれかから ${\bf x}_{n},\ldots,{\bf x}_{N}$ のどれかへの経路は、すべて ${\bf z}_{n},{\bf z}_{n+1}$ を通り、
そこでhead-to-tailまたはtail-to-tailで観測されていると仮定されているため、
$\{{\bf x}_{1},\ldots,{\bf x}_{n-1}\}\mathop{\perp\!\!\!\!\perp}\{{\bf x}_{n},\ldots,{\bf x}_N\}|{\bf z}_{n-1},{\bf z}_{n}$ であり、以下の式 $(11)$ が成り立ちます。

$\begin{eqnarray} p({\bf X}|{\bf z}_{n-1},{\bf z}_n)=p({\bf x}_1,\ldots,{\bf x}_{n-1}|{\bf z}_{n-1},{\bf z}_n)p({\bf x}_n,\ldots,{\bf x}_N|{\bf z}_{n-1},{\bf z}_n)\tag{11} \end{eqnarray}$

式 $(3)\ \ p({\bf x}_1,\ldots,{\bf x}_{n-1}|{\bf z}_{n-1},{\bf z}_n)=p({\bf x}_1,\ldots,{\bf x}_{n-1}|{\bf z}_{n-1})$ を式 $(11)$ に代入します。

$\begin{eqnarray} p({\bf X}|{\bf z}_{n-1},{\bf z}_n)=p({\bf x}_1,\ldots,{\bf x}_{n-1}|{\bf z}_{n-1})p({\bf x}_n,\ldots,{\bf x}_N|{\bf z}_{n-1},{\bf z}_n)\tag{12} \end{eqnarray}$

式 $(12)$ の右辺の因数 $p({\bf x}_n,\ldots,{\bf x}_N|{\bf z}_{n-1},{\bf z}_n)$ に着目します。
f:id:olj611:20210923213846p:plain:w700
${\bf x}_{n},\ldots,{\bf x}_{N}$ のどれかから ${\bf z}_{n-1}$ への経路は、すべて ${\bf z}_{n}$ を通り、
そこでhead-to-tailで観測されていると仮定されているため、
$\{{\bf x}_{n},\ldots,{\bf x}_{N}\}\mathop{\perp\!\!\!\!\perp}{\bf z}_{n-1}|{\bf z}_{n}$ であり、以下の式 $(13)$ が成り立ちます。

$\begin{eqnarray} p({\bf x}_n,\ldots,{\bf x}_N|{\bf z}_{n-1},{\bf z}_n)=p({\bf x}_n,\ldots,{\bf x}_N|{\bf z}_n)\tag{13} \end{eqnarray}$

式 $(13)$ を式 $(12)$ に代入します。

$\begin{eqnarray} p({\bf X}|{\bf z}_{n-1},{\bf z}_n)=p({\bf x}_1,\ldots,{\bf x}_{n-1}|{\bf z}_{n-1})p({\bf x}_n,\ldots,{\bf x}_N|{\bf z}_n)\tag{14} \end{eqnarray}$

式 $(14)$ の右辺の因数 $p({\bf x}_n,\ldots,{\bf x}_N|{\bf z}_n)$ に着目します。
f:id:olj611:20210923214405p:plain:w700
${\bf x}_{n}$ のから ${\bf x}_{n+1},\ldots,{\bf x}_N$ のどれかへの経路は、すべて ${\bf z}_{n}$ を通り、
そこでhead-to-tailで観測されていると仮定されているため、
${\bf x}_{n}\mathop{\perp\!\!\!\!\perp}\{{\bf x}_{n+1},\ldots,{\bf x}_N\}|{\bf z}_{n}$ であり、以下の式 $(15)$ が成り立ちます。

$\begin{eqnarray} p({\bf x}_n,\ldots,{\bf x}_N|{\bf z}_n)=p({\bf x}_n|{\bf z}_n)p({\bf x}_{n+1},\ldots,{\bf x}_N|{\bf z}_n)\tag{15} \end{eqnarray}$

式 $(15)$ を式 $(14)$ に代入します。

$\begin{eqnarray} p({\bf X}|{\bf z}_{n-1},{\bf z}_n)=p({\bf x}_1,\ldots,{\bf x}_{n-1}|{\bf z}_{n-1})p({\bf x}_n|{\bf z}_n)p({\bf x}_{n+1},\ldots,{\bf x}_N|{\bf z}_n)\tag{16} \end{eqnarray}$

式 $(16)$ より、式 $(6)$ が示せました。

式 $(7)\ \ p({\bf x}_{N+1}|{\bf X},{\bf z}_{N+1})=p({\bf x}_{N+1}|{\bf z}_{N+1})$ の説明

f:id:olj611:20210923205141p:plain:w700
${\bf x}_{N+1}$ から ${\bf X}$ のどれかへの経路は、すべて ${\bf z}_{N+1}$ を通り、
そこでhead-to-tailで観測されていると仮定されているため、
${\bf x}_{N+1}\mathop{\perp\!\!\!\!\perp}{\bf X}|{\bf z}_{N+1}$ であり、式 $(7)$ が成り立ちます。

式 $(8)\ \ p({\bf z}_{N+1}|{\bf z}_N,{\bf X})=p({\bf z}_{N+1}|{\bf z}_N)$ の説明

f:id:olj611:20210923210056p:plain:w700
${\bf z}_{N+1}$ から ${\bf X}$ のどれかへの経路は、すべて ${\bf z}_{N}$ を通り、
そこでhead-to-tailまたはtail-to-tailで観測されていると仮定されているため、
${\bf z}_{N+1}\mathop{\perp\!\!\!\!\perp}{\bf X}|{\bf z}_{N}$ であり、式 $(8)$ が成り立ちます。

式 $(1)$ から式 $(8)$ まで有向分離を使って説明しましたが、
確率の加法定理、乗法定理用いて、隠れマルコフモデルの同時分布から導くこともできます。

$\gamma(z_{nk})$ を求める

まず最初に、 $\gamma(z_{nk})$ を求めます。

$\gamma({\bf z}_n)$ を計算していきます。

$\begin{eqnarray} \gamma({\bf z}_n)&=&p({\bf z}_n|{\bf X})\\ &=&\frac{p({\bf X}|{\bf z}_n)p({\bf z}_n)}{p({\bf X})}\\ &=&\frac{p({\bf x}_1,\ldots,{\bf x}_n,{\bf z}_n)p({\bf x}_{n+1},\ldots,{\bf x}_N|{\bf z}_n)}{p({\bf X})}\tag{17}\\ &=&\frac{\alpha({\bf z}_n)\beta({\bf z}_n)}{p({\bf X})}\tag{18} \end{eqnarray}$

式 $(17)$ の変形には、式 $(1)$ を用いました。
式 $(18)$ において、以下のように定義しました。

$\begin{eqnarray} &&\alpha({\bf z}_n)\equiv p({\bf x}_1,\ldots,{\bf x}_n,{\bf z}_n)\tag{19}\\ &&\beta({\bf z}_n)\equiv p({\bf x}_{n+1},\ldots,{\bf x}_N|{\bf z}_n)\tag{20} \end{eqnarray}$

また、 $z_{nk}=1$ に対応する $\alpha({\bf z}_n)$ の値を $\alpha(z_{nk})$ とします。 $\beta(z_{nk})$ についても同様です。

$z_{nk}=1$ の時、式 $(18)$ は以下のようになります。

$\begin{eqnarray} \gamma(z_{nk})=\frac{\alpha(z_{nk})\beta(z_{nk})}{p({\bf X})}\tag{21} \end{eqnarray}$

式 $(21)$ より、 $\alpha(z_{nk}),\beta(z_{nk}),p({\bf X})$ が求まれば、 $\gamma(z_{nk})$ が求まることが分かります。

$\alpha(z_{nk})$ を求める

$\alpha({\bf z}_n)$ を計算していきます。

$\begin{eqnarray} \alpha({\bf z}_n)&=&p({\bf x}_1,\ldots,{\bf x}_n,{\bf z}_n)\\ &=&p({\bf x}_1,\ldots,{\bf x}_n|{\bf z}_n)p({\bf z}_n)\\ &=&p({\bf x}_n|{\bf z}_n)p({\bf x}_1,\ldots,{\bf x}_{n-1}|{\bf x}_n,{\bf z}_n)p({\bf z}_n)\\ &=&p({\bf x}_n|{\bf z}_n)p({\bf x}_1,\ldots,{\bf x}_{n-1}|{\bf z}_n)p({\bf z}_n)\tag{22}\\ &=&p({\bf x}_n|{\bf z}_n)p({\bf x}_1,\ldots,{\bf x}_{n-1},{\bf z}_n)\\ &=&p({\bf x}_n|{\bf z}_n)\sum_{{\bf z}_{n-1}}p({\bf x}_1,\ldots,{\bf x}_{n-1},{\bf z}_{n-1},{\bf z}_n)\\ &=&p({\bf x}_n|{\bf z}_n)\sum_{{\bf z}_{n-1}}p({\bf x}_1,\ldots,{\bf x}_{n-1},{\bf z}_n|{\bf z}_{n-1})p({\bf z}_{n-1})\\ &=&p({\bf x}_n|{\bf z}_n)\sum_{{\bf z}_{n-1}}p({\bf x}_1,\ldots,{\bf x}_{n-1}|{\bf z}_n,{\bf z}_{n-1})p({\bf z}_n|{\bf z}_{n-1})p({\bf z}_{n-1})\\ &=&p({\bf x}_n|{\bf z}_n)\sum_{{\bf z}_{n-1}}p({\bf x}_1,\ldots,{\bf x}_{n-1}|{\bf z}_{n-1})p({\bf z}_n|{\bf z}_{n-1})p({\bf z}_{n-1})\tag{23}\\ &=&p({\bf x}_n|{\bf z}_n)\sum_{{\bf z}_{n-1}}p({\bf x}_1,\ldots,{\bf x}_{n-1},{\bf z}_{n-1})p({\bf z}_n|{\bf z}_{n-1})\\ &=&p({\bf x}_n|{\bf z}_n)\sum_{{\bf z}_{n-1}}\alpha({\bf z}_{n-1})p({\bf z}_n|{\bf z}_{n-1})\tag{24} \end{eqnarray}$

式 $(22)$ の変形は、式 $(2)$ を用いました。
式 $(23)$ の変形は、式 $(3)$ を用いました。

$\alpha(z_{nk})$ を求めるために、式 $(24)$ において、 $z_{nk}=1$ の場合を考えると以下のようになります。

$\begin{eqnarray} \alpha(z_{nk})&=&p({\bf x}_n|z_{nk}=1)\sum_{{\bf z}_{n-1}}\alpha({\bf z}_{n-1})p(z_{nk}=1|{\bf z}_{n-1})\\ &=&p({\bf x}_n|z_{nk}=1)\sum_{j=1}^K\alpha(z_{n-1,j})p(z_{nk}=1|z_{n-1,j}=1)\\ &=&p({\bf x}_n|z_{nk}=1)\sum_{j=1}^K\alpha(z_{n-1,j})A_{jk}\tag{25} \end{eqnarray}$

式 $(25)$ の再帰式のイメージを下に図で示します。(図1における $p({\bf x}_n|z_{n,1})$ は $p({\bf x}_n|z_{n,1}=1)$ のことだと思います。)
図1
f:id:olj611:20210925111629p:plain:h400

式 $(24)$ の再帰を開始するために、初期条件 $\alpha({\bf z}_1)$ が必要となります。

$\begin{eqnarray} \alpha({\bf z}_1)&=&p({\bf x}_1,{\bf z}_1)\\ &=&p({\bf z}_1)p({\bf x}_1|{\bf z}_1)\\ &=&p({\bf z}_1|{\boldsymbol\pi})p({\bf x}_1|{\bf z}_1,{\boldsymbol\phi})\\ &=&\prod_{k=1}^K\pi_k^{z_{1k}}\prod_{k=1}^Kp({\bf x}_1|{\boldsymbol\phi}_k)^{z_{1k}}\\ &=&\prod_{k=1}^K\left(\pi_kp({\bf x}_1|{\boldsymbol\phi}_k)\right)^{z_{1k}}\tag{26} \end{eqnarray}$

$\alpha(z_{1k})$ を求めるために、式 $(26)$ において、 $z_{1k}=1$ の場合を考えると以下のようになります。

$\begin{eqnarray} \alpha(z_{1k})=\pi_kp({\bf x}_1|{\boldsymbol\phi}_k)\tag{27} \end{eqnarray}$

初期条件の式 $(27)$ と再帰式 $(25)$ により、 $\alpha(z_{nk})$ が求まることが分かります。

$\beta(z_{nk})$ を求める

$\beta({\bf z}_n)$ を計算していきます。

$\begin{eqnarray} \beta({\bf z}_n)&=&p({\bf x}_{n+1},\ldots,{\bf x}_N|{\bf z}_n)\\ &=&\sum_{{\bf z}_{n+1}}p({\bf x}_{n+1},\ldots,{\bf x}_N,{\bf z}_{n+1}|{\bf z}_n)\\ &=&\sum_{{\bf z}_{n+1}}p({\bf x}_{n+1},\ldots,{\bf x}_N|{\bf z}_n,{\bf z}_{n+1})p({\bf z}_{n+1}|{\bf z}_n)\\ &=&\sum_{{\bf z}_{n+1}}p({\bf x}_{n+1},\ldots,{\bf x}_N|{\bf z}_{n+1})p({\bf z}_{n+1}|{\bf z}_n)\tag{28}\\ &=&\sum_{{\bf z}_{n+1}}p({\bf x}_{n+2},\ldots,{\bf x}_N|{\bf x}_{n+1},{\bf z}_{n+1})p({\bf x}_{n+1}|{\bf z}_{n+1})p({\bf z}_{n+1}|{\bf z}_n)\\ &=&\sum_{{\bf z}_{n+1}}p({\bf x}_{n+2},\ldots,{\bf x}_N|{\bf z}_{n+1})p({\bf x}_{n+1}|{\bf z}_{n+1})p({\bf z}_{n+1}|{\bf z}_n)\tag{29}\\ &=&\sum_{{\bf z}_{n+1}}\beta({\bf z}_{n+1})p({\bf x}_{n+1}|{\bf z}_{n+1})p({\bf z}_{n+1}|{\bf z}_n)\tag{30} \end{eqnarray}$

式 $(28)$ の変形は、式 $(4)$ を用いました。
式 $(29)$ の変形は、式 $(5)$ を用いました。
式 $(30)$ は、 $\beta({\bf z}_{n+1})$ を用いて $\beta({\bf z}_n)$ を求める後ろ向きメッセージパッシングアルゴリズムになっていることに注意しましょう。

$\beta(z_{nk})$ を求めるために、式 $(30)$ において、 $z_{nk}=1$ の場合を考えると以下のようになります。

$\begin{eqnarray} \beta(z_{nk})&=&\sum_{{\bf z}_{n+1}}\beta({\bf z}_{n+1})p({\bf x}_{n+1}|{\bf z}_{n+1})p({\bf z}_{n+1}|z_{nk}=1)\\ &=&\sum_{j=1}^K\beta(z_{n+1,j})p({\bf x}_{n+1}|z_{n+1,j}=1)p(z_{n+1,j}|z_{nk}=1)\\ &=&\sum_{j=1}^K\beta(z_{n+1,j})p({\bf x}_{n+1}|z_{n+1,j}=1)A_{kj}\tag{31} \end{eqnarray}$

式 $(31)$ の再帰式のイメージを下に図で示します。
(図2における $p({\bf x}_n|z_{n+1,k})$ は $p({\bf x}_n|z_{n+1,k}=1)$ のことだと思います。)
図2
f:id:olj611:20210925120425p:plain:h400

式 $(30)$ の再帰を開始するために、初期条件 $\beta({\bf z}_N)$ が必要となります。
式 $(18)$ で、 $n=N$ とおきます。

$\begin{eqnarray} p({\bf z}_N|{\bf X})&=&\frac{\alpha({\bf z}_N)\beta({\bf z}_N)}{p({\bf X})}\\ &=&\frac{p({\bf X},{\bf z}_N)\beta({\bf z}_N)}{p({\bf X})}\tag{32} \end{eqnarray}$

式 $(32)$ が ${\bf z}_N$ のすべての値について、成り立つためには、

$\begin{eqnarray} \beta({\bf z}_N)=1\tag{33} \end{eqnarray}$

となっていればよいです。( $\beta({\bf z}_N)=1$ のとき、式 $(32)$ において確率の乗法定理が成り立ちます。)

$\beta(z_{Nk})$ を求めるために、式 $(33)$ において、 $z_{Nk}=1$ の場合を考えると以下のようになります。

$\begin{eqnarray} \beta(z_{Nk})=1\tag{34} \end{eqnarray}$

初期条件の式 $(34)$ と再帰式 $(31)$ により、 $\beta(z_{nk})$ が求まることが分かります。

完全データの尤度関数の値

式 $(18)$ において、 ${\bf z}_n$ について周辺化することにより、完全データの尤度関数 $p({\bf X})$ を計算します。

$\begin{eqnarray} &&p({\bf z}_n|{\bf X})=\frac{\alpha({\bf z}_n)\beta({\bf z}_n)}{p({\bf X})}\\ &&\Leftrightarrow\sum_{{\bf z}_n}p({\bf z}_n|{\bf X})=\frac{1}{{p({\bf X})}}\sum_{{\bf z}_n}\alpha({\bf z}_n)\beta({\bf z}_n)\\ &&\Leftrightarrow 1=\frac{1}{{p({\bf X})}}\sum_{{\bf z}_n}\alpha({\bf z}_n)\beta({\bf z}_n)\\ &&\Leftrightarrow p({\bf X})=\sum_{{\bf z}_n}\alpha({\bf z}_n)\beta({\bf z}_n)\tag{35} \end{eqnarray}$

式 $(35)$ において、 $n=N$ とおくと、以下の式が成り立ちます。

$\begin{eqnarray} p({\bf X})=\sum_{{\bf z}_N}\alpha({\bf z}_N)\tag{36} \end{eqnarray}$

式 $(36)$ は式 $(33)$ を利用しています。

$\xi(z_{n-1,k},z_{nk})$ を求める

次に、 $\xi(z_{n-1,k},z_{nk})$ を求めます。

$\xi({\bf z}_{n-1},{\bf z}_n)$ を計算していきます。

$\begin{eqnarray} \xi({\bf z}_{n-1},{\bf z}_n)&=&p({\bf z}_{n-1},{\bf z}_n|{\bf X})\\ &=&\frac{p({\bf X}|{\bf z}_{n-1},{\bf z}_n)p({\bf z}_{n-1},{\bf z}_n)}{p({\bf X})}\\ &=&\frac{p({\bf x}_1,\ldots,{\bf x}_{n-1}|{\bf z}_{n-1})p({\bf x}_n|{\bf z}_n)p({\bf x}_{n+1},\ldots,{\bf x}_N|{\bf z}_n)p({\bf z}_n|{\bf z}_{n-1})p({\bf z}_{n-1})}{p({\bf X})}\tag{37}\\ &=&\frac{p({\bf x}_1,\ldots,{\bf x}_{n-1},{\bf z}_{n-1})p({\bf x}_n|{\bf z}_n)p({\bf x}_{n+1},\ldots,{\bf x}_N|{\bf z}_n)p({\bf z}_n|{\bf z}_{n-1})}{p({\bf X})}\\ &=&\frac{\alpha({\bf z}_{n-1})p({\bf x}_n|{\bf z}_n)p({\bf z}_n|{\bf z}_{n-1})\beta({\bf z}_n)}{p({\bf X})}\tag{38} \end{eqnarray}$

式 $(37)$ の変形は、式 $(6)$ を用いました。

$\xi(z_{n-1,k},z_{nk})$ を求めるために、式 $(37)$ において、 $z_{n-1,k}=1,z_{nk}=1$ の場合を考えると以下のようになります。

$\begin{eqnarray} \xi(z_{n-1,k},z_{nk})&=&\frac{\alpha(z_{n-1,k})p({\bf x}_n|z_{nk}=1)p(z_{nk}=1|z_{n-1,k})\beta(z_{nk})}{p({\bf X})}\\ &=&\frac{\alpha(z_{n-1,k})p({\bf x}_n|z_{nk}=1)A_{kk}\beta(z_{nk})}{p({\bf X})}\tag{39} \end{eqnarray}$

式 $(39)$ において、 $\alpha(z_{n-1,k}),\beta(z_{nk})$ は $\alpha$ 再帰、 $\beta$ 再帰の結果を使えばよいです。

予測分布

データ ${\bf X}$ が観測されたときに、 ${\bf x}_{N+1}$ を予測することを考えます。

$p({\bf x}_{N+1}|{\bf X})$ を計算していきます。

$\begin{eqnarray} p({\bf x}_{N+1}|{\bf X})&=&\sum_{{\bf z}_{N+1}}p({\bf x}_{N+1},{\bf z}_{N+1}|{\bf X})\\ &=&\sum_{{\bf z}_{N+1}}p({\bf x}_{N+1}|{\bf X},{\bf z}_{N+1})p({\bf z}_{N+1}|{\bf X})\\ &=&\sum_{{\bf z}_{N+1}}p({\bf x}_{N+1}|{\bf z}_{N+1})p({\bf z}_{N+1}|{\bf X})\tag{40}\\ &=&\sum_{{\bf z}_{N+1}}p({\bf x}_{N+1}|{\bf z}_{N+1})\sum_{{\bf z}_N}p({\bf z}_{N+1},{\bf z}_N|{\bf X})\\ &=&\sum_{{\bf z}_{N+1}}p({\bf x}_{N+1}|{\bf z}_{N+1})\sum_{{\bf z}_N}p({\bf z}_{N+1}|{\bf z}_N,{\bf X})p({\bf z}_N|{\bf X})\\ &=&\sum_{{\bf z}_{N+1}}p({\bf x}_{N+1}|{\bf z}_{N+1})\sum_{{\bf z}_N}p({\bf z}_{N+1}|{\bf z}_N)p({\bf z}_N|{\bf X})\tag{41}\\ &=&\sum_{{\bf z}_{N+1}}p({\bf x}_{N+1}|{\bf z}_{N+1})\sum_{{\bf z}_N}p({\bf z}_{N+1}|{\bf z}_N)\frac{p({\bf z}_N,{\bf X})}{p({\bf X})}\\ &=&\frac{1}{p({\bf X})}\sum_{{\bf z}_{N+1}}p({\bf x}_{N+1}|{\bf z}_{N+1})\sum_{{\bf z}_N}p({\bf z}_{N+1}|{\bf z}_N)\alpha({\bf z}_N)\tag{42} \end{eqnarray}$

式 $(40)$ の変形は、式 $(7)$ を用いました。
式 $(41)$ の変形は、式 $(8)$ を用いました。

最後に

実は、このアルゴリズムは数値計算するときに問題があります。
それについて、スケーリング係数 - フォワード-バックワードアルゴリズム(α-βアルゴリズム)の記事で説明しています。

偉人の名言

f:id:olj611:20210925165507p:plain:h300
失敗したところでやめてしまうから失敗になる。
成功するところまで続ければ、それは成功になる。
松下幸之助

参考文献

パターン認識と機械学習下巻 p336-p343

動画

なし

機械学習基礎理論独習

誤りがあればご指摘いただけると幸いです。数式が整うまで少し時間かかります。リンクフリーです。