An Adaptive Compression Algorithm in a Deterministic World

摘要

Assume that we live in a deterministic world, we ask ourselves which place the device of randomness still may have, even in case that there is no philosophical incentive for it. This note argues that improved accuracy may be achieved when modeling the (deterministic) residuals of the best model of a certain complexity as 'random'. In order to make this statement precise, the setting of adaptive compression is considered: (1) accuracy is understood in terms of codelength, and (2) the 'random device' relates to Solomonoff's Algorithmic Probability (ALP) via arithmetic coding. The contribution of this letter is threefold: (a) the proposed adaptive coding scheme possesses interesting behavior in terms of its regret bound, and (b) a mathematical characterization of a deterministic world assumption is given, (c) The previous issues then facilitate the derivation of the Randomness- Complexity (RC) frontier of the given algorithm.