式展開: 平均符号長の下限(エントロピー, Kullback-Leiblerダイバージェンス)

\begin{array}{rcl} l (x^{n}) & = & - \log_{2} P (x^{n}) \\ - l (x^{n}) & = & \log_{2} P (x^{n}) \\ 2^{- l (x^{n})} & = & 2^{\log_{2} P (x^{n})} \\ = & P (x^{n}) \\ P (x^{n}) & = & 2^{- l (x^{n})} \\ \sum_{x^{n} \in χ^{n}} P (x^{n}) & \leq & 1 & \dots P (x^{n}) は 確 率 質 量 凾 数 な の で 総 和 は 1, P (x^{n}) を 劣 確 率 凾 数 と す る ケ ー ス を 考 え る 場 合 は 総 和 は 1 以 下 \\ \sum_{x^{n} \in χ^{n}} 2^{- l (x^{n})} & \leq & 1 & \dots 2^{- l (x^{n})} = P (x^{n}) な の で や は り 総 和 は 1, P (x^{n}) を 劣 確 率 凾 数 と す る ケ ー ス を 考 え る 場 合 は 総 和 は 1 以 下 \end{array}

劣確率凾数は

P (x) \geq 0

の条件は確率(質量)凾数と同じで，

\sum P (x) \leq 1

となる凾数．

\begin{array}{rcl} E_{P}^{n} [l (X^{n})] & \geq & H_{n} (P) & \dots 符 号 長 の 期 待 値 ・ 平 均 符 号 長 の 下 限 \\ H_{n} (P) & \overset{def}{=} & E_{P}^{n} [- \log_{2} P (X^{n})] & \dots 確 率 P (x^{n}) に 基 づ く 符 号 化 の 長 さ で あ る こ と が 条 件 l (X^{n}) = - \log_{2} P (X^{n}) \end{array}

H_{n} (P)

をエントロピー(entropy)と呼ぶ．

\begin{array}{rcl} \log_{2} P (x^{n}) - \log_{2} P (x^{n}) & = & \log_{2} Q (x^{n}) - \log_{2} Q (x^{n}) \\ - \log_{2} Q (x^{n}) & = & - \log_{2} P (x^{n}) + \log_{2} P (x^{n}) - \log_{2} Q (x^{n}) \\ = & - \log_{2} P (x^{n}) + \log_{2} \frac{P (x^{n})}{Q (x^{n})} \\ E_{P}^{n} [- \log_{2} Q (X^{n})] & = & E_{P}^{n} [- \log_{2} P (X^{n})] + E_{P}^{n} [\log_{2} \frac{P (X^{n})}{Q (X^{n})}] \\ = & H_{n} (P) + D_{n} (P ∥ Q) \\ D_{n} (P ∥ Q) & \overset{def}{=} & E_{P}^{n} [\log_{2} \frac{P (X^{n})}{Q (X^{n})}] \end{array}

D_{n} (P ∥ Q)

をKullback-Leiblerダイバージェンス(Kullback-Leibler divergence)と呼ぶ．

式展開