Minimax optimal rates for Mondrian trees and forests
Minimax optimal rates for Mondrian trees and forests
复制标题
DOI：
10.1214/19-aos1886
复制
发表时间：
2018-03
期刊：
影响因子：
--
通讯作者：
Jaouad Mourtada;St'ephane Gaiffas;Erwan Scornet
中科院分区：
文献类型：
--
作者：
Jaouad Mourtada;St'ephane Gaiffas;Erwan Scornet
由Breiman（2001）提出的随机森林被广泛用作分类和回归算法。虽然最初被设计为批处理算法，但已经提出了几种变体来处理在线学习。这种森林的一个特殊例子是蒙德里安森林，其树木使用所谓的蒙德里安过程构建，因此可以轻松地以流式方式更新其构建。在本文中，我们研究蒙德里安森林在一个批处理设置，并证明其一致性假设适当调整的生命周期序列。一个彻底的蒙德里安分区的理论研究，使我们能够推导出蒙德里安森林的风险，这原来是Lipschitz和二次可微回归函数的最小最大最优率的上限。这些结果实际上是第一个声明某些特定的随机森林在任意维度上实现极大极小化率的结果，为精细的理论分析铺平了道路，从而更深入地理解这些黑箱算法。
Introduced by Breiman (2001), Random Forests are widely used as classification and regression algorithms. While being initially designed as batch algorithms, several variants have been proposed to handle online learning. One particular instance of such forests is the Mondrian Forest, whose trees are built using the so-called Mondrian process, therefore allowing to easily update their construction in a streaming fashion. In this paper, we study Mondrian Forests in a batch setting and prove their consistency assuming a proper tuning of the lifetime sequence. A thorough theoretical study of Mondrian partitions allows us to derive an upper bound for the risk of Mondrian Forests, which turns out to be the minimax optimal rate for both Lipschitz and twice differentiable regression functions. These results are actually the first to state that some particular random forests achieve minimax rates \textit{in arbitrary dimension}, paving the way to a refined theoretical analysis and thus a deeper understanding of these black box algorithms.