论文标题
可证明的决策树归纳保证：不可知论的环境
Provable guarantees for decision tree induction: the agnostic setting
论文作者
论文摘要
我们为广泛使用和经验成功{\ SL自上而下的决策树学习启发式}的表现提供了可证明的保证。虽然先前的作品集中在可实现的设置上，但我们考虑了更现实和具有挑战性的{\ sl abnostic}设置。我们证明，对于所有单调函数〜$ f $和参数$ s \ in \ mathbb {n} $，这些启发式方法构建了一个尺寸$ s^{\ tilde {\ tilde {O}（（（\ log s）/\ varepsilon^2）} $的决策树，以达到错误$ \ le \ le \ le \ le \ le \ mathsf i \ s. $ \ mathsf {opt} _s $表示$ f $的最佳大小 - $ s $决策树的错误。以前，这种保证是通过任何算法都无法实现的，即使是基于自上而下的启发式方法也是如此。我们通过接近匹配的$ s^{\tildeΩ（\ log s）} $下限来补充算法保证。
We give strengthened provable guarantees on the performance of widely employed and empirically successful {\sl top-down decision tree learning heuristics}. While prior works have focused on the realizable setting, we consider the more realistic and challenging {\sl agnostic} setting. We show that for all monotone functions~$f$ and parameters $s\in \mathbb{N}$, these heuristics construct a decision tree of size $s^{\tilde{O}((\log s)/\varepsilon^2)}$ that achieves error $\le \mathsf{opt}_s + \varepsilon$, where $\mathsf{opt}_s$ denotes the error of the optimal size-$s$ decision tree for $f$. Previously, such a guarantee was not known to be achievable by any algorithm, even one that is not based on top-down heuristics. We complement our algorithmic guarantee with a near-matching $s^{\tildeΩ(\log s)}$ lower bound.
