Applications of Kolmogorov Complexity and Universal Codes to Nonparametric Estimation of Characteristics of Time Series

Article type: Research Article

Authors: Ryabko, Boris

Affiliations: Siberian State University of Telecommunications and Informatics, Institute of Computational Technologies of Siberian Branch of Russian Academy of Science Kirov Street, 86, 630102, Novosibirsk, Russia. E-mail: boris@ryabko.net

Abstract: We consider finite-alphabet and real-valued time series and the following four problems: i) estimation of the (limiting) probability P(x_0 … x_s) for every s and each sequence x_0 … x_s of letters from the process alphabet (or estimation of the density p(x_0, …, x_s) for real-valued time series), ii) the so-called on-line prediction, where the conditional probability P(x_{t+1}∣x_1x_2 … x_t) (or the conditional density P(x_{t+1}∣x_1x_2 … x_t)) should be estimated, where x_1x_2 … x_t are given, iii) regression and iv) classification (or so-called problems with side information). We show that Kolmogorov complexity (KC) and universal codes (or universal data compressors), whose codeword length can be considered as an estimation of KC, can be used as a basis for constructing asymptotically optimal methods for the above problems. (By definition, a universal code can "compress" any sequence generated by a stationary and ergodic source asymptotically to the Shannon entropy of the source.)

Keywords: time series, nonparametric estimation, universal coding, data compression, on-line prediction, Shannon entropy, stationary and ergodic process, regression

Journal: Fundamenta Informaticae, vol. 83, no. 1-2, pp. 177-196, 2008