<p>Apparently, no. This is a generalization where the relationship between <span class="math-container">$k$</span> and <span class="math-container">$i$</span> is stochastic (i.e. defined by a distribution and not deterministic).</p>
<p>To recover the original bits-back argument, we would need to pick a value <span class="math-container">$i_k$</span> for each possible value of <span class="math-container">$k$</span> and force <span class="math-container">$p(i=i_k \vert x, k)=1$</span> and 0 if <span class="math-container">$i \neq i_k$</span>. Naturally, we would need to extend the support of <span class="math-container">$k$</span> to the same of <span class="math-container">$i$</span>. In this particular example, <span class="math-container">$k \in \{0, 1, 2, 3\}$</span></p>

CC BY-SA 4.0
2020-09-03T21:39:53.233Z
2020-09-03T21:39:53.233Z
Daniel Severo
<p>I've been trying to understand Bits-back coding (<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.109.6760&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">Frey, B. J., and G. E. Hinton. 1997.)</a> a bit more (pun intended), which can be used to encode data with latent variable models. This <a href="https://docs.google.com/presentation/d/1hmzi-VZG9NfvpXcYcm06xGHFZ9CMYZSCcd_CKfTGhlY/edit#slide=id.g728deafd99_0_500" rel="nofollow noreferrer">tutorial by Pieter Abbeel et al.</a> sums up the procedure with an example which I present below, but with an explicit auxiliary variable (i.e. I added the variable <span class="math-container">$k$</span>).</p>
<p>Consider a mixture of Gaussians where <span class="math-container">$i$</span> indexes the Gaussian from which the data <span class="math-container">$x$</span> is sampled; <span class="math-container">$p(x\vert i) = \mathcal{N}(x|\mu_i, \sigma^2_i)$</span>. Assume, although possibly intractable, the true posterior <span class="math-container">$p(i \vert x, k)$</span> is available from which it is possible to sample and encode values <span class="math-container">$i$</span>, where <span class="math-container">$k \sim p(k)$</span> is some auxiliary information used to sample <span class="math-container">$i$</span>. Note that <span class="math-container">$k$</span> is used solely in the process of selecting <span class="math-container">$i$</span>, therefore <span class="math-container">$k \rightarrow i \rightarrow x$</span> forms a Markov chain and <span class="math-container">$p(x \vert i, k) = p(x \vert i)$</span></p>
<p>Given a data point <span class="math-container">$x$</span> to compress, bits-back coding then proceeds to</p>
<ol start="0">
<li>Sample <span class="math-container">$k$</span> from <span class="math-container">$p(k)$</span></li>
<li>Sample <span class="math-container">$i$</span> from <span class="math-container">$p(i \vert x, k)$</span></li>
<li>Encode <span class="math-container">$i$</span> with a prior <span class="math-container">$p(i)$</span>, resulting in code-length <span class="math-container">$\log_2(1/p(i))$</span></li>
<li>Encode <span class="math-container">$x$</span> with <span class="math-container">$p(x \vert i)$</span>, resulting in code-length <span class="math-container">$\log_2(1/p(x \vert i))$</span></li>
<li>Although <span class="math-container">$i$</span> was encoded with <span class="math-container">$p(i)$</span>, given that we know <span class="math-container">$p(i \vert x, k)$</span>, it is possible to get &quot;bits back&quot; (hence the name) by reconstructing <span class="math-container">$k$</span>.</li>
</ol>
<p>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:</p>
<p>Say there are 4 modes (Gaussians) of the mixture represented by <span class="math-container">$i \in \{0, 1, 2, 3\}$</span> and <span class="math-container">$k \in \{0, 1\}$</span>. For a given point <span class="math-container">$x_o$</span>, assume the given values for <span class="math-container">$p(i \vert x_o, k)$</span> and <span class="math-container">$p(i)$</span>, as well as the code used to represent them from a binary alphabet, are the following:</p>
<p><span class="math-container">$$\begin{array}{c|c|c} 
i &amp; p(i) &amp; \text{code-word} \\ \hline
0 &amp; 1/4  &amp; 00 \\
1 &amp; 1/4  &amp; 01 \\
2 &amp; 1/4  &amp; 10 \\
3 &amp; 1/4  &amp; 11 \\
\end{array}$$</span></p>
<p><span class="math-container">$$\begin{array}{c|c|c} 
k &amp;i &amp; p(i \vert x_o, k) \\ \hline
0 &amp; 0 &amp; 1/2 \\
0 &amp; 1 &amp; 1/4 \\
0 &amp; 2 &amp; 1/4 \\
0 &amp; 3 &amp;   0 \\
1 &amp; 0 &amp;   0 \\
1 &amp; 1 &amp; 1/2 \\
1 &amp; 2 &amp; 1/4 \\
1 &amp; 3 &amp; 1/4 
\end{array}$$</span></p>
<p>I've conveniently made the symbols I.I.D. with dyadic probability mass functions, therefore making traditional Huffman Coding optimal.</p>
<p>On the receiving end, if <span class="math-container">$i=0$</span>, surely <span class="math-container">$k=0$</span> since <span class="math-container">$p(i=0 | x_o, k=1) = 0$</span>. Similarly, <span class="math-container">$i=3$</span> implies <span class="math-container">$k=1$</span>. In general:</p>
<p><span class="math-container">$$\begin{array}{c|c|c} 
i &amp; p(k=0 \vert x_o, i) &amp; p(k=1 \vert x_o, i) \\ \hline
0 &amp;   1 &amp;   0 \\
1 &amp; 1/3 &amp; 2/3 \\
2 &amp; 1/2 &amp; 1/2 \\
3 &amp; 0 &amp; 1 
\end{array}$$</span></p>
<p>Therefore, we are able to recover <span class="math-container">$k$</span> to some extent.</p>
<p><strong>I have 2 questions:</strong></p>
<ol>
<li>is this the bits-back coding scheme or am I missing something?</li>
<li>For <span class="math-container">$i=0$</span> and <span class="math-container">$i=3$</span> we can recover <span class="math-container">$k$</span>, but for <span class="math-container">$i \in \{1, 2\}$</span> all we have are the probabilities over <span class="math-container">$k$</span>. How do we get these bits-back?</li>
</ol>

<it.information-theory><coding-theory>
Explicit Bits-back Coding (a.k.a. Free Energy Coding) applied to Gaussian mixtures
Daniel Severo
# Explicit Bits-back Coding (a.k.a. Free Energy Coding) applied to Gaussian mixtures

(Asked by: username_0 on 2020-09-03)

I've been trying to understand Bits-back coding ([Frey, B. J., and G. E. Hinton. 1997.)](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.109.6760&rep=rep1&type=pdf) a bit more (pun intended), which can be used to encode data with latent variable models. This [tutorial by Pieter Abbeel et al.](https://docs.google.com/presentation/d/1hmzi-VZG9NfvpXcYcm06xGHFZ9CMYZSCcd_CKfTGhlY/edit#slide=id.g728deafd99_0_500) 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

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

**Tags:** it.information-theory, coding-theory


---

## 1 answers

### Answer by username_0 on 2020-09-03. Score: 1 | Accepted answer

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\}$


---

