「パターン認識と機械学習」の読書メモ（第1章）

第1章　序論

正誤表
http://ibisforest.org/index.php?PRML/errata1

1.5　決定理論

1.5.1 誤識別率の最小化

誤りの確率が最小になるのは，事後確率$p(C_k | x)$が最大のクラスに割り当てるとき．

1.5.2 期待損失の最小化

多くの応用では，誤りの種類によって重要度が異なる．そこで，より深刻な誤りを犯した場合の値が大きくなるような損失関数（コスト関数）を考える．損失関数の代わりに，損失行列$L_{kj}$と各事象の同時確率分布の積の積分値（損失の平均値）を最小化する．

1.5.3 棄却オプション

事後確率にしきい値を設けて，それより小さい場合（クラス分けがあいまいな場合）は判断を放棄する．

1.5.4 推論と決定

決定問題を解く3つのアプローチ．

1. クラスの条件付き密度$p(x|C_k)$を決める推論問題を解く．ベイズの定理からクラス事後確率$p(C_k|x)$を求める．入力の分布もモデル化するので，モデルからのサンプリングによって入力空間で人口データ点を生成できる．生成モデル．

2. 事後確率$p(C_k|x)$を決める．識別モデル．

3. 直接識別する．識別モデル．

計算コストは1>2>3．
単にクラス分類したいだけなら1は計算資源の無駄．
ただ，事後確率を計算したくなる理由は複数考えられる．

1.5.5 回帰のための損失関数

1.6　情報理論

ある離散確率変数$x$．
情報量$h(x)$：$x$の値を得た際の「驚きの度合い」．めったにない事象が起きるとそれだけ多くの情報が得られそうなので，情報量は確率分布$p(x)$に依存していると考えられる．

2つの独立な事象$x$と$y$を観測したときの情報量は，それぞれを別々に観測したときの和になる．
$h(x,y) = h(x) + h(y)$
また，その事象が起きる確率は
$p(x,y) = p(x) p(y)$
したがって，$h(x)$は$p(x)$の対数となる．

h(x) = - \log_2 p(x) 
\tag{1.92}

$p(x)$は$0$から$1$の値を取るので，その対数にマイナス記号を付けることで情報量は$0$以上の値を取り，低い確率で起きる事象ほど大きくなる．対数の底は情報理論で一般的に使われている底2を採用している．

ある送信者が確率変数の値を受信者に送る場合，その情報の平均量は確率分布$p(x)$に関して期待値を取ったものとなる．

H[x] = - \sum_x p(x) \log_2 p(x)
\tag{1.93}

これは確率変数$x$のエントロピーと呼ばれる．¹

確率変数$x$が$8$個の可能な状態を取る場合を考える．
$p(x)$が等確率のとき，$x$の値を受信者に伝えるためには$\log_2 8 = 3$ビットの長さのメッセージを送る必要があり，エントロピーは
$H[x] = - 8 \times \frac{1}{8} \log_2 \frac{1}{8} = 3$ビット
確率分布$p(x)$が非一様な場合のエントロピーはこれより小さくなる．乱雑であるほどエントロピーは大きい．

変数$x$がどの状態にあるかを受信者に伝える場合，単純には$3$ビットの数を使えばよい．ただし，確率が非一様の場合には，よく起きる事象に短い符号を使い，あまり起きない事象に長い符号を使うことに寄って，符号長の平均を短くすることができる．実は，最短符号長は確率変数のエントロピーに等しくなる（ノイズなし符号化定理）．

以降，エントロピーの定義に自然対数を使い，その単位にビットの代わりに「ナット」を使う．ビットと$\ln 2$倍だけ異なる．

エントロピーは物理学に起源を発する．熱平衡状態の文脈で導入され，統計力学の発展とともに乱雑さを測る尺度という解釈に至った．

