TY - GEN

T1 - Concept learning with geometric hypotheses

AU - Dobkin, David P.

AU - Gunopulos, Dimitrios

N1 - Funding Information:
sity, 35 Olden St., Princeton, NJ 08.540, USA, e-mail: dg@cs.princeton. edu. The research work of this author was supported by NSF Grant CCR93-01254 and by DIMACS, an NSF Science and Technology Center.
Publisher Copyright:
© 1995 ACM.

PY - 1995/7/5

Y1 - 1995/7/5

N2 - We present a general approach to solving the minimizing disagreement problem for geometric hypotheses with finite VC-dimension. These results also imply efficient agnostic-PAC learning of these hypotheses classes. In particular we give an O(nmin(α-1,2κ-1)log n) algorithm that solves the m.d.p. for two-dimensional convex κ-gon hypotheses (α is the VC dimension of the implied set system, κ is constant), and an O(n3κ-1 log n) algorithm for convex κ-hedra hypotheses in three dimensions. We also give an O(κ2n2 logn) algorithm that solves the m.d. p. for planar κ-stripes, and give an approach to approximation algorithms.

AB - We present a general approach to solving the minimizing disagreement problem for geometric hypotheses with finite VC-dimension. These results also imply efficient agnostic-PAC learning of these hypotheses classes. In particular we give an O(nmin(α-1,2κ-1)log n) algorithm that solves the m.d.p. for two-dimensional convex κ-gon hypotheses (α is the VC dimension of the implied set system, κ is constant), and an O(n3κ-1 log n) algorithm for convex κ-hedra hypotheses in three dimensions. We also give an O(κ2n2 logn) algorithm that solves the m.d. p. for planar κ-stripes, and give an approach to approximation algorithms.

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

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

U2 - 10.1145/225298.225338

DO - 10.1145/225298.225338

M3 - Conference contribution

AN - SCOPUS:84961365937

T3 - Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995

SP - 329

EP - 336

BT - Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995

PB - Association for Computing Machinery, Inc

T2 - 8th Annual Conference on Computational Learning Theory, COLT 1995

Y2 - 5 July 1995 through 8 July 1995

ER -