提出首个可证明的决策树主动学习算法，标签查询量仅对数级增长。
Active Learning for Decision Trees with Provable Guarantees
- 基于特征路径独立与数据网格结构假设，分析决策树分歧系数。
- 实现$(1+ε)$近似分类器，标签查询次数为数据规模的对数级。
- 理论证明算法误差依赖接近最优，适合高维稀疏数据场景。
本文推进了决策树作为二分类器时主动学习标签复杂度的理论理解。主要贡献有二：其一，首次分析了决策树的分歧系数——决定主动学习标签复杂度的关键参数。该分析在两个自然假设下成立：(i) 每条根到叶路径查询不同特征维度；(ii) 输入数据具有规则的网格结构。我们证明这些假设不可或缺，放松后标签复杂度变为多项式级。其二，提出首个通用主动学习算法，可实现乘法误差保证，输出$(1+ε)$-近似分类器。结合上述结果，设计出在给定假设下标签查询次数仅为数据规模的多项式对数级的决策树主动学习算法。最后，建立标签复杂度下界，表明算法对误差容限$ε$的依赖接近最优。
原文摘要 · Abstract (English)
This paper advances the theoretical understanding of active learning label complexity for decision trees as binary classifiers. We make two main contributions. First, we provide the first analysis of the disagreement coefficient for decision trees-a key parameter governing active learning label complexity. Our analysis holds under two natural assumptions required for achieving polylogarithmic label complexity, (i) each root-to-leaf path queries distinct feature dimensions, and (ii) the input data has a regular, grid-like structure. We show these assumptions are essential, as relaxing them leads to polynomial label complexity. Second, we present the first general active learning algorithm for binary classification that achieves a multiplicative error guarantee, producing a $(1+ε)$-approximate classifier. By combining these results, we design an active learning algorithm for decision trees that uses only a polylogarithmic number of label queries in the dataset size, under the stated assumptions. Finally, we establish a label complexity lower bound, showing our algorithm's dependence on the error tolerance $ε$ is close to optimal.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。