Computer Science – Artificial Intelligence
Scientific paper
2001-01-21
Proc. 18th Int. Conf. on Machine Learning ICML (2001) 210-217
Computer Science
Artificial Intelligence
8 two-column pages, LaTeX2e
Scientific paper
The Bayesian framework is ideally suited for induction problems. The probability of observing $x_t$ at time $t$, given past observations $x_1...x_{t-1}$ can be computed with Bayes' rule if the true distribution $\mu$ of the sequences $x_1x_2x_3...$ is known. The problem, however, is that in many cases one does not even have a reasonable estimate of the true distribution. In order to overcome this problem a universal distribution $\xi$ is defined as a weighted sum of distributions $\mu_i\inM$, where $M$ is any countable set of distributions including $\mu$. This is a generalization of Solomonoff induction, in which $M$ is the set of all enumerable semi-measures. Systems which predict $y_t$, given $x_1...x_{t-1}$ and which receive loss $l_{x_t y_t}$ if $x_t$ is the true next symbol of the sequence are considered. It is proven that using the universal $\xi$ as a prior is nearly as good as using the unknown true distribution $\mu$. Furthermore, games of chance, defined as a sequence of bets, observations, and rewards are studied. The time needed to reach the winning zone is bounded in terms of the relative entropy of $\mu$ and $\xi$. Extensions to arbitrary alphabets, partial and delayed prediction, and more active systems are discussed.
No associations
LandOfFree
General Loss Bounds for Universal Sequence Prediction does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with General Loss Bounds for Universal Sequence Prediction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and General Loss Bounds for Universal Sequence Prediction will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-655808