{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T05:46:50Z","timestamp":1771998410047,"version":"3.50.1"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,5,14]],"date-time":"2022-05-14T00:00:00Z","timestamp":1652486400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,5,14]],"date-time":"2022-05-14T00:00:00Z","timestamp":1652486400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100008982","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100008982","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Real-Time Syst"],"published-print":{"date-parts":[[2023,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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 \u201cI Don\u2019t Know\u201d (IDK) for certain inputs. Multiple distinct IDK classifiers may be available for the same classification problem, offering different trade-offs between effectiveness, i.e.\u00a0the probability of successful classification, and efficiency, i.e.\u00a0execution 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.<\/jats:p>","DOI":"10.1007\/s11241-022-09383-w","type":"journal-article","created":{"date-parts":[[2022,5,14]],"date-time":"2022-05-14T15:03:02Z","timestamp":1652540582000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Optimally ordering IDK classifiers subject to deadlines"],"prefix":"10.1007","volume":"59","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4541-3445","authenticated-orcid":false,"given":"Sanjoy","family":"Baruah","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5621-8816","authenticated-orcid":false,"given":"Alan","family":"Burns","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5772-0928","authenticated-orcid":false,"given":"Robert I.","family":"Davis","sequence":"additional","affiliation":[]},{"given":"Yue","family":"Wu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,5,14]]},"reference":[{"key":"9383_CR1","doi-asserted-by":"publisher","unstructured":"Baruah SK, Burns A, Wu Y (2021) Optimal synthesis of IDK-cascades. In: Queudet A, Bate I, Lipari G (eds) RTNS\u20192021: 29th International Conference on Real-Time Networks and Systems, Nantes, France, April 7\u20139, 2021, ACM, pp 184\u2013191, https:\/\/doi.org\/10.1145\/3453417.3453425,","DOI":"10.1145\/3453417.3453425"},{"key":"9383_CR2","volume-title":"Dynamic programming","author":"R Bellman","year":"1957","unstructured":"Bellman R (1957) Dynamic programming, 1st edn. Princeton University Press, Princeton, NJ, USA","edition":"1"},{"key":"9383_CR3","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to Algorithms, 3rd edn. MIT Press, http:\/\/mitpress.mit.edu\/books\/introduction-algorithms"},{"key":"9383_CR4","doi-asserted-by":"publisher","unstructured":"Fujiyoshi H, Hirakawa T, Yamashita T (2019) Deep learning-based image recognition for autonomous driving. IATSS Research 43(4):244\u2013252 https:\/\/doi.org\/10.1016\/j.iatssr.2019.11.008, https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0386111219301566","DOI":"10.1016\/j.iatssr.2019.11.008"},{"key":"9383_CR5","doi-asserted-by":"publisher","unstructured":"Hu Y, Liu S, Abdelzaher TF, Wigness M, David P (2021) On exploring image resizing for optimizing criticality-based machine perception. In: 27th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2021, Houston, TX, USA, August 18\u201320, 2021, IEEE, pp 169\u2013178, https:\/\/doi.org\/10.1109\/RTCSA52859.2021.00027,","DOI":"10.1109\/RTCSA52859.2021.00027"},{"key":"9383_CR6","doi-asserted-by":"publisher","unstructured":"Khani F, Rinard MC, Liang P (2016) Unanimous prediction for 100% precision with application to learning semantic mappings. In: Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, ACL 2016, August 7\u201312, 2016, Berlin, Germany, Volume 1: Long Papers, The Association for Computer Linguistics, https:\/\/doi.org\/10.18653\/v1\/p16-1090,","DOI":"10.18653\/v1\/p16-1090"},{"key":"9383_CR7","unstructured":"Madani O, Georg M, Ross DA (2012) On using nearly-independent feature families for high precision and confidence. In: Hoi SCH, Buntine WL (eds) Proceedings of the 4th Asian Conference on Machine Learning, ACML 2012, Singapore, Singapore, November 4\u20136, 2012, JMLR.org, JMLR Proceedings, vol\u00a025, pp 269\u2013284, http:\/\/proceedings.mlr.press\/v25\/madani12.html"},{"issue":"2\u20133","key":"9383_CR8","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1007\/s10994-013-5377-0","volume":"92","author":"O Madani","year":"2013","unstructured":"Madani O, Georg M, Ross DA (2013) On using nearly-independent feature families for high precision and confidence. Mach Learn 92(2\u20133):457\u2013477. https:\/\/doi.org\/10.1007\/s10994-013-5377-0","journal-title":"Mach Learn"},{"key":"9383_CR9","unstructured":"Madras D, Pitassi T, Zemel RS (2018) Predict responsibly: Improving fairness and accuracy by learning to defer. In: Bengio S, Wallach HM, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R (eds) Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3\u20138, 2018, Montr\u00e9al, Canada, pp 6150\u20136160, https:\/\/proceedings.neurips.cc\/paper\/2018\/hash\/09d37c08f7b129e96277388757530c72-Abstract.html"},{"key":"9383_CR10","volume-title":"Learning machines","author":"N Nilsson","year":"1965","unstructured":"Nilsson N (1965) Learning machines. McGraw-Hill, New York"},{"issue":"1","key":"9383_CR11","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1016\/j.inffus.2007.07.002","volume":"9","author":"NC Oza","year":"2008","unstructured":"Oza NC, Tumer K (2008) Classifier ensembles: select real-world applications. Inf Fusion 9(1):4\u201320. https:\/\/doi.org\/10.1016\/j.inffus.2007.07.002","journal-title":"Inf Fusion"},{"issue":"3","key":"9383_CR12","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/s11263-015-0816-y","volume":"115","author":"O Russakovsky","year":"2015","unstructured":"Russakovsky O, Deng J, Su H, Krause J, Satheesh S, Ma S, Huang Z, Karpathy A, Khosla A, Bernstein MS, Berg AC, Fei-Fei L (2015) Imagenet large scale visual recognition challenge. Int J Comput Vis 115(3):211\u2013252. https:\/\/doi.org\/10.1007\/s11263-015-0816-y","journal-title":"Int J Comput Vis"},{"key":"9383_CR13","doi-asserted-by":"publisher","unstructured":"Trappenberg TP, Back AD (2000) A classification scheme for applications with ambiguous data. In: Proceedings of the IEEE-INNS-ENNS International Joint Conference on Neural Networks, IJCNN 2000, Neural Computing: New Challenges and Perspectives for the New Millennium, Como, Italy, July 24\u201327, 2000, Volume 6, IEEE Computer Society, pp 296\u2013301, https:\/\/doi.org\/10.1109\/IJCNN.2000.859412,","DOI":"10.1109\/IJCNN.2000.859412"},{"key":"9383_CR14","unstructured":"Wang X, Luo Y, Crankshaw D, Tumanov A, Yu F, Gonzalez JE (2018) IDK cascades: Fast deep learning by learning not to overthink. In: Globerson A, Silva R (eds) Proceedings of the Thirty-Fourth Conference on Uncertainty in Artificial Intelligence, UAI 2018, Monterey, California, USA, August 6\u201310, 2018, AUAI Press, pp 580\u2013590, http:\/\/auai.org\/uai2018\/proceedings\/papers\/212.pdf"}],"container-title":["Real-Time Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-022-09383-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11241-022-09383-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-022-09383-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,19]],"date-time":"2023-02-19T21:39:17Z","timestamp":1676842757000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11241-022-09383-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,14]]},"references-count":14,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["9383"],"URL":"https:\/\/doi.org\/10.1007\/s11241-022-09383-w","relation":{},"ISSN":["0922-6443","1573-1383"],"issn-type":[{"value":"0922-6443","type":"print"},{"value":"1573-1383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,14]]},"assertion":[{"value":"10 April 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 May 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}