Md. Asif Uddin
    I.13.X09

    The rate is information plus mismatch, for any encoder

    proof▲▲▲

    Let the training set have NN examples, chosen with equal probability q(n)=1/Nq(n)=1/N, and let the encoder give q(z∣n)q(\vec z\mid n). Prove (I.13.9): the average of KL⁡(q(z∣n) ∥ p(z))\KL(q(\vec z\mid n)\,\|\,p(\vec z)) equals Iq(n;z)+KL⁡(q(z) ∥ p(z))I_q(n;\vec z)+\KL(q(\vec z)\,\|\,p(\vec z)), with q(z)=1N∑nq(z∣n)q(\vec z)=\frac1N\sum_nq(\vec z\mid n). Deduce that a zero average KL means a code that carries no information, and that the rate bounds the information from above.

    Hint

    Insert q(z)q(\vec z) into the log-ratio: log⁡q(z∣n)p(z)=log⁡q(z∣n)q(z)+log⁡q(z)p(z)\log\frac{q(\vec z\mid n)}{p(\vec z)} =\log\frac{q(\vec z\mid n)}{q(\vec z)}+\log\frac{q(\vec z)}{p(\vec z)}.

    Solution

    The identity. Average the split in the hint over q(n,z)=q(n) q(z∣n)q(n,\vec z)=q(n)\,q(\vec z\mid n):

    1N∑nKL⁡(q(z∣n) ∥ p(z))  =Eq(n,z)[log⁡q(z∣n)q(z)]  +Eq(n,z)[log⁡q(z)p(z)].\begin{aligned} &\frac1N\sum_n\KL\big(q(\vec z\mid n)\,\|\,p(\vec z)\big)\\ &\;=\E_{q(n,\vec z)}\Big[\log\frac{q(\vec z\mid n)}{q(\vec z)}\Big]\\ &\;\quad+\E_{q(n,\vec z)}\Big[\log\frac{q(\vec z)}{p(\vec z)}\Big]. \end{aligned}

    In the first term, q(z∣n)/q(z)=q(n,z)/(q(n) q(z))q(\vec z\mid n)/q(\vec z)=q(n,\vec z)/\big(q(n)\,q(\vec z)\big), so it is KL⁡(q(n,z) ∥ q(n)q(z))=Iq(n;z)\KL(q(n,\vec z)\,\|\,q(n)q(\vec z))=I_q(n;\vec z) (Mutual information 0.IT.04). The second term depends on z\vec z alone, and the marginal of q(n,z)q(n,\vec z) over z\vec z is q(z)q(\vec z), so it is KL⁡(q(z) ∥ p(z))\KL(q(\vec z)\,\|\,p(\vec z)). ■\blacksquare

    Zero rate means no information. Both terms on the right are non-negative. If the left side is zero, both are zero. Then Iq(n;z)=0I_q(n;\vec z)=0: the code is independent of the example, so it tells the decoder nothing about which input it came from. Equivalently, each KL⁡(q(z∣n) ∥ p)\KL(q(\vec z\mid n)\,\|\,p) is non-negative and their average is zero, so each is zero and every q(z∣n)q(\vec z\mid n) is the prior. That is posterior collapse.

    The rate bounds the information. Dropping the non-negative second term gives Iq(n;z)≤1N∑nKL⁡(q(z∣n) ∥ p)I_q(n;\vec z)\leq\frac1N\sum_n\KL(q(\vec z\mid n)\,\|\,p). The rate is an upper bound on what the code says about the example. Since nn takes NN values, the information is also at most log⁡N\log N; any rate above that is spent on the mismatch.

    The identity holds for every encoder, not only at an optimum. The script checks it for three encoders on the four points, including the collapsed one, where both sides are zero.

    Draws on