Information entropy(資訊熵)

以下為若無特別說明，皆討論離散隨機變數的性質。

資訊測度關係(離散隨機變數)

• Entropy(熵) $H(X)$: 隨機變數的資訊量。
• Joint etnropy(聯合熵) H(X,Y): 兩個隨機變數所含有的總資訊量。
• Mutual information*(互資訊) $I(X;Y)$: 兩個隨機變數(分佈)的接近程度。
• Conditional entropy*(條件熵) $H(X|Y)$ or $H(Y|X)$ : 給定隨機變數$X$之後，隨機變數$Y$的資訊量。
• Relative entropy*(相對熵) $D(P||Q)$: 兩個隨機變數(分佈)的分散程度(此測度無交換性，不滿足metric space中distance function的定義，所以不應視為兩個隨機變數的距離)。
  • 論文中較常用Kullback–Leibler(KL) divergence或information gain的名稱。
  • 

熵 (Entropy)

• $H(X) = -\sum_{x \in X} p(x) \log_2(x)$.
  • $p(X)$: (univariate) 離散隨機變數 $X$的機率質量函數 (probability mass function).
• 熵是隨機變數的不確定性的平均度量數，隨機變數變異數越大，即隨機變數越"亂"，則熵之值越大。
• 熵最大值發生在隨機變數為平均分佈(uniform distribution)時。
• 熵也可以解釋為使用binary編碼隨機變數時，平均的編碼長度。
• $H(X)$是凹函數(concave function)(開口向下)。

Entropy properties

• If $X \sim P(X)$, the expected value of the random variable $g(X)$ is $E_P(g(X))=\sum_{x\in X} g(x)P(x)$.
• $H(X) = -\sum_{x \in X} P(x)\log{P(x)} = E_P\left(\log{\frac{1}{P(x)}}\right)$.
• $H(X) \geq 0$. $\left[ \because 0 \leq P(x) \leq 1 \Rightarrow \log{\left( \frac{1}{P(x)} \right)} \geq 0 \right]$
• $H_b(X) = \left( \log_b{(a)} \right) H_a(X)$. $\left[ \because \log_b(p) = \log_b(a) \log_a(p) \right]$.

• Chain rule:

  • $H(X,Y) = H(X) + H(Y|X) = H(Y) + H(Y|X)$.

  • $\begin{array}{rcl} H(X,Y) & = & - \sum_{x \in X} \sum_{y \in Y} P(x,y) \log{P(x,y)} \\ & = & - \sum_{x \in X} \sum_{y \in Y} P(x,y) \log{(P(x) P(y|x))} \\ & = & - \sum_{ x in X} \sum_{y \in Y} P(x,y)\log{P(x)} - \sum_{x \in X} \sum_{y \in Y} P(x,y) \log{P(y|x)} \\ & = & - \sum_{x \in X} P(x)\log{P(x)} - \sum_{x \in X} \sum_{y \in Y} P(x,y) \log{P(y|x)} \\ & = & H(X) + H(Y|X). \end{array}$.

    • $\log{P(X,Y)} =\log{P(X)} + \log{P(Y|X)}$.

    • 可推廣至 $H(X,Y|Z)=H(X|Z) + H(X|Y,Z)=H(Y|Z) + H(Y|X,Z)$.

• Chain rule2:

  • $H(X_1, X_2, \cdots X_n) = \sum_{i=1}^{n} H(X_i | X_{i-1}, X_{i-2}, \cdots, X_1)$

    • $H(X_1, X_2) = H(X_1) + H(X_2 | X_1)$.

    • $H(X_1, X_2, X_3) = H(X_1) + H(X_2, X_3 | X_1) = H(X_1) + H(X_2|X_1) + H(X_3|X_1, X_2)$.

聯合熵 (Joint entropy)

• 兩個隨機變數的熵，令$P(X,Y)$為joint distribution。
• $H(X, Y) = -\sum_{x \in X} \sum_{y \in Y} P(x,y)\log{P(x,y)} = -E(\log{P(x,y)})$.

條件熵 (Conditional entropy)

