2
$\begingroup$

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

  1. Sample $k$ from $p(k)$
  2. Sample $i$ from $p(i \vert x, k)$
  3. Encode $i$ with a prior $p(i)$, resulting in code-length $\log_2(1/p(i))$
  4. Encode $x$ with $p(x \vert i)$, resulting in code-length $\log_2(1/p(x \vert i))$
  5. 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:

  1. is this the bits-back coding scheme or am I missing something?
  2. 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?
$\endgroup$

1 Answer 1

1
$\begingroup$

Apparently, no. This is a generalization where the relationship between $k$ and $i$ is stochastic (i.e. defined by a distribution and not deterministic).

To recover the original bits-back argument, we would need to pick a value $i_k$ for each possible value of $k$ and force $p(i=i_k \vert x, k)=1$ and 0 if $i \neq i_k$. Naturally, we would need to extend the support of $k$ to the same of $i$. In this particular example, $k \in \{0, 1, 2, 3\}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.