{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/129323"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/129323","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Rho, Saeyoung."],"institution":"Massachusetts Institute of Technology","degree_name":"Master","degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Institute for Data, Systems, and Society","school":null,"contributors":[],"advisors":["Devavrat Shah."],"committee_chairs":[],"committee_members":[],"year":2020,"date_issued":"2020","date_published":"2020","updated_at":"2026-07-22T22:21:01Z","subjects":["Institute for Data, Systems, and Society.","Technology and Policy Program.","Electrical Engineering and Computer Science."],"languages":["eng"],"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."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1721.1/129323","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Devavrat Shah."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Institute for Data, Systems, and Society","TPP","Technology and Policy Program","ESD","Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science","IDSS","Massachusetts Institute of Technology. Engineering Systems Division"]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Institute for Data, Systems, and Society.","Technology and Policy Program.","Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Rho, Saeyoung."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2021-01-06T20:44:13Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2021-01-06T20:44:13Z"]},{"key":"dc:date.issued","label":"Date","values":["2020"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Institute for Data, Systems, and Society.","Technology and Policy Program.","Electrical Engineering and Computer Science."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["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."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1721.1/129323"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis: S.M. in Technology and Policy, Massachusetts Institute of Technology, School of Engineering, Institute for Data, Systems, and Society, Technology and Policy Program, September, 2020","Thesis: S.M. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, September, 2020","Cataloged from student-submitted PDF version of thesis.","Includes bibliographical references (pages 67-69)."]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["S.M. in Technology and Policy","S.M. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science"]},{"key":"dc:title","label":"Title","values":["Estimating lower bounds for time series prediction error"]}]}],"canonical_facts":{"dc:contributor.advisor":["Devavrat Shah."],"dc:contributor.department":["Massachusetts Institute of Technology. Institute for Data, Systems, and Society","TPP","Technology and Policy Program","ESD","Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science","IDSS","Massachusetts Institute of Technology. Engineering Systems Division"],"dc:contributor.other":["Massachusetts Institute of Technology. Institute for Data, Systems, and Society.","Technology and Policy Program.","Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."],"dc:creator":["Rho, Saeyoung."],"dc:date.accessioned":["2021-01-06T20:44:13Z"],"dc:date.available":["2021-01-06T20:44:13Z"],"dc:date.issued":["2020"],"dc:description":["Thesis: S.M. in Technology and Policy, Massachusetts Institute of Technology, School of Engineering, Institute for Data, Systems, and Society, Technology and Policy Program, September, 2020","Thesis: S.M. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, September, 2020","Cataloged from student-submitted PDF version of thesis.","Includes bibliographical references (pages 67-69)."],"dc:description.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."],"dc:description.degree":["S.M. in Technology and Policy","S.M. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science"],"dc:identifier.uri":["https://hdl.handle.net/1721.1/129323"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"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."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Institute for Data, Systems, and Society.","Technology and Policy Program.","Electrical Engineering and Computer Science."],"dc:title":["Estimating lower bounds for time series prediction error"],"dc:type":["Thesis"],"thesis:degree_name":["Master"]},"updated_at":"2026-07-22T22:21:01Z"}