通过 γ-VC 维理解 Boosting 与简单弱学习器的表达能力
Boosting and the Expressive Power of Simple Weak Learners via the $\gamma$-VC Dimension
Arthur da Cunha · Kasper Green Larsen · Liang-Yu Zou
中文摘要
Boosting 能将仅略优于随机猜测的弱假设提升为高准确率的预测器,但最终分类器的表达能力可能强烈依赖于基学习器类的结构。本文借助 Alon 等人(STOC 2021)提出的 γ-VC 维来研究这一现象。第一个结果表明,该参数以关于 γ 的常数因子刻画了弱到强学习(weak-to-strong learning)的样本复杂度。随后,本文进一步精细化了经典 VC 维与 γ-VC 维之间的一般关系。最后,针对决策树桩(decision stumps)与 ℝ^d 中轴平行矩形这两类基本概念类,给出了改进的 γ-VC 维上下界。
关键要点
- 01用 Alon 等人(STOC 2021)提出的 γ-VC 维刻画 boosting 后分类器的表达能力
- 02证明 γ-VC 维以关于 γ 的常数因子决定弱到强学习的样本复杂度
- 03给出经典 VC 维与 γ-VC 维一般关系的更精细刻画
- 04对决策树桩和 ℝ^d 中轴平行矩形两类基本概念类,改进其 γ-VC 维的上下界
- 05为基学习器类结构如何影响 boosting 结果提供理论分析框架
解读
尚无解读。
原始英文摘要
arXiv:2610.10383v1 Announce Type: new Abstract: Boosting converts weak hypotheses with a small edge over random guessing into highly accurate predictors, but the expressive power of the resulting classifier can depend strongly on the structure of the base class. We study this phenomenon through the $\gamma$-VC dimension introduced by Alon et al. (STOC 2021). Our first result shows that this parameter characterizes the sample complexity for weak-to-strong learning up to a constant factor scaling in $\gamma$. We then sharpen the general relationship between the classic VC dimension and the $\gamma$-VC dimension. Finally, we also give improved upper and lower bounds on the $\gamma$-VC dimension for the fundamental concept classes of decision stumps and axis-parallel rectangles in $\mathbb{R}^d$.