Quantitative Regular Expressions for Arrhythmia Detection Algorithms

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

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). 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 and various discriminators used to distinguish fatal from non-fatal arrhythmias. We show that a range of peak detectors and discriminators at the heart of today's arrhythmia-detection devices are easily expressible in QREs. This unified formalism opens the way to formal analysis and rigorous testing, potentially alleviating the regulatory burden on device developers. The performance of the QRE-based detectors is demonstrated on real patient data, yielding results on par with those provided by a cardiologist.

Introduction

Implantable Cardioverter Defibrillators (ICDs) are life-saving medical devices that monitor heart rhythms to detect and treat fatal arrhythmias. The reliability of these devices depends on the seamless integration of high-speed signal processing and complex decision logic. However, verifying the correctness of these algorithms is a significant challenge due to the limitations of existing formal methods when applied to numerical data streams.

The Challenge of Medical Device Verification

Modern ICD algorithms perform two critical tasks: peak detection (identifying individual heartbeats) and discrimination (distinguishing fatal arrhythmias like Ventricular Fibrillation from harmless fast heart rates). Historically, engineers have attempted to use temporal logics such as Signal Temporal Logic (STL) or Linear Temporal Logic (LTL) to specify these requirements. However, these logics struggle with the heavy numerical lifting required for signal processing, such as calculating moving averages or performing wavelet transforms. This "fracturing of formalisms"—using different tools for different parts of the pipeline—makes end-to-end safety verification nearly impossible.

Quantitative Regular Expressions (QREs)

We propose Quantitative Regular Expressions (QREs) as a "one-stop shop" for both signal processing and decision logic. QREs extend standard regular expressions by allowing them to match patterns in data streams while simultaneously performing numerical computations, or "costs."

Succinct QRE implementation of a sudden onset discriminator.

A key advantage of QREs is the "split-op" combinator, which enables developers to break a signal into discrete windows, perform mathematical operations, and pass the results to subsequent stages without manual state management. This declarative approach reduces the surface area for bugs compared to traditional imperative programming.

Implementation and Results

The researchers implemented three distinct peak detectors using QREs: the Wavelet Peaks with Maxima (WPM), the Wavelet Peaks with Blanking (WPB), and a formalization of a commercial time-domain detector (MDT). These were evaluated using real patient intra-cardiac electrograms (EGMs) annotated by expert cardiologists.

Cardiac signal with peaks used for arrhythmia detection.

The QRE-based WPM detector achieved perfect detection on patient data, matching cardiologist-level accuracy. Furthermore, it demonstrated superior precision compared to the commercial MDT detector, particularly in disorganized signals like Ventricular Fibrillation, where the MDT often produced false positives (over-sensing). Complex discriminators that required unwieldy formulas in temporal logic were expressed clearly and concisely in just a few lines of QRE code.

Conclusion and Future Work

QREs provide a unified, expressive, and efficient framework for formalizing arrhythmia detection. By bridging the gap between signal processing and high-level logic, they enable more rigorous testing and formal analysis of medical device software. Future work will focus on compiling QREs into highly optimized code for low-power microcontrollers and conducting detailed energy consumption analyses to ensure suitability for battery-powered implants.

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. In contrast, we show that a range of peak detectors (in both the time and wavelet domains) and various discriminators at the heart of today's arrhythmia-detection devices are easily expressible in QREs. The fact that one formalism (QREs) is used to describe the desired end-to-end operation of an arrhythmia detector opens the way to formal analysis and rigorous testing of these detectors' correctness and performance. Such analysis could alleviate the regulatory burden on device developers when modifying their algorithms. The performance of the peak-detection QREs is demonstrated by running them on real patient data, on which they yield results on par with those provided by a cardiologist.
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