「続・わかりやすいパターン認識」の8章「隠れマルコフモデル」の問題点 2つ #ぞくパタ

【追記】
本記事の内容は公式の正誤表ですでに修正済みです。第1版第4刷以降が出ることがあれば、そちらに反映されていることが期待されます。

続・わかりやすい　パターン認識－教師なし学習入門－ | Ohmsha

【／追記】

昨日はぞくパタ読書会にのこのこ行ってきた。主催者、発表者、参加者の皆さん、会場を提供してくださったドワンゴさんに感謝。

続・わかりやすいパターン認識―教師なし学習入門―

作者: 石井健一郎,上田修功
出版社/メーカー: オーム社
発売日: 2014/08/26
メディア: 単行本（ソフトカバー）
この商品を含むブログ (2件) を見る

「続・わかりやすいパターン認識」(以降「ぞくパタ」)の8章「隠れマルコフモデル」を読んだわけだが、この章には理解のさまたげになりうる問題点が大きく2つあると感じた。

自明ではない条件付き独立性を、言及なく使っている
ビタービアルゴリズムで求める ψ_t(j) の定義が明記されていない

前者は読書会でも突っ込んだのだが、残念ながらピンときている人はいない様子だった？　式変形を追えばそこで詰まると思うのだが……いや、全員まったく問題なく式変形できた可能性もまだ残っている。

まあそれはともかく。簡単に問題点を整理・フォローしてみる。

自明ではない条件付き独立性を、言及なく使っている

書籍の中で対象となるのは次の番号の式。

(8.6)
(8.10) 前向きアルゴリズム更新式
(8.16) 後ろ向きアルゴリズム更新式
(8.24) ビタービ更新式
(8.40) バウム・ウェルチのξ(正規化前)

見ればわかるが「隠れマルコフで重要な式のほぼ全て」である。
それもそのはず、そもそも隠れマルコフの仮定はまさにその条件付き独立性を得るため導入されており、その条件付き独立性のおかげでこのモデルは計算できるようになっているのだから。

ぞくパタはグラフィカルモデルをやってなく、グラフィカルモデルなしでモデルに含まれる条件付き独立性を導出するのは面倒なので、ネグったのだろう。そこまでは理解できるのだが、条件付き独立性を使っていることを言いもしないのはさすがにまずい。

「この式変形では、隠れマルコフの仮定から導かれる〜という条件付き独立性を用いている」と一言あるだけでも、無条件で成立するものではないと知れるし、ちゃんと式の導出を追っかけたいと思った人は条件付き独立性について調べ考える機会が与えられる。
今の状態では、隠れマルコフの仮定がいかにして強力な枠組みを生み出しているのか、その様子を目の当たりにすることもできない。

もったいない。

確かに何もかも理解するのは難しいし、そんな必要なんてないという意見もあるだろう。
が、捨てる順番的には、確率モデルで一番大切な条件付き独立性は最後ちゃうかなあ、と個人的には強く思う。

というわけで、使われている条件付き独立性を紹介し、それを使って実際に式変形する。
式変形は全部ではなくあえて 1つだけにしておくので、興味があれば残りはぜひ自力で。

まずは条件付き独立性。
つか一応「条件付き独立性」って何ってところからやっとくか。
ぞくパタ 7ページに書いてあるのをそのまま引くと、「 S が与えられた下で事象 X, Y は条件付き独立である」とは次のいずれかが成り立つこと。

$P(X|Y,S)=P(X|S)$
$P(Y|X,S)=P(Y|S)$
$P(X,Y|S)=P(X|S)P(Y|S)$

ぞくパタでは「事象」になっているが「確率変数」に対しても同様に定義する。

そして「S が与えられた下で X, Y は条件付き独立である」ことを $X\perp Y | S$ と書くことにする。
本来なら条件付き独立性の ⊥ の縦棒は2本なのだが、はてダの環境では出ないので1本にさせてもらってる。手抜きですまん。

さて、隠れマルコフモデルでは以下のような条件付き独立性が成立する。記号はぞくパタのままなので、notation は省略。

(1) $x_1,\cdots,x_t\;\perp\;x_{t+1},\cdots,x_n\;|\;s_t$
(2) $x_1,\cdots,x_t \;\perp\;s_{t+1}\;|\;s_t$
(3) $x_1,\cdots,x_{t-1},s_{t-1} \;\perp\; x_t \;|\;s_t$

他にもあるのだが、とりあえず。
導出は……省略（苦笑）。上にも書いた通り、隠れマルコフの仮定から導出できなくないのだが、めんどくさすぎる。
ここでの主眼は「条件付き独立性を示す」ことではなく「条件付き独立性を使っていることを言う」なので、いいのだ（開き直り）。

ちなみにグラフィカルモデルは、そのめんどくさすぎる条件付き独立性の導出を「見ただけでわかる」ようにしてくれる強力なツールである。
興味があれば PRML 8章などをどうぞ。

さて条件付き独立性を使って上の式の 1つをやっつけよう。前向きアルゴリズム更新式 (8.10) あたりでいいか。

$\alpha_t(j)\;=\;\left\{\sum_{i=1}^c\alpha_{t-1}(i)\;a_{ij}\right\}\;b(\omega_j,x_t)$ 　 (8.10)

