{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T10:02:05Z","timestamp":1766138525079,"version":"3.37.3"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,12,26]],"date-time":"2023-12-26T00:00:00Z","timestamp":1703548800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,12,26]],"date-time":"2023-12-26T00:00:00Z","timestamp":1703548800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100024020","name":"University of Mons","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100024020","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2024,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Active learning is a paradigm of machine learning which aims at reducing the amount of labeled data needed to train a classifier. Its overall principle is to sequentially select the most informative data points, which amounts to determining the uncertainty of regions of the input space. The main challenge lies in building a procedure that is computationally efficient and that offers appealing theoretical properties; most of the current methods satisfy only one or the other. In this paper, we use the classification with rejection in a novel way to estimate the uncertain regions. We provide an active learning algorithm and prove its theoretical benefits under classical assumptions. In addition to the theoretical results, numerical experiments are carried out on synthetic and non-synthetic datasets. These experiments provide empirical evidence that the use of rejection arguments in our active learning algorithm is beneficial and allows good performance in various statistical situations.<\/jats:p>","DOI":"10.1007\/s10994-023-06494-8","type":"journal-article","created":{"date-parts":[[2023,12,26]],"date-time":"2023-12-26T17:02:22Z","timestamp":1703610142000},"page":"753-788","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Active learning algorithm through the lens of rejection arguments"],"prefix":"10.1007","volume":"113","author":[{"given":"Christophe","family":"Denis","sequence":"first","affiliation":[]},{"given":"Mohamed","family":"Hebiri","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2122-9942","authenticated-orcid":false,"given":"Boris","family":"Ndjia Njike","sequence":"additional","affiliation":[]},{"given":"Xavier","family":"Siebert","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,12,26]]},"reference":[{"key":"6494_CR1","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1214\/009053606000001217","volume":"35","author":"J Audibert","year":"2007","unstructured":"Audibert, J., & Tsybakov, A. (2007). Fast learning rates for plug-in classifiers. Annals of Statistics, 35, 608\u2013633.","journal-title":"Annals of Statistics"},{"key":"6494_CR2","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/j.jcss.2008.07.003","volume":"75","author":"M-F Balcan","year":"2009","unstructured":"Balcan, M.-F., Beygelzimer, A., & Langford, J. (2009). Agnostic active learning. Journal of Computer and System Sciences, 75, 78\u201389.","journal-title":"Journal of Computer and System Sciences"},{"key":"6494_CR3","doi-asserted-by":"crossref","unstructured":"Beygelzimer, A., Dasgupta, S., & Langford, J. (2009). Importance weighted active learning. In Proceedings of the 26th annual international conference on machine learning (pp. 49\u201356).","DOI":"10.1145\/1553374.1553381"},{"key":"6494_CR4","doi-asserted-by":"publisher","first-page":"2339","DOI":"10.1109\/TIT.2008.920189","volume":"54","author":"RM Castro","year":"2008","unstructured":"Castro, R. M., & Nowak, R. D. (2008). Minimax bounds for active learning. IEEE Transactions on Information Theory, 54, 2339\u20132353.","journal-title":"IEEE Transactions on Information Theory"},{"key":"6494_CR5","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1109\/TEC.1957.5222035","volume":"4","author":"C Chow","year":"1957","unstructured":"Chow, C. (1957). An optimum character recognition system using decision functions. IRE Transactions on Electronic Computers, 4, 247\u2013254.","journal-title":"IRE Transactions on Electronic Computers"},{"key":"6494_CR6","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/BF00993277","volume":"15","author":"D Cohn","year":"1994","unstructured":"Cohn, D., Atlas, L., & Ladner, R. (1994). Improving generalization with active learning. Machine Learning, 15, 201\u2013221.","journal-title":"Machine Learning"},{"key":"6494_CR7","doi-asserted-by":"crossref","unstructured":"Cortes, C., DeSalvo, G., & Mohri, M. (2016). Learning with rejection. In International conference on algorithmic learning theory (pp. 67\u201382). Springer.","DOI":"10.1007\/978-3-319-46379-7_5"},{"key":"6494_CR8","doi-asserted-by":"publisher","first-page":"1767","DOI":"10.1016\/j.tcs.2010.12.054","volume":"412","author":"S Dasgupta","year":"2011","unstructured":"Dasgupta, S. (2011). Two faces of active learning. Theoretical Computer Science, 412, 1767\u20131781.","journal-title":"Theoretical Computer Science"},{"key":"6494_CR9","volume-title":"A general agnostic active learning algorithm","author":"S Dasgupta","year":"2007","unstructured":"Dasgupta, S., Hsu, D. J., & Monteleoni, C. (2007). A general agnostic active learning algorithm. Citeseer."},{"key":"6494_CR10","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1080\/10485252.2019.1689241","volume":"32","author":"C Denis","year":"2019","unstructured":"Denis, C., & Hebiri, M. (2019). Consistency of plug-in confidence sets for classification in semi-supervised learning. Journal of Nonparametric Statistics, 32, 42\u201372.","journal-title":"Journal of Nonparametric Statistics"},{"key":"6494_CR11","unstructured":"Denis, C., Hebiri, M., & Zaoui, A. (2020). Regression with reject option and application to knn. arXiv preprint arXiv:2006.16597"},{"key":"6494_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0711-5","volume-title":"A probabilistic theory of pattern recognition","author":"L Devroye","year":"1996","unstructured":"Devroye, L., Gy\u00f6rfi, L., & Lugosi, G. (1996). A probabilistic theory of pattern recognition. Springer."},{"key":"6494_CR13","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1023\/A:1007330508534","volume":"28","author":"Y Freund","year":"1997","unstructured":"Freund, Y., Seung, H. S., Shamir, E., & Tishby, N. (1997). Selective sampling using the query by committee algorithm. Machine Learning, 28, 133\u2013168.","journal-title":"Machine Learning"},{"key":"6494_CR14","doi-asserted-by":"publisher","first-page":"982","DOI":"10.1214\/15-AOS1395","volume":"44","author":"S Gadat","year":"2016","unstructured":"Gadat, S., Klein, T., & Marteau, C. (2016). Classification in general finite dimensional spaces with the k-nearest neighbor rule. The Annals of Statistics, 44, 982\u20131009.","journal-title":"The Annals of Statistics"},{"key":"6494_CR15","series-title":"Cambridge series in statistical and probabilistic mathematics","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107337862","volume-title":"Mathematical foundations of infinite-dimensional statistical models","author":"E Gin\u00e9","year":"2015","unstructured":"Gin\u00e9, E., & Nickl, R. (2015). Mathematical foundations of infinite-dimensional statistical models. Cambridge series in statistical and probabilistic mathematicsCambridge University Press."},{"key":"6494_CR16","unstructured":"Grandvalet, Y., Rakotomamonjy, A., Keshet, J., & Canu, S. (2009). Support vector machines with a reject option. In NIPS (pp. 537\u2013544)."},{"key":"6494_CR17","doi-asserted-by":"crossref","unstructured":"Hanneke, S. (2007). A bound on the label complexity of agnostic active learning. In Proceedings of the 24th international conference on Machine learning (pp. 353\u2013360).","DOI":"10.1145\/1273496.1273541"},{"key":"6494_CR18","first-page":"333","volume":"2","author":"S Hanneke","year":"2011","unstructured":"Hanneke, S. (2011). Rates of convergence in active learning. The Annals of Statistics, 2, 333\u2013361.","journal-title":"The Annals of Statistics"},{"key":"6494_CR19","first-page":"3487","volume":"16","author":"S Hanneke","year":"2015","unstructured":"Hanneke, S., & Yang, L. (2015). Minimax analysis of active learning. Journal of Machine Learning Research, 16, 3487\u20133602.","journal-title":"Journal of Machine Learning Research"},{"key":"6494_CR20","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1561\/2200000037","volume":"7","author":"S Hanneke","year":"2014","unstructured":"Hanneke, S., et al. (2014). Theory of disagreement-based active learning. Foundations and Trends in Machine Learning, 7, 131\u2013309.","journal-title":"Foundations and Trends in Machine Learning"},{"key":"6494_CR21","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1002\/cjs.5550340410","volume":"34","author":"R Herbei","year":"2006","unstructured":"Herbei, R., & Wegkamp, M. (2006). Classification with reject option. Canadian Journal of Statistics, 34, 709\u2013721.","journal-title":"Canadian Journal of Statistics"},{"key":"6494_CR22","unstructured":"Kpotufe, S., Yuan, G., & Zhao, Y. (2022). Nuances in margin conditions determine gains in active learning. In International conference on artificial intelligence and statistics (pp. 8112\u20138126). PMLR."},{"key":"6494_CR23","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1093\/biomet\/asu038","volume":"101","author":"J Lei","year":"2014","unstructured":"Lei, J. (2014). Classification with confidence. Biometrika, 101, 755\u2013769.","journal-title":"Biometrika"},{"key":"6494_CR24","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-1-4471-2099-5_1","volume-title":"SIGIR \u201994","author":"DD Lewis","year":"1994","unstructured":"Lewis, D. D., & Gale, W. A. (1994). A sequential algorithm for training text classifiers. In B. W. Croft & C. J. van Rijsbergen (Eds.), SIGIR \u201994 (pp. 3\u201312). Springer."},{"key":"6494_CR25","first-page":"1","volume":"65","author":"A Locatelli","year":"2017","unstructured":"Locatelli, A., Carpentier, A., & Kpotufe, S. (2017). Adaptivity to noise parameters in nonparametric active learning. Proceedings of Machine Learning Research, 65, 1\u201334.","journal-title":"Proceedings of Machine Learning Research"},{"key":"6494_CR26","unstructured":"Locatelli, A., Carpentier, A., & Kpotufe, S. (2018). An adaptive strategy for active learning with smooth decision boundary. In Algorithmic learning theory (pp. 547\u2013571). PMLR."},{"key":"6494_CR27","doi-asserted-by":"crossref","unstructured":"Lugosi, G. (2002). Pattern classification and learning theory. In Principles of nonparametric learning (pp. 1\u201356). Springer.","DOI":"10.1007\/978-3-7091-2568-7_1"},{"key":"6494_CR28","doi-asserted-by":"publisher","first-page":"2326","DOI":"10.1214\/009053606000000786","volume":"34","author":"P Massart","year":"2006","unstructured":"Massart, P., & N\u00e9d\u00e9lec, \u00c9. (2006). Risk bounds for statistical learning. Annals of Statistics, 34, 2326\u20132366.","journal-title":"Annals of Statistics"},{"key":"6494_CR29","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1007\/s00440-016-0720-6","volume":"168","author":"S Mendelson","year":"2017","unstructured":"Mendelson, S. (2017). On aggregation for heavy-tailed classes. Probability Theory and Related Fields, 168, 641\u2013674.","journal-title":"Probability Theory and Related Fields"},{"key":"6494_CR30","first-page":"1","volume":"13","author":"S Minsker","year":"2012","unstructured":"Minsker, S. (2012). Plug-in approach to active learning. Journal of Machine Learning Research, 13, 1.","journal-title":"Journal of Machine Learning Research"},{"key":"6494_CR31","unstructured":"Naadeem, M., Zucker, J., & Hanczar, B. (2010). Accuracy-rejection curves (ARCs) for comparing classification methods with a reject option. In MLSB (pp. 65\u201381)."},{"key":"6494_CR32","first-page":"2825","volume":"12","author":"F Pedregosa","year":"2011","unstructured":"Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., & Duchesnay, E. (2011). Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12, 2825\u20132830.","journal-title":"Journal of Machine Learning Research"},{"key":"6494_CR33","unstructured":"Puchkin, N. & Zhivotovskiy, N. (2021). Exponential savings in agnostic active learning through abstention. In Conference on learning theory (pp. 3806\u20133832). PMLR."},{"key":"6494_CR34","unstructured":"Schreuder, N. & Chzhen, E. (2021). Classification with abstention but without disparities. In Proceedings of the thirty-seventh conference on uncertainty in artificial intelligence, UAI 2021, virtual event, 27\u201330 July 2021. Proceedings of machine learning research (Vol. 61, pp. 1227\u20131236). AUAI Press."},{"key":"6494_CR35","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1023\/A:1022673506211","volume":"15","author":"B Settles","year":"1994","unstructured":"Settles, B. (1994). Active learning literature survey. Machine Learning, 15, 201\u2013221.","journal-title":"Machine Learning"},{"key":"6494_CR36","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1109\/JSAIT.2021.3081433","volume":"2","author":"S Shekhar","year":"2021","unstructured":"Shekhar, S., Ghavamzadeh, M., & Javidi, T. (2021). Active learning for classification with abstention. IEEE Journal on Selected Areas in Information Theory, 2, 705\u2013719.","journal-title":"IEEE Journal on Selected Areas in Information Theory"},{"key":"6494_CR37","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1214\/aos\/1079120131","volume":"32","author":"A Tsybakov","year":"2004","unstructured":"Tsybakov, A. (2004). Optimal aggregation of classifiers in statistical learning. Annals of Statistics, 32, 135\u2013166.","journal-title":"Annals of Statistics"},{"key":"6494_CR38","volume-title":"Introduction to nonparametric estimation","author":"A Tsybakov","year":"2008","unstructured":"Tsybakov, A. (2008). Introduction to nonparametric estimation (1st ed.). Springer.","edition":"1"},{"key":"6494_CR39","unstructured":"Urner, R., Wulff, S., & Ben-David, S. (2013). Plal: Cluster-based active learning. In Conference on learning theory (pp. 376\u2013397). PMLR."},{"key":"6494_CR40","unstructured":"Vovk, V., Gammerman, A., & Saunders, C. (1999). Machine-learning applications of algorithmic randomness. In Proceedings of the sixteenth international conference on machine learning (pp. 444\u2013453). Morgan Kaufmann."},{"key":"6494_CR41","volume-title":"Algorithmic learning in a random world","author":"V Vovk","year":"2005","unstructured":"Vovk, V., Gammerman, A., & Shafer, G. (2005). Algorithmic learning in a random world. Springer."},{"key":"6494_CR42","first-page":"111","volume":"11","author":"M Yuan","year":"2010","unstructured":"Yuan, M., & Wegkamp, M. (2010). Classification methods with reject option based on convex risk minimization. Journal of Machine Learning Research, 11, 111\u2013130.","journal-title":"Journal of Machine Learning Research"},{"key":"6494_CR43","unstructured":"Zhu, Y. & Nowak, R. (2022). Efficient active learning with abstention. arXiv preprint arXiv:2204.00043"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-023-06494-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-023-06494-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-023-06494-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,18]],"date-time":"2024-01-18T19:12:10Z","timestamp":1705605130000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-023-06494-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,26]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["6494"],"URL":"https:\/\/doi.org\/10.1007\/s10994-023-06494-8","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"type":"print","value":"0885-6125"},{"type":"electronic","value":"1573-0565"}],"subject":[],"published":{"date-parts":[[2023,12,26]]},"assertion":[{"value":"25 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 November 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 November 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 December 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Yes.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}},{"value":"Yes.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"Yes.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"Yes.","order":6,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}]}}