### Abstract

Prediction suffix trees (PST) provide a popular and effective tool for tasks such as compression, classification, and language modeling. In this paper we take a decision theoretic view of PSTs for the task of sequence prediction. Generalizing the notion of margin to PSTs, we present an online PST learning algorithm and derive a loss bound for it. The depth of the PST generated by this algorithm scales linearly with the length of the input. We then describe a self-bounded enhancement of our learning algorithm which automatically grows a bounded-depth PST.We also prove an analogous mistake-bound for the self-bounded algorithm. The result is an efficient algorithm that neither relies on a-priori assumptions on the shape or maximal depth of the target PST nor does it require any parameters. To our knowledge, this is the first provably-correct PST learning algorithm which generates a bounded-depth PST while being competitive with any fixed PST determined in hindsight.

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

Title of host publication | Advances in Neural Information Processing Systems 17 - Proceedings of the 2004 Conference, NIPS 2004 |

Publisher | Neural information processing systems foundation |

ISBN (Print) | 0262195348, 9780262195348 |

State | Published - Jan 1 2005 |

Externally published | Yes |

Event | 18th Annual Conference on Neural Information Processing Systems, NIPS 2004 - Vancouver, BC, Canada Duration: Dec 13 2004 → Dec 16 2004 |

### Publication series

Name | Advances in Neural Information Processing Systems |
---|---|

ISSN (Print) | 1049-5258 |

### Other

Other | 18th Annual Conference on Neural Information Processing Systems, NIPS 2004 |
---|---|

Country | Canada |

City | Vancouver, BC |

Period | 12/13/04 → 12/16/04 |

### All Science Journal Classification (ASJC) codes

- Computer Networks and Communications
- Information Systems
- Signal Processing

## Fingerprint Dive into the research topics of 'The power of selective memory: Self-bounded learning of prediction suffix trees'. Together they form a unique fingerprint.

## Cite this

*Advances in Neural Information Processing Systems 17 - Proceedings of the 2004 Conference, NIPS 2004*(Advances in Neural Information Processing Systems). Neural information processing systems foundation.