Tight Lower Bounds on the VC-dimension of Geometric Set Systems
Tight Lower Bounds on the VC-dimension of Geometric Set Systems
复制标题
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
M. Csikós;Nabil H. Mustafa;A. Kupavskii
中科院分区：
文献类型：
--
作者：
M. Csikós;Nabil H. Mustafa;A. Kupavskii
集合系统的VC维是刻画其复杂性的一种方法，是机器学习和几何界广泛研究的一个关键参数。在这篇文章中，我们解决了两个基本集合系统：半空间的K重并/交和单纯集系统的VC维界的两个长期公开的问题。在其他影响中，它解决了机器学习中的一个悬而未决的问题，该问题最初是在Blumer等人的基础论文中研究的。()以及艾森斯塔特和安格鲁因(2007年)和约翰逊(2008年)。
The VC-dimension of a set system is a way to capture its complexity and has been a key parameter studied extensively in machine learning and geometry communities. In this paper, we resolve two longstanding open problems on bounding the VC-dimension of two fundamental set systems: k-fold unions/intersections of half-spaces and the simplices set system. Among other implications, it settles an open question in machine learning that was first studied in the foundational paper of Blumer et al. (1989) as well as by Eisenstat and Angluin (2007) and Johnson (2008).