Geometrical Concept Learning and Convex Polytopes
Abstract
We consider exact identification of geometrical objects over the domain 0,1,…,n−1d, 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.
Cite
Text
Hegedüs. "Geometrical Concept Learning and Convex Polytopes." Annual Conference on Computational Learning Theory, 1994. doi:10.1145/180139.181124Markdown
[Hegedüs. "Geometrical Concept Learning and Convex Polytopes." Annual Conference on Computational Learning Theory, 1994.](https://mlanthology.org/colt/1994/hegedus1994colt-geometrical/) doi:10.1145/180139.181124BibTeX
@inproceedings{hegedus1994colt-geometrical,
title = {{Geometrical Concept Learning and Convex Polytopes}},
author = {Hegedüs, Tibor},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1994},
pages = {228-236},
doi = {10.1145/180139.181124},
url = {https://mlanthology.org/colt/1994/hegedus1994colt-geometrical/}
}