### Abstract

We examine the sequential prediction of individual sequences under the square error loss using a competitive algorithm framework. Previous work has described a first-order algorithm that competes against a doubly exponential number of piecewise linear models. Using context trees, this firstorder algorithm achieves the performance of the best piecewise linear first-order model that can choose its prediction parameters observing the entire sequence in advance, uniformly, for any individual sequence, with a complexity only linear in the depth of the context tree. In this paper, we extend these results to a sequential predictor of order p > 1, that asymptotically performs as well as the best piecewise linear p^{th}-order model.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006 |

Publisher | IEEE Computer Society |

Pages | 141-146 |

Number of pages | 6 |

ISBN (Print) | 1424406560, 9781424406562 |

DOIs | |

State | Published - Jan 1 2006 |

Event | 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006 - Maynooth, Ireland Duration: Sep 6 2006 → Sep 8 2006 |

### Publication series

Name | Proceedings of the 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006 |
---|

### Other

Other | 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006 |
---|---|

Country | Ireland |

City | Maynooth |

Period | 9/6/06 → 9/8/06 |

### ASJC Scopus subject areas

- Artificial Intelligence
- Software
- Signal Processing

### Cite this

^{TH}-order least squares prediction. In

*Proceedings of the 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006*(pp. 141-146). [4053636] (Proceedings of the 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006). IEEE Computer Society. https://doi.org/10.1109/MLSP.2006.275537

**Universal context tree P ^{TH}-order least squares prediction.** / Singer, Andrew Carl; Kozat, Suleyman S.; Zeitler, Georg C.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

^{TH}-order least squares prediction. in

*Proceedings of the 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006.*, 4053636, Proceedings of the 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006, IEEE Computer Society, pp. 141-146, 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006, Maynooth, Ireland, 9/6/06. https://doi.org/10.1109/MLSP.2006.275537

^{TH}-order least squares prediction. In Proceedings of the 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006. IEEE Computer Society. 2006. p. 141-146. 4053636. (Proceedings of the 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006). https://doi.org/10.1109/MLSP.2006.275537

}

TY - GEN

T1 - Universal context tree PTH-order least squares prediction

AU - Singer, Andrew Carl

AU - Kozat, Suleyman S.

AU - Zeitler, Georg C.

PY - 2006/1/1

Y1 - 2006/1/1

N2 - We examine the sequential prediction of individual sequences under the square error loss using a competitive algorithm framework. Previous work has described a first-order algorithm that competes against a doubly exponential number of piecewise linear models. Using context trees, this firstorder algorithm achieves the performance of the best piecewise linear first-order model that can choose its prediction parameters observing the entire sequence in advance, uniformly, for any individual sequence, with a complexity only linear in the depth of the context tree. In this paper, we extend these results to a sequential predictor of order p > 1, that asymptotically performs as well as the best piecewise linear pth-order model.

AB - We examine the sequential prediction of individual sequences under the square error loss using a competitive algorithm framework. Previous work has described a first-order algorithm that competes against a doubly exponential number of piecewise linear models. Using context trees, this firstorder algorithm achieves the performance of the best piecewise linear first-order model that can choose its prediction parameters observing the entire sequence in advance, uniformly, for any individual sequence, with a complexity only linear in the depth of the context tree. In this paper, we extend these results to a sequential predictor of order p > 1, that asymptotically performs as well as the best piecewise linear pth-order model.

UR - http://www.scopus.com/inward/record.url?scp=38949086490&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38949086490&partnerID=8YFLogxK

U2 - 10.1109/MLSP.2006.275537

DO - 10.1109/MLSP.2006.275537

M3 - Conference contribution

AN - SCOPUS:38949086490

SN - 1424406560

SN - 9781424406562

T3 - Proceedings of the 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006

SP - 141

EP - 146

BT - Proceedings of the 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006

PB - IEEE Computer Society

ER -