Predictive complexity

Predictive complexity is a generalization of Kolmogorov complexity to a wide class of on-line prediction games (including both prediction and decision-making scenarios). Some of the most popular on-line prediction games are:

  • The log-loss game. It formalizes the processes of probability forecasting and loss-less compression. Predictive complexity for this game is a variant of Kolmogorov complexity (the logarithm of the a priori semimeasure).
  • The square-loss game. This game formalizes statistical regression done in the on-line fashion.
  • Cover's game. Formalizes the process of investing in a stock market when only long positions are allowed.
  • The long-short game. A version of the previous game when short positions are also allowed.

The area of potential applications of predictive complexity is very wide (such as pattern recognition, regression, financial portfolio management, etc.), but the research carried out so far has been mainly directed towards solving fundamental theoretical problems. These are some interesting results (by Yuri Kalnishkan and Mikhail Vyugin):

  • The criterion of existence of predictive complexity for binary games: the predictive complexity only exists for mixable games.
  • The number of easy-to-predict binary sequences is exponentially small, with a known base of the exponent.

References

  • Vladimir Vovk. Probability theory for the Brier game. This and next papers introduce predictive complexity. Published in the ALT 1997 proceedings and Theoretical Computer Science 261, 57–79, 2001.
  • Vladimir Vovk and Chris Watkins. Universal portfolio selection. This and previous papers introduce predictive complexity. Published in the COLT 1998 proceedings, pp. 12–13.
  • Yuri Kalnishkan. General linear relations between different types of predictive complexity. This paper gives a general method for establishing tight linear inequalities between predictive complexities. Published in the ALT 1999 proceedings and Theoretical Computer Science 271, 181–200, 2002.
  • Yuri Kalnishkan, Vladimir Vovk, and Mikhail Vyugin. Loss functions, complexities and the Legendre transformation. This paper shows how the loss function can be extracted (up to the parameterization) from the predictive complexity. It appears that convex analysis (via, e.g., the notion of generalized entropy) plays a fundamental role in the theory of predictive complexity. Published in the ALT 2001 proceedings and Theoretical Computer Science 313, 195–207, 2004.
  • Yuri Kalnishkan and Mikhail Vyugin. Mixability and the existence of weak complexities. By definition, predictive complexity is the best, with accuracy O(1), upper semicomputable superloss process. For some important games predictive complexity in this sense does not exist. This paper shows that for a wide class of games there is "weak predictive complexity", where O(1) is replaced by O(sqrt(n)), n being the length of the data sequence. Published in the COLT 2002 proceedings.
  • Yuri Kalnishkan and Mikhail Vyugin. On the absence of predictive complexity for some games. This paper proves the absence of predictive complexity (defined, as usual, to within an additive constant) in the case where the curvature of the loss function vanishes at an interior point. This result is less general than the criterion in [8], but it gives an estimate of the accuracy with which predictive complexity exists. Published in the ALT 2002 proceedings.
  • Yuri Kalnishkan, Vladimir Vovk, and Mikhail Vyugin. How many strings are easy to predict? The result of this paper generalizes the incompressibility property of Kolmogorov complexity. Published in the COLT 2003 proceedings and Information and Computation 201, 55–71, 2005.
  • Yuri Kalnishkan, Vladimir Vovk, and Mikhail Vyugin. A criterion for the existence of predictive complexity for binary games. It is well known that there exists a universal (i.e., optimal to within an additive constant if allowed to work infinitely long) algorithm for lossless data compression (Kolmogorov, Levin). The game of lossless compression is an example of an on-line prediction game; for some other on-line prediction games (such as the simple prediction game) a universal algorithm is known not to exist. This paper gives an analytic characterisation of those binary on-line prediction games for which a universal prediction algorithm exists. Published in the ALT 2004 proceedings.
  • Yuri Kalnishkan, Vladimir Vovk, and Mikhail Vyugin. Generalized entropy and asymptotic complexities of languages. This paper introduces the concept of asymptotic complexity of languages is introduced. This concept formalises the notion of learnability in a particular environment and generalises Lutz and Fortnow's concepts of predictability and dimension. Then asymptotic complexities in different prediction environments are compared by describing the set of all pairs of asymptotic complexities with respect to different environments. A geometric characterisation in terms of generalised entropies is obtained and thus the results of Lutz and Fortnow are generalised. The conference version of this paper is published in the COLT 2007 proceedings.