Abstract

The identification of useful temporal structure in discrete time series is an important component of algorithms used for many tasks in statistical inference and machine learning. Most early approaches developed were ineffective in practice, because the amount of data required for reliable modeling grew exponentially with memory length. On the other hand, many of the more modern methodologies that make use of more flexible and parsimonious models, result in algorithms that do not scale well and are computationally ineffective for larger data sets.

We will discuss a class of novel methodological tools for effective Bayesian inference for general discrete time series, which offer promising results on both small and big data. Our starting point is the development of a rich class of Bayesian hierarchical models for variable-memory Markov chains. The particular prior structure we adopt makes it possible to design effective, linear-time algorithms that can compute most of the important features of the resulting posterior and predictive distributions without resorting to simulation.

We have applied the resulting tools to numerous application-specific tasks (including on-line prediction, segmentation, classification, anomaly detection, entropy estimation, and causality testing) on data sets from a very broad range of applications. Results on both simulated and real data will be presented, with an emphasis on data sets from neuroscience and genetics studies.