Pattern matching

For certain sensor and endpoint problems, the endpoint is indicated by a distinctive pattern or waveform, rather than a simple change-point (e.g., see Fig. 2). To detect such a waveform inside a (much longer) time series $y_1 y_2 \ldots y_t \ldots$, an obvious approach would be to match the model against every subwindow $y_i y_{i+1} \ldots y_j$, find the most likely state sequence $s_i s_{i+1} \ldots s_j$, and declare ``found" if the likelihood is above a certain threshold. The problems with this approach are (1) how to set the likelihood threshold and (2) the redundant computation from the fact that the computation for every subwindow is carried out from scratch, even if a subwindow overlaps with another subwindow.

To deal with these problems, we augment the model with two extra ``background" states: a pre-pattern background state (state 0) to model the data before the pattern, and a post-pattern background state (state $K+1$) for the data after the pattern. This augmented model may be seen as a ``global" model that can be matched directly against the whole time series (instead of the subwindows). With this augmented model, we run the MLSS algorithm of Section 2 online as new data points $y_1 y_2 \ldots y_t \ldots$ are coming in. If, at time $t$, $s_t=K$ in the most likely state sequence where $K$ is the last segment in the waveform, we declare that the waveform is detected with end time at $y_t$.

To test the above algorithm, a segmental semi-Markov model was estimated from the example pattern in Fig. 2(a), and the pattern matching algorithm was run on the data in Fig. 2(b). The algorithm correctly found the matched pattern at 230-252. The semi-Markov algorithm was found to be substantially more accurate than alternative approaches such as dynamic time warping or squared-error correlation. See Ge and Smyth (2000a) for more details.