Estimating lower bounds for time series prediction error

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.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Institute for Data, Systems, and Society

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2020

Author dc:creator

• Rho, Saeyoung.

Advisor dc:contributor.advisor

• Devavrat Shah.

• Institute for Data, Systems, and Society.
• Technology and Policy Program.
• Electrical Engineering and Computer Science.

Statement dc:rights

• MIT theses may be protected by copyright. Please reuse MIT thesis content according to the MIT Libraries Permissions Policy, which is available through the URL provided.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/129323

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/129323