Concept Learning with Simple Geometric Hypotheses
Report ID:
TR-481-94
Authors:
Date:
November 1994
Pages:
12
Download Formats:
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 + 1/2, 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-1 log n) algorithm
for three-dimensional convex k-hedra hypotheses. We extend these
results to handle unions of k-gons and give an approach to
approximation algorithms.