Optimally ordering IDK classifiers subject to deadlines

TY - JOUR

T1 - Optimally ordering IDK classifiers subject to deadlines

AU - Baruah, Sanjoy

AU - Burns, Alan

AU - Davis, Robert Ian

AU - Wu, Yue

N1 - © The Author(s) 2022

PY - 2023/3/1

Y1 - 2023/3/1

N2 - 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.

AB - 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.

KW - Deep Learning

KW - Optimal synthesis

KW - IDK cascades

KW - Hard deadlines

KW - Classifiers

UR - https://www-users.cs.york.ac.uk/~robdavis/

U2 - 10.1007/s11241-022-09383-w

DO - 10.1007/s11241-022-09383-w

M3 - Article

SN - 0922-6443

VL - 59

JO - Real-Time Systems

JF - Real-Time Systems

ER -