PAC Learning Intersections of Halfspaces with Membership Queries
PAC Learning Intersections of Halfspaces with Membership Queries
复制标题
PAC 学习半空间与成员资格查询的交集
DOI：
10.1007/pl00013834
复制
发表时间：
1998
期刊：
影响因子：
1.1
通讯作者：
L. Pitt
中科院分区：
文献类型：
--
作者：
Stephen Kwek;L. Pitt
抽象的。提出了一种随机学习算法{POLLY}，它能有效地学习n维s半空间的交集，在s和n的时间多项式中。学习协议是Valiant的PAC（可能近似正确）模型，增加了成员查询。特别地，{POLLY}从单位超立方体上的任意分布中接收m = poly（n，s，1/ε，1/δ）随机生成点的集合S，并被精确地告知哪些点包含在由半空间定义的凸多面体P中，哪些点不包含在由半空间定义的凸多面体P中。{POLLY}也可以获得关于其自己选择的点的相同信息。证明了在poly（n，s，1/ε，1/δ，log（1/d））时间之后，{POLLY}不能输出s个半空间的集合且分类误差不超过ε的概率不超过δ .这里，d是目标的边界与S中不位于边界上的那些示例之间的最小距离。参数log（1/d）可以由编码边界超平面的系数和采样样本S的坐标所需的比特数来限定。此外，{POLLY}可以扩展为学习k个不相交的多面体的并集，每个多面体最多有s个小面，时间为poly（n，k，s，1/ε，1/δ，log（1/d），1/γ），其中γ是任何两个不同多面体之间的最小距离。
Abstract. A randomized learning algorithm {POLLY} is presented that efficiently learns intersections of s halfspaces in n dimensions, in time polynomial in both s and n . The learning protocol is the PAC (probably approximately correct) model of Valiant, augmented with membership queries. In particular, {POLLY} receives a set S of m = poly(n,s,1/ε,1/δ) randomly generated points from an arbitrary distribution over the unit hypercube, and is told exactly which points are contained in, and which points are not contained in, the convex polyhedron P defined by the halfspaces. {POLLY} may also obtain the same information about points of its own choosing. It is shown that after poly(n , s , 1/ε , 1/δ , log(1/d) ) time, the probability that {POLLY} fails to output a collection of s halfspaces with classification error at most ε , is at most δ . Here, d is the minimum distance between the boundary of the target and those examples in S that are not lying on the boundary. The parameter log(1/d) can be bounded by the number of bits needed to encode the coefficients of the bounding hyperplanes and the coordinates of the sampled examples S . Moreover, {POLLY} can be extended to learn unions of k disjoint polyhedra with each polyhedron having at most s facets, in time poly(n , k , s , 1/ε , 1/δ , log(1/d) , 1/γ ) where γ is the minimum distance between any two distinct polyhedra.