{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:47:01Z","timestamp":1750308421473,"version":"3.41.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,7,14]],"date-time":"2021-07-14T00:00:00Z","timestamp":1626220800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. Emerg. Technol. Comput. Syst."],"published-print":{"date-parts":[[2021,10,31]]},"abstract":"<jats:p>\n            Given a classifier ensemble and a dataset, many examples may be confidently and accurately classified after only a subset of the base models in the ensemble is evaluated. Dynamically deciding to classify early can reduce both mean latency and CPU without harming the accuracy of the original ensemble. To achieve such gains, we propose jointly optimizing the evaluation order of the base models and early-stopping thresholds. Our proposed objective is a combinatorial optimization problem, but we provide a greedy algorithm that achieves a 4-approximation of the optimal solution under certain assumptions, which is also the best achievable polynomial-time approximation bound. Experiments on benchmark and real-world problems show that the proposed\n            <jats:bold>Quit When You Can (QWYC)<\/jats:bold>\n            algorithm can speed up average evaluation time by 1.8\u20132.7 times on even jointly trained ensembles, which are more difficult to speed up than independently or sequentially trained ensembles. QWYC\u2019s joint optimization of ordering and thresholds also performed better in experiments than previous fixed orderings, including gradient boosted trees\u2019 ordering.\n          <\/jats:p>","DOI":"10.1145\/3451209","type":"journal-article","created":{"date-parts":[[2021,7,14]],"date-time":"2021-07-14T16:27:00Z","timestamp":1626280020000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Quit When You Can: Efficient Evaluation of Ensembles by Optimized Ordering"],"prefix":"10.1145","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9664-4609","authenticated-orcid":false,"given":"Serena","family":"Wang","sequence":"first","affiliation":[{"name":"Google Research, Mountain View, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maya","family":"Gupta","sequence":"additional","affiliation":[{"name":"Google Research, Mountain View, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seungil","family":"You","sequence":"additional","affiliation":[{"name":"Kakao Mobility, Jeju City, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,7,14]]},"reference":[{"volume-title":"IEEE International Conference on Data Mining (ICDM).","author":"Basilico J. D.","key":"e_1_2_1_1_1","unstructured":"J. D. Basilico , M. A. Munson , T. G. Kolda , K. R. Dixon , and W. P. Kegelmeyer . 2011. COMET: A recipe for learning and using large ensembles on massive data . In IEEE International Conference on Data Mining (ICDM). J. D. Basilico, M. A. Munson, T. G. Kolda, K. R. Dixon, and W. P. Kegelmeyer. 2011. COMET: A recipe for learning and using large ensembles on massive data. In IEEE International Conference on Data Mining (ICDM)."},{"volume-title":"International Conference on Machine Learning (ICML).","author":"Benbouzid D.","key":"e_1_2_1_2_1","unstructured":"D. Benbouzid , R. Busa-Fekete , and B. K\u00e9gl . 2012. Fast classification using sparse decision DAGs . In International Conference on Machine Learning (ICML). D. Benbouzid, R. Busa-Fekete, and B. K\u00e9gl. 2012. Fast classification using sparse decision DAGs. In International Conference on Machine Learning (ICML)."},{"volume-title":"Conference on Computer Vision and Pattern Recognition (CVPR).","author":"Bourdev L.","key":"e_1_2_1_3_1","unstructured":"L. Bourdev and J. Brandt . 2005. Robust object detection via soft cascade . In Conference on Computer Vision and Pattern Recognition (CVPR). L. Bourdev and J. Brandt. 2005. Robust object detection via soft cascade. In Conference on Computer Vision and Pattern Recognition (CVPR)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1010933404324"},{"key":"e_1_2_1_5_1","unstructured":"R. L. Burden and J. D. Faires. 1985. Numerical Analysis (3rd ed.). PWS Publishers.  R. L. Burden and J. D. Faires. 1985. Numerical Analysis (3rd ed.). PWS Publishers."},{"key":"e_1_2_1_6_1","unstructured":"K. Canini A. Cotter M. M. Fard M. R. Gupta and J. Pfeifer. 2016. Fast and flexible monotonic functions with ensembles of lattices. In Advances in Neural Information Processing Systems (NIPS).  K. Canini A. Cotter M. M. Fard M. R. Gupta and J. Pfeifer. 2016. Fast and flexible monotonic functions with ensembles of lattices. In Advances in Neural Information Processing Systems (NIPS)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/IJCNN.2015.7280594"},{"key":"e_1_2_1_8_1","unstructured":"Dheeru Dua and Casey Graff. 2017. UCI Machine Learning Repository. http:\/\/archive.ics.uci.edu\/ml.  Dheeru Dua and Casey Graff. 2017. UCI Machine Learning Repository. http:\/\/archive.ics.uci.edu\/ml."},{"volume-title":"AAAI Conference on Artificial Intelligence.","author":"Fan W.","key":"e_1_2_1_9_1","unstructured":"W. Fan , F. Chu , H. Wang , and P. S. Yu . 2002. Pruning and dynamic scheduling of cost-sensitive ensembles . In AAAI Conference on Artificial Intelligence. W. Fan, F. Chu, H. Wang, and P. S. Yu. 2002. Pruning and dynamic scheduling of cost-sensitive ensembles. In AAAI Conference on Artificial Intelligence."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"U. Feige L. Lovasz and P. Tetali. 2004. Approximating min-sum set cover. Algorithmica (2004).  U. Feige L. Lovasz and P. Tetali. 2004. Approximating min-sum set cover. Algorithmica (2004).","DOI":"10.1007\/s00453-004-1110-5"},{"key":"e_1_2_1_11_1","unstructured":"M. Fernandez-Delgado E. Cernadas S. Barro and D. Amorim. 2014. Do we need hundreds of classifiers to solve real world classification problems?Journal of Machine Learning Research (JMLR) (2014).  M. Fernandez-Delgado E. Cernadas S. Barro and D. Amorim. 2014. Do we need hundreds of classifiers to solve real world classification problems?Journal of Machine Learning Research (JMLR) (2014)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1013203451"},{"key":"e_1_2_1_13_1","unstructured":"T. Gao and D. Koller. 2011. Active classification based on value of classifier. In Advances in Neural Information Processing Systems (NIPS).  T. Gao and D. Koller. 2011. Active classification based on value of classifier. In Advances in Neural Information Processing Systems (NIPS)."},{"key":"e_1_2_1_14_1","unstructured":"T. Hastie and R. Tibshirani. 1990. Generalized Additive Models. Chapman Hall New York.  T. Hastie and R. Tibshirani. 1990. Generalized Additive Models. Chapman Hall New York."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2008.204"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"T. Kim I. Budvytis and R. Cipolla. 2012. Making a shallow network deep: Conversion of a boosting classifier into a decision tree by Boolean optimisation. International Journal of Computer Vision (2012).  T. Kim I. Budvytis and R. Cipolla. 2012. Making a shallow network deep: Conversion of a boosting classifier into a decision tree by Boolean optimisation. International Journal of Computer Vision (2012).","DOI":"10.1007\/s11263-011-0461-z"},{"key":"e_1_2_1_17_1","unstructured":"S. Z. Li Z. Q. Zhang H. Shum and H. J. Zhang. 2002. FloatBoost learning for classification. In Advances in Neural Information Processing Systems (NIPS).  S. Z. Li Z. Q. Zhang H. Shum and H. J. Zhang. 2002. FloatBoost learning for classification. In Advances in Neural Information Processing Systems (NIPS)."},{"volume-title":"International Conference on Machine Learning (ICML).","author":"Margineantu D.","key":"e_1_2_1_18_1","unstructured":"D. Margineantu and T. Dietterich . 1997. Pruning adaptive boosting . In International Conference on Machine Learning (ICML). D. Margineantu and T. Dietterich. 1997. Pruning adaptive boosting. In International Conference on Machine Learning (ICML)."},{"volume-title":"International Conference on Machine Learning (ICML).","author":"Martinez-Munoz G.","key":"e_1_2_1_19_1","unstructured":"G. Martinez-Munoz and A. Suarez . 2006. Pruning in ordered bagging ensembles . In International Conference on Machine Learning (ICML). G. Martinez-Munoz and A. Suarez. 2006. Pruning in ordered bagging ensembles. In International Conference on Machine Learning (ICML)."},{"volume-title":"International Conference on Database Theory.","author":"Munagala K.","key":"e_1_2_1_20_1","unstructured":"K. Munagala , S. Babu , R. Motwani , and J. Widom . 2005. The pipelined set cover problem . In International Conference on Database Theory. K. Munagala, S. Babu, R. Motwani, and J. Widom. 2005. The pipelined set cover problem. In International Conference on Database Theory."},{"key":"e_1_2_1_21_1","unstructured":"F. Nan J. Wang and V. Saligrama. 2016. Pruning random forests for prediction on a budget. In Advances in Neural Information Processing Systems (NIPS).  F. Nan J. Wang and V. Saligrama. 2016. Pruning random forests for prediction on a budget. In Advances in Neural Information Processing Systems (NIPS)."},{"key":"e_1_2_1_22_1","volume-title":"International Conference on KDD-Cup","volume":"7","author":"Niculescu-Mizil A.","unstructured":"A. Niculescu-Mizil , C. Perlich , G. Swirszcz , V. Sindhwani , Y. Liu , P. Melville , D. Wang , J. Xiao , J. Hu , M. Singh amd W. X. Shang , and Y. F. Zhu . 2009. Winning the KDD cup orange challenge with ensemble selection . In International Conference on KDD-Cup , Vol. 7 . JMLR.org, 23\u201334. A. Niculescu-Mizil, C. Perlich, G. Swirszcz, V. Sindhwani, Y. Liu, P. Melville, D. Wang, J. Xiao, J. Hu, M. Singh amd W. X. Shang, and Y. F. Zhu. 2009. Winning the KDD cup orange challenge with ensemble selection. In International Conference on KDD-Cup, Vol. 7. JMLR.org, 23\u201334."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2567709.2627671"},{"volume-title":"AAAI Conference on Artificial Intelligence.","author":"Qian C.","key":"e_1_2_1_24_1","unstructured":"C. Qian , Y. Yu , and Z. H. Zhou . 2015. Pareto ensemble pruning . In AAAI Conference on Artificial Intelligence. C. Qian, Y. Yu, and Z. H. Zhou. 2015. Pareto ensemble pruning. In AAAI Conference on Artificial Intelligence."},{"key":"e_1_2_1_25_1","unstructured":"M. J. Saberian and N. Vasconcelos. 2010. Boosting classfier cascades. In Advances in Neural Information Processing Systems (NIPS).  M. J. Saberian and N. Vasconcelos. 2010. Boosting classfier cascades. In Advances in Neural Information Processing Systems (NIPS)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/SBRN.2006.1"},{"volume-title":"International Conference on Information Fusion.","author":"Santos E. M. D.","key":"e_1_2_1_27_1","unstructured":"E. M. D. Santos , R. Sabourin , and P. Maupin . 2007. Ambiguity-guided dynamic selection of ensemble of classifiers . In International Conference on Information Fusion. E. M. D. Santos, R. Sabourin, and P. Maupin. 2007. Ambiguity-guided dynamic selection of ensemble of classifiers. In International Conference on Information Fusion."},{"volume-title":"Conference on Computer Vision and Pattern Recognition (CVPR).","author":"Schwing G. A.","key":"e_1_2_1_28_1","unstructured":"G. A. Schwing , C. Zach , Y. Zheng , and M. Pollefeys . 2011. Adaptive random forest - How many experts to ask before making a decision? In Conference on Computer Vision and Pattern Recognition (CVPR). G. A. Schwing, C. Zach, Y. Zheng, and M. Pollefeys. 2011. Adaptive random forest - How many experts to ask before making a decision? In Conference on Computer Vision and Pattern Recognition (CVPR)."},{"volume-title":"Conference on Computer Vision and Pattern Recognition (CVPR).","author":"Sochman J.","key":"e_1_2_1_29_1","unstructured":"J. Sochman and J. Matas . 2005. Waldboost-learning for time constrained sequential detection . In Conference on Computer Vision and Pattern Recognition (CVPR). J. Sochman and J. Matas. 2005. Waldboost-learning for time constrained sequential detection. In Conference on Computer Vision and Pattern Recognition (CVPR)."},{"key":"e_1_2_1_30_1","unstructured":"V. Soto A. Suarez and G. Martinez-Munoz. 2016. An urn model for majority voting in classification ensembles. In Advances in Neural Information Processing Systems (NIPS).  V. Soto A. Suarez and G. Martinez-Munoz. 2016. An urn model for majority voting in classification ensembles. In Advances in Neural Information Processing Systems (NIPS)."},{"volume-title":"International Conference on Machine Learning (ICML).","author":"Sun P.","key":"e_1_2_1_31_1","unstructured":"P. Sun and J. Zhou . 2013. Saving evaluation time for the decision function in boosting: Representation and reording base learner . In International Conference on Machine Learning (ICML). P. Sun and J. Zhou. 2013. Saving evaluation time for the decision function in boosting: Representation and reording base learner. In International Conference on Machine Learning (ICML)."},{"volume-title":"European Conference on Machine Learning (ECML).","author":"Tamon C.","key":"e_1_2_1_32_1","unstructured":"C. Tamon and J. Xiang . 2000. On the boosting pruning problem . In European Conference on Machine Learning (ECML). C. Tamon and J. Xiang. 2000. On the boosting pruning problem. In European Conference on Machine Learning (ECML)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8655(99)00012-4"},{"volume-title":"ICCV Workshop on Statistical and Computational Theories of Vision.","author":"Viola P.","key":"e_1_2_1_34_1","unstructured":"P. Viola and M. Jones . 2001. Robust real-time object detection . In ICCV Workshop on Statistical and Computational Theories of Vision. P. Viola and M. Jones. 2001. Robust real-time object detection. In ICCV Workshop on Statistical and Computational Theories of Vision."},{"key":"e_1_2_1_35_1","unstructured":"J. Wang K. Trapeznikov and V. Saligrama. 2015. Efficient Learning by directed acyclic graph for resource constrained prediction. In Advances in Neural Information Processing Systems (NIPS).  J. Wang K. Trapeznikov and V. Saligrama. 2015. Efficient Learning by directed acyclic graph for resource constrained prediction. In Advances in Neural Information Processing Systems (NIPS)."},{"key":"e_1_2_1_36_1","volume-title":"Stacked generalization. Neural Networks 5","author":"Wolpert D. H.","year":"1992","unstructured":"D. H. Wolpert . 1992. Stacked generalization. Neural Networks 5 ( 1992 ). D. H. Wolpert. 1992. Stacked generalization. Neural Networks 5 (1992)."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.588027"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2010.05.021"},{"volume-title":"International Conference on Machine Learning (ICML).","author":"Xu Z.","key":"e_1_2_1_39_1","unstructured":"Z. Xu , M. J. Kusner , K. Q. Weinberger , and M. Chen . 2013. Cost-sensitive tree of classifiers . In International Conference on Machine Learning (ICML). Z. Xu, M. J. Kusner, K. Q. Weinberger, and M. Chen. 2013. Cost-sensitive tree of classifiers. In International Conference on Machine Learning (ICML)."},{"key":"e_1_2_1_40_1","unstructured":"C. Zhang and P. Viola. 2007. Multiple-instance pruning for learning efficient cascade detectors. In Advances in Neural Information Processing Systems (NIPS).  C. Zhang and P. Viola. 2007. Multiple-instance pruning for learning efficient cascade detectors. In Advances in Neural Information Processing Systems (NIPS)."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/11564386_16"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00190-X"}],"container-title":["ACM Journal on Emerging Technologies in Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3451209","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3451209","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:25Z","timestamp":1750268965000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3451209"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,14]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,10,31]]}},"alternative-id":["10.1145\/3451209"],"URL":"https:\/\/doi.org\/10.1145\/3451209","relation":{},"ISSN":["1550-4832","1550-4840"],"issn-type":[{"type":"print","value":"1550-4832"},{"type":"electronic","value":"1550-4840"}],"subject":[],"published":{"date-parts":[[2021,7,14]]},"assertion":[{"value":"2020-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}