Computationally lightweight classifiers with frequentist bounds on predictions

Shreeram Murali; Cristian R. Rojas; Dominik Baumann

cs.LGMar 23, 2026

Computationally lightweight classifiers with frequentist bounds on predictions

Authors: Shreeram Murali, Cristian R. Rojas, Dominik Baumann

Organizations: Cyber-physical Systems Group, Aalto University · Decision and Control Systems, KTH Royal Institute of Technology

Abstract

While both classical and neural network classifiers can achieve high accuracy, they fall short on offering uncertainty bounds on their predictions, making them unfit for safety-critical applications. Existing kernel-based classifiers that provide such bounds scale with $\mathcal O (n^{\sim3})$ in time, making them computationally intractable for large datasets. To address this, we propose a novel, computationally efficient classification algorithm based on the Nadaraya-Watson estimator, for whose estimates we derive frequentist uncertainty intervals. We evaluate our classifier on synthetically generated data and on electrocardiographic heartbeat signals from the MIT-BIH Arrhythmia database. We show that the method achieves competitive accuracy $>$ \SI{96}{\percent} at $\mathcal O(n)$ and $\mathcal O(\log n)$ operations, while providing actionable uncertainty bounds. These bounds can, e.g., aid in flagging low-confidence predictions, making them suitable for real-time settings with resource constraints, such as diagnostic monitoring or implantable devices.

Figures & tables

	Preprocessing	Querying
Regular	–	$\displaystyle\mathcal{O}(n)$
Dyadic	$\displaystyle\mathcal{O}(n)$	$\displaystyle\mathcal{O}(\log n)$
Localized	$\displaystyle\mathcal{O}(n\log n)$	$\displaystyle\mathcal{O}(k+\log n)$
CME	–	$\displaystyle\mathcal{O}(n^{3})$
LR	$\displaystyle\mathcal{O}(nd)$	$\displaystyle\mathcal{O}(d)$

Table 1: Time complexity of different NWC implementations compared with CMEs and Logistic Regression.

Figure 1: The two synthetic datasets used for evaluating the classifier. One dataset with overlapping classes, adhering to Assumption 1 (left), and one with classes separated by a known margin, in accordance with Assumption 2 (right).

Panel of Figure 2 — Figure 2: Performance of the proposed classifiers on the synthetic datasets compared to baselines with varying sample sizes. We plot total runtime, prediction time, fit time (top row); average bounds $\displaystyle\bar{\epsilon}_{c}$ for $\displaystyle\delta=0.05$ for all classes, accuracy on the overlapping and separable dataset (bottom row). We observe that our algorithm is significantly more sample-efficient than the CME-based classifier, while achieving high accuracy with minimal uncertainty.

Panel of Figure 3 — Figure 3: Mean uncertainty intervals, precision-recall metrics for the proposed classifiers, and waveforms. Our classifier shows higher uncertainty in misclassified labels, as well as high precision and recall scores.

Size	Classifier	Accuracy	Precision	Recall	Precompute (s)	Query Time (s)
1 000	Regular NWC	86.4	0.881	0.864	–	0.140
	Localized NWC	91.0	0.903	0.910	0.0008	0.085
	Logistic Regression	88.8	0.859	0.888	0.0128	0.0002
	CME	92.0	0.846	92.0	–	8.883
10 000	Regular NWC	93.4	0.938	0.934	–	1.573
	Localized NWC	96.4	0.963	0.964	0.0145	0.395

Table 2: Acccuracy and runtime comparison of the classifiers on the ECG dataset. We observe that both our approaches outperform logistic regression and the CME-based classifier in terms of accuracy, while being computationally orders of magnitude cheaper than the latter.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: Two synthetic datasets and their corresponding dyadic cell prediction grids. The figures on the left correspond to the Lipschitz-continuous overlapping dataset; the figures on the right correspond to the dataset separated by a margin.

Panel of Figure 5 — Figure 5: Illustrative ECG waveforms (amplitude normalized from $\displaystyle\mathrm{m}\mathrm{V}$ , $\displaystyle t$ denotes time step) and associated class probabilities for each class from the MIT-BIH database; class Q (unclassifiable) has been excluded.

Figure 9: Results from the reduced GTSRB dataset. On the left are the two classes considered in our study. On the right are confusion matrices from the two proposed variants of our classifier. In the confusion matrices, the label 0 corresponds to the ‘go’ sign and 1 corresponds to the ‘stop’ sign.

Literature	Remark	Accuracy	Bounds
Kumari and Sai (2022)	Optimized decision tree	$\displaystyle 98.77\text{\,}\mathrm{\char 37\relax}$	✗
Zhou and Fang (2024)	CNN with frequency channel attention	$\displaystyle 99.6\text{\,}\mathrm{\char 37\relax}$	✗
Abdalla et al. (2020)	CNN with 11 layers	$\displaystyle 99.84\text{\,}\mathrm{\char 37\relax}$	✗
Gao et al. (2019)	Long short-term memory model with focal loss	$\displaystyle 99.26\text{\,}\mathrm{\char 37\relax}$	✗
Jha and Kolekar (2020)	SVM with tunable Q-wavelet transform	$\displaystyle 99.27\text{\,}\mathrm{\char 37\relax}$	✗
Nnyaba et al. (2024)	GP classification with bounds	$\displaystyle\approx$ $\displaystyle 98\text{\,}\mathrm{\char 37\relax}$	✓

