Concept Learning with Simple Geometric Hypotheses

Report ID: TR-481-94

---

Author: Gunopulos, Dimitrios / Dobkin, David P.

---

Date: 1994-12-00

---

Pages: 12

---

Download Formats: |Postscript|

---

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(n^{min(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(n^3k-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.