I've been trying to understand Bits-back coding (Frey, B. J., and G. E. Hinton. 1997.) a bit more (pun intended), which can be used to encode data with latent variable models. This tutorial by Pieter Abbeel et al. sums up the procedure with an example which I present below, but with an explicit auxiliary variable (i.e. I added the variable $k$).
Consider a mixture of Gaussians where $i$ indexes the Gaussian from which the data $x$ is sampled; $p(x\vert i) = \mathcal{N}(x|\mu_i, \sigma^2_i)$. Assume, although possibly intractable, the true posterior $p(i \vert x, k)$ is available from which it is possible to sample and encode values $i$, where $k \sim p(k)$ is some auxiliary information used to sample $i$. Note that $k$ is used solely in the process of selecting $i$, therefore $k \rightarrow i \rightarrow x$ forms a Markov chain and $p(x \vert i, k) = p(x \vert i)$
Given a data point $x$ to compress, bits-back coding then proceeds to
- Sample $k$ from $p(k)$
- Sample $i$ from $p(i \vert x, k)$
- Encode $i$ with a prior $p(i)$, resulting in code-length $\log_2(1/p(i))$
- Encode $x$ with $p(x \vert i)$, resulting in code-length $\log_2(1/p(x \vert i))$
- Although $i$ was encoded with $p(i)$, given that we know $p(i \vert x, k)$, it is possible to get "bits back" (hence the name) by reconstructing $k$.
My goal is to understand this concretely, since most tutorials I've found stop here and never actually give an example. Hence, consider the following:
Say there are 4 modes (Gaussians) of the mixture represented by $i \in \{0, 1, 2, 3\}$ and $k \in \{0, 1\}$. For a given point $x_o$, assume the given values for $p(i \vert x_o, k)$ and $p(i)$, as well as the code used to represent them from a binary alphabet, are the following:
$$\begin{array}{c|c|c} i & p(i) & \text{code-word} \\ \hline 0 & 1/4 & 00 \\ 1 & 1/4 & 01 \\ 2 & 1/4 & 10 \\ 3 & 1/4 & 11 \\ \end{array}$$
$$\begin{array}{c|c|c} k &i & p(i \vert x_o, k) \\ \hline 0 & 0 & 1/2 \\ 0 & 1 & 1/4 \\ 0 & 2 & 1/4 \\ 0 & 3 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1/2 \\ 1 & 2 & 1/4 \\ 1 & 3 & 1/4 \end{array}$$
I've conveniently made the symbols I.I.D. with dyadic probability mass functions, therefore making traditional Huffman Coding optimal.
On the receiving end, if $i=0$, surely $k=0$ since $p(i=0 | x_o, k=1) = 0$. Similarly, $i=3$ implies $k=1$. In general:
$$\begin{array}{c|c|c} i & p(k=0 \vert x_o, i) & p(k=1 \vert x_o, i) \\ \hline 0 & 1 & 0 \\ 1 & 1/3 & 2/3 \\ 2 & 1/2 & 1/2 \\ 3 & 0 & 1 \end{array}$$
Therefore, we are able to recover $k$ to some extent.
I have 2 questions:
- is this the bits-back coding scheme or am I missing something?
- For $i=0$ and $i=3$ we can recover $k$, but for $i \in \{1, 2\}$ all we have are the probabilities over $k$. How do we get these bits-back?