TY - GEN
T1 - On probably correct classification of concepts
AU - Kulkarni, Sanjeev R.
AU - Zeitouni, Ofer
PY - 1993
Y1 - 1993
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0027800248&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0027800248&partnerID=8YFLogxK
U2 - 10.1145/168304.168318
DO - 10.1145/168304.168318
M3 - Conference contribution
AN - SCOPUS:0027800248
SN - 0897916115
SN - 9780897916110
T3 - Proc 6 Annu ACM Conf Comput Learn Theory
SP - 111
EP - 116
BT - Proc 6 Annu ACM Conf Comput Learn Theory
PB - Publ by ACM
T2 - Proceedings of the 6th Annual ACM Conference on Computational Learning Theory
Y2 - 26 July 1993 through 28 July 1993
ER -