{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T16:34:19Z","timestamp":1775666059480,"version":"3.50.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2021,11,5]],"date-time":"2021-11-05T00:00:00Z","timestamp":1636070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,11,5]],"date-time":"2021-11-05T00:00:00Z","timestamp":1636070400000},"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":[[2022,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Decision trees have favorable properties, including interpretability, high computational efficiency, and the ability to learn from little training data. Learning a decision tree is known to be NP-complete. The researchers have proposed many greedy algorithms such as CART to learn approximate solutions. Inspired by the current popular neural networks, <jats:italic>soft<\/jats:italic> trees that support end-to-end training with back-propagation have attracted more and more attention. However, existing <jats:italic>soft<\/jats:italic> trees either lose the interpretability due to the continuous relaxation or employ the two-stage method of end-to-end building and then pruning. In this paper, we propose One-Stage Tree to build and prune the decision tree jointly through a bilevel optimization problem. Moreover, we leverage the reparameterization trick and proximal iterations to keep the tree discrete during end-to-end training. As a result, One-Stage Tree reduces the performance gap between training and testing and maintains the advantage of interpretability. Extensive experiments demonstrate that the proposed One-Stage Tree outperforms CART and the existing <jats:italic>soft<\/jats:italic> trees on classification and regression tasks.<\/jats:p>","DOI":"10.1007\/s10994-021-06094-4","type":"journal-article","created":{"date-parts":[[2021,11,5]],"date-time":"2021-11-05T21:34:29Z","timestamp":1636148069000},"page":"1959-1985","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["One-Stage Tree: end-to-end tree builder and pruner"],"prefix":"10.1007","volume":"111","author":[{"given":"Zhuoer","family":"Xu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5069-5950","authenticated-orcid":false,"given":"Guanghui","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chunfeng","family":"Yuan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yihua","family":"Huang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,11,5]]},"reference":[{"key":"6094_CR1","unstructured":"Bai, Y., Wang, Y. X., & Liberty, E. (2018). Proxquant: Quantized neural networks via proximal operators. In International conference on learning representations."},{"key":"6094_CR2","unstructured":"Blum, A., Haghtalab, N., & Procaccia, A. D. (2015). Variational dropout and the local reparameterization trick. In NIPS."},{"key":"6094_CR3","doi-asserted-by":"crossref","unstructured":"Bottou, L. (2012). Stochastic gradient descent tricks. In Neural networks: Tricks of the trade (pp. 421\u2013436). Springer.","DOI":"10.1007\/978-3-642-35289-8_25"},{"key":"6094_CR4","unstructured":"Bousquet, O., Chapelle, O., & Hein, M. (2004). Measure based regularization. In Advances in Neural Information Processing Systems (pp. 1221\u20131228)."},{"key":"6094_CR5","unstructured":"Breiman, L., Friedman, J., Stone, C. J., & Olshen, R. A. (1984). Classification and regression trees. CRC Press."},{"key":"6094_CR6","doi-asserted-by":"crossref","unstructured":"Chen, T., & Guestrin, C. (2016). Xgboost: A scalable tree boosting system. In Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining (pp. 785\u2013794).","DOI":"10.1145\/2939672.2939785"},{"key":"6094_CR7","first-page":"3123","volume":"28","author":"M Courbariaux","year":"2015","unstructured":"Courbariaux, M., Bengio, Y., & David, J. P. (2015). Binaryconnect: Training deep neural networks with binary weights during propagations. Advances in Neural Information Processing Systems, 28, 3123\u20133131.","journal-title":"Advances in Neural Information Processing Systems"},{"issue":"1","key":"6094_CR8","first-page":"1","volume":"7","author":"J Dem\u0161ar","year":"2006","unstructured":"Dem\u0161ar, J. (2006). Statistical comparisons of classifiers over multiple data sets. Journal of Machine Learning Research, 7(1), 1\u201330.","journal-title":"Journal of Machine Learning Research"},{"key":"6094_CR9","unstructured":"Finn, C., Abbeel, P., & Levine, S. (2017). Model-agnostic meta-learning for fast adaptation of deep networks. In Proceedings of the 34th international conference on machine learning (vol. 70, pp. 1126\u20131135)."},{"key":"6094_CR10","doi-asserted-by":"crossref","unstructured":"Friedman, J. H. (2001). Greedy function approximation: A gradient boosting machine. Annals of Statistics, 1189\u20131232.","DOI":"10.1214\/aos\/1013203451"},{"key":"6094_CR11","unstructured":"Gumbel, E. J. (1954). Statistical theory of extreme values and some practical applications: A series of lectures (vol.\u00a033). US Government Printing Office."},{"key":"6094_CR12","doi-asserted-by":"crossref","unstructured":"Hehn, T. M., Kooij, J. F., & Hamprecht, F. A. (2019). End-to-end learning of decision trees and forests. International Journal of Computer Vision, 1\u201315 .","DOI":"10.1007\/s11263-019-01237-6"},{"key":"6094_CR13","unstructured":"Hou, L., Yao, Q., & Kwok, J. T. (2017). Loss-aware binarization of deep networks. In 5th international conference on learning representations, ICLR 2017, Toulon, France April 24\u201326, 2017, Conference Track Proceedings. OpenReview.net. https:\/\/openreview.net\/forum?id=S1oWlN9ll"},{"key":"6094_CR14","unstructured":"Irsoy, O., Y\u0131ld\u0131z, O. T., Alpayd\u0131n, E. (2012). Soft decision trees. In Proceedings of the 21st international conference on pattern recognition (ICPR2012) (pp. 1819\u20131822). IEEE."},{"key":"6094_CR15","doi-asserted-by":"crossref","unstructured":"Irsoy, O., Yildiz, O. T., & Alpaydin, E. (2014). Budding trees. In 2014 22nd international conference on pattern recognition (pp. 3582\u20133587). IEEE.","DOI":"10.1109\/ICPR.2014.616"},{"key":"6094_CR16","unstructured":"Jang, E., Gu, S., & Poole, B. (2016). Categorical reparameterization with gumbel-softmax. Preprint arXiv:1611.01144"},{"key":"6094_CR17","first-page":"3146","volume":"30","author":"G Ke","year":"2017","unstructured":"Ke, G., Meng, Q., Finley, T., Wang, T., Chen, W., Ma, W., et al. (2017). Lightgbm: A highly efficient gradient boosting decision tree. Advances in Neural Information Processing Systems, 30, 3146\u20133154.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"6094_CR18","unstructured":"Kingma, D., & Ba, J. (2014). Adam: A method for stochastic optimization. In International Conference on Learning Representations."},{"issue":"4","key":"6094_CR19","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/s10462-011-9272-4","volume":"39","author":"SB Kotsiantis","year":"2013","unstructured":"Kotsiantis, S. B. (2013). Decision trees: A recent overview. Artificial Intelligence Review, 39(4), 261\u2013283.","journal-title":"Artificial Intelligence Review"},{"key":"6094_CR20","doi-asserted-by":"crossref","unstructured":"Li, Q., Wen, Z., & He, B. (2020). Practical federated gradient boosting decision trees. In Proceedings of the AAAI conference on artificial intelligence (vol.\u00a034, pp. 4642\u20134649).","DOI":"10.1609\/aaai.v34i04.5895"},{"key":"6094_CR21","unstructured":"Liu, H., Simonyan, K., & Yang, Y. (2018). Darts: Differentiable architecture search. In International conference on learning representations."},{"key":"6094_CR22","first-page":"3086","volume":"27","author":"CJ Maddison","year":"2014","unstructured":"Maddison, C. J., Tarlow, D., & Minka, T. (2014). A* sampling. Advances in Neural Information Processing Systems, 27, 3086\u20133094.","journal-title":"Advances in Neural Information Processing Systems"},{"issue":"247","key":"6094_CR23","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1080\/01621459.1949.10483310","volume":"44","author":"N Metropolis","year":"1949","unstructured":"Metropolis, N., & Ulam, S. (1949). The monte carlo method. Journal of the American Statistical Association, 44(247), 335\u2013341.","journal-title":"Journal of the American Statistical Association"},{"key":"6094_CR24","unstructured":"Mukkamala, M. C., & Hein, M. (2017). Variants of rmsprop and adagrad with logarithmic regret bounds. In International conference on machine learning (pp. 2545\u20132553). PMLR."},{"key":"6094_CR25","unstructured":"Nemenyi, P. (1963). Distribution-free multiple comparisons. Princeton University."},{"key":"6094_CR26","unstructured":"Norouzi, M., Collins, M., Johnson, M. A., Fleet, D. J., & Kohli, P. (2015). Efficient non-greedy optimization of decision trees. In Advances in neural information processing systems (pp. 1729\u20131737)."},{"issue":"3","key":"6094_CR27","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1561\/2400000003","volume":"1","author":"N Parikh","year":"2014","unstructured":"Parikh, N., & Boyd, S. (2014). Proximal algorithms. Foundations and Trends in Optimization, 1(3), 127\u2013239.","journal-title":"Foundations and Trends in Optimization"},{"key":"6094_CR28","doi-asserted-by":"crossref","unstructured":"Prechelt, L. (1998). Early stopping-but when? In Neural networks: Tricks of the trade (pp. 55\u201369). Springer.","DOI":"10.1007\/3-540-49430-8_3"},{"key":"6094_CR29","unstructured":"Quinlan, J. (1996). Bagging, boosting, and c4. s. In Proceedings of the thirteenth national conference on Artificial intelligence (vol. 1, pp. 725\u2013730)."},{"issue":"1","key":"6094_CR30","first-page":"81","volume":"1","author":"JR Quinlan","year":"1986","unstructured":"Quinlan, J. R. (1986). Induction of decision trees. Machine Learning, 1(1), 81\u2013106.","journal-title":"Machine Learning"},{"key":"6094_CR31","doi-asserted-by":"crossref","unstructured":"Wu, L., Rao, Y., Liang, H., Nazir, A., et\u00a0al. (2020). Dtca: Decision tree-based co-attention networks for explainable claim verification. In Proceedings of the 58th annual meeting of the association for computational linguistics (pp. 1024\u20131035).","DOI":"10.18653\/v1\/2020.acl-main.97"},{"key":"6094_CR32","first-page":"2543","volume":"11","author":"L Xiao","year":"2010","unstructured":"Xiao, L. (2010). Dual averaging methods for regularized stochastic learning and online optimization. The Journal of Machine Learning Research, 11, 2543\u20132596.","journal-title":"The Journal of Machine Learning Research"},{"key":"6094_CR33","doi-asserted-by":"crossref","unstructured":"Yao, Q., Chen, X., Kwok, J. T., Li, Y., & Hsieh, C. J. (2020). Efficient neural interaction function search for collaborative filtering. In Proceedings of The web conference 2020 (pp. 1660\u20131670).","DOI":"10.1145\/3366423.3380237"},{"key":"6094_CR34","doi-asserted-by":"crossref","unstructured":"Yao, Q., Xu, J., Tu, W. W., & Zhu, Z. (2020). Efficient neural architecture search via proximal iterations. In AAAI (pp. 6664\u20136671).","DOI":"10.1609\/aaai.v34i04.6143"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-021-06094-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-021-06094-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-021-06094-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,20]],"date-time":"2022-05-20T20:15:31Z","timestamp":1653077731000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-021-06094-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,5]]},"references-count":34,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["6094"],"URL":"https:\/\/doi.org\/10.1007\/s10994-021-06094-4","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,5]]},"assertion":[{"value":"31 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 August 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 October 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 November 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}