Complexity Monotone in Conditions and Future Prediction Errors

Alexey V. Chernov, Marcus Hutter, Jürgen Schmidhuber

TL;DR

This paper tackles the challenge of predicting future events in a sequence when we've already observed some past data. The authors introduce a new type of algorithmic complexity that's "monotone in its condition," meaning it gets simpler as we observe more data. This new measure leads to tighter bounds on prediction errors, improving upon classic results from Solomonoff.

What Problem Does This Paper Address?

Imagine you're trying to predict the weather, stock prices, or any complex sequence of events. You have a "true" underlying process generating these events, but you don't know exactly what it is. A universal predictor, like Solomonoff's, can make good predictions by considering all possible generating processes, weighted by their complexity. Solomonoff showed that the total number of prediction errors is bounded by the algorithmic complexity of the true process.

However, what if you've already seen a chunk of the sequence (say, the last week's weather)? Intuitively, this past data should help you make better future predictions. The problem this paper addresses is how to quantify this improvement. Specifically, it aims to bound the future prediction error, given past observations, using a measure that reflects how much information the past data provides about the true process. The challenge is that standard measures of complexity don't always behave nicely when conditioned on observed data, especially when that data is not perfectly "typical."

Methods

The core of the paper is the development of a new complexity measure: complexity monotone in conditions, denoted as $K^*(y|x^*)$. This is a variant of Kolmogorov complexity, which measures the length of the shortest program needed to generate a string $y$ given a condition $x$. The "monotone in its condition" aspect means that if we have a condition $x$ and observe more data $z$, the complexity of predicting $y$ given $xz$ ($K^*(y|xz^*)$) is no worse than predicting $y$ given just $x$ ($K^*(y|x^*)$). This aligns with the intuition that more data should not hurt our prediction capabilities.

The authors derive two main bounds on future prediction errors. The first bound uses a complexity related to the length of the observed data. The second, finer bound, uses the new monotone complexity and the "randomness deficiency" of the observed data. The randomness deficiency ($d_\mu(x)$) quantifies how "typical" a sequence $x$ is with respect to a true distribution $\mu$. Sequences with low randomness deficiency are considered more "random" or "typical."

Datasets

Not discussed in the paper. The paper deals with theoretical bounds on prediction performance for any computable sequence, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • More data, better predictions: The fundamental intuition that observing more data should improve future predictions is formally quantified.
  • A new complexity measure: The introduction of "complexity monotone in conditions" ($K^*$) is a key contribution. This measure is designed to behave well when conditioned on observed data, unlike standard complexities which can sometimes increase unexpectedly.
  • Randomness deficiency matters: The paper highlights the importance of the "randomness deficiency" of observed data. Sequences that are less "random" (higher deficiency) can pose challenges for prediction, and this deficiency term appears in the bounds.
  • Tighter bounds: The new complexity measure leads to improved bounds on future prediction errors, especially in cases where past data might not be perfectly typical. This is demonstrated by showing that the new bounds can be significantly better than older, unconditional bounds in specific scenarios.

Key Results

The paper presents two main theorems providing bounds on the future prediction error of Solomonoff's universal predictor $M$, given past observations $x$.

  • Theorem 1: Provides a bound on the future error in terms of the complexity of the true distribution $\mu$ conditioned on $x$, plus the complexity of the length of $x$.
  • Theorem 3: Introduces the monotone complexity $K^*$ and provides a tighter bound on the future error, using $K^*$ and the randomness deficiency of $x$. This bound is shown to be more robust and can be exponentially better than previous bounds in certain cases, particularly when dealing with deterministic environments. For example, for a specific deterministic sequence, the new bound is $K(K(n))$ instead of $K(n)$, which is a significant improvement.

Limitations and Future Work

  • General Bayesian Mixtures: The authors pose the question of whether similar posterior bounds can be derived for general Bayesian mixtures (not just Solomonoff's universal prior).
  • Online Classification: They suggest exploring how these concepts might apply to online classification problems, where predictions are made based on observed data and associated labels.
  • Asymptotic Behavior of $K^*$: A key open problem is to understand the asymptotic behavior of $K^*$ for "most" sequences and whether it can be bounded by an absolute constant.
  • Equality of Complexity Definitions: The authors conjecture that their new complexity definitions are equivalent (up to an additive constant) to those based on optimal machines, and proving this would be valuable.
  • Class of Sequences with Fast Convergence: They raise the problem of identifying a wide class of sequences for which the future prediction error tails ($D_{l:\infty}$) tend to zero quickly, suggesting that $\mu$-random sequences might be a good candidate.

Summary updated

Abstract

We bound the future loss when predicting any (computably) stochastic sequence online. Solomonoff finitely bounded the total deviation of his universal predictor $M$ from the true distribution $mu$ by the algorithmic complexity of $mu$. Here we assume we are at a time $t>1$ and already observed $x=x_1...x_t$. We bound the future prediction performance on $x_{t+1}x_{t+2}...$ by a new variant of algorithmic complexity of $mu$ given $x$, plus the complexity of the randomness deficiency of $x$. The new complexity is monotone in its condition in the sense that this complexity can only decrease if the condition is prolonged. We also briefly discuss potential generalizations to Bayesian model classes and to classification problems.
BibTeX
@inproceedings{chernov2006complexity,
  author = {Alexey V. Chernov and Marcus Hutter and Jürgen Schmidhuber},
  title = {{Complexity Monotone in Conditions and Future Prediction Errors}},
  booktitle = {Kolmogorov Complexity and Applications},
  year = {2006},
  url = {https://openreview.net/forum?id=wW8QQXrW7Kz},
}
Figure