Self-Bounded Prediction Suffix Tree via Approximate String Matching

Dongwoo Kim, Christian Walder
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:2659-2667, 2018.

Abstract

Prediction suffix trees (PST) provide an effective tool for sequence modelling and prediction. Current prediction techniques for PSTs rely on exact matching between the suffix of the current sequence and the previously observed sequence. We present a provably correct algorithm for learning a PST with approximate suffix matching by relaxing the exact matching condition. We then present a self-bounded enhancement of our algorithm where the depth of suffix tree grows automatically in response to the model performance on a training sequence. Through experiments on synthetic datasets as well as three real-world datasets, we show that the approximate matching PST results in better predictive performance than the other variants of PST.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-kim18c, title = {Self-Bounded Prediction Suffix Tree via Approximate String Matching}, author = {Kim, Dongwoo and Walder, Christian}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {2659--2667}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/kim18c/kim18c.pdf}, url = {https://proceedings.mlr.press/v80/kim18c.html}, abstract = {Prediction suffix trees (PST) provide an effective tool for sequence modelling and prediction. Current prediction techniques for PSTs rely on exact matching between the suffix of the current sequence and the previously observed sequence. We present a provably correct algorithm for learning a PST with approximate suffix matching by relaxing the exact matching condition. We then present a self-bounded enhancement of our algorithm where the depth of suffix tree grows automatically in response to the model performance on a training sequence. Through experiments on synthetic datasets as well as three real-world datasets, we show that the approximate matching PST results in better predictive performance than the other variants of PST.} }
Endnote
%0 Conference Paper %T Self-Bounded Prediction Suffix Tree via Approximate String Matching %A Dongwoo Kim %A Christian Walder %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-kim18c %I PMLR %P 2659--2667 %U https://proceedings.mlr.press/v80/kim18c.html %V 80 %X Prediction suffix trees (PST) provide an effective tool for sequence modelling and prediction. Current prediction techniques for PSTs rely on exact matching between the suffix of the current sequence and the previously observed sequence. We present a provably correct algorithm for learning a PST with approximate suffix matching by relaxing the exact matching condition. We then present a self-bounded enhancement of our algorithm where the depth of suffix tree grows automatically in response to the model performance on a training sequence. Through experiments on synthetic datasets as well as three real-world datasets, we show that the approximate matching PST results in better predictive performance than the other variants of PST.
APA
Kim, D. & Walder, C.. (2018). Self-Bounded Prediction Suffix Tree via Approximate String Matching. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:2659-2667 Available from https://proceedings.mlr.press/v80/kim18c.html.

Related Material