a とかαとかをもとの確率になおす。

$P(x_1,x_2,\cdots,x_t,s_t=\omega_j)\\ \;=\;\left\{\sum_{i=1}^c P(x_1,x_2,\cdots,x_{t-1},s_{t-1}=\omega_i) \;P(s_t=\omega_j|s_{t-1}=\omega_i) \right\}\;P(x_t|s_t=\omega_j)$

長い。

$x_1,x_2,\cdots,x_{t-1}$ はセットでしか動かさないので、それを ${\bf x}_1^{t-1}$ と書くことにする。
また $s_t=\omega_j$ や $s_{t-1}=\omega_i$ は常に値が指定されているものとして、それぞれ単に $s_t, s_{t-1}$ と記す。
それだけだと右辺の sum のインデックス i の指すものが行方不明になるので、sum は s_{t-1} についてとる形で表す。

$P({\bf x}_1^{t-1},x_t,s_t)\;=\;\left\{\sum_{s_{t-1}} P({\bf x}_1^{t-1},s_{t-1}) \;P(s_t|s_{t-1}) \right\}\;P(x_t|s_t)$

見通しが良くなった。これを示す。
確率の加法定理から

$P({\bf x}_1^{t-1},x_t,s_t)\;=\;\sum_{s_{t-1}} P({\bf x}_1^{t-1},x_t,s_t,s_{t-1})$

である。s_{t-1} を増やして消しただけ。
右辺の sum の中身を、乗法定理を2回使って変形する。

$P({\bf x}_1^{t-1},x_t,s_t,s_{t-1})$
$=P(x_t|{\bf x}_1^{t-1},s_t,s_{t-1})\;P({\bf x}_1^{t-1},s_t,s_{t-1})$
$=P(x_t|{\bf x}_1^{t-1},s_t,s_{t-1})\;P(s_t|{\bf x}_1^{t-1},s_{t-1})\;P({\bf x}_1^{t-1},s_{t-1})$

$\alpha_{t-1}(i)=P({\bf x}_1^{t-1},s_{t-1})$ なので、分解の3項目は片付いた。
（ここまでは乗法・加法定理しか使っていないので、隠れマルコフでなくても成立する）

1項目は上の条件付き独立性の (3) $x_1,\cdots,x_{t-1},s_{t-1}\;\perp\;x_t\;|\;s_t$ を使うと、

$P(x_t|{\bf x}_1^{t-1},s_t,s_{t-1})=P(x_t|,s_t)$

となり、これは $b(\omega_j,x_t)$ である。

2項目は同じく条件付き独立性 (2) $x_1,\cdots,x_t\;\perp\;s_{t+1}\;|\;s_t$ から

$P(s_t|{\bf x}_1^{t-1},s_{t-1})=P(s_t|s_{t-1})$

となり、 $a_{ij}$ である。これで (8.10) が示された。

ここで一番大事なことは、「前向きアルゴリズムやビタービを導出するには隠れマルコフの仮定がちゃんと必要だった」とわかること。
これらのアルゴリズムは隠れマルコフ以外でも出てくるので、そのときになんで使えるかもこの辺りを理解していれば納得しやすい。

ビタービアルゴリズムで求める ψ_t(j) の定義が明記されていない

ビタービは、ψ_t(j) という値を再帰的に求めることで状態の系列を推定するアルゴリズムだが、その ψ_t(j) について、ぞくパタでは次のように説明している。

「ある時点 t で状態 ω_j に到達し、かつ x_t が観測される確率を考える。その確率は、1時点前の状態が ω_1〜ω_c のいずれであるかによって異なり、c 種存在する。その中で最大となる確率を ψ_t(j) で表す」

正直、この説明では ψ_t(j) がなんなのかわからなかった。
ψ_t(j) が何かわからなくても、(8.24) 式では漸化式が与えられるので、それを認めれば計算はできる。
が、その ψ_t(j) で最適な状態の系列が推定できることはなぜわかるのだろう？

ψ_t(j) が定義されていれば、漸化式はそこから導ける(ここでも条件付き独立性を使う)し、それを求められれば最適系列を与えることもわかる。問題解決。
というわけで定義をしよう。*1

$\psi_t(j)\;:=\;\max_{s_1,\cdots,s_{t-1}}\;P(x_1,\cdots,x_t,s_1,\cdots,s_{t-1},s_t=\omega_j)$

ちなみに Ψ_t(j) の方は、この最大値を与えるときの $s_{t-1}=\omega_i$ のインデックス i である。このことをふまえると、Ψ を逆向きにたどると最適系列を得られることも間違いなく理解できる。

条件付き独立性についてはグラフィカルモデルをやってないという同情点があったが、こちらは単なる定義の明記漏れである。
~~次版があるならぜひ改善してほしい……と思うが、話を聞くとそういったフィードバックは受け付けられにくそうな雰囲気なので、期待はしない。~~

次回読書会参加は……ツッコミの反応イマイチだったし、11章のディリクレ過程と、あともしかして行くとしたら12章かなあ。
teramonagi さんと sfchaos さんはガチツッコミしてもいいと聞いているのでｗ

*1:この定義を見ると、本の「説明」が実はまずいということもわかる