スケーリング係数 - フォワード-バックワードアルゴリズム(α-βアルゴリズム)

はじめに

本記事では、モデルパラメータ ${\boldsymbol\theta}^{old}$ は一定なので、依存性は明記しません。
本記事は、フォワード-バックワードアルゴリズム(α-βアルゴリズム)の続きの記事です。

$\alpha$ - $\beta$ アルゴリズムの数値計算時の問題点

$\alpha(z_{nk})$ の再帰式は以下でした。

$\begin{eqnarray} \alpha({\bf z}_n)&=&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{1} \end{eqnarray}$

再帰式 $(1)$ を見ると、お各々のステップの新しい値 $\alpha({\bf z}_n)$ は、
直前の値 $\alpha({\bf z}_{n-1})$ に $p({\bf z}_n|{\bf z}_{n-1})$ と $p({\bf x}_n|{\bf z}_n)$ を掛けることにより得られます。
これらの確率は、しばしば $1$ に比べてとても小さく、鎖に沿って前向きに進んでいくにつれて、
$\alpha({\bf z}_n)$ の値は指数的な速さでゼロに近づいていく可能性が高いです。

そこで、 $\alpha({\bf z}_n)$ と $\beta({\bf z}_n)$ にスケーリングを施し、それらの値が $1$ のオーダーに留まるようにします。

スケーリング - $\widehat{\alpha}$

正規化された $\widehat{\alpha}({\bf z}_n)$ の定義は以下で与えられます。

$\begin{eqnarray} \widehat{\alpha}({\bf z}_n)&=&p({\bf z}_n|{\bf x}_1,\ldots,{\bf x}_n)\\ &=&\frac{p({\bf x}_1,\ldots,{\bf x}_n,{\bf z}_n)}{p({\bf x}_1,\ldots,{\bf x}_n)}\\ &=&\frac{\alpha({\bf z}_n)}{p({\bf x}_1,\ldots,{\bf x}_n)}\tag{2} \end{eqnarray}$

式 $(2)$ が正規化されているか確認します。

$\begin{eqnarray} \sum_{{\bf z}_n}\widehat{\alpha}({\bf z}_n)&=&\sum_{{\bf z}_n}\frac{\alpha({\bf z}_n)}{p({\bf x}_1,\ldots,{\bf x}_n)}\\ &=&\frac{1}{p({\bf x}_1,\ldots,{\bf x}_n)}\sum_{{\bf z}_n}p({\bf x}_1,\ldots,{\bf x}_n,{\bf z}_n)\\ &=&\frac{1}{p({\bf x}_1,\ldots,{\bf x}_n)}p({\bf x}_1,\ldots,{\bf x}_n)\\ &=&1\tag{3} \end{eqnarray}$

式 $(3)$ より、式 $(2)$ が正規化されていることが確認できました。

式 $(2)$ の値は数値計算において良い振る舞いをすることが期待できます。
なぜなら、どの $n$ の値に対しても $K$ 個の変数上の確率分布だからです。

スケーリングを施した $\alpha$ 変数と、もともとの $\alpha$ 変数とを関係づけるために、
観測変数上の条件付き分布によって定義されるスケーリング係数を導入します。

$\begin{eqnarray} c_n=p({\bf x}_n|{\bf x}_1,\ldots,{\bf x}_{n-1})\tag{4} \end{eqnarray}$

確率の乗法定理より、以下の式が成り立ちます。

$\begin{eqnarray} \prod_{m=1}^nc_m=p({\bf x}_1,\ldots,{\bf x}_n)\tag{5} \end{eqnarray}$

式 $(5)$ が成り立つことを帰納法で示します。
$n=1$ の時、

$\begin{eqnarray} \prod_{m=1}^1c_m&=&c_1\\ &=&p({\bf x}_1)\tag{6} \end{eqnarray}$

