Skip navigation
Skip navigation

On the Convergence Speed of MDL Predictions for Bernoulli Sequences

Poland, Jan; Hutter, Marcus

Description

We consider the Minimum Description Length principle for online sequence prediction. If the underlying model class is discrete, then the total expected square loss is a particularly interesting performance measure: (a) this quantity is bounded, implying convergence with probability one, and (b) it additionally specifies a rate of convergence. Generally, for MDL only exponential loss bounds hold, as opposed to the linear bounds for a Bayes mixture. We show that this is even the case if the model...[Show more]

dc.contributor.authorPoland, Jan
dc.contributor.authorHutter, Marcus
dc.coverage.spatialPadova Italy
dc.date.accessioned2015-12-10T22:43:06Z
dc.date.createdOctober 2-5 2004
dc.identifier.isbn3540233563
dc.identifier.urihttp://hdl.handle.net/1885/58048
dc.description.abstractWe consider the Minimum Description Length principle for online sequence prediction. If the underlying model class is discrete, then the total expected square loss is a particularly interesting performance measure: (a) this quantity is bounded, implying convergence with probability one, and (b) it additionally specifies a rate of convergence. Generally, for MDL only exponential loss bounds hold, as opposed to the linear bounds for a Bayes mixture. We show that this is even the case if the model class contains only Bernoulli distributions. We derive a new upper bound on the prediction error for countable Bernoulli classes. This implies a small bound (comparable to the one for Bayes mixtures) for certain important model classes. The results apply to many Machine Learning tasks including classification and hypothesis testing. We provide arguments that our theorems generalize to countable classes of i.i.d. models.
dc.publisherSpringer
dc.relation.ispartofseriesInternational Conference on Algorithmic Learning Theory (ALT 2004)
dc.rightsCopyright Information: © Springer-Verlag Berlin Heidelberg 2004. http://www.sherpa.ac.uk/romeo/issn/0302-9743/..."Author's post-print on any open access repository after 12 months after publication" from SHERPA/RoMEO site (as at 1/09/15).
dc.sourceAlgorithmic Learning Theory: 15th International Conference, ALT 2004, Pedova, Italy, October 2004, Proceedings
dc.source.urihttp://www.informatik.uni-trier.de/~ley/db/conf/alt/alt2004.html
dc.source.urihttp://springerlink.metapress.com/content/95ftf6ldte1cfj5k/fulltext.pdf
dc.subjectKeywords: Algorithms; Approximation theory; Computational complexity; Error analysis; Forecasting; Learning systems; Mathematical models; Probability; Turing machines; Bayes mixtures; Bernoulli distributions; Kolmogorov complexity; Minimum description length (MDL)
dc.titleOn the Convergence Speed of MDL Predictions for Bernoulli Sequences
dc.typeConference paper
local.description.notesImported from ARIES
local.description.refereedYes
dc.date.issued2004
local.identifier.absfor080299 - Computation Theory and Mathematics not elsewhere classified
local.identifier.ariespublicationu8803936xPUB425
local.type.statusPublished Version
local.contributor.affiliationPoland, Jan, IDSIA-Istituto Dalle Molle di Studi sull Intelligenza Artificiale
local.contributor.affiliationHutter, Marcus, College of Engineering and Computer Science, ANU
local.description.embargo2037-12-31
local.bibliographicCitation.startpage294
local.bibliographicCitation.lastpage308
dc.date.updated2016-02-24T11:44:58Z
local.identifier.scopusID2-s2.0-22944458209
CollectionsANU Research Publications

Download

File Description SizeFormat Image
01_Poland_On_the_Convergence_Speed_of_2004.pdf351.16 kBAdobe PDF    Request a copy


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator