ベルヌイモデルとベルヌイモデルの尤度に対する情報量
ベルヌイモデル \(P_{Ber}\)
$$\begin{array}{rcl} P(X|\theta) = \begin{cases} \displaystyle \theta & \,: \left(X=1\right)\\ \displaystyle 1-\theta & \,: \left(X=0\right)\\ \end{cases}\\ \displaystyle P_{Ber}=\left\{P(X|\theta)\,:(0\leq\theta\leq1)\right\}\\ \end{array}$$\(x^n\)を\(P_{Ber}\)で最短長の符号化をすることを考える
データ列\(x^n\)が与えられた時の生成確率\(P(x^n|\theta)\)を\(\theta\)の凾数とみなすと $$\begin{array}{rcl} \displaystyle L(\theta|x^n)&=&P(x^n|\theta) \end{array}$$ としてこれを尤度(likelihood)と呼ぶ．ベルヌイモデルの尤度に対する情報量
\(x^n\)の1の発生回数を\(m\)とすると0の発生回数は\(n-m\)となるので最尤推定値(maximum likelihood estimator)は $$\begin{array}{rcl} \displaystyle L(\theta|x^n)&=&\theta^{m}(1-\theta)^{(n-m)}\\ \end{array}$$ 情報量(=符号長)を考えると $$\begin{array}{rcl} \displaystyle -\log_{2}{\left(L(\theta|x^n)\right)}&=&-\log_{2}{\left(\theta^{m}(1-\theta)^{(n-m)}\right)}\\ &=&\displaystyle -\log_{2}{\left(\theta^{m}\right)}-\log_{2}{\left((1-\theta)^{(n-m)}\right)}\\ &=&\displaystyle -m\log_{2}{\left(\theta\right)}-(n-m)\log_{2}{\left(1-\theta\right)}\\ \end{array}$$確率Pで発生しているデータ系列を確率Qに基づく符号化した際のKullback-Leiblerダイバージェンス
例:確率Pで発生しているデータ系列を確率Qに基づく符号化した際のKullback-Leiblerダイバージェンス\(D_n\)
| \(y_1\) | \(y_2\) | \(x^2\) \(=y_1y_2\) |
\(P(x^2)\) | \(Q(x^2)\) | \(Q'(x^2)\) | \(Q''(x^2)\) |
|---|---|---|---|---|---|---|
| 0 | 0 | 00 | \(\frac{1}{8}\) | \(\frac{1}{8}\) | \(\frac{1}{2}\) | \(\frac{1}{4}\) |
| 0 | 1 | 01 | \(\frac{1}{8}\) | \(\frac{1}{8}\) | \(\frac{1}{4}\) | \(\frac{1}{4}\) |
| 1 | 0 | 10 | \(\frac{1}{4}\) | \(\frac{1}{4}\) | \(\frac{1}{8}\) | \(\frac{1}{4}\) |
| 1 | 1 | 11 | \(\frac{1}{2}\) | \(\frac{1}{2}\) | \(\frac{1}{8}\) | \(\frac{1}{4}\) |
\(Q(x^2)\)でのダイバージェンス
$$\begin{array}{rcl} D_n(P\parallel Q)&=&E^{n}_{P}\left[\log_2{\frac{P(X^n)}{Q(X^n)}}\right]\\ &=&\displaystyle \sum_{x^2\in\chi^2} P(x^2)\log_2{\frac{P(x^2)}{Q(x^2)}}\\ &=&\frac{1}{8} \times \log_2{\frac{\frac{1}{8}}{\frac{1}{8}}} +\frac{1}{8} \times \log_2{\frac{\frac{1}{8}}{\frac{1}{8}}} +\frac{1}{4} \times \log_2{\frac{\frac{1}{4}}{\frac{1}{4}}} +\frac{1}{2} \times \log_2{\frac{\frac{1}{2}}{\frac{1}{2}}}\\ &=&\frac{1}{8} \times \log_2{1} +\frac{1}{8} \times \log_2{1} +\frac{1}{4} \times \log_2{1} +\frac{1}{2} \times \log_2{1}\\ &=&\frac{1}{8} \times 0 +\frac{1}{8} \times 0 +\frac{1}{4} \times 0 +\frac{1}{2} \times 0\\ &=&0+0+0+0\\ &=&0 \end{array}$$\(Q'(x^2)\)でのダイバージェンス
$$\begin{array}{rcl} D_n(P\parallel Q')&=&E^{n}_{P}\left[\log_2{\frac{P(X^n)}{Q'(X^n)}}\right]\\ &=&\displaystyle \sum_{x^2\in\chi^2} P(x^2)\log_2{\frac{P(x^2)}{Q'(x^2)}}\\ &=&\frac{1}{8} \times \log_2{\frac{\frac{1}{8}}{\frac{1}{2}}} +\frac{1}{8} \times \log_2{\frac{\frac{1}{8}}{\frac{1}{4}}} +\frac{1}{4} \times \log_2{\frac{\frac{1}{4}}{\frac{1}{8}}} +\frac{1}{2} \times \log_2{\frac{\frac{1}{2}}{\frac{1}{8}}} \\ &=&\frac{1}{8} \times \log_2{\frac{1}{4}} +\frac{1}{8} \times \log_2{\frac{1}{2}} +\frac{1}{4} \times \log_2{2} +\frac{1}{2} \times \log_2{4} \\ &=&\frac{1}{8} \times -2 +\frac{1}{8} \times -1 +\frac{1}{4} \times 1 +\frac{1}{2} \times 2 \\ &=&-\frac{1}{4}-\frac{1}{8}+\frac{1}{4}+1\\ &=&\frac{7}{8}=0.875 \end{array}$$\(Q''(x^2)\)でのダイバージェンス
$$\begin{array}{rcl} D_n(P\parallel Q'')&=&E^{n}_{P}\left[\log_2{\frac{P(X^n)}{Q''(X^n)}}\right]\\ &=&\displaystyle \sum_{x^2\in\chi^2} P(x^2)\log_2{\frac{P(x^2)}{Q''(x^2)}}\\ &=&\frac{1}{8} \times \log_2{\frac{\frac{1}{8}}{\frac{1}{4}}} +\frac{1}{8} \times \log_2{\frac{\frac{1}{8}}{\frac{1}{4}}} +\frac{1}{4} \times \log_2{\frac{\frac{1}{4}}{\frac{1}{4}}} +\frac{1}{2} \times \log_2{\frac{\frac{1}{2}}{\frac{1}{4}}} \\ &=&\frac{1}{8} \times \log_2{\frac{1}{2}} +\frac{1}{8} \times \log_2{\frac{1}{2}} +\frac{1}{4} \times \log_2{1} +\frac{1}{2} \times \log_2{2} \\ &=&\frac{1}{8} \times -1 +\frac{1}{8} \times -1 +\frac{1}{4} \times 0 +\frac{1}{2} \times 1 \\ &=&-\frac{1}{8}-\frac{1}{8}+0+\frac{1}{2}\\ &=&\frac{1}{4}=0.25 \end{array}$$KLダイバージェンスの下限
\(\log_{\mathrm{e}}{x}\leq(x-1)\)の証明
$$\begin{array}{rcl} f(x)&=&x-1-\log_{\mathrm{e}}{x}\\ f'(x)&=&\frac{x-1}{x}\\ f''(x)&=&\frac{1}{x^2}\\ f'=0&は&x=1\\ \end{array}$$ よって\(f''(1)\gt0\)より\(f\)は\(x=1\)で極小であり，また \(x\lt1\) で常に\(f'\lt0\) 及び \(x\gt1\) で常に\(f'\gt0\) なので最小でもある．\(f(1)=0\)なので\(f\geq0\)である． $$\begin{array}{rcl} x-1-\log_{\mathrm{e}}{x}&\geq&0\\ -\log_{\mathrm{e}}{x}&\geq&-x+1=-(x-1)\\ \log_{\mathrm{e}}{x}&\leq&(x-1)\\ \end{array}$$
\(\log_{\mathrm{e}}{x}\leq(x-1)\)の底の変換等の式変形
$$\begin{array}{rcl} \log_{\mathrm{e}}{x}&\leq&(x-1)\\ &\leq&-(1-x)\\ -\log_{\mathrm{e}}{x}&\geq&(1-x)\\ \log_{\mathrm{e}}{\frac{1}{x}}&\geq&(1-x)\\ \frac{\log_2{\frac{1}{x}}}{\log_2{\mathrm{e}}}&\geq&(1-x)\\ \log_2{\frac{1}{x}}&\geq&(\log_2{\mathrm{e}})(1-x)\\ \end{array}$$\(D_n(P\parallel Q)\)の下限
$$\begin{array}{rcl} \log_2{\frac{1}{x}}&\geq&(\log_2{\mathrm{e}})(1-x)\\ \log_2{\frac{1}{\frac{Q(x^n)}{P(x^n)}}}&\geq&(\log_2{\mathrm{e}})\left\{1-\frac{Q(x^n)}{P(x^n)}\right\}&x=\frac{Q(x^n)}{P(x^n)}として代入\\ \log_2{\frac{P(x^n)}{Q(x^n)}}&\geq&(\log_2{\mathrm{e}})\left\{1-\frac{Q(x^n)}{P(x^n)}\right\}\\ E^{n}_{P}\left[\log_2{\frac{P(X^n)}{Q(X^n)}}\right]&\geq&E^{n}_{P}\left[(\log_2{\mathrm{e}})\left\{1-\frac{Q(X^n)}{P(X^n)}\right\}\right]&両辺期待値を取る\\ D_n(P\parallel Q)&\geq&E^{n}_{P}\left[(\log_2{\mathrm{e}})\left\{1-\frac{Q(X^n)}{P(X^n)}\right\}\right]\\ &\geq&(\log_2{\mathrm{e}})E^{n}_{P}\left[1-\frac{Q(X^n)}{P(X^n)}\right]&E[cX]=cE[X]\\ &\geq&\displaystyle (\log_2{\mathrm{e}})\left[\left\{1-\frac{Q(x^m)}{P(x^m)}\right\}P(x^m)+\left\{1-\frac{Q(x^n_2)}{P(x^n_2)}\right\}P(x^n_2)+\dotsb\right]\\ &\geq&\displaystyle (\log_2{\mathrm{e}})\left[\left\{P(x^m)-Q(x^m)\right\}+\left\{P(x^n_2)-Q(x^n_2)\right\}+\dotsb\right]\\ &\geq&\displaystyle (\log_2{\mathrm{e}})\left[\left\{P(x^m)+P(x^n_2)+\dotsb\right\}-\left\{Q(x^m)+Q(x^n_2)+\dotsb\right\}\right]\\ &\geq&\displaystyle (\log_2{\mathrm{e}})\left\{\sum_{X^n}P(x^n)-\sum_{X^n}Q(x^n)\right\}\\ &\geq&\displaystyle (\log_2{\mathrm{e}})\left\{1-\sum_{X^n}Q(x^n)\right\}&\displaystyle \sum_{X^n}P(x^n)=1\\ &\geq&0&\displaystyle \sum_{X^n}Q(x^n)=1のときは0\\ \end{array}$$平均符号長の下限(エントロピー, Kullback-Leiblerダイバージェンス)
符号長(\(l(x^n)\))がShannon情報量(\(-\log_2{P(x^n)}\))と等しい場合(確率\(P(x^n)\)に基づく符号化(P-based coding))
$$\begin{array}{rcl} \mathcal{l}(x^n) &=& -\log_2{P(x^n)} \\ -\mathcal{l}(x^n) &=&\log_2{P(x^n)}\\ 2^{-\mathcal{l}(x^n)} &=&2^{\log_2{P(x^n)}}\\ &=&P(x^n)\\ P(x^n) &=&2^{-\mathcal{l}(x^n)}\\ \displaystyle \sum_{x^n \in \chi^n}P(x^n) &\leq& 1&\quad\dotso P(x^n)は確率質量凾数なので総和は1,\;P(x^n)を劣確率凾数とするケースを考える場合は総和は1以下\\ \displaystyle \sum_{x^n \in \chi^n}2^{-\mathcal{l}(x^n)}&\leq&1&\quad\dotso 2^{-\mathcal{l}(x^n)}=P(x^n)なのでやはり総和は1,\;P(x^n)を劣確率凾数とするケースを考える場合は総和は1以下\\ \end{array}$$ 劣確率凾数は \(P(x)\geq0\) の条件は確率(質量)凾数と同じで，\(\sum P(x) \leq 1\)となる凾数．符号長の期待値とその下限
$$\begin{array}{rcl} E^{n}_{P}\left[\mathcal{l}(X^n)\right]&\geq&H_n(P)&\quad\dotso 符号長の期待値・平均符号長の下限\\ H_n(P)&\overset{\mathrm{def}}{=}& E^{n}_{P}\left[-\log_2{P(X^n)}\right]&\quad\dotso 確率P(x^n)に基づく符号化の長さであることが条件\,\mathcal{l}(X^n)=-\log_2{P(X^n)}\\ \end{array}$$ \(H_n(P)\)をエントロピー(entropy)と呼ぶ．確率Pで発生しているデータ系列を確率Qに基づく符号化した場合の平均符号長
$$\begin{array}{rcl} \displaystyle \log_2{P(x^n)}-\log_2{P(x^n)} &=&\displaystyle \log_2{Q(x^n)}-\log_2{Q(x^n)}\\ \displaystyle -\log_2{Q(x^n)}&=&-\log_2{P(x^n)}+\log_2{P(x^n)}-\log_2{Q(x^n)}\\ &=&\displaystyle -\log_2{P(x^n)}+\log_2{\frac{P(x^n)}{Q(x^n)}}\\ \displaystyle E^{n}_{P}\left[-\log_2{Q(X^n)}\right] &=&\displaystyle E^{n}_{P}\left[-\log_2{P(X^n)}\right]+E^{n}_{P}\left[\log_2{\frac{P(X^n)}{Q(X^n)}}\right]\\ &=&\displaystyle H_n(P)+D_n(P\parallel Q)\\ D_n(P\parallel Q)&\overset{\mathrm{def}}{=}&E^{n}_{P}\left[\log_2{\frac{P(X^n)}{Q(X^n)}}\right]\\ \end{array}$$ \(D_n(P\parallel Q)\)をKullback-Leiblerダイバージェンス(Kullback-Leibler divergence)と呼ぶ．χ^n上の確率質量凾数P(x^n)から求める符号長(符号長の期待値, 平均符号長)
\(\chi^n\)上の確率質量凾数\(P(x^n)\)から求める符号長
$$\begin{array}{rl} I(x^n)=\lceil -\log_2{P(x^n)} \rceil &\quad\dotso \chi^n上の確率質量凾数P(x^n)から求める符号長(I:\chi^n \rightarrow \mathbb{R}^{+})\\ \end{array}$$符号長の期待値
$$\begin{array}{rl} E\left[\mathcal{l}(x^n)\right]=\displaystyle \sum_{x^n\in \chi^n} \mathcal{l}(x^n)P(x^n)&\quad\dotso符号長の期待値, 平均符号長(average\;codeword\;length)\\ \end{array}$$例:\(\chi=\{0,1\},\;n=2\)
| \(y_1\) | \(y_2\) | \(x^2\) \(=y_1y_2\) |
\(P(x^2)\) | \(-\log_2{P(x^2)}\) Shannon情報量 |
\(I(x^2)=\lceil -\log_2{P(x^2)}\rceil\) \(\chi^2\)上の確率質量凾数\(P(x^2)\)から求める符号長 |
\(\pi(x^2)\) | \(\mathcal{l}(x^2)\) \(=|\pi(x^2)|\) |
\(\pi'(x^2)\) | \(\mathcal{l}'(x^2)\) \(=|\pi'(x^2)|\) |
\(\pi''(x^2)\) | \(\mathcal{l}''(x^2)\) \(=|\pi''(x^2)|\) |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 00 | \(\frac{1}{8}\) | \(-\log_2{\frac{1}{8}}=3\) | \(\lceil -\log_2{\frac{1}{8}}\rceil=3\) | 000 | 3 | 1 | 1 | 00 | 2 |
| 0 | 1 | 01 | \(\frac{1}{8}\) | \(-\log_2{\frac{1}{8}}=3\) | \(\lceil -\log_2{\frac{1}{8}}\rceil=3\) | 001 | 3 | 01 | 2 | 01 | 2 |
| 1 | 0 | 10 | \(\frac{1}{4}\) | \(-\log_2{\frac{1}{4}}=2\) | \(\lceil -\log_2{\frac{1}{4}}\rceil=2\) | 01 | 2 | 001 | 3 | 10 | 2 |
| 1 | 1 | 11 | \(\frac{1}{2}\) | \(-\log_2{\frac{1}{2}}=1\) | \(\lceil -\log_2{\frac{1}{2}}\rceil=1\) | 1 | 1 | 000 | 3 | 11 | 2 |
上記例で\(\mathcal{l}(x^2)\)が\(I\)と等しい符号化(\(\pi\))の平均符号長
$$\begin{array}{rcl} \displaystyle E\left[\mathcal{l}(x^2)\right] &=&\displaystyle \sum_{x^2\in \chi^2} \mathcal{l}(x^2)P(x^2)\\ &=&\displaystyle 3\times\frac{1}{8}+3\times\frac{1}{8}+2\times\frac{1}{4}+1\times\frac{1}{2}\\ &=&\displaystyle \frac{3+3+4+4}{8} = \frac{14}{8}\\ &=&\displaystyle 1+\frac{3}{4}=1.75\\ \end{array}$$上記例で\(\mathcal{l}'(x^2)\)が\(I\)と等しくない符号化(\(\pi'\))の平均符号長
$$\begin{array}{rcl} \displaystyle E\left[\mathcal{l}'(x^2)\right] &=&\displaystyle \sum_{x^2\in \chi^2} \mathcal{l}'(x^2)P(x^2)\\ &=&\displaystyle 1\times\frac{1}{8}+2\times\frac{1}{8}+3\times\frac{1}{4}+3\times\frac{1}{2}\\ &=&\displaystyle \frac{1+2+6+12}{8} = \frac{21}{8}\\ &=&\displaystyle 2+\frac{5}{8}=2.625\\ \end{array}$$上記例で\(\mathcal{l}(x^n)=2\)と常に一定となる符号化(\(\pi''\))の平均符号長
$$\begin{array}{rcl} \displaystyle E\left[\mathcal{l}''(x^2)\right] &=&\displaystyle \sum_{x^2\in \chi^2} \mathcal{l}''(x^2)P(x^2)\\ &=&\displaystyle 2\times\frac{1}{8}+2\times\frac{1}{8}+2\times\frac{1}{4}+2\times\frac{1}{2}\\ &=&\displaystyle 2\times\left(\frac{1}{8}+\frac{1}{8}+\frac{1}{4}+\frac{1}{2}\right)\\ &=&\displaystyle 2\times 1 \\ &=&\displaystyle 2\\ \end{array}$$データ系列・符号化・符号長(語頭属性, 語頭符号, 語頭符号化)
データ系列
$$\begin{array}{rl} y \in \chi &\quad\dotso yは集合\chiの要素\\ x^n(=y_1y_2 \dotso y_n) \in \chi^n &\quad\dotso 集合\chiの要素を並べた長さnのデータ系列x^n\\ P(x^n)&\quad\dotso\chi^n上の確率質量凾数(probability\;mass\;function)\\ -\log_2{P(x^n)} &\quad\dotso Shannon情報量(Shannon\;information)\\ \end{array}$$符号化・符号長
$$\begin{array}{rl} \{0,1\}* &\quad\dotso 0と1の任意長さの系列集合\\ \pi:\chi^n \rightarrow \{0,1\}* &\quad\dotso 符号化(coding)\\ \pi(x^n) &\quad\dotso 符号・符号語(codeword)\\ |\pi(x^n)| &\quad\dotso 符号・符号語(\pi(x^n))の長さ,\,符号長(codeword\;length)\\ \mathcal{l}(x^n)=|\pi(x^n)| &\quad\dotso \mathcal{l}:\chi^n \rightarrow \mathbb{R}^{+}(\mathbb{R}^{+}は正の実数)\\ \end{array}$$ 任意の\(x_1,x_2\in\chi^n\)に対して\(\pi(x_1),\pi(x_2)\)の一方が他方の先頭部分に一致しない性質(語頭属性(prefix property))を持つ符号を語頭符号(prefix code)，語頭符号へ変換する\(\pi\)を語頭符号化(prefix coding)と呼ぶ．
登録:
コメント (Atom)