式 $(6)$ より、式 $(5)$ が成り立ちます。
$n=l$ の時、式 $(5)$ が成り立つとすると、以下の式が成り立ちます。

$\begin{eqnarray} \prod_{m=1}^lc_m=p({\bf x}_1,\ldots,{\bf x}_l)\tag{7} \end{eqnarray}$

$\prod_{m=1}^{l+1}c_m$ を計算します。

$\begin{eqnarray} \prod_{m=1}^{l+1}c_m&=&\left(\prod_{m=1}^lc_m\right)c_{l+1}\\ &=&p({\bf x}_1,\ldots,{\bf x}_l)p({\bf x}_{l+1}|{\bf x}_1,\ldots,{\bf x}_l)\\ &=&p({\bf x}_1,\ldots,{\bf x}_{l+1})\tag{8} \end{eqnarray}$

式 $(8)$ より、 $n=l+1$ の時、式 $(5)$ が成り立ちます。
以上より、式 $(5)$ が成り立つことが分かります。

$\alpha({\bf z}_n)$ と $\widehat{\alpha}({\bf z}_n)$ の関係式を導きます。

$\begin{eqnarray} \alpha({\bf z}_n)&=&p({\bf x}_1,\ldots,{\bf x}_n,{\bf z}_n)\\ &=&p({\bf z}_n|{\bf x}_1,\ldots,{\bf x}_n)p({\bf x}_1,\ldots,{\bf x}_n)\\ &=&\left(\prod_{m=1}^nc_m\right)\widehat{\alpha}({\bf z}_n)\tag{9} \end{eqnarray}$

$\alpha({\bf z}_n)$ の再帰式は以下の式でした。

$\begin{eqnarray} \alpha({\bf z}_n)=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{10} \end{eqnarray}$

式 $(9)$ を式 $(10)$ に代入して、 $\widehat{\alpha}({\bf z}_n)$ の再帰式を得ます。

$\begin{eqnarray} &&\left(\prod_{m=1}^nc_m\right)\widehat{\alpha}({\bf z}_n)=p({\bf x}_n|{\bf z}_n)\sum_{{\bf z}_{n-1}}\left(\prod_{m=1}^{n-1}c_m\right)\widehat{\alpha}({\bf z}_{n-1})p({\bf z}_n|{\bf z}_{n-1})\\ &&\Leftrightarrow c_n\widehat{\alpha}({\bf z}_n)=p({\bf x}_n|{\bf z}_n)\sum_{{\bf z}_{n-1}}\widehat{\alpha}({\bf z}_{n-1})p({\bf z}_n|{\bf z}_{n-1})\\ &&\Leftrightarrow \widehat{\alpha}({\bf z}_n)=\frac{1}{c_n}p({\bf x}_n|{\bf z}_n)\sum_{{\bf z}_{n-1}}\widehat{\alpha}({\bf z}_{n-1})p({\bf z}_n|{\bf z}_{n-1})\tag{11} \end{eqnarray}$

ここで、 $\widehat{\alpha}({\bf z}_n)$ の計算に用いた前向きのメッセージパッシングの各段階で、
$c_n$ を計算し、記憶しておかなければならないことに注意が必要です。
この $c_n$ は $\widehat{\alpha}({\bf z}_n)$ の計算において、式 $(10)$ の右辺を正規化する係数なので、以下のように求められると思います。
一時的な変数として、 $\widetilde{\alpha}(z_{nk})$ を $z_{nk}=1$ の時の式 $(11)$ の右辺の分子として、定義します。

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

このとき、 $c_n$ は以下のようになります。

$\begin{eqnarray} c_n=\sum_{k=1}^K\widetilde{\alpha}(z_{nk})\tag{13} \end{eqnarray}$

求めた $\widetilde{\alpha}(z_{nk}),c_n$ を使って、 $\widehat{\alpha}(z_{nk})$ は次の式で書けます。

$\begin{eqnarray} \widehat{\alpha}(z_{nk})=\frac{\widetilde{\alpha}(z_{nk})}{c_n}\tag{14} \end{eqnarray}$

