Self-Bounded Prediction Suffix Tree via Approximate String Matching

2018-02-09 · ICML 2018 7 · Dongwoo Kim, Christian Walder

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.

📄 PDF Abstract BibTeX arXiv:1802.03184

Code (0)

등록된 구현이 없습니다.

Tasks

Prediction

Dynamic-Depth Context Tree Weighting

2017-12-01 · NeurIPS 2017 12 · Joao V. Messias, Shimon Whiteson

Reinforcement learning (RL) in partially observable settings is challenging because the agent’s observations are not Markov. Recently proposed methods can learn variable-order Markov models of the underlying process but …

Reinforcement Learning Reinforcement Learning (RL)Time Series Time Series Analysis+1

Suffix Trees as Language Models

2012-05-01 · LREC 2012 5 · Casey Redd Kennington, Martin Kay, Annemarie Friedrich

Suffix trees are data structures that can be used to index a corpus. In this paper, we explore how some properties of suffix trees naturally provide the functionality of an n-gram language model with variable n. We expla…

Information Retrieval Language Modeling Language Modelling Machine Translation+2

An Event based Prediction Suffix Tree

2023-10-20 · Evie Andrew, Travis Monk, André van Schaik

This article introduces the Event based Prediction Suffix Tree (EPST), a biologically inspired, event-based prediction algorithm. The EPST learns a model online based on the statistics of an event based input and can mak…

Anomaly Detection One-Shot Learning Prediction

Advances in Learning Bayesian Networks of Bounded Treewidth

2014-06-05 · NeurIPS 2014 12 · Siqi Nie, Denis Deratani Maua, Cassio Polpo de Campos, Qiang Ji

This work presents novel algorithms for learning Bayesian network structures with bounded treewidth. Both exact and approximate methods are developed. The exact method combines mixed-integer linear programming formulatio…

Complex Event Forecasting with Prediction Suffix Trees: Extended Technical Report

2021-09-01 · Elias Alevizos, Alexander Artikis, Georgios Paliouras

Complex Event Recognition (CER) systems have become popular in the past two decades due to their ability to "instantly" detect patterns on real-time streams of events. However, there is a lack of methods for forecasting …