### 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 C_{0} and C_{1} are two disjoint subsets of C, given an unknown c ∈ C_{0} in union with C_{1} we wish to decide whether c ∈ C_{0} or c ∈ C_{1} 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 C_{0} and C_{1} that allow probably correct classification. The conditions obtained are in terms of separability and/or coverability conditions on the classes C_{0} and C_{1}. 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 language | English (US) |
---|---|

Title of host publication | Proc 6 Annu ACM Conf Comput Learn Theory |

Editors | Anon |

Publisher | Publ by ACM |

Pages | 111-116 |

Number of pages | 6 |

ISBN (Print) | 0897916115 |

State | Published - Dec 1 1993 |

Event | Proceedings of the 6th Annual ACM Conference on Computational Learning Theory - Santa Cruz, CA, USA Duration: Jul 26 1993 → Jul 28 1993 |

### Publication series

Name | Proc 6 Annu ACM Conf Comput Learn Theory |
---|

### Other

Other | Proceedings of the 6th Annual ACM Conference on Computational Learning Theory |
---|---|

City | Santa Cruz, CA, USA |

Period | 7/26/93 → 7/28/93 |

### All Science Journal Classification (ASJC) codes

- Engineering(all)

## Cite this

*Proc 6 Annu ACM Conf Comput Learn Theory*(pp. 111-116). (Proc 6 Annu ACM Conf Comput Learn Theory). Publ by ACM.