Computationally lightweight classifiers with frequentist bounds on predictions
This addresses the need for safe, real-time classification in resource-constrained applications like diagnostic monitoring, though it is incremental as it builds on existing kernel-based methods.
The paper tackles the problem of computationally expensive uncertainty bounds in classifiers by proposing a novel algorithm based on the Nadaraya-Watson estimator, achieving competitive accuracy >96% with O(n) and O(log n) operations while providing actionable frequentist uncertainty intervals.
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.