Optimally ordering IDK classifiers subject to deadlines

Sanjoy Baruah, Alan Burns, Robert Ian Davis, Yue Wu

Research output: Contribution to journalArticlepeer-review


A classifier is a software component, often based on Deep Learning, that categorizes each input provided to it into one of a fixed set of classes. An IDK classifier may additionally output “I Don’t Know” (IDK) for certain inputs. Multiple distinct IDK classifiers may be available for the same classification problem, offering different trade-offs between effectiveness, i.e. the probability of successful classification, and efficiency, i.e. execution time. Optimal offline algorithms are proposed for sequentially ordering IDK classifiers such that the expected duration to successfully classify an input is minimized, optionally subject to a hard deadline on the maximum time permitted for classification. Solutions are provided considering independent and dependent relationships between pairs of classifiers, as well as a mix of the two.
Original languageEnglish
Number of pages34
JournalReal-Time Systems
Early online date14 May 2022
Publication statusPublished - 1 Mar 2023

Bibliographical note

© The Author(s) 2022


  • Deep Learning
  • Optimal synthesis
  • IDK cascades
  • Hard deadlines
  • Classifiers

Cite this