ベルヌイモデルのエントロピーやKLダイバージェンスを考える

\(P_{Ber}\)の\(H_n(x)\)や\(D_n(x\parallel y)\)を考える

\(n\)回の試行結果である\(x^n\)の1の発生回数を\(m\)とすると\(P_{Ber}\)の\(\theta\)の最尤推定値\(\hat{\theta}\)は\(\frac{m}{n}\)となる． $$\begin{array}{rcl} \displaystyle \hat{\theta} &=&\displaystyle \frac{m}{n}\\ H_n(P)&\overset{\mathrm{def}}{=}& E^{n}_{P}\left[-\log_2{P(X^n)}\right] \\ \displaystyle H(\theta) &\overset{\mathrm{def}}{=}& \displaystyle -\theta\log_{2}{\left(\theta\right)}-\left(1-\theta\right)\log_{2}{\left(1-\theta\right)} \quad\dotso P=P_{Ber}で\thetaを引数として括弧の内側に記載する． \\ \displaystyle H(\hat{\theta}) &=&\displaystyle -\hat{\theta}\log_{2}{\left(\hat{\theta}\right)}-\left(1-\hat{\theta}\right)\log_{2}{\left(1-\hat{\theta}\right)}\\ &=&\displaystyle -\frac{m}{n}\log_{2}{\left(\frac{m}{n}\right)}-\left(1-\frac{m}{n}\right)\log_{2}{\left(1-\frac{m}{n}\right)}\\ &=&\displaystyle \frac{1}{n}\left\{-m\log_{2}{\left(\frac{m}{n}\right)}-\left(n-m\right)\log_{2}{\left(\frac{n-m}{n}\right)}\right\}\\ &=&\displaystyle \frac{1}{n}\left\{ \displaystyle -m\log_{2}{ \left(m\right) } \displaystyle +m\log_{2}{ \left(n\right) } \displaystyle -\left(n-m\right)\log_{2}{ \left(n-m\right) } \displaystyle +\left(n-m\right)\log_{2}{ \left(n\right) } \displaystyle \right\}\\ \displaystyle D(\hat{\theta}\parallel \theta) &=&\displaystyle \hat{\theta}\log_{2}{\left(\frac{\hat{\theta}}{\theta}\right)}+\left(1-\hat{\theta}\right)\log_{2}{\left(\frac{1-\hat{\theta}}{1-\theta}\right)}\\ &=&\displaystyle \frac{m}{n}\log_{2}{\left(\frac{\frac{m}{n}}{\theta}\right)}+\left(1-\frac{m}{n}\right)\log_{2}{\left(\frac{1-\frac{m}{n}}{1-\theta}\right)}\\ &=&\displaystyle \frac{1}{n}\left\{ \displaystyle m\log_{2}{\left(\frac{\frac{m}{n}}{\theta}\right)} \displaystyle +\left(n-m\right)\log_{2}{\left(\frac{1-\frac{m}{n}}{1-\theta}\right)} \displaystyle \right\}\\ &=&\displaystyle \frac{1}{n}\left\{ \displaystyle m\log_{2}{\left(\frac{m}{n}\right)} \displaystyle -m\log_{2}{\left(\theta\right)} \displaystyle +\left(n-m\right)\log_{2}{\left(1-\frac{m}{n}\right)} \displaystyle \displaystyle -\left(n-m\right)\log_{2}{\left(1-\theta\right)} \displaystyle \right\}\\ &=&\displaystyle \frac{1}{n}\left\{ \displaystyle m\log_{2}{\left(m\right)} \displaystyle -m\log_{2}{\left(n\right)} \displaystyle -m\log_{2}{\left(\theta\right)} \displaystyle +\left(n-m\right)\log_{2}{\left(n-m\right)} \displaystyle -\left(n-m\right)\log_{2}{\left(n\right)} \displaystyle -\left(n-m\right)\log_{2}{\left(1-\theta\right)} \displaystyle \right\}\\ \displaystyle H(\hat{\theta})+D(\hat{\theta}\parallel \theta) &=&\displaystyle \frac{1}{n}\left\{ \displaystyle -m\log_{2}{\left(\theta\right)}-\left(n-m\right)\log_{2}{\left(1-\theta\right)} \displaystyle \right\}\\ \displaystyle n\left\{H(\hat{\theta})+D(\hat{\theta}\parallel \theta)\right\} &=&\displaystyle -m\log_{2}{\left(\theta\right)}-\left(n-m\right)\log_2{\left(1-\theta\right)}\\ \end{array}$$ $$\begin{array}{rcl} -\log_2{\left( L(\theta|x^n) \right)} &=&-m\log_2{\left( \theta \right)}-(n-m)\log_2{\left(1-\theta\right)}\\ n\left\{H\left( \hat{\theta} \right)+D(\hat{\theta}\parallel \theta)\right\} &=&-m\log_2{\left( \theta \right)}-\left( n-m \right)\log_2{\left( 1-\theta \right)}\\ -\log_2{\left( L\left(\theta|x^n\right) \right)} &=&n\left\{H\left( \hat{\theta} \right)+D\left( \hat{\theta}\parallel \theta \right)\right\}\\ &=&nH\left( \hat{\theta} \right)+nD\left( \hat{\theta}\parallel \theta \right)\\ -\log_2{\left( L\left(\hat{\theta}|x^n\right) \right)} &=&nH\left( \hat{\theta} \right)+nD\left( \hat{\theta}\parallel \hat{\theta} \right)\quad\dotso\theta=\hat{\theta}\\ &=&nH\left( \hat{\theta} \right)+n0\quad\dotso D\left( \hat{\theta}\parallel \hat{\theta} \right)=0\\ &=&nH\left( \frac{m}{n} \right)\quad\dotso \hat{\theta}=\frac{m}{n}\\ \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)と呼ぶ．