An Universal Predictor Based on Pattern Matching: Preliminary results 1
Philippe Jacquet, Wojciech Szpankowski, Izydor Apostoł · Mathematics and Computer Science · 2000
We consider here an universal predictor based on pattern matching. For a given string x 1 , x 2 …, x n , the predictor will guess the next symbol x n+1 in such a way that the prediction error tends to zero as n →∞ provided the string x n 1 = x 1 , x 2 , …, x n , is generated by a mixing source. We shall prove that the rate of convergence of the prediction error is 0(n -ε ) for any ε > 0. In this preliminary version, we only prove our results for memoryless sources and a sketch for mixing sources. However, we indicate that our algorithm can predict equally successfully the next k symbols as long as k= 0(1). These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.