Compression-based methods for nonparametric density estimation, on-line prediction, regression and classification for time series

2007/01/07 by Boris Ryabko, Ryabko, Boris · 1 citation
Computer Science · Mathematics · #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT

paper · pdf · doi:10.48550/arxiv.cs/0701036

arxiv created 2007/11/01 · arxiv updated 2009/12/01

Abstract

We address the problem of nonparametric estimation of characteristics for stationary and ergodic time series. We consider finite-alphabet time series and real-valued ones and the following four problems: i) estimation of the (limiting) probability (or estimation of the density for real-valued time series), ii) on-line prediction, iii) regression and iv) classification (or so-called problems with side information). We show that so-called archivers (or data compressors) can be used as a tool for solving these problems. In particular, firstly, it is proven that any so-called universal code (or universal data compressor) 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 till the Shannon entropy of the source.) And, secondly, we show experimentally that estimates, which are based on practically used methods of data compression, have a reasonable precision.

Cited by

• LZ Penalty: An information-theoretic repetition penalty for autoregressive language models

Related

• Applications of Universal Source Coding to Statistical Analysis of Time Series
• Lossless Compression of Time Series Data: A Comparative Study
• Universal Codes as a Basis for Time Series Testing
• Lossless Compression: A New Benchmark for Time Series Model Evaluation
• Nonparametric Estimation and On-Line Prediction for General Stationary Ergodic Sources