$N$個の同じ物体がたくさんの箱の中に分けられている状況を考える．
$i$番目の箱に$n_i$個の物体があるとする．
$N$個の物体を箱に入れる「場合の数」$W$は，
$N$個の物体を入れる順番が$N!$通りで，それぞれの箱へ入れた順番を区別しないとすると$i$番目の箱には$n_i!$通りの順番付けの方法があるので，

W = \dfrac{N!}{\prod_i n_i!} 
\tag{1.94}

これを多重度（multiplicity）と呼ぶ．エントロピーは多重度の対数を適当に定数倍したものとして定義される．

H = \frac{1}{N} \ln W
= \frac{1}{N} \ln N! - \frac{1}{N} \sum_i \ln n_i!
\tag{1.95}

$n_i/N$を一定に保ったまま$N \to \infty$という極限を考えて，スターリングの近似式を使うと

H 
= - \lim_{N\to \infty} \sum_i \left( \frac{n_i}{N} \right) \ln \left( \frac{n_i}{N}\right)
= - \sum_i p_i \ln p_i
\tag{1.97}

ここで，$p_i = \lim_{N\to\infty} (n_i/N)$は物体が$i$番目の箱に割り当てられる確率．
箱の中の物体の特定の状態：ミクロ状態
$n_i/N$で表される物体の占有数の分布：マクロ状態
多重度$W$：マクロ状態の重み

箱は離散確率変数$X$の状態$x_i$と解釈できる．確率変数$X$のエントロピーは

H[p] 
= - \sum_i p(x_i) \ln p(x_i) 
\tag{1.98} 

図1.30：幅広い分布のほうがエントロピーは大きい．デルタ関数的に分布する場合にエントロピーは最小値0となる．

最大のエントロピーを持つ確率分布は，ラグランジュ乗数法を使って$H$を最大化することで求まる．
その結果，$p(x_i)$がすべて等しいとき（変数の取りうる状態が等確率であるとき）であることがわかる．

エントロピーを連続変数$x$の分布$p(x)$に拡張．
$x$を等間隔の区間$\Delta$に分ける．平均値の定理より

\int^{(i+1)\Delta}_{i\Delta} p(x) dx
= p(x_i) \Delta
\tag{1.101}

となる値$x_i$が存在する．
$i$番目の区間に入る任意の値$x$に値$x_i$を割り当てると，$x_i$の値を観測する確率は$p(x_i)\Delta$．
このときエントロピーは

\begin{align}
H_\Delta
&= - \sum_i p(x_i) \Delta \ln [p(x_i) \Delta] \\
&= - \sum_i p(x_i) \Delta [\ln p(x_i) + \ln \Delta] \\
&= - \sum_i p(x_i) \Delta \ln p(x_i) -  \ln \Delta \sum_i p(x_i) \Delta \\
&= - \sum_i p(x_i) \Delta \ln p(x_i) -  \ln \Delta  
\end{align}
\tag{1.102}

右辺の第二項を無視して$\Delta \to 0$の極限を取ると，²

\lim_{\Delta \to 0} \left[ - \sum_i p(x_i) \Delta \ln p(x_i) \right] 
= - \int p(x) \ln p(x) dx
\tag{1.104}

右辺の量は微分エントロピーと呼ばれる．

微分エントロピーが最大になるときを同様にラグランジュ乗数法で求めると，$p(x)$がガウス分布にしたがうときであることが導かれる．

ガウス分布の微分エントロピーは，

H[x]
= \frac{1}{2} \left[ 1 + \ln (2 \pi \sigma^2) \right]
\tag{1.110}

エントロピーは分布の幅が広くなるにつれて大きくなることがわかる．
また，微分エントロピーは負になりうることもわかる．

$x$と$y$の組を取って同時分布$p(x,y)$を考える．
$x$が既知の時，$y$を特定するのに必要な付加的な情報は$- \ln p(y|x)$．
したがって，$y$を特定するための付加的な情報量の平均は

