Wytock and Kolter take on a challenging problem in time series analysis – segmentation. The goal is to partition the time series into subsets of observations which can be regarded as generated by the same distribution. A particular example is the popular hidden Markov model, in which the partition is given by the value of a latent variable that describes the state of the system.
The authors develop an approach to probabilistic segmentation and modeling of time series data that relies on convexity. The approach builds upon recent advances in multivariate total variation regularization. Their proposal seeks to estimate a separate set of parameters for the distribution over the observations at each time point, but with an additional penalty term that reflects prior belief (which is well supported by many applications) that the parameters tend to remain constant over time rather than changing. They propose efficient optimization methods for solving the resulting (large) optimization problems, and a two-stage procedure for estimating recurring clusters under such models, based upon kernel density estimation. The method exploits convexity, which counteracts a tendency to converge to local optima. Finally, they illustrate the ideas by application to a number of real-world segmentation tasks. They find that their methods often perform as well as or better than existing latent variable models, while being substantially easier to estimate.
Read the paper:
Probabilistic Segmentation via Total Variation Regularization. Matt Wytock and J. Zico Kolter.