Geometrical concept learning and convex polytopes
Tibor Hegedüs · 1994
We consider exact identification of geometrical objects over the domain {0,1,…,n−1}d, d≥1 fixed. We give efficient implementations of the general incremental scheme “identify the target concept by constructing its convex hull” for learning convex concepts. This approach is of interest for intersections of half-spaces over the considered domain, as the convex hull of a concept of this type is known to have “few” vertices. In this case we obtain positive results on learning intersections of halfspaces with superset/disjointedness queries, and on learning single halfspaces with membership queries. We believe that the presented paradigm may become important for neural networks with a fixed number of discrete inputs.