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

摘要

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.)