On probably correct classification of concepts

Sanjeev R. Kulkarni, Ofer Zeitouni

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

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 C0 and C1 are two disjoint subsets of C, given an unknown c ∈ C0 in union with C1 we wish to decide whether c ∈ C0 or c ∈ C1 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 C0 and C1 that allow probably correct classification. The conditions obtained are in terms of separability and/or coverability conditions on the classes C0 and C1. 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.

Original languageEnglish (US)
Title of host publicationProc 6 Annu ACM Conf Comput Learn Theory
Editors Anon
PublisherPubl by ACM
Pages111-116
Number of pages6
ISBN (Print)0897916115
StatePublished - Dec 1 1993
EventProceedings of the 6th Annual ACM Conference on Computational Learning Theory - Santa Cruz, CA, USA
Duration: Jul 26 1993Jul 28 1993

Publication series

NameProc 6 Annu ACM Conf Comput Learn Theory

Other

OtherProceedings of the 6th Annual ACM Conference on Computational Learning Theory
CitySanta Cruz, CA, USA
Period7/26/937/28/93

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Cite this

Kulkarni, S. R., & Zeitouni, O. (1993). On probably correct classification of concepts. In Anon (Ed.), Proc 6 Annu ACM Conf Comput Learn Theory (pp. 111-116). (Proc 6 Annu ACM Conf Comput Learn Theory). Publ by ACM.