Modeling Waveform Shapes with Random Eects Segmental Hidden Markov Models

Seyoung Kim, Padhraic Smyth, Stefan Luther

TL;DR

This paper introduces a novel probabilistic framework, Random Effects Segmental Hidden Markov Models (RES-HMMs), to model the inherent shape variability in waveforms like ECG signals. By incorporating random effects into traditional segmental HMMs, the model can better capture individual waveform nuances, leading to improved accuracy in parsing, classification, and prediction tasks.

What Problem Does This Paper Address?

Automatically recognizing and parsing waveforms is a long-standing challenge in pattern recognition with applications ranging from medical diagnostics (ECG analysis) to fluid dynamics and seismology. A key difficulty is the significant variability in shape that waveforms within the same class can exhibit. Traditional methods, like standard Hidden Markov Models (HMMs) and even their segmental extensions, often struggle to account for this individual-level shape variation, treating all waveforms within a class as if they were generated by a single, fixed model. This limitation can lead to suboptimal performance in tasks like classification and segmentation.

Methods

The core contribution is the extension of Segmental Hidden Markov Models (SHMMs) with random effects.

  • Segmental HMMs (SHMMs): These models are an improvement over standard HMMs for waveform modeling. They allow for more flexible segment durations and model the waveform shape within each segment using regression functions (e.g., piecewise linear). However, they assume fixed parameters for these regression functions across all waveforms of a given class.
  • Random Effects: The paper introduces random effects to the regression parameters (like slopes and intercepts) of the SHMM segments. This means that while there's a common "population prior" for these parameters, each individual waveform can have its own unique deviation from this average. This allows the model to capture subtle, individual shape variations.
  • EM Algorithm: A computationally efficient Expectation-Maximization (EM) algorithm is derived to learn the parameters of these RES-HMMs from data. This algorithm iteratively refines estimates of the model parameters by handling the unobserved state sequences and random effects.
  • Scoring Methods: Beyond the standard likelihood score, the authors propose two new scores: ScoreShape and ScoreNoise. These scores decompose the model's fit into aspects related to shape deformation and measurement noise, respectively. Using these decomposed scores as features for classification is shown to be more effective than relying solely on the overall likelihood.

Datasets

The paper evaluates its proposed model on two real-world datasets:

  • Bubble-probe interaction data: This dataset consists of 50 waveforms from experiments where a probe interacts with bubbles. The authors used this for modeling and demonstrated improved segmentation and classification.
  • ECG data: This dataset includes normal heartbeats and heartbeats exhibiting premature ventricular contractions (PVCs). The model was used to classify these different heartbeat types.

The paper does not introduce new benchmark datasets but rather applies its method to existing types of data.

Key Insights and Ideas

  • Individual Variability Matters: The most significant insight is that explicitly modeling individual waveform shape variation through random effects is crucial for improving performance in tasks like classification and segmentation. Simply assuming a single average shape for a class is insufficient.
  • Unified Framework: RES-HMMs provide a unified probabilistic framework that can handle waveform modeling, parsing, classification, and prediction within a single, coherent structure.
  • Decomposed Scores for Better Classification: Separating the assessment of waveform shape fit (ScoreShape) from measurement noise (ScoreNoise) provides more informative features for classification than a single likelihood score. This allows for a more nuanced understanding of why a waveform is classified in a certain way.
  • Computational Efficiency: Despite the added complexity of random effects, the authors derive an EM algorithm that is computationally efficient, reducing complexity compared to naive approaches.

Key Results

  • Improved Accuracy: The RES-HMMs consistently outperformed standard SHMMs across both datasets.
  • On the bubble-probe interaction data, RES-HMMs achieved an approximate 80% reduction in mean squared error for segmentations and significantly better one-step-ahead prediction.
  • On ECG data, RES-HMMs showed significant improvements in LogP scores and segmentation error. For classification, RES-HMMs achieved 100% accuracy on ECG data, compared to 98% for SHMMs.
  • Enhanced Classification with Decomposed Scores: Using the ScoreShape and ScoreNoise as features for k-nearest neighbor classification significantly improved accuracy over using only the likelihood score.
  • Better Segmentation: Visualizations show that the Viterbi algorithm with RES-HMMs produces qualitatively better segmentations of waveforms compared to standard SHMMs.

Limitations and Future Work

  • Computational Complexity: While the authors derived an efficient EM algorithm, the inference for RES-HMMs can still be computationally more expensive than for standard SHMMs, especially for very long waveforms. The paper mentions a reduction in complexity from O(M²T⁵) to O(M²T³) or O(M²T²) with precomputation, but this remains a factor.
  • Parameter Tuning: The paper mentions subjectively choosing the number of states (M) for the models. Future work could explore more automated methods for determining the optimal number of states.
  • Generalization of Segment Models: The paper focuses on piecewise linear segment models. Extending the framework to more complex segment models could further enhance its applicability.
  • Exploration of Other Distributions: While Poisson distribution was used for duration, exploring other distributions could be beneficial.

Summary updated

Abstract

In this paper we describe a general probabilistic framework for modeling waveforms such as heartbeats from ECG data. The model is based on segmental hidden Markov models (as used in speech recognition) with the addition of random effects to the generative model. The random effects component of the model handles shape variability across different waveforms within a general class of waveforms of similar shape. We show that this probabilistic model provides a unified framework for learning these models from sets of waveform data as well as parsing, classification, and prediction of new waveforms. We derive a computationally efficient EM algorithm to fit the model on multiple waveforms, and introduce a scoring method that evaluates a test waveform based on its shape. Results on two real-world data sets demonstrate that the random effects methodology leads to improved accuracy (compared to alternative approaches) on classification and segmentation of real-world waveforms.
BibTeX
@inproceedings{kim2004modeling,
  author = {Seyoung Kim and Padhraic Smyth and Stefan Luther},
  title = {{Modeling Waveform Shapes with Random Eects Segmental Hidden Markov Models}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2004},
  url = {https://openreview.net/forum?id=UeKheEpxRf},
}
Figure