Concept learning with geometric hypotheses

David P. Dobkin, Dimitrios Gunopulos

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

16 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
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
Country/TerritoryUnited 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