Abstract
We investigate the problem of sequential prediction of individual sequences using a competitive algorithm approach. We have previously developed prediction algorithms that are universal with respect to the class of all linear predictors, such that the prediction algorithm competes against a continuous class of prediction algorithms, under the square error loss. In this paper, we introduce the use of a "context tree," to compete against a doubly exponential number of piecewise linear models. We use the context tree to achieve the performance of the best piecewise linear model that can choose its partition of the real line and real-valued prediction parameters, based on observing the entire sequence in advance, for the square error loss, uniformly, for any individual sequence. This performance is achieved with a prediction algorithm whose complexity is only linear in the depth of the context tree.
| Original language | English (US) |
|---|---|
| Title of host publication | Proceedings - 2006 IEEE International Symposium on Information Theory, ISIT 2006 |
| Pages | 426-430 |
| Number of pages | 5 |
| DOIs | |
| State | Published - Dec 1 2006 |
| Event | 2006 IEEE International Symposium on Information Theory, ISIT 2006 - Seattle, WA, United States Duration: Jul 9 2006 → Jul 14 2006 |
Publication series
| Name | IEEE International Symposium on Information Theory - Proceedings |
|---|---|
| ISSN (Print) | 2157-8101 |
Other
| Other | 2006 IEEE International Symposium on Information Theory, ISIT 2006 |
|---|---|
| Country | United States |
| City | Seattle, WA |
| Period | 7/9/06 → 7/14/06 |
Fingerprint
ASJC Scopus subject areas
- Theoretical Computer Science
- Information Systems
- Modeling and Simulation
- Applied Mathematics
Cite this
Universal context tree least squares prediction. / Singer, Andrew Carl; Kozat, Suleyman S.
Proceedings - 2006 IEEE International Symposium on Information Theory, ISIT 2006. 2006. p. 426-430 4035996 (IEEE International Symposium on Information Theory - Proceedings).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
}
TY - GEN
T1 - Universal context tree least squares prediction
AU - Singer, Andrew Carl
AU - Kozat, Suleyman S.
PY - 2006/12/1
Y1 - 2006/12/1
N2 - We investigate the problem of sequential prediction of individual sequences using a competitive algorithm approach. We have previously developed prediction algorithms that are universal with respect to the class of all linear predictors, such that the prediction algorithm competes against a continuous class of prediction algorithms, under the square error loss. In this paper, we introduce the use of a "context tree," to compete against a doubly exponential number of piecewise linear models. We use the context tree to achieve the performance of the best piecewise linear model that can choose its partition of the real line and real-valued prediction parameters, based on observing the entire sequence in advance, for the square error loss, uniformly, for any individual sequence. This performance is achieved with a prediction algorithm whose complexity is only linear in the depth of the context tree.
AB - We investigate the problem of sequential prediction of individual sequences using a competitive algorithm approach. We have previously developed prediction algorithms that are universal with respect to the class of all linear predictors, such that the prediction algorithm competes against a continuous class of prediction algorithms, under the square error loss. In this paper, we introduce the use of a "context tree," to compete against a doubly exponential number of piecewise linear models. We use the context tree to achieve the performance of the best piecewise linear model that can choose its partition of the real line and real-valued prediction parameters, based on observing the entire sequence in advance, for the square error loss, uniformly, for any individual sequence. This performance is achieved with a prediction algorithm whose complexity is only linear in the depth of the context tree.
UR - http://www.scopus.com/inward/record.url?scp=39049154885&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=39049154885&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2006.261704
DO - 10.1109/ISIT.2006.261704
M3 - Conference contribution
AN - SCOPUS:39049154885
SN - 1424405041
SN - 9781424405046
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 426
EP - 430
BT - Proceedings - 2006 IEEE International Symposium on Information Theory, ISIT 2006
ER -