TY - GEN
T1 - Concept learning with geometric hypotheses
AU - Dobkin, David P.
AU - Gunopulos, Dimitrios
N1 - 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
T2 - 8th Annual Conference on Computational Learning Theory, COLT 1995
Y2 - 5 July 1995 through 8 July 1995
ER -