式 $(12),(13)$ だと $c_n(n\geqslant 2)$ は計算できますが、 $c_1$ は計算できない(？)ので、以下のようにすればよいと思います。
式 $(9)$ より、

$\begin{eqnarray} \widehat{\alpha}({\bf z}_1)=\frac{\alpha({\bf z}_1)}{c_1}\tag{15} \end{eqnarray}$

となります。
$\widehat{\alpha}({\bf z}_1)$ は正規化されているので、

$\begin{eqnarray} c_1&=&\sum_{{\bf z}_1}\alpha({\bf z}_1)\\ &=&\sum_{k=1}^K\alpha(z_{1k})\tag{16} \end{eqnarray}$

と求まります。

スケーリング - $\widehat{\beta}$

同様に、スケーリングを施した変数 $\widehat{\beta}({\bf z}_n)$ を以下のように定義することができます。

$\begin{eqnarray} \beta({\bf z}_n)=\left(\prod_{m=n+1}^Nc_m\right)\widehat{\beta}({\bf z}_n)\tag{17} \end{eqnarray}$

確率の乗法定理より、以下の式が成り立ちます。

$\begin{eqnarray} \prod_{m=n+1}^Nc_m=p({\bf x}_{n+1},\ldots,{\bf x}_N|{\bf x}_1,\ldots,{\bf x}_n)\tag{18} \end{eqnarray}$

式 $(18)$ が成り立つことを帰納法で示します。
$n=N-1$ の時、

$\begin{eqnarray} \prod_{m=N}^Nc_m&=&c_N\\ &=&p({\bf x}_N|{\bf x}_1,\ldots,{\bf x}_{N-1})\tag{19} \end{eqnarray}$

式 $(19)$ より、式 $(18)$ が成り立ちます。
$n=l$ の時、式 $(18)$ が成り立つとすると、以下の式が成り立ちます。

$\begin{eqnarray} \prod_{m=l+1}^Nc_m=p({\bf x}_{l+1},\ldots,{\bf x}_N|{\bf x}_1,\ldots,{\bf x}_l)\tag{20} \end{eqnarray}$

$\prod_{m=l}^Nc_m$ を計算します。

$\begin{eqnarray} \prod_{m=l}^Nc_m&=&\left(\prod_{m=l+1}^Nc_m\right)c_l\\ &=&p({\bf x}_{l+1},\ldots,{\bf x}_N|{\bf x}_1,\ldots,{\bf x}_l)p({\bf x}_l|{\bf x}_1,\ldots,{\bf x}_{l-1})\\ &=&p({\bf x}_l,\ldots,{\bf x}_N|{\bf x}_1,\ldots,{\bf x}_{l-1})\tag{21} \end{eqnarray}$

式 $(21)$ より、 $n=l-1$ の時、式 $(5)$ が成り立ちます。
以上より、式 $(18)$ が成り立つことが分かります。

式 $(17),(18)$ より、 $\beta({\bf z}_n)$ と $\widehat{\beta}({\bf z}_n)$ の関係式は次のように書くこともできます。

$\begin{eqnarray} &&\beta({\bf z}_n)=p({\bf x}_{n+1},\ldots,{\bf x}_N|{\bf x}_1,\ldots,{\bf x}_n)\widehat{\beta}({\bf z}_n)\\ &&\Leftrightarrow \widehat{\beta}({\bf z}_n)=\frac{p({\bf x}_{n+1},\ldots,{\bf x}_N|{\bf z}_n)}{p({\bf x}_{n+1},\ldots,{\bf x}_N|{\bf x}_1,\ldots,{\bf x}_n)}\tag{22} \end{eqnarray}$

式 $(22)$ より、 $\widehat{\beta}({\bf z}_n)$ は単に $2$ つの条件付き確率の比であるから、計算機の精度内に収まります。
※ $\widehat{\alpha}({\bf z}_n)$ の時と異なり、正規化されていない(正規化されていることを確認していない)ことに注意しましょう。

