Sequential predictions based on algorithmic complexity

dc.contributor.authorHutter, Marcus
dc.date.accessioned2015-08-31T02:27:17Z
dc.date.available2015-08-31T02:27:17Z
dc.date.issued2006-02
dc.description.abstractThis paper studies sequence prediction based on the monotone Kolmogorov complexity Km = − log m, i.e. based on universal deterministic/one-part MDL. m is extremely close to Solomonoff’s universal prior M, the latter being an excellent predictor in deterministic as well as probabilistic environments, where performance is measured in terms of convergence of posteriors or losses. Despite this closeness to M, it is difficult to assess the prediction quality of m, since little is known about the closeness of their posteriors, which are the important quantities for prediction. We show that for deterministic computable environments, the “posterior” and losses of m converge, but rapid convergence could only be shown on-sequence; the off-sequence convergence can be slow. In probabilistic environments, neither the posterior nor the losses converge, in general.en_AU
dc.identifier.issn0022-0000en_AU
dc.identifier.urihttp://hdl.handle.net/1885/15035
dc.publisherElsevieren_AU
dc.rights© 2005 Elsevier Inc. http://www.sherpa.ac.uk/romeo/issn/0022-0000/..."Author's post-print on open access repository after an embargo period of between 12 months and 48 months" from SHERPA/RoMEO site (as at 31/08/15).en_AU
dc.rights.licenseCreative Commons Attribution licence
dc.rights.urihttp://creativecommons.org/licenses/ by-nc-nd/4.0/
dc.sourceJournal of Computer and System Sciencesen_AU
dc.titleSequential predictions based on algorithmic complexityen_AU
dc.typeJournal articleen_AU
dcterms.accessRightsOpen Access
local.bibliographicCitation.issue1en_AU
local.bibliographicCitation.lastpage117en_AU
local.bibliographicCitation.startpage95en_AU
local.contributor.affiliationHutter, M., Research School of Computer Science, The Australian National Universityen_AU
local.contributor.authoremailmarcus.hutter@anu.edu.auen_AU
local.contributor.authoruidu4350841en_AU
local.identifier.citationvolume72en_AU
local.identifier.doi10.1016/j.jcss.2005.07.001en_AU
local.identifier.uidSubmittedByu1005913en_AU
local.publisher.urlhttp://www.elsevier.com/en_AU
local.type.statusAccepted Versionen_AU

Downloads

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Hutter et al Sequential Predictions based on Algorithmic Complexity 2006.pdf
Size:
357.29 KB
Format:
Adobe Portable Document Format
Description:

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
884 B
Format:
Item-specific license agreed upon to submission
Description: