Brendan J. Frey and Geoffrey E. Hinton 1997.
Efficient stochastic source coding and an application to a Bayesian network source model.
The Computer Journal 40, 157-165.
In this paper, we introduce a new algorithm called ``bits-back coding''
that makes stochastic source
codes efficient. For a given one-to-many source code, we show that this
algorithm can actually be more efficient than the algorithm that always
picks the shortest codeword. Optimal efficiency is achieved when codewords
are chosen according to the Boltzmann distribution based on the codeword
lengths.
It turns out that a commonly used technique for determining parameters
- maximum likelihood estimation - actually minimizes the bits-back coding
cost when codewords are chosen according to the Boltzmann distribution.
A tractable approximation to maximum likelihood estimation
- the generalized expectation maximization algorithm -
minimizes the bits-back coding cost.
After presenting a binary Bayesian network model that assigns
exponentially many codewords to each symbol, we show how a tractable
approximation to the Boltzmann distribution can be used for bits-back
coding.
We illustrate the performance of bits-back coding using
using nonsynthetic data with a binary Bayesian network source model that
produces 2^60 possible codewords for each input symbol.
The rate for bits-back coding is nearly one half of that obtained by picking
the shortest codeword for each symbol.
Compressed postscript,
uncompressed postscript.
Back to Brendan Frey's home page.