TY - JOUR

T1 - PAC learning intersections of halfspaces with membership queries

AU - Kwek, Stephen

AU - Pitt, Leonard B

PY - 1996

Y1 - 1996

N2 - 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 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/δ, B) time, the probability that POLLY fails to output a collection of s halfspaces with classification error at most ε, is at most δ. Here B is the number of bits needed to encode the coefficients of the bounding hyperplanes and the coordinates of the example points in an initial sample of m = poly(n, s, 1/ε, 1/δ) examples. A number of extensions are given, including the learning of a union of disjoint polytopes in time polynomial in the total number of facets, the dimension, and various other parameters.

AB - 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 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/δ, B) time, the probability that POLLY fails to output a collection of s halfspaces with classification error at most ε, is at most δ. Here B is the number of bits needed to encode the coefficients of the bounding hyperplanes and the coordinates of the example points in an initial sample of m = poly(n, s, 1/ε, 1/δ) examples. A number of extensions are given, including the learning of a union of disjoint polytopes in time polynomial in the total number of facets, the dimension, and various other parameters.

UR - http://www.scopus.com/inward/record.url?scp=0030402083&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030402083&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:0030402083

SP - 244

EP - 254

JO - Proceedings of the Annual ACM Conference on Computational Learning Theory

JF - Proceedings of the Annual ACM Conference on Computational Learning Theory

ER -