Estimating lower bounds for time series prediction error

Abstract

Research on how to evaluate the time series prediction algorithms are relatively under investigated compared to those to develop prediction algorithms. This research presents a way to estimate lower bounds for a time series prediction error by utilizing the conditional entropy rate, which allows us to take the inherent difficulty of a problem into account. The main focus of this research is on a discrete time series composed of discrete random variables, and stationarity of the time series is assumed. In this thesis, the lower bound is estimated based on the Fano's inequality, which shows the relationship between the conditional entropy rate and prediction error. Therefore, a method to approximate the entropy rate using the Lempel-Ziv compressor is suggested as a subroutine. Also, a discretization method is introduced to adopt this approach to real-valued sequences. Finally, the method is validated for both discrete and continuous distributions, and applications with real-world datasets are demonstrated. The proposed error lower bound can serve as an objective criterion to evaluate the current status of the algorithm and has the potential to aid the technocratic knowledge assessment process in science that involves discrete time series prediction problem.