An adaptive compression algorithm in a deterministic world
2013 (English)In: Algorithmic Probability and Friends: Bayesian Prediction and Artificial Intelligence, Springer Berlin/Heidelberg, 2013, 299-305 p.Conference paper (Refereed)
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.
Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2013. 299-305 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 7070
Computer and Information Science
IdentifiersURN: urn:nbn:se:uu:diva-236271DOI: 10.1007/978-3-642-44958-1_23ISI: 000342696800023ISBN: 978-3-642-44957-4OAI: oai:DiVA.org:uu-236271DiVA: diva2:764159
Ray Solomonoff 85th Memorial Conference, November 30 – December 2, 2011, Melbourne, Australia