INFOTH Note 3: Relative Ent. (KL), Mutual Info.
I now start cancel numbering for sections since I’m lazy.
3.1 Log-sum Inequality
Theorem
Suppose \(a_i,b_i>0\) for a countable set \(\mathcal X\), then
\[ \sum_{i\in\mathcal X}a_i\log {a_i\over b_i}\ge a\log b,\quad a=\sum_i a_i, \quad b=\sum_i b_i. \]Proof
Using Jensen’s Inequality, given \(u\log u\) is convex and \(\sum_i (b_i/b) = 1\)
\[ \begin{aligned} \sum_{i\in\cal X}a_i\log {a_i\over b_i}&=b\sum_{i}({b_i\over b}){a_i\over b_i}\log {a_i\over b_i} \\&= b\sum_i \lambda_i u_i\log u_i,\qquad\lambda_i:=b_i/b,\quad\sum_i\lambda_i=1,\quad u_i=a_i/b_i, \\&\ge b\cdot (\sum_i\lambda_iu_i) \cdot \log \sum_i\lambda_iu_i \\&=b\cdot(\sum_i{a_i\over b})\cdot\log \sum_i {a_i\over b} \\&=a\log{a\over b}.\qquad\square \end{aligned} \]3.2 Relative Entropy (KL distance)
Def: Relative Entropy 相对熵 = KL散度
The relative entropy i.e. Kullback-Leibler (KL) Distance between 2 probability mass functions \(p(x)\) and \(q(x)\) is defined as
\[ D(p||q)=\sum_{x\in\mathcal X}p(x)\log{p(x)\over q(x)}\equiv E_p[\log{p(X)\over q(X)}] \]Def: Cross Entropy
\[ H(p||q)=\sum_x p(x)\log q(x)=E_p[\log q(X)] \]When we are predicting the labels (one-hots) \(p\) with \(p'\) we have the \(H(p||p')\) as the loss.
And the relation of KL, cross entropy and entropy is
\[ H(p) = H(p||q) + D(p||q) \]Properties of KL
-
Asymmetric: \(D(p||q)\ne D(q||p)\) in general.
For example, \(p=(1/2,1/2)\) and \(q=(1,0)\). Both on the alphabet \({\cal X}=\{0,1\}\).
Then
- \(D(q||p)=1\cdot \log2 + 0=1\), while \(D(p||q)=\frac12\log(\frac12/0)+\frac12\log(\frac12/1)=+\infty\)
We can observe the image space of \(D\).
\(D:\Delta_{\cal X}\times \Delta_{\cal X}\mapsto \R\cup \{+\infty\}\)
-
Nonnegative: \(D(p||q)\ge 0\) always, where \(D(p||q)=0\iff p=q\)
-
Jointly Convex, for the pair \((p,q)\).
For \(\forall t\in[0,1]\),
\[ D(tp_1+(1-t)p_2||tq_1+(1-t)q_2)\le tD(p_1||q_1)+(1-t)D(p_2||q_2). \]
3.3 Mutual Information
Def: Mutual Info.
\[ I(X;Y)=I(Y;X)=D(\Pr(X,Y)||\Pr(X)\Pr(Y))=H(X)-H(X|Y)=H(Y)-H(Y|X) \]Break the KL Divergence down, for discrete distributions of \(X\) and \(Y\) named \(p_X\) and \(p_Y\), and their joint dist. \(p_{X,Y}\):
\[ \begin{aligned} D(p_{X,Y}||p_Xp_Y) &=\sum_{x,y}p_{X,Y}(x,y)\log{p_{X,Y}(x,y)\over p_X(x) p_Y(y)} \\ & = E_{X,Y}[p_{X,Y}\log(p_{X,Y}/p_Xp_Y)] \end{aligned} \]- Memorize: Joint || Product distribution
Properties
Nonnegativity
- \(I(X;Y)\ge 0\), with equality iff \(X\perp\!\!\!\perp Y\) (since mutual information can be written as KL, and this KL=0 iff joint distribution equals the product distribution, which means the independence)
- equivalent to this: \(H(X)\ge H(X|Y)\) or \(H(Y)\ge H(Y|X)\) and the equality holds iff they are independent
- \(H(X_1\dots X_n)\le \sum_i H(X_i)\); the equality of which holds iff they are mutually independent (all independent) not pairwise
- \(X_j\perp\!\!\!\perp(X_1\cdots X_{j-1})\)
Symmetry
\(I(X;Y)=I(Y;X)\)
Def: Multivariant Mutual Information
\[ I(X;Y,Z)=H(X)-H(X|Y,Z)=H(Y,Z)-H(Y,Z|X) \]Venn Diagram about Mutual Information
