{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,27]],"date-time":"2026-09-27T20:57:16Z","timestamp":1790542636494,"version":"4.1.0"},"reference-count":43,"publisher":"Oxford University Press (OUP)","issue":"3","license":[{"start":{"date-parts":[[2021,5,19]],"date-time":"2021-05-19T00:00:00Z","timestamp":1621382400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Random forest (RF) is one of the algorithms of choice in many supervised learning applications, be it classification or regression. The appeal of such tree-ensemble methods comes from a combination of several characteristics: a remarkable accuracy in a variety of tasks, a small number of parameters to tune, robustness with respect to features scaling, a reasonable computational cost for training and prediction, and their suitability in high-dimensional settings. The most commonly used RF variants, however, are \u2018offline\u2019 algorithms, which require the availability of the whole dataset at once. In this paper, we introduce AMF, an online RF algorithm based on Mondrian Forests. Using a variant of the context tree weighting algorithm, we show that it is possible to efficiently perform an exact aggregation over all prunings of the trees; in particular, this enables to obtain a truly online parameter-free algorithm which is competitive with the optimal pruning of the Mondrian tree, and thus adaptive to the unknown regularity of the regression function. Numerical experiments show that AMF is competitive with respect to several strong baselines on a large number of datasets for multi-class classification.<\/jats:p>","DOI":"10.1111\/rssb.12425","type":"journal-article","created":{"date-parts":[[2021,5,19]],"date-time":"2021-05-19T11:21:51Z","timestamp":1621423311000},"page":"505-533","source":"Crossref","is-referenced-by-count":31,"title":["AMF: Aggregated Mondrian Forests for Online Learning"],"prefix":"10.1093","volume":"83","author":[{"given":"Jaouad","family":"Mourtada","sequence":"first","affiliation":[{"name":"CMAP, CNRS, Ecole Polytechnique, Institut Polytechnique de Paris , Palaiseau, 91128 , France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"St\u00e9phane","family":"Ga\u00efffas","sequence":"additional","affiliation":[{"name":"LPSM, CNRS UMR 8001, Universit\u00e9 Paris Diderot , Paris , France"},{"name":"DMA, CNRS UMR 8553, Ecole normale sup\u00e9rieure , Paris , France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Erwan","family":"Scornet","sequence":"additional","affiliation":[{"name":"CMAP, CNRS, Ecole Polytechnique, Institut Polytechnique de Paris , Palaiseau, 91128 , France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2021,5,19]]},"reference":[{"key":"2023022408371941400_","volume-title":"Analysis of purely random forests bias","author":"Arlot","year":"2014"},{"key":"2023022408371941400_","first-page":"1458","volume-title":"Skip context tree switching","author":"Bellemare","year":"2014"},{"issue":"1","key":"2023022408371941400_","first-page":"1063","article-title":"Analysis of a random forests model","volume":"13","author":"Biau","year":"2012","journal-title":"Journal of Machine Learning Research"},{"key":"2023022408371941400_","first-page":"2015","article-title":"Consistency of random forests and other averaging classifiers","volume":"9","author":"Biau","year":"2008","journal-title":"Journal of Machine Learning Research"},{"key":"2023022408371941400_","first-page":"793","volume-title":"Annales de l\u2019Institut Henri Poincar\u00e9 (B) probability and statistics","author":"Blanchard","year":"1999"},{"issue":"1","key":"2023022408371941400_","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1023\/A:1010933404324","article-title":"Random forests","volume":"45","author":"Breiman","year":"2001","journal-title":"Machine Learning"},{"key":"2023022408371941400_","doi-asserted-by":"crossref","DOI":"10.1007\/b99352","volume-title":"Statistical learning theory and stochastic optimization: Ecole d\u2019Et\u00e9 de probabilit\u00e9s de Saint-Flour XXXI - 2001","author":"Catoni","year":"2004"},{"key":"2023022408371941400_","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546921","volume-title":"Prediction, learning, and games","author":"Cesa-Bianchi","year":"2006"},{"issue":"9","key":"2023022408371941400_","doi-asserted-by":"crossref","first-page":"2050","DOI":"10.1109\/TIT.2004.833339","article-title":"On the generalization ability of on-line learning algorithms","volume":"50","author":"Cesa-Bianchi","year":"2004","journal-title":"IEEE Transactions on Information Theory"},{"issue":"6","key":"2023022408371941400_","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/j.ygeno.2012.04.003","article-title":"Random forests for genomic data analysis","volume":"99","author":"Chen","year":"2012","journal-title":"Genomics"},{"issue":"443","key":"2023022408371941400_","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1080\/01621459.1998.10473750","article-title":"Bayesian CART model search","volume":"93","author":"Chipman","year":"1998","journal-title":"Journal of the American Statistical Association"},{"issue":"1","key":"2023022408371941400_","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1214\/09-AOAS285","article-title":"BART: Bayesian additive regression trees","volume":"4","author":"Chipman","year":"2010","journal-title":"The Annals of Applied Statistics"},{"key":"2023022408371941400_","volume-title":"Consistency of online random forests","author":"Denil","year":"2013"},{"issue":"2","key":"2023022408371941400_","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1093\/biomet\/85.2.363","article-title":"A Bayesian CART algorithm","volume":"85","author":"Denison","year":"1998","journal-title":"Biometrika"},{"issue":"1","key":"2023022408371941400_","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1186\/1471-2105-7-3","article-title":"Gene selection and classification of microarray data using random forest","volume":"7","author":"D\u00edaz-Uriarte","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023022408371941400_","doi-asserted-by":"crossref","DOI":"10.1145\/347090.347107","volume-title":"Mining high-speed data streams","author":"Domingos","year":"2000"},{"key":"2023022408371941400_","volume-title":"UCI machine learning repository","author":"Dua","year":"2017"},{"key":"2023022408371941400_","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1051\/ps\/2018008","article-title":"Impact of subsampling and tree depth on random forests","volume":"22","author":"Duroux","year":"2018","journal-title":"ESAIM: Probability and Statistics"},{"issue":"3","key":"2023022408371941400_","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1080\/10485252.2012.677843","article-title":"Variance reduction in purely random forests","volume":"24","author":"Genuer","year":"2012","journal-title":"Journal of Nonparametric Statistics"},{"issue":"1","key":"2023022408371941400_","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s10994-006-6226-1","article-title":"Extremely randomized trees","volume":"63","author":"Geurts","year":"2006","journal-title":"Machine Learning"},{"issue":"1","key":"2023022408371941400_","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1023\/A:1007396710653","article-title":"Predicting nearly as well as the best pruning of a decision tree","volume":"27","author":"Helmbold","year":"1997","journal-title":"Machine Learning"},{"key":"2023022408371941400_","volume-title":"Party: A laboratory for recursive partytioning","author":"Hothorn","year":"2010"},{"key":"2023022408371941400_","first-page":"3140","volume-title":"Advances in neural information processing systems 27","author":"Lakshminarayanan","year":"2014"},{"key":"2023022408371941400_","volume-title":"Mondrian forests for large-scale regression when uncertainty matters","author":"Lakshminarayanan","year":"2016"},{"issue":"5","key":"2023022408371941400_","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1111\/rssb.12293","article-title":"Bayesian regression tree ensembles that adapt to smoothness and sparsity","volume":"80","author":"Linero","year":"2018","journal-title":"Journal of the Royal Statistical Society: Series B (Statistical Methodology)"},{"key":"2023022408371941400_","volume-title":"Understanding random forests: From theory to practice","author":"Louppe","year":"2014"},{"key":"2023022408371941400_","first-page":"3759","volume-title":"Advances in neural information processing systems 30","author":"Mourtada","year":"2017"},{"key":"2023022408371941400_","volume-title":"Minimax optimal rates for Mondrian trees and forests","author":"Mourtada","year":"2018"},{"key":"2023022408371941400_","first-page":"2825","article-title":"Scikit-learn: Machine learning in Python","volume":"12","author":"Pedregosa","year":"2011","journal-title":"Journal of Machine Learning Research"},{"issue":"1","key":"2023022408371941400_","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BF00116251","article-title":"Induction of decision trees","volume":"1","author":"Quinlan","year":"1986","journal-title":"Machine Learning"},{"key":"2023022408371941400_","volume-title":"Posterior concentration for Bayesian regression trees and their ensembles","author":"Rockova","year":"2017"},{"key":"2023022408371941400_","volume-title":"Computability, inference and modeling in probabilistic programming","author":"Roy","year":"2011"},{"key":"2023022408371941400_","first-page":"1377","volume-title":"Advances in neural information processing systems 21","author":"Roy","year":"2009"},{"key":"2023022408371941400_","doi-asserted-by":"crossref","DOI":"10.1109\/ICCVW.2009.5457447","volume-title":"On-line random forests","author":"Saffari","year":"2009"},{"issue":"4","key":"2023022408371941400_","doi-asserted-by":"crossref","first-page":"1716","DOI":"10.1214\/15-AOS1321","article-title":"Consistency of random forests","volume":"43","author":"Scornet","year":"2015","journal-title":"The Annals of Statistics"},{"key":"2023022408371941400_","doi-asserted-by":"crossref","first-page":"1040","DOI":"10.1214\/aos\/1176345969","article-title":"Optimal global rates of convergence for nonparametric regression","volume":"10","author":"Stone","year":"1982","journal-title":"The Annals of Statistics"},{"issue":"493","key":"2023022408371941400_","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1198\/jasa.2011.ap09769","article-title":"Dynamic trees for learning and design","volume":"106","author":"Taddy","year":"2011","journal-title":"Journal of the American Statistical Association"},{"key":"2023022408371941400_","volume-title":"Sequential weighting algorithms for multi-alphabet sources","author":"Tjalkens","year":"1993"},{"issue":"2","key":"2023022408371941400_","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1023\/A:1022699900025","article-title":"Incremental induction of decision trees","volume":"4","author":"Utgoff","year":"1989","journal-title":"Machine Learning"},{"key":"2023022408371941400_","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1109\/DCC.2012.39","article-title":"Context tree switching","volume-title":"2012 data compression conference","author":"Veness","year":"2012"},{"key":"2023022408371941400_","volume-title":"Adaptive concentration of regression trees, with application to random forests","author":"Wager","year":"2015"},{"issue":"2","key":"2023022408371941400_","doi-asserted-by":"crossref","first-page":"792","DOI":"10.1109\/18.661523","article-title":"The context-tree weighting method: Extensions","volume":"44","author":"Willems","year":"1998","journal-title":"IEEE Transactions on Information Theory"},{"issue":"3","key":"2023022408371941400_","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1109\/18.382012","article-title":"The context-tree weighting method: Basic properties","volume":"41","author":"Willems","year":"1995","journal-title":"IEEE Transactions on Information Theory"}],"container-title":["Journal of the Royal Statistical Society Series B: Statistical Methodology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1111\/rssb.12425","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1111\/rssb.12425","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/academic.oup.com\/jrsssb\/article-pdf\/83\/3\/505\/49321747\/jrsssb_83_3_505.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/jrsssb\/article-pdf\/83\/3\/505\/49321747\/jrsssb_83_3_505.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,3]],"date-time":"2023-11-03T18:47:25Z","timestamp":1699037245000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/jrsssb\/article\/83\/3\/505\/7056109"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,19]]},"references-count":43,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2021,5,19]]},"published-print":{"date-parts":[[2021,7,1]]}},"URL":"https:\/\/doi.org\/10.1111\/rssb.12425","relation":{},"ISSN":["1369-7412","1467-9868"],"issn-type":[{"value":"1369-7412","type":"print"},{"value":"1467-9868","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,7]]},"published":{"date-parts":[[2021,5,19]]}}}