• 條件熵無交換性，$H(X|Y) \neq H(Y|X)$，因隨機變數$X$與$Y$的資訊量不相同。
• $H(X) - H(X|Y) = H(Y) - H(Y|X) = I(X;Y)$. ** $H(X) - H(X|Y)$可解釋為分佈$X$的資訊量，減去給定$Y$的資訊量後$X$資訊量，此時剩下的資訊為$X$與$Y$共有的資訊，即$I(X;Y)$.
• $\begin{array}{rcl} H(Y|X) & = & -\sum_{x \in X} P(x)H(Y|X=x) \\ & = & - \sum_{x \in X} P(x) \sum_{y \in Y} P(y|x)\log{P(y|x)} \\ & = & - \sum_{x \in X} \sum_{y \in Y} P(x,y)\log{P(y|x)} \\ & = & -E(\log{P(Y|X)}). \end{array}$. ** $H(Y|X)$中，$X$是隨機變數，而非定值。

互資訊 (Mutual information)

• $\begin{array}{rcl} I(X;Y) & = & \sum_{x \in X} \sum_{y \in Y} P(x,y)\log{\left( \frac{P(x,y)}{P(x)P(y)} \right)} \\ & = & D(P(x,y) || P(x)P(y)) \\ & = & E_P\left( \log {\frac{P(X,Y)}{P(X)P(Y)}} \right). \end{array}$
• $D(P(x,y) || P(x)P(y))$可解釋為聯合分配相對於兩變數為獨立分佈的分散程度。
• $I(X;Y)=0 \Leftrightarrow \log {\frac{P(X,Y)}{P(X)P(Y)}} =0$, then $P(X,Y)=P(X)P(Y)$即兩隨機變數獨立(indepedent)，因為彼此之間沒有任何相關的訊息。

Mutual information properties

• $\begin{array}{rcl} I(X;Y) & = & \sum_{x \in X, y\in Y}P(x,y)\log{\left( \frac{P(x,y)}{P(x)P(y)} \right)} \\ & = & \sum_{x \in X, y \in Y} P(x,y) \log{\left( \frac{P(x|y)}{p(x)} \right)}\\ & = & -\sum_{x \in X, y \in Y} P(x,y) \log{P(x)} + \sum_{x \in X, y \in Y} P(x,y) \log{P(x|y)} \\ & = & H(X) - H(X|Y) \\ & = & H(Y) - H(Y|X). \end{array}$
• $H(X,Y) = H(X) + H(X|Y) \Rightarrow I(X;Y) = H(X) + H(Y) - H(X,Y)$.
• (Self information) $I(X;X) = H(X) - H(X|X) = H(X)$.

相對熵 (Relative entropy), KL散度(Kullback-Leibler divergence)

• 此資訊測度非常重要，常用於給定的隨機變數(分佈)與資料的隨機變數(分佈)之間的最佳化。
• $D(P||Q)=\sum_{x \in X} P(x)\log{\left( \frac{P(x)}{Q(x)} \right)} = E_P\left( \log{\frac{P(x)}{Q(x)}} \right)$.
  • Let $0 \log{\frac{0}{0}} = 0$, $0 \log{\frac{0}{Q}}=0$, $P\log{\frac{P}{0}}=\infty$.
  • 通常$Q$為資料的分佈(未知)，而$P$為使用者給定的分佈(已知)。
• $D(P||Q) \neq D(Q||P)$，不滿足交換律，所以不符合distance function的定義。
• $D(P||Q)=0 \Leftrightarrow P = Q \ a.s.$

條件互資訊(Conditional mutual information)

• The uncertainty of $X$ due to the knowledge of $Y$ when $Z$ is given.

• $I(X;Y|Z)=H(Z)-H(X|Y,Z)=E_{P(X,Y,Z)}\left( \log{\frac{P(X,Y|Z)}{P(X|Z)P(Y|Z)}} \right)$.

• $I(X_1,X_2,\cdots,X_n;Y) = \sum_{i=1}^{n} I(X_i;Y|X_{i-1},X_{i-2},\cdots, X_1)$.