Convergence and Error Bounds for Universal Prediction of Nonbinary Sequences

Simple item page
dc.creatorHutter, Marcus
dc.date2001-06-15
dc.date.accessioned2026-07-07T03:17:15Z
dc.date.available2026-07-07T03:17:15Z
dc.descriptionSolomonoff's uncomputable universal prediction scheme $ξ$ allows to predict the next symbol $x_k$ of a sequence $x_1...x_{k-1}$ for any Turing computable, but otherwise unknown, probabilistic environment $μ$. This scheme will be generalized to arbitrary environmental classes, which, among others, allows the construction of computable universal prediction schemes $ξ$. Convergence of $ξ$ to $μ$ in a conditional mean squared sense and with $μ$ probability 1 is proven. It is shown that the average number of prediction errors made by the universal $ξ$ scheme rapidly converges to those made by the best possible informed $μ$ scheme. The schemes, theorems and proofs are given for general finite alphabet, which results in additional complications as compared to the binary case. Several extensions of the presented theory and results are outlined. They include general loss functions and bounds, games of chance, infinite alphabet, partial and delayed prediction, classification, and more active systems.
dc.description11 LaTeX pages
dc.identifierhttps://arxiv.org/abs/cs/0106036
dc.identifierhttp://arxiv.org/abs/cs/0106036
dc.identifierLecture Notes in Artificial Intelligence (LNAI 2167), Proc. 12th Eurpean Conf. on Machine Learning (ECML) (2001) 239-250
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/30655
dc.subjectMachine Learning
dc.subjectArtificial Intelligence
dc.subjectComputational Complexity
dc.subjectProbability
dc.subjectF.2.3
dc.titleConvergence and Error Bounds for Universal Prediction of Nonbinary Sequences
dc.typetext

Files

Collections

arXiv