Information Theory and Data Compression

Information measurement⚓︎

The definition of entropy⚓︎

\[\begin{aligned} H(X) = - \sum_{x \in X} p(x) \log p(x) \end{aligned} \]

Entropy可以看成是一個機率分佈的資訊量，而如果entropy越大，代表資訊量越大。反之如果entropty越小，代表資訊量越小。

舉例來說，一個投擲出去的硬幣，是正面或反面的機率為1，不是正面也不是反面的機率為0，顯然這句話是廢話。
於是我們將上述的機率分佈代入entropy，算出\(-( 0 \log 0+ 1 \log 1 ) = 0\)，廢話的entropy還真的是0。

而透過微分找極值，顯然當二項分布\(p=0.5\)時，entropy最大，因為這個機率分佈不會暗示說哪個事件發生的可能比較大。

The derivation of entropy⚓︎

通過上述簡單的介紹entropy，接著推導entropy的公式如何求得。

假如有三個事件\(A_{1},A_{2},A_{3}\)，其對應的機率分別為\(p_{1},p_{2},p_{3}\)。
我們將其中兩個事件\(A_{2},A_{3}\)組成一組，使得另外有兩個事件，\(B_{1} = \{ A_{1} \}\) \(,\) \(B_{2} = \{ A_{2} , A_{3} \}\)，其對應的機率為\(q_{1}=p_{1},q_{2}=p_{2}+p_{3}\)。

而我們希望，從\(A_{1},A_{2},A_{3}\)算出來的entropy，要與先算\(B_{1},B_{2}\)的entropy，再按機率比例算\(B_{1},B_{2}\)集合內的entropy的總和相等。也就是

\[\begin{aligned} H(p_{1},p_{2},p_{3}) = H(q_{1},q_{2})+ q_{1}H(p_{1}/q_{1})+q_{2}H(p_{2}/q_{2},p_{3}/q_{2}) \end{aligned} \tag{1.1.1} \]

得到了關係式後，我們繼續推導entropy的公式。
先令\(H(1/n,1/n,1/n...)=A(n)\)

舉例來說：

\[\begin{aligned}H(1/2,1/2)=A(2)\end{aligned}\]

\[\begin{aligned}H(1/8,1/8,1/8,1/8,1/8,1/8,1/8,1/8)=A(8)\end{aligned}\]

而從\((1.1.1)\)我們可以得出：

\[\begin{aligned} A(8)&=H(1/2,1/2)+1/2(H(1/2,1/2) \\&+1/2H(1/2,1/2)+1/2H(1/2,1/2))\\&=3A(2) \end{aligned} \]

從上面的例子可以觀察出下式，證明方法可以從畫顆樹下手

\[\tag{1.1.2}A(j^l)=lA(j)\]

而對於足夠大的\(l\),可以找到一組\((k,m)\)使得\(A(k^m) \le A(j^l)<A(k^{m+1})\)
因此\((1.1.2)\)可以將其化簡為\(m/l \le A(j)/A(k) < m/l + 1/l\)，也就是

\[\tag{1.1.3}|m/l - A(j)/A(k)| < \epsilon\]

而因為\(k^m \le j^l<k^{m+1}\)，且\(\log{j^l} = l \log j\)，所以透過類似\((1.1.3)\)的過程，可以得到

\[\tag{1.1.4}|m/l - \log (j)/ \log(k)| < \epsilon\]

最後將\((1.1.3)\)和\((1.1.4)\)合併，得到\(|A(j)/A(k) - \log (j)/ \log(k)| <2 \epsilon\)，也代表著

\[\tag{1.1.5}H=K \log (n)\]

其中\(K\)為常數。

而上面我們只探討了所有事件機率相等的情況，接下來繼續討論事件的機率不相等的情況。

這次假設我們有\(\sum_{i \in I} n_{i}\)種機率相等的事件。
根據\((1.1.1)\)和\((1.1.5)\)，可以得出下列結論。

\[ \begin{aligned} H &= H(p_{1},p{2}...,p_{i}) + \sum_{i \in I}p_{i}H(1/n_{i},...,1/n_{i}) \\&= H(p_{1},p{2}...,p_{i})+ K\sum_{i \in I} p_{i} \log(n_{i}) \end{aligned} \]

左右移位後，可以得到:

\[ \begin{aligned} H(p_{1},p_{2}...,p_{i}) &= K \log (\sum_{i \in I} n_{i}) - K\sum_{i \in I} p_{i} \log(n_{i}) \\&= -K[\sum_{i \in I} p_{i} \log(n_{i})-\log (\sum_{j \in J} n_{j})] \\&= -K[\sum_{i=1}^{n} p_{i} \log(n_{i})-\log (\sum_{j=1}^{n} n_{j}) \sum_{i=1}^{n}p_{i}] \\&= -K \sum_{i=1}^{n}p_{i}\log [n_{i}-(\sum_{j=1}^{n} n_{j})] \\&= -K \sum_{i=1}^{n}p_{i}\log[\frac{n_{i}}{(\sum_{j=1}^{n} n_{j})}] \\&= -K \sum_{i=1}^{n}p_{i}\log p_{i} \end{aligned} \]

為了方便，將\(K\)帶入\(1\)，最後得到entropy的式子

\[\tag{1.1}H=-\sum_{i \in I}p_{i}\log p_{i}\]

Reference⚓︎

Elements of Information Theory, 2nd edition
Introduction to data compression, 3rd edition