Test environment running 7.6.6

Cultural advice

The Australian National University acknowledges, celebrates and pays our respects to the Ngunnawal and Ngambri people of the Canberra region and to all First Nations Australians on whose traditional lands we meet and work, and whose cultures are among the oldest continuing cultures in human history.

Aboriginal and Torres Strait Islander peoples are advised that ANU Library collections may include images, names, voices, and other representations of deceased persons.

Material in the collection may contain terms, language or views that reflect the period in which the item was created and may be considered inappropriate today.

Convergence and error bounds for universal prediction of nonbinary sequences

Loading...
Thumbnail Image

Authors

Hutter, Marcus

Journal Title

Journal ISSN

Volume Title

Publisher

Springer Verlag

Abstract

Solomonoff’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.

Description

Citation

Source

Book Title

Machine Learning: ECML 2001 : 12th European Conference on Machine Learning, Freiburg, Germany, September 5-7, 2001. Proceedings (Lecture Notes in Computer Science)

Entity type

Access Statement

License Rights

Restricted until