Optimal Synthesis of Robust IDK Classifier Cascades
Open Access
- 9 September 2023
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Embedded Computing Systems
- Vol. 22 (5s) , 1-26
Abstract
An IDK classifier is a computing component that categorizes inputs into one of a number of classes, if it is able to do so with the required level of confidence, otherwise it returns “I Don’t Know” (IDK). IDK classifier cascades have been proposed as a way of balancing the needs for fast response and high accuracy in classification-based machine perception. Efficient algorithms for the synthesis of IDK classifier cascades have been derived; however, the responsiveness of these cascades is highly dependent on the accuracy of predictions regarding the run-time behavior of the classifiers from which they are built. Accurate predictions of such run-time behavior is difficult to obtain for many of the classifiers used for perception. By applying the algorithms using predictions framework, we propose efficient algorithms for the synthesis of IDK classifier cascades that are robust to inaccurate predictions in the following sense: the IDK classifier cascades synthesized by our algorithms have short expected execution durations when the predictions are accurate, and these expected durations increase only within specified bounds when the predictions are inaccurate.Keywords
Funding Information
- Innovate UK HICLASS (113213)
- US National Science Foundation (CNS-2141256 and CPS-2229290)
This publication has 13 references indexed in Scilit:
- Real-Time Scheduling with Predictions2022
- Optimally ordering IDK classifiers subject to deadlinesReal-Time Systems, 2022
- Optimal Synthesis of IDK-Cascades2021
- Algorithms with Predictions2020
- Beyond the Worst-Case Analysis of Algorithms2020
- Robust Mixed-Criticality SystemsIEEE Transactions on Computers, 2018
- Unanimous Prediction for 100\% Precision with Application to Learning Semantic Mappings2016
- ImageNet Large Scale Visual Recognition ChallengeInternational Journal of Computer Vision, 2015
- The worst-case execution-time problem—overview of methods and survey of toolsACM Transactions on Embedded Computing Systems, 2008
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973