Appendix

Table 3: Summary of reported ECG classification results in the literature.

Kernel	Definition
Boxcar kernel	$\displaystyle\displaystyle K(v)=\begin{cases}1&\text{if }\\|v\\|\leq 1\\ 0&\text{otherwise}\end{cases}$
Gaussian kernel (without truncation)	$\displaystyle\displaystyle K(v)=\exp\left(-\frac{\\|v\\|^{2}}{2}\right)$
Epanechnikov kernel	$\displaystyle\displaystyle K(v)=\begin{cases}1-v^{2}&\text{if }\\|v\\|\leq 1\\ 0&\text{otherwise}\end{cases}$
Quartic kernel	$\displaystyle\displaystyle K(v)=\begin{cases}(1-v^{2})^{2}&\text{if }\\|v\\|\leq 1\\ 0&\text{otherwise}\end{cases}$
Triweight kernel	$\displaystyle\displaystyle K(v)=\begin{cases}(1-v^{2})^{3}&\text{if }\\|v\\|\leq 1\\ 0&\text{otherwise}\end{cases}$
Tricube kernel	$\displaystyle\displaystyle K(v)=\begin{cases}(1-\|v\|^{3})^{3}&\text{if }\\|v\\|<1\\ 0&\text{otherwise}\end{cases}$

Appendix

Table 4: Different kernel functions and their definitions.

Panel of Figure 10 — Figure 10: Hyperparameter optimization on the kernels. On the left, we show the baseline and optimized score $\displaystyle J(A,B)$ on all kernels from Table 4 . Here, the results show that the effect of hyperparameter optimization to find the optimal $\displaystyle\lambda$ on each kernel is, at best, only moderately significant. On the right, we show the Epanechnikov kernel evaluated at all pairs of 100 randomly sampled MNIST images with optimized $\displaystyle\lambda=7.5$ .

Classification

Classification maps observations to discrete labels, including familiar, unknown, hierarchical, or multiple categories.

See all 408 papers

Uncertainty-aware classification and triage of structural heart disease using electrocardiography and echocardiography metrics
May 21, 2026Mitchel J. ColebankBayesian Neural Networks Uncertainty Quantification
Department of Mathematics, University of South Carolina,, Columbia, 29208, South Carolina, USA
Estimation of Confidence Bounds in Binary Classification using Wilson Score Kernel Density Estimation
Feb 24, 2026Thorbjørn Mosekjær Iversen, Zebin Duan, Frederik HagelskjærBinary Classification Confidence Region Estimation
SDU Robotics, The Maersk Mc-Kinney Moller Institute, University of Southern
UCTECG-Net: Uncertainty-aware Convolution Transformer ECG Network for Arrhythmia Detection
Feb 18, 2026Hamzeh Asgharnezhad, Pegah Tabarisaadi, Abbas Khosravi +2Electrocardiogram Classification Hybrid CNN-Transformer Architectures
Deakin University, Australia . · School of Mathematics, Physics and Computing, University of Southern Queensland, Toowoomba, QLD, Australia .

May 21, 2026J/K move · Enter open · S save

Uncertainty-aware classification and triage of structural heart disease using electrocardiography and echocardiography metrics

Mitchel J. Colebank

Department of Mathematics, University of South Carolina,, Columbia, 29208, South Carolina, USA

Bayesian Neural Networks Uncertainty Quantification Healthcare Clinical Triage Clinical Decision Support Bayesian Inference+2

Open paper AskPDF arXiv

Machine learning methods provide a methodological innovation that can help screen for cardiovascular disease through noninvasive and readily available measurement modalities. Recent investments in using electrocardiogram (ECG) data to screen for structural heart disease (SHD) are one example, where ECGs provide a low-cost, available modality for screening. This has led to the EchoNext dataset, a paired ECG-echocardiogram data repository for testing new methods of SHD detection. However, relatively few studies have investigated how more probabilistic classification through Bayesian inference may improve uncertainty quantification in this setting. Moreover, few studies have considered how triage systems can be developed to alleviate healthcare bottlenecks, such as the review of data from underserved, rural clinics by expert sonographers for SHD assessment. In this study, we leverage existing ECG-echocardiogram data to compare frequentist and Bayesian neural network classifiers. We show that the Bayesian approach is comparable or better than frequentist methods in SHD classification, and that they have a more robust uncertainty quantification attached to them. We provide an example of how this uncertainty-aware classification scheme can be used for screening SHD, providing a proof-of-concept for how machine learning can help with triage in getting individuals expert sonographer input when SHD is highly likely or measurements are highly uncertain.

Abstract

Classification

Explore similar work

Uncertainty-aware classification and triage of structural heart disease using electrocardiography and echocardiography metrics

Estimation of Confidence Bounds in Binary Classification using Wilson Score Kernel Density Estimation

UCTECG-Net: Uncertainty-aware Convolution Transformer ECG Network for Arrhythmia Detection