H[y|x]
= - \int \int p(y,x) \ln p(y|x) dy dx
\tag{1.111}

$x$に対する$y$の条件付きエントロピー．

\begin{align}
H[x,y]
&= - \int \int p(y,x) \ln p(y,x) dy dx \\
&= - \int \int p(y,x) \ln [p(y|x) p(x)] dy dx \\
&= - \int \int p(y,x) \ln p(y|x) dy dx - \int \int p(y,x) \ln p(x) dy dx \\
&= H[y|x] - \int \int p(y,x) dy \ln p(x) dx \\
&= H[y|x] - \int p(x) \ln p(x) dx \\
&= H[y|x] + H[x] 
\tag{1.112}
\end{align}

であるから³，$x$と$y$を記述するのに必要な情報量は，$x$だけを記述するための情報量と，$x$が与えられたときに$y$を記述するための付加的な情報量との和で与えられる．

1.6.1　相対エントロピーと相互情報量

ある未知の分布$p(x)$を近似的に$q(x)$でモデル化．
真の分布$p(x)$の代わりに$q(x)$を使うと$x$の値を特定するのに必要な追加情報量の平均は

{\rm KL}(p||q) 
= - \int p(x) \ln q(x) dx - \left[ - \int p(x) \ln p(x) \right]
= - \int p(x) \ln \frac{q(x)}{p(x)} dx
\tag{1.113}

分布$p(x)$と$q(x)$の間の相対エントロピーあるいはKullback-Leibler (KL)ダイバージェンスと呼ばれる．

KL$(p||q) \geq 0$を満たし，等式が成り立つ時は$p(x) = q(x)$のときに限る（Jensenの不等式を用いて示すことができる）．

データ圧縮と密度推定（未知の確率分布のモデル化の問題）は密接に関係しており，最も効率的な圧縮は真の分布を知っているときに達成される．真の分布と異なるときは非効率的な符号化になり，追加情報量は平均して2つの分布の間のKLダイバージェンスと等しくなる．

データが未知の分布$p(x)$から生成されるとき，可変なパラメータ$\theta$を持つパラメトリック分布$q(x|\theta)$で近似するとする．$\theta$を決める一つの方法は，$p(x)$と$q(x|\theta)$の間のKLダイバージェンスを$\theta$について最小化すること．$p(x)$から得られた有限個の訓練データ{$x_i$} $(i=1,\cdots,N)$があるので，$p(x)$に関する期待値はその有限和で近似できて，(1.35)式から

{\rm KL}(p||q)
\simeq \frac{1}{N} \sum_{n=1}^N \left[ \ln q(x_n | \theta) + \ln p(x_n) \right] 
\tag{1.119}

右辺第二項は$\theta$と独立．最初の項は負の対数尤度．KLダイバージェンスの最小化は尤度の最大化と等価であることがわかる．

2つの変数集合$x$と$y$がある．これらが独立に近いかどうかを知るために，同時分布と周辺分布の積の間のKLダイバージェンスを使う．

I[x,y]
\equiv {\rm KL} \left( p(x,y) || p(x) p(y) \right)
= - \int\int p(x,y) \ln \left( \frac{p(x)p(y)}{p(x,y)} \right) dx dy

これは変数$x$と$y$の間の相互情報量と呼ばれる．条件付きエントロピーとの関係は

I[x,y]
= H[x] - H[x|y] = H[y] - H[y|x]

つまり，相互情報量は，$y$の値を知ることに寄って，$x$に関する不確実性がどれだけ減少するかを表す．

1. なお，$\displaystyle \lim_{p\to0} p \log p = 0$なので，$p(x)=0$の場合は$p \log p = 0$． ↩

2. 右辺第二項は離散と連続の場合のエントロピー差．連続変数を厳密に規定するのに無限のビット数を必要とするところから来ているとか． ↩

3. 演習1.37． ↩