Quantitative Regular Expressions for Arrhythmia Detection Algorithms

Houssam Abbas, Alëna Rodionova, Ezio Bartocci, Scott A. Smolka, Radu Grosu

TL;DR

Researchers have successfully applied Quantitative Regular Expressions (QREs) to formalize and implement the complex algorithms used in life-saving medical devices like Implantable Cardioverter Defibrillators (ICDs). By replacing cumbersome temporal logics with this stream-processing language, they’ve created a unified framework that detects heart arrhythmias with the accuracy of a cardiologist while providing provable guarantees for real-time performance.

What Problem Does This Paper Address?

Modern medical devices are a hybrid of high-speed signal processing (SP) and critical decision-making logic. For an ICD to decide whether to deliver a life-saving shock, it must first accurately detect heartbeats (peak detection) and then analyze those beats to distinguish between a harmless fast heart rate and a fatal arrhythmia (discrimination).

Historically, verifying these algorithms has been a nightmare. Engineers often try to use temporal logics (like STL or LTL) to specify requirements, but these logics struggle with the heavy numerical lifting required for signal processing. They become "unwieldy, error-prone, and computationally expensive" when dealing with things like moving averages or wavelet transforms. This "fracturing of formalisms"—using different tools for different parts of the pipeline—makes it nearly impossible to verify the safety and correctness of the device as a whole.

Methods

The authors propose using Quantitative Regular Expressions (QREs) as a "one-stop shop" for both signal processing and decision logic.

  • What are QREs? Think of them as regular expressions on steroids. While a standard regex matches patterns in text, a QRE matches patterns in a data stream and performs numerical computations (costs) along the way.
  • The "Split-Op" Advantage: QREs use combinators like split-op and iter that allow developers to break a signal into windows, perform math (like averaging or finding a maximum), and pass those results to the next stage of the algorithm without manually managing state.
  • Formalized Detectors: The team implemented three distinct peak detectors:
  • WPM (Wavelet Peaks with Maxima): A sophisticated approach using Continuous Wavelet Transforms (CWT) to find singularities in the signal.
  • WPB (Wavelet Peaks with Blanking): A simplified, faster version of WPM.
  • MDT: A formalization of a commercial time-domain peak detector currently found in market-leading ICDs.

Datasets

The algorithms were evaluated using real patient intra-cardiac electrograms (EGMs). These datasets included various heart rhythms, specifically focusing on Ventricular Tachycardia (VT) and Ventricular Fibrillation (VF), which are the primary targets for ICD therapy. Ground truth for the evaluation was provided by expert cardiologists who manually annotated the true peaks in the signals.

Key Insights and Ideas

  • Unified Formalism: The biggest "aha" moment is that QREs can bridge the gap between raw signal processing and high-level logic. You can describe a wavelet transform and a heart-rate-based decision in the same language.
  • State Management without the Headache: In traditional programming, tracking "the value of the last peak" requires explicit state variables. In QREs, this is handled declaratively through the structure of the expression, reducing the surface area for bugs.
  • Efficiency by Design: QREs are designed to be compiled into monitors with polynomial runtime and memory guarantees, which is a hard requirement for implanted devices with limited battery life and processing power.

Key Results

  • Human-Level Accuracy: The QRE-based WPM detector achieved "perfect detection" on patient data, matching the annotations provided by cardiologists.
  • Precision Matters: WPM outperformed the simpler WPB and the commercial MDT detector in terms of time precision. While the commercial MDT worked well for normal rhythms, it struggled with disorganized signals like Ventricular Fibrillation, where it produced false positives (over-sensing).
  • Succinctness: Complex discriminators that required deeply nested, "unwieldy" formulas in temporal logic were expressed clearly and concisely in just a few lines of QRE code.

Limitations and Future Work

While the paper proves that QREs are expressive and accurate, a few hurdles remain before they end up in your chest:

  • Hardware Compilation: The current implementation uses a Java library. For actual medical devices, the QREs need to be compiled into highly optimized C or assembly code to run on low-power microcontrollers.
  • Energy Consumption: While QREs have theoretical complexity guarantees, the authors note that future work is needed to explicitly calculate the "energy cost" of running these expressions to ensure they don't drain a device's battery prematurely.
  • Probabilistic Analysis: The authors suggest moving toward a probabilistic model to estimate the likelihood of an incorrect detection under noisy conditions, further bolstering the safety profile of the device.

Summary updated

Abstract

Motivated by the problem of verifying the correctness of arrhythmia-detection algorithms, we present a formalization of these algorithms in the language of Quantitative Regular Expressions. QREs are a flexible formal language for specifying complex numerical queries over data streams, with provable runtime and memory consumption guarantees. The medical-device algorithms of interest include peak detection (where a peak in a cardiac signal indicates a heartbeat) and various discriminators, each of which uses a feature of the cardiac signal to distinguish fatal from non-fatal arrhythmias. Expressing these algorithms’ desired output in current temporal logics, and implementing them via monitor synthesis, is cumbersome, error-prone, computationally expensive, and sometimes infeasible.
BibTeX
@inproceedings{abbas2017quantitative,
  author = {Houssam Abbas and Alëna Rodionova and Ezio Bartocci and Scott A. Smolka and Radu Grosu},
  title = {{Quantitative Regular Expressions for Arrhythmia Detection Algorithms}},
  booktitle = {CMSB},
  year = {2017},
  doi = {10.1007/978-3-319-67471-1\_2},
}

Loading related content...

Figure