Probabilistic time series classification

Abstract

In this thesis, we investigate probabilistic methods for time series classification and clustering problems. For various classification and clustering tasks, we survey different time series models such as Markov models, hidden Markov models (HMM), mixture of Markov models and mixture of Hidden Markov models. We also investigate discriminative versions of Markov models and Hidden Markov models. The novel contribution of this thesis is the derivation of algorithms for learning mixtures of Markov models and mixtures of hidden Markov models. Mixture models are special latent variable models that require the usage of local search heuristics such as Expectation Maximization (EM) algorithm, that can only provide locally optimal solutions. In contrast, we make use of the spectral learning algorithms, recently popularized in the machine learning community. Under mild assumptions, spectral learning algorithms are able to estimate the parameters in latent variable models by solving systems of equations via eigendecompositions of matrices or tensors of observable moments. As such, spectral methods can be viewed as an instance of the method of moments for parameter estimation, an alternative to maximum likelihood. The popularity stems from the fact that these methods provide a computationally cheap and local optima free alternative to EM. We conduct classification experiments on human action sequences extracted from videos, clustering experiments on motion capture data and network traffic data to illustrate the viability of our approach. We conclude that the spectral methods are a practical and useful alternative in terms of computational effort and solution quality to standard iterative techniques such as EM in many application areas.