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

May 21, 2026

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

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.

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

Ask PDF

Feb 24, 2026

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

The performance and ease of use of deep learning-based binary classifiers have improved significantly in recent years. This has opened up the potential for automating critical inspection tasks, which have traditionally only been trusted to be done manually. However, the application of binary classifiers in critical operations depends on the estimation of reliable confidence bounds such that system performance can be ensured up to a given statistical significance. We present Wilson Score Kernel Density Classification, which is a novel kernel-based method for estimating confidence bounds in binary classification. The core of our method is the Wilson Score Kernel Density Estimator, which is a function estimator for estimating confidence bounds in Binomial experiments with conditionally varying success probabilities. Our method is evaluated in the context of selective classification on four different datasets, illustrating its use as a classification head of any feature extractor, including vision foundation models. Our proposed method shows similar performance to Gaussian Process Classification, but at a lower computational complexity.

Thorbjørn Mosekjær Iversen, Zebin Duan, Frederik Hagelskjær

SDU Robotics, The Maersk Mc-Kinney Moller Institute, University of Southern

Binary Classification Confidence Region Estimation Kernel Density Estimation

Ask PDF

Feb 18, 2026

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

Deep learning has improved automated electrocardiogram (ECG) classification, but limited insight into prediction reliability hinders its use in safety-critical settings. This paper proposes UCTECG-Net, an uncertainty-aware hybrid architecture that combines one-dimensional convolutions and Transformer encoders to process raw ECG signals and their spectrograms jointly. Evaluated on the MIT-BIH Arrhythmia and PTB Diagnostic datasets, UCTECG-Net outperforms LSTM, CNN1D, and Transformer baselines in terms of accuracy, precision, recall and F1 score, achieving up to 98.58% accuracy on MIT-BIH and 99.14% on PTB. To assess predictive reliability, we integrate three uncertainty quantification methods (Monte Carlo Dropout, Deep Ensembles, and Ensemble Monte Carlo Dropout) into all models and analyze their behavior using an uncertainty-aware confusion matrix and derived metrics. The results show that UCTECG-Net, particularly with Ensemble or EMCD, provides more reliable and better-aligned uncertainty estimates than competing architectures, offering a stronger basis for risk-aware ECG decision support.

Hamzeh Asgharnezhad, Pegah Tabarisaadi, Abbas Khosravi +2

Deakin University, Australia . · School of Mathematics, Physics and Computing, University of Southern Queensland, Toowoomba, QLD, Australia .

Electrocardiogram Classification Hybrid CNN-Transformer Architectures Uncertainty Quantification

Ask PDF

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