Improved Lower Bounds for Learning Intersections of Halfspaces
Improved Lower Bounds for Learning Intersections of Halfspaces
复制标题
改进学习半空间交点的下界
DOI：
10.1007/11776420_26
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Alexander A. Sherstov
中科院分区：
文献类型：
--
作者：
Adam R. Klivans;Alexander A. Sherstov
我们证明了新的下界学习半空间，在计算学习理论中最重要的概念类之一的交集。我们的主要结果是，任何学习n维半空间交的查询算法必须进行查询。这是该概念类的统计查询维度的第一个非平凡下界（先前的最佳下界不是）。我们的下界甚至对低权重半空间的交集也成立。在后一种情况下，它几乎是紧的，我们还证明了两个多数（低权半空间）的交集不能用一个多项式阈值函数（PTF）来计算。这是这个概念类的PTF长度的第一个超多项式下界，并且几乎是最优的。对于k =ω（logn）低权半空间的交，我们改进了我们的下界，使之也接近最优.因此，即使是两个半空间的交集也不能用多项式权重的PTF来计算，而多项式权重的PTF是已知通过杰克逊的谐波筛算法可以有效学习的最具表现力的函数类。最后，我们报告了在均匀分布下半空间交的弱可学习性的研究进展。
We prove new lower bounds for learning intersections of halfspaces, one of the most important concept classes in computational learning theory. Our main result is that any statistical-query algorithm for learning the intersection ofhalfspaces inndimensions must makequeries. This is the first non-trivial lower bound on the statistical query dimension for this concept class (the previous best lower bound wasn). Our lower bound holds even for intersections oflow-weighthalfspaces. In the latter case, it is nearly tight.We also show that the intersection of two majorities (low-weight halfspaces) cannot be computed by a polynomial threshold function (PTF) with fewer thannmonomials. This is the first super-polynomial lower bound on the PTF length of this concept class, and is nearly optimal. For intersections ofk=ω(logn) low-weight halfspaces, we improve our lower bound towhich too is nearly optimal. As a consequence, intersections of even two halfspaces are not computable by polynomial-weight PTFs, the most expressive class of functions known to be efficiently learnable via Jackson’s Harmonic Sieve algorithm. Finally, we report our progress on theweaklearnability of intersections of halfspaces under the uniform distribution.