Bits Back Encoding

In Information Theory and Machine Learning, bits back encoding is a data compression scheme originally proposed as a thought experiment on defining the minimum description length for a Bayesian neural network. It has since been proposed as a method for incorporating neural networks into a data compression algorithm.

In bits-back encoding, the sender and receiver share a source coding algorithm parameterized by a weight w and a commonly agreed upon procedure to learn a posterior probability distribution Q_y(w) upon seeing a sequence of messages y such that weights drawn from Q_y(w) should in expectation produce short encodings for y under the shared coding algorithm.

Then, in order to transmit y together with a previously encoded message, the sender uses the previously encoded message as a source of random bits in order to sample a weight w from Q_y(w). The sender then transmits w, along with the message y encoded according to w. The receiver can now decode y, and, by using the value of y to reconstruct Q_y(w), can recover some number of bits from the previously encoded message used as the seed to sample w from Q_y(w). Hence, the receiver has managed to recover some number of "bits-back."

It is notable for the property that continuous values for $w$ can be transmitted to arbitrary levels of precision without a penalty in expected message-length as the number of bits-back recovered in expectation increases with precision at exactly the same rate that the message-length needed to transmit $w$ does.

In particular, if $w$ is transmitted according to a coding-scheme optimized for a prior distribution $P(w)$, the expected number of bits required to transmit $w$ after netting out the bits-back is always the Kullback-Leibler divergence, $D_{\text{KL}}(Q\parallel P)$.

References

This article "Bits Back Encoding" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Bits Back Encoding. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

📰 Article(s) of the same category(ies)

• Avenade
• Ellie Malonzo (Violinist and Composer)
• Whive Protocol Core
• Catically
• Current events in school
• Siddiqa Lodge
• Utopunk

---