$\beta({\bf x}_n)$ の再帰式は、以下でした。

$\begin{eqnarray} \beta({\bf z}_n)=\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{23} \end{eqnarray}$

式 $(17)$ を式 $(23)$ に代入して、 $\widehat{\beta}({\bf z}_n)$ の再帰式を得ます。

$\begin{eqnarray} &&\left(\prod_{m=n+1}^Nc_m\right)\widehat{\beta}({\bf z}_n)=\sum_{{\bf z}_{n+1}}\left(\prod_{m=n+2}^Nc_m\right)\widehat{\beta}({\bf z}_{n+1})p({\bf x}_{n+1}|{\bf z}_{n+1})p({\bf z}_{n+1}|{\bf z}_n)\\ &&\Leftrightarrow c_{n+1}\widehat{\beta}({\bf z}_n)=\sum_{{\bf z}_{n+1}}\widehat{\beta}({\bf z}_{n+1})p({\bf x}_{n+1}|{\bf z}_{n+1})p({\bf z}_{n+1}|{\bf z}_n)\tag{24} \end{eqnarray}$

尤度関数

尤度関数 $p({\bf X})$ は、式 $(5)$ よりスケーリング係数 $c_n$ を利用して、以下のように書けます。

$\begin{eqnarray} p({\bf X})&=&p({\bf x}_1,\ldots,{\bf x}_N)\\ &=&\prod_{n=1}^Nc_n\tag{25} \end{eqnarray}$

$\gamma,\xi$ を $\widehat{\alpha},\widehat{\beta}$ で再定義

$\gamma({\bf z}_n),\xi({\bf z}_{n-1},{\bf z}_n)$ は $\widehat{\alpha}({\bf z}_n),\widehat{\beta}({\bf z}_n)$ を用いて以下のように書けます。

$\begin{eqnarray} \gamma({\bf z}_n)=\widehat{\alpha}({\bf z}_n)\widehat{\beta}({\bf z}_n)\tag{26} \end{eqnarray}$

$\begin{eqnarray} \xi({\bf z}_{n-1},{\bf z}_n)=\widehat{\alpha}({\bf z}_n)p({\bf x}_n|{\bf z}_n)p({\bf z}_n|{\bf z}_{n-1})\widehat{\beta}({\bf z}_n)\tag{27} \end{eqnarray}$

式 $(26),(27)$ の導出については、PRML演習問題 13.15(標準)をご覧ください。

最後に

本記事は、私自身で導いた式もいくつか(式 $(12)$ ～ $(16)$ )あるので、注意してお読みください。

偉人の名言

f:id:olj611:20210926134752p:plain:h300
背伸びして視野をひろげているうち、
背が伸びてしまうこともあり得る。
それが人生の面白さである。
城山三郎

参考文献

パターン認識と機械学習下巻 p345-p347

動画

なし

機械学習基礎理論独習

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

スケーリング係数 - フォワード-バックワードアルゴリズム(α-βアルゴリズム)

はじめに

$\alpha$ - $\beta$ アルゴリズムの数値計算時の問題点

スケーリング - $\widehat{\alpha}$

スケーリング - $\widehat{\beta}$

尤度関数

$\gamma,\xi$ を $\widehat{\alpha},\widehat{\beta}$ で再定義

最後に

偉人の名言

参考文献

動画

はじめに

-アルゴリズムの数値計算時の問題点

スケーリング -

スケーリング -

尤度関数

をで再定義

最後に

偉人の名言

参考文献

動画

$\alpha$ - $\beta$ アルゴリズムの数値計算時の問題点

スケーリング - $\widehat{\alpha}$

スケーリング - $\widehat{\beta}$

$\gamma,\xi$ を $\widehat{\alpha},\widehat{\beta}$ で再定義