On Probably Correct Classification of Concepts
Abstract
We consider the problem of classifying an unknown concept into one of two subclasses of concepts. Specifically, if C is a concept class and Co and Cl are two disjoint subsets of C, given an unknown c E Co U Cl we wish to decide whether c c Co or c E Cl based on a set of random examples. We consider both uniform and non-uniform probably correct classification for which the number of samples is or is not required to be independent of c, respectively. For both cases, we obtain necessary and sufficient conditions on Co and Cl that allow probably correct classification. The conditions obtained are in terms of separability and/or coverability conditions on the classes Co and Cl. Furthermore, in the non-uniform case we show that this is equivalent to classification in the limit. Several examples of the applicability of our results are also provided.
Cite
Text
Kulkarni and Zeitouni. "On Probably Correct Classification of Concepts." Annual Conference on Computational Learning Theory, 1993. doi:10.1145/168304.168318Markdown
[Kulkarni and Zeitouni. "On Probably Correct Classification of Concepts." Annual Conference on Computational Learning Theory, 1993.](https://mlanthology.org/colt/1993/kulkarni1993colt-probably/) doi:10.1145/168304.168318BibTeX
@inproceedings{kulkarni1993colt-probably,
title = {{On Probably Correct Classification of Concepts}},
author = {Kulkarni, Sanjeev R. and Zeitouni, Ofer},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1993},
pages = {111-116},
doi = {10.1145/168304.168318},
url = {https://mlanthology.org/colt/1993/kulkarni1993colt-probably/}
}