Quantitative Regular Expressions for Arrhythmia Detection

Houssam Abbas, Alëna Rodionova, Konstantinos Mamouras, Ezio Bartocci, Scott A. Smolka, Radu GrosuIEEE/ACM Trans. CBB 2019 · DOI · OpenReview

TL;DR

This paper introduces Quantitative Regular Expressions (QREs) as a powerful and concise formalism for specifying and analyzing complex algorithms used in medical devices, specifically for arrhythmia detection. By demonstrating that QREs can elegantly express peak detection and discrimination tasks, the authors pave the way for more rigorous testing and formal verification of these critical safety systems.

What Problem Does This Paper Address?

Medical devices like Implantable Cardioverter Defibrillators (ICDs) rely on sophisticated algorithms to detect and differentiate between life-threatening and benign heart rhythms. These algorithms often involve signal processing steps, such as peak detection (identifying heartbeats), followed by decision-making logic (discriminators). Ensuring the correctness and performance of these algorithms is paramount, especially given strict constraints on memory and processing power within these devices. Traditional approaches using temporal logics to formally specify and verify these algorithms are often cumbersome, error-prone, and can lead to computationally expensive implementations. The paper aims to bridge this gap by proposing a unified, expressive, and efficient formalism for specifying these complex algorithms.

Methods

The core contribution of this paper is the application and demonstration of Quantitative Regular Expressions (QREs) for specifying arrhythmia detection algorithms. QREs are presented as a declarative formal language that extends classical regular expressions with the ability to perform numerical computations and store intermediate values. This allows for the specification of complex queries over data streams, with guarantees on runtime and memory consumption.

The authors demonstrate the expressiveness of QREs by:

  • Formalizing various peak detectors: This includes detectors operating in both the time domain and the wavelet domain (specifically, the Wavelet Peaks with Maxima (WPM) and Wavelet Peaks with Blanking (WPB) characterizations).
  • Formalizing common discriminators: Examples include a heart rate counting discriminator and a discriminator for detecting sudden onset of arrhythmias.
  • Comparing QREs to temporal logics: The paper highlights how QREs offer a more concise and less error-prone way to express these algorithms compared to existing temporal logics, which often require complex constructs like freeze quantifiers or explicit clocks.

The paper also details the implementation of QREs for the WPM and WPB peak detectors, illustrating how these complex procedures can be described declaratively without explicit state management.

Datasets

The paper mentions using real patient electrogram data for evaluating the performance of the QRE-based peak detectors. Specifically, they use data from a dataset of intra-cardiac electrograms, including examples of Normal Sinus Rhythm (NSR), Ventricular Tachycardia (VT), and Ventricular Fibrillation (VF) rhythms.

Key Insights and Ideas

  • QREs as a Unified Formalism: The paper strongly advocates for QREs as a single, powerful language capable of expressing a wide range of signal processing and decision-making algorithms found in medical devices, overcoming the "fracturing of formalisms" seen with temporal logics.
  • Elegance and Conciseness: QREs allow for a much more direct and readable encoding of complex algorithms compared to the often unwieldy and error-prone specifications in temporal logics.
  • Provable Guarantees: A key advantage of QREs is their ability to provide provable runtime and memory consumption guarantees, which is critical for resource-constrained embedded systems like ICDs.
  • Bridging Theory and Practice: The paper demonstrates the practical applicability of QREs by implementing and testing them on real patient data, showing results comparable to expert annotations.
  • Formal Analysis Potential: By providing a formal description, QREs open the door for rigorous formal analysis and testing, which can significantly ease the regulatory burden for device developers.

Key Results

  • The paper successfully demonstrates that various peak detectors (including wavelet-based and time-domain) and common arrhythmia discriminators can be easily and clearly expressed using QREs.
  • The QRE-based peak detectors (peakWPM and peakWPB) were tested on real patient data, yielding results on par with those provided by a cardiologist (for peakWPM in nominal settings).
  • The paper highlights that peakWPM, when properly parameterized, achieves perfect detection on VT rhythms, while peakWPB sometimes detects additional false peaks.
  • The paper shows that the commercial detector MDT performs well on NSR but struggles with more disorganized rhythms like VF, underscoring the need for robust algorithms and formal verification.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that QREs primarily allow for regular matching, which is somewhat mitigated by chaining QREs for more complex tasks.
  • The performance comparison in the paper is limited by the lack of a compiler for QREs to run on specific hardware platforms, preventing definitive runtime and memory consumption benchmarks.
  • Future Work:
    • Compilation to C/Assembly: Compiling QREs to low-level code to measure actual performance on hardware platforms.
  • Formal Equivalence: Establishing an equivalent machine model for QREs (similar to DFAs for REs) to enable formal analysis of correctness and efficiency.
  • Probabilistic Analysis: Developing methods to analyze QRE behavior under probabilistic input models, allowing for estimation of detection times and error probabilities.
  • Energy Calculations: Computing the energy consumption of QRE-based algorithms, which is crucial for battery-powered implanted medical devices.

Summary updated

Abstract

Implantable medical devices are safety-critical systems whose incorrect operation can jeopardize a patient's health, and whose algorithms must meet tight platform constraints like memory consumption and runtime. In particular, we consider here the case of implantable cardioverter defibrillators, where peak detection algorithms and various others discrimination algorithms serve to distinguish fatal from non-fatal arrhythmias in a cardiac signal. Motivated by the need for powerful formal methods to reason about the performance of arrhythmia detection algorithms, we show how to specify all these algorithms using Quantitative Regular Expressions (QREs). QRE is a formal language to express complex numerical queries over data streams, with provable runtime and memory consumption guarantees. We show that QREs are more suitable than classical temporal logics to express in a concise and easy way a range of peak detectors (in both the time and wavelet domains) and various discriminators at the heart of today's arrhythmia detection devices. The proposed formalization also opens the way to formal analysis and rigorous testing of these detectors' correctness and performance, alleviating the regulatory burden on device developers when modifying their algorithms. We demonstrate the effectiveness of our approach by executing QRE-based monitors on real patient data on which they yield results on par with the results reported in the medical literature.
BibTeX
@article{abbas2019quantitative,
  author = {Houssam Abbas and Alëna Rodionova and Konstantinos Mamouras and Ezio Bartocci and Scott A. Smolka and Radu Grosu},
  title = {{Quantitative Regular Expressions for Arrhythmia Detection}},
  journal = {IEEE ACM Trans. Comput. Biol. Bioinform.},
  year = {2019},
  doi = {10.1109/tcbb.2018.2885274},
}
Figure