On the sysRatio and its critical point
What is the relationship between the complexity of a learner and the randomness of his mistakes? This question was posed in Ratsaby (2009) [8] who showed that the more complex the learner the higher the possibility that his mistakes deviate from a true random sequence. In the current paper we report on an empirical investigation of this problem. We investigate two characteristics of randomness, the stochastic and algorithmic complexity of the binary sequence of mistakes. A learner with a Markov model of order k is trained on a finite binary sequence produced by a Markov source of order k* and is tested on a different random sequence. As a measure of learner's complexity we define a quantity called the sysRatio, denoted by rho, which is the ratio between the compressed and uncompressed lengths of the binary string whose ith bit represents the maximum a posteriori decision made at state i of the learner's model. The quantity rho is a measure of information density. The main result of the paper shows that this ratio is crucial in answering the above posed question. The result indicates that there is a critical threshold rho* such that when rho   rho*, the characteristics of the mistake sequence changes sharply towards a high Delta and high variance in algorithmic complexity. It is also shown that the quantity rho is inversely proportional to k and the value of rho* corresponds to the value k*. This is the point where the learner's model becomes too simple and is unable to approximate the Bayes optimal decision. Here the characteristics of the mistake sequence change sharply. (C) 2010 Elsevier Ltd. All rights reserved.
description complexity binary sequence prediction