Concept Learning with Geometric Hypotheses

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{alpha +
½ , 2k-1} log n) algorithm that solves the
m.d.p. for two-dimensional convex k-gon hypotheses (where
alpha is the VC dimension of the implied set system, k is
constant), and an O(n3k-1log n)
algorithm for convex k-hedra hypotheses in three dimensions. We
extend these results to handle unions of k-gons and give an
approach to approximation algorithms.