{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:33:16Z","timestamp":1740123196848,"version":"3.37.3"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2021,4,18]],"date-time":"2021-04-18T00:00:00Z","timestamp":1618704000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,4,18]],"date-time":"2021-04-18T00:00:00Z","timestamp":1618704000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2021,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In some applications, acquiring covariates comes at a cost which is not negligible. For example in the medical domain, in order to classify whether a patient has diabetes or not, measuring glucose tolerance can be expensive. Assuming that the cost of each covariate, and the cost of misclassification can be specified by the user, our goal is to minimize the (expected) total cost of classification, i.e. the cost of misclassification plus the cost of the acquired covariates. We formalize this optimization goal using the (conditional) Bayes risk and describe the optimal solution using a recursive procedure. Since the procedure is computationally infeasible, we consequently introduce two assumptions: (1) the optimal classifier can be represented by a generalized additive model, (2) the optimal sets of covariates are limited to a sequence of sets of increasing size. We show that under these two assumptions, a computationally efficient solution exists. Furthermore, on several medical datasets, we show that the proposed method achieves in most situations the lowest total costs when compared to various previous methods. Finally, we weaken the requirement on the user to specify all misclassification costs by allowing the user to specify the minimally acceptable recall (target recall). Our experiments confirm that the proposed method achieves the target recall while minimizing the false discovery rate and the covariate acquisition costs better than previous methods.<\/jats:p>","DOI":"10.1007\/s10994-021-05958-z","type":"journal-article","created":{"date-parts":[[2021,4,18]],"date-time":"2021-04-18T18:02:37Z","timestamp":1618768957000},"page":"1067-1104","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Adaptive covariate acquisition for minimizing total cost of classification"],"prefix":"10.1007","volume":"110","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1123-4369","authenticated-orcid":false,"given":"Daniel","family":"Andrade","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuzuru","family":"Okajima","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,4,18]]},"reference":[{"key":"5958_CR1","volume-title":"An introduction to multivariate statistical analysis","author":"TW Anderson","year":"2003","unstructured":"Anderson, T. W. (2003). An introduction to multivariate statistical analysis (Vol. 2). Wiley."},{"key":"5958_CR2","unstructured":"Andrade, D., & Okajima, Y. (2019). Efficient bayes risk estimation for cost-sensitive classification. In The 22nd international conference on artificial intelligence and statistics (pp. 3372\u20133381)"},{"key":"5958_CR3","unstructured":"Bayer-Zubek, V. (2004). Learning diagnostic policies from examples by systematic search. In Proceedings of the 20th conference on uncertainty in artificial intelligence (pp. 27\u201334). AUAI Press."},{"key":"5958_CR4","unstructured":"Benbouzid, D., Busa-Fekete, R., & K\u00e9gl, B. (2012). Fast classification using sparse decision dags. In Proceedings of the 29th international conference on international conference on machine learning (pp. 747\u2013754)"},{"key":"5958_CR5","unstructured":"Berger, J. O. (2013). Statistical decision theory and Bayesian analysis. Springer."},{"key":"5958_CR6","unstructured":"Bilgic, M., & Getoor, L. (2007). Voila: Efficient feature-value acquisition for classification. In Proceedings of the national conference on artificial intelligence (Vol.\u00a022, p. 1225). AAAI Press, Menlo Park."},{"key":"5958_CR7","doi-asserted-by":"crossref","unstructured":"Contardo, G., Denoyer, L., & Arti\u00e8res, T. (2016). Sequential cost-sensitive feature acquisition. In International symposium on intelligent data analysis (pp. 284\u2013294). Springer.","DOI":"10.1007\/978-3-319-46349-0_25"},{"key":"5958_CR8","doi-asserted-by":"crossref","unstructured":"Dulac-Arnold, G., Denoyer, L., Preux, P., & Gallinari, P. (2011). Datum-wise classification: a sequential approach to sparsity. In Joint European conference on machine learning and knowledge discovery in databases (pp. 375\u2013390). Springer.","DOI":"10.1007\/978-3-642-23780-5_34"},{"issue":"1\u20132","key":"5958_CR9","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s10994-012-5306-7","volume":"89","author":"G Dulac-Arnold","year":"2012","unstructured":"Dulac-Arnold, G., Denoyer, L., Preux, P., & Gallinari, P. (2012). Sequential approaches for learning datum-wise sparse representations. Machine Learning, 89(1\u20132), 87\u2013122.","journal-title":"Machine Learning"},{"key":"5958_CR10","first-page":"973","volume":"17","author":"C Elkan","year":"2001","unstructured":"Elkan, C. (2001). The foundations of cost-sensitive learning. International Joint Conference on Artificial Intelligence, 17, 973\u2013978.","journal-title":"International Joint Conference on Artificial Intelligence"},{"key":"5958_CR11","doi-asserted-by":"publisher","first-page":"1189","DOI":"10.1214\/aos\/1013203451","volume":"29","author":"JH Friedman","year":"2001","unstructured":"Friedman, J. H. (2001). Greedy function approximation: A gradient boosting machine. Annals of Statistics, 29, 1189\u20131232.","journal-title":"Annals of Statistics"},{"key":"5958_CR12","unstructured":"Gao, T., & Koller, D. (2011). Active classification based on value of classifier. In Advances in neural information processing systems (pp 1062\u20131070)."},{"key":"5958_CR13","doi-asserted-by":"crossref","unstructured":"Gelman, A., Stern, H. S., Carlin, J. B., Dunson, D. B., Vehtari, A., & Rubin, D. B. (2013). Bayesian data analysis. Chapman and Hall\/CRC.","DOI":"10.1201\/b16018"},{"issue":"23","key":"5958_CR14","doi-asserted-by":"publisher","first-page":"e215","DOI":"10.1161\/01.CIR.101.23.e215","volume":"101","author":"AL Goldberger","year":"2000","unstructured":"Goldberger, A. L., Amaral, L. A., Glass, L., Hausdorff, J. M., Ivanov, P. C., Mark, R. G., Mietus, J. E., Moody, G. B., Peng, C. K., & Stanley, H. E. (2000). Physiobank, physiotoolkit, and physionet: components of a new research resource for complex physiologic signals. Circulation, 101(23), e215\u2013e220.","journal-title":"Circulation"},{"key":"5958_CR15","unstructured":"Gong, W., Tschiatschek, S., Nowozin, S., Turner, R.E., Hern\u00e1ndez-Lobato, J. M., & Zhang, C. (2019). Icebreaker: Element-wise efficient information acquisition with a bayesian deep latent gaussian model. In Advances in neural information processing systems (pp 14791\u201314802)."},{"issue":"2","key":"5958_CR16","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/S0004-3702(02)00209-6","volume":"139","author":"R Greiner","year":"2002","unstructured":"Greiner, R., Grove, A. J., & Roth, D. (2002). Learning cost-sensitive active classifiers. Artificial Intelligence, 139(2), 137\u2013174.","journal-title":"Artificial Intelligence"},{"key":"5958_CR17","doi-asserted-by":"crossref","unstructured":"Hastie, T., Tibshirani, R., & Friedman, J. (2009). The elements of statistical learning: Data mining, inference, and prediction. Springer.","DOI":"10.1007\/978-0-387-84858-7"},{"key":"5958_CR18","doi-asserted-by":"crossref","unstructured":"Hastie, T., Tibshirani, R., & Wainwright, M. (2015). Statistical learning with sparsity: The lasso and generalizations. Chapman and Hall\/CRC.","DOI":"10.1201\/b18401"},{"key":"5958_CR19","unstructured":"He, H., Eisner, J., & Daume, H. (2012) Imitation learning by coaching. In Advances in neural information processing systems (pp 3149\u20133157)."},{"key":"5958_CR20","unstructured":"Janisch, J., Pevn\u1ef3, T., & Lis\u1ef3, V. (2017). Classification with costly features using deep reinforcement learning. arXiv preprint arXiv:171107364."},{"issue":"5","key":"5958_CR21","doi-asserted-by":"publisher","first-page":"1474","DOI":"10.1016\/j.patcog.2006.11.008","volume":"40","author":"S Ji","year":"2007","unstructured":"Ji, S., & Carin, L. (2007). Cost-sensitive feature acquisition and classification. Pattern Recognition, 40(5), 1474\u20131485.","journal-title":"Pattern Recognition"},{"issue":"8","key":"5958_CR22","doi-asserted-by":"publisher","first-page":"2252","DOI":"10.1109\/TNNLS.2018.2880403","volume":"30","author":"M Kachuee","year":"2018","unstructured":"Kachuee, M., Darabi, S., Moatamed, B., & Sarrafzadeh, M. (2018). Dynamic feature acquisition using denoising autoencoders. IEEE Transactions on Neural Networks and Learning Systems, 30(8), 2252\u20132262.","journal-title":"IEEE Transactions on Neural Networks and Learning Systems"},{"key":"5958_CR23","unstructured":"Kanani, P., & Melville, P. (2008). Prediction-time active feature-value acquisition for cost-effective customer targeting. In Advances in neural information processing systems (NIPS)."},{"issue":"181","key":"5958_CR24","doi-asserted-by":"publisher","first-page":"748","DOI":"10.1016\/S0022-5347(09)62087-5","volume":"4","author":"K Kanao","year":"2009","unstructured":"Kanao, K., Komori, O., Nakashima, J., Ohigashi, T., Kikuchi, E., Miyajima, A., Nakagawa, K., Eguchi, S., & Oya, M. (2009). PSA cut-off nomogram that avoid over-detection of prostate cancer in elderly men. The Journal of Urology, 4(181), 748.","journal-title":"The Journal of Urology"},{"key":"5958_CR25","unstructured":"Kapoor, A., & Horvitz, E. (2009). Breaking boundaries: Active information acquisition across learning and diagnosis. InProceedings of the 22nd international conference on neural information processing systems (pp. 898\u2013906). Curran Associates Inc."},{"key":"5958_CR26","unstructured":"Karayev, S., Fritz, M. J., & Darrell, T. (2013). Dynamic feature selection for classification on a budget. In International conference on machine learning (ICML): Workshop on prediction with sequential models."},{"key":"5958_CR27","doi-asserted-by":"crossref","unstructured":"Kusner, M. J., Chen, W., Zhou, Q., Xu, Z. E., Weinberger, K. Q., & Chen, Y. (2014). Feature-cost sensitive learning with submodular trees of classifiers. In AAAI (pp. 1939\u20131945).","DOI":"10.1609\/aaai.v28i1.8967"},{"key":"5958_CR28","unstructured":"Lakkaraju, H., & Rudin, C. (2017). Learning cost-effective and interpretable treatment regimes. In Artificial intelligence and statistics (pp. 166\u2013175)."},{"issue":"3","key":"5958_CR29","doi-asserted-by":"publisher","first-page":"1029","DOI":"10.3150\/12-BEJ487","volume":"20","author":"K Lounici","year":"2014","unstructured":"Lounici, K. (2014). High-dimensional covariance matrix estimation with missing observations. Bernoulli, 20(3), 1029\u20131058.","journal-title":"Bernoulli"},{"key":"5958_CR30","unstructured":"Ma, C., Tschiatschek, S., Palla, K., Hernandez-Lobato, J. M., Nowozin, S., & Zhang, C. (2019). Eddi: Efficient dynamic discovery of high-value information with partial VAE. In International conference on machine learning (pp. 4234\u20134243)."},{"key":"5958_CR31","unstructured":"Nan, F., & Saligrama, V. (2017). Adaptive classification for prediction under a budget. In Advances in neural information processing systems (pp. 4730\u20134740)."},{"key":"5958_CR32","doi-asserted-by":"crossref","unstructured":"Nan, F., Wang, J., Trapeznikov, K., & Saligrama, V. (2014). Fast margin-based cost-sensitive classification. In 2014 IEEE international conference on acoustics, speech and signal processing (ICASSP) (pp. 2952\u20132956). IEEE.","DOI":"10.1109\/ICASSP.2014.6854141"},{"key":"5958_CR33","unstructured":"Nan, F., Wang, J., & Saligrama, V. (2015). Feature-budgeted random forest. In International conference on machine learning (pp. 1983\u20131991)."},{"key":"5958_CR34","unstructured":"Nan, F., Wang, J., & Saligrama, V. (2016). Pruning random forests for prediction on a budget. In Advances in neural information processing systems (pp. 2334\u20132342)."},{"issue":"1","key":"5958_CR35","first-page":"85","volume":"4","author":"RB O\u2019Hara","year":"2009","unstructured":"O\u2019Hara, R. B., & Sillanp\u00e4\u00e4, M. J. (2009). A review of Bayesian variable selection methods: What, how and which. Bayesian Analysis, 4(1), 85\u2013117.","journal-title":"Bayesian Analysis"},{"key":"5958_CR36","unstructured":"Peter, S., Diego, F., Hamprecht, F. A., & Nadler, B. (2017). Cost efficient gradient boosting. In Advances in neural information processing systems (pp 1550\u20131560)."},{"key":"5958_CR37","doi-asserted-by":"crossref","unstructured":"Rasmussen, C. E., & Williams, C. K. (2006). Gaussian processes for machine learning. MIT Press.","DOI":"10.7551\/mitpress\/3206.001.0001"},{"key":"5958_CR38","unstructured":"Russell, S., & Norvig, P. (2003). Artificial intelligence: A modern approach.\u00a0Pearson."},{"key":"5958_CR39","doi-asserted-by":"crossref","unstructured":"Sheng, V. S., & Ling, C. X. (2006). Feature value acquisition in testing: a sequential batch test algorithm. In Proceedings of the 23rd international conference on Machine learning (pp. 809\u2013816). ACM.","DOI":"10.1145\/1143844.1143946"},{"key":"5958_CR40","unstructured":"Shim, H., Hwang, S. J., & Yang, E. (2018). Joint active feature acquisition and classification with variable-size set encoding. In Advances in neural information processing systems (pp. 1368\u20131378)."},{"key":"5958_CR41","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1111\/j.2517-6161.1996.tb02080.x","volume":"58","author":"R Tibshirani","year":"1996","unstructured":"Tibshirani, R. (1996). Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society Series B (Methodological), 58,\u00a0267\u2013288.","journal-title":"Journal of the Royal Statistical Society Series B (Methodological)"},{"key":"5958_CR42","unstructured":"Trapeznikov, K., & Saligrama, V. (2013). Supervised sequential classification under budget constraints. In Artificial intelligence and statistics (pp. 581\u2013589)."},{"key":"5958_CR43","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1613\/jair.120","volume":"2","author":"PD Turney","year":"1994","unstructured":"Turney, P. D. (1994). Cost-sensitive classification: Empirical evaluation of a hybrid genetic decision tree induction algorithm. Journal of Artificial Intelligence Research, 2, 369\u2013409.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"5958_CR44","doi-asserted-by":"crossref","unstructured":"Wang, J., Bolukbasi, T., Trapeznikov, K., & Saligrama, V. (2014a). Model selection by linear programming. In European conference on computer vision (pp. 647\u2013662). Springer.","DOI":"10.1007\/978-3-319-10605-2_42"},{"key":"5958_CR45","unstructured":"Wang, J., Trapeznikov, K., & Saligrama, V. (2014b). An LP for sequential learning under budgets. In Artificial intelligence and statistics (pp. 987\u2013995)."},{"key":"5958_CR46","unstructured":"Wang, J., Trapeznikov, K., & Saligrama, V. (2015). Efficient learning by directed acyclic graph for resource constrained prediction. In Advances in neural information processing systems (pp. 2152\u20132160)."},{"key":"5958_CR48","unstructured":"Xu, Z., Kusner, M., Weinberger, K., & Chen, M. (2013). Cost-sensitive tree of classifiers. In International conference on machine learning (pp. 133\u2013141)."},{"key":"5958_CR47","unstructured":"Xu, Z., Weinberger, K. Q., & Chapelle, O. (2012). The greedy miser: learning under test-time budgets. In Proceedings of the 29th international conference on international conference on machine learning (pp. 1299\u20131306). Omnipress."},{"key":"5958_CR49","doi-asserted-by":"crossref","unstructured":"Zadrozny, B., & Elkan, C. (2001). Learning and making decisions when costs and probabilities are both unknown. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 204\u2013213).","DOI":"10.1145\/502512.502540"},{"key":"5958_CR50","doi-asserted-by":"crossref","unstructured":"Zadrozny, B., Langford, J., & Abe, N. (2003). Cost-sensitive learning by cost-proportionate example weighting. In Third IEEE international conference on data mining (pp. 435\u2013442). IEEE.","DOI":"10.1109\/ICDM.2003.1250950"},{"key":"5958_CR51","unstructured":"Zubek, V. B., & Dietterich, T. G. (2002). Pruning improves heuristic search for cost-sensitive learning. In International conference on machine learning (pp.\u00a019\u201326)."}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-021-05958-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-021-05958-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-021-05958-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,24]],"date-time":"2022-12-24T16:21:45Z","timestamp":1671898905000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-021-05958-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,18]]},"references-count":51,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["5958"],"URL":"https:\/\/doi.org\/10.1007\/s10994-021-05958-z","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"type":"print","value":"0885-6125"},{"type":"electronic","value":"1573-0565"}],"subject":[],"published":{"date-parts":[[2021,4,18]]},"assertion":[{"value":"21 February 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 January 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 February 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 April 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}