Deformable Markov model templates for time-series pattern matching

Abstract

This paper addresses the problem of automatically detecting specific patterns or shapes in time-series data. A novel and exible approach is proposed based on segmental semi-Markov models. Unlike dynamic time-warping or template-matching, the proposed framework provides a systematic and coherent framework for leveraging both prior knowledge and training data. The pattern of interest is modeled as a K-state segmental hidden Markov model where each state is responsible for the generation of a component of the overall shape using a state-based regression function. The distance (in time) between segments is modeled as a semi-Markov process, allowing exible deformation of time. The model can be constructed from a single training example. Recognition of a pattern in a new time series is achieved by a recursive Viterbi-like algorithm which scales linearly in the length of the sequence. The method is successfully demonstrated on real data sets, including an application to end-point detection in s...