The Complexity and Effectiveness of Prediction Algorithms |
| |
Affiliation: | Department of Applied Mathematics and Cybernetics, Novosibirsk Telecommunication Inst., Kirov Str.-86, Novosibirsk - 102, 630102, Russia |
| |
Abstract: | The problem of predicting an arbitrary sequence x1x2x3 · · · is considered with xt + 1 being predicted from an analysis of the word x1x2 · · · xt. There are no presumptions concerning the probability structure on this process. The relation between prediction effectiveness and Kolmogorov complexity is established. Then the Hausdorff dimension of sets of sequences for which effective methods of prediction exist is estimated. The prediction method which is asymptotically superior to other arbitrary ones realized by finite automata is constructed. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|