Concept learning with geometric hypotheses

David P. Dobkin, Dimitrios Gunopulos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995
PublisherAssociation for Computing Machinery, Inc
Pages329-336
Number of pages8
ISBN (Electronic)0897917235, 9780897917230
DOIs
StatePublished - Jul 5 1995
Event8th Annual Conference on Computational Learning Theory, COLT 1995 - Santa Cruz, United States
Duration: Jul 5 1995Jul 8 1995

Publication series

NameProceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995
Volume1995-January

Other

Other8th Annual Conference on Computational Learning Theory, COLT 1995
CountryUnited States
CitySanta Cruz
Period7/5/957/8/95

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Artificial Intelligence
  • Software

Fingerprint Dive into the research topics of 'Concept learning with geometric hypotheses'. Together they form a unique fingerprint.

  • Cite this

    Dobkin, D. P., & Gunopulos, D. (1995). Concept learning with geometric hypotheses. In Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995 (pp. 329-336). (Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995; Vol. 1995-January). Association for Computing Machinery, Inc. https://doi.org/10.1145/225298.225338