CLASSIC learning

Michael Frazier, Leonard Pitt

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

Abstract

Description logics, also called terminological logics, are commonly used in knowledge-based systems to describe objects and their relationships. We investigate the learnability ofatypical description logic, CLASSIC, and show that CLASSIC sentences are learnable in polynomial time in the exact learning model using equivalence queries and membership queries (which are in essence, "subsumption queries"). We show that membership queries alone are insufficient for polynomial time learning of CLASSIC sentences, Combined with earlier negative results of Cohen and Hirsh [16, 20] showing that, given standard complexity theoretic assumptions, equivalence queries alone are insufficient (or random examples alone in the PAC setting are insufficient ), this shows that both sources of information are necessary for efficient learning in that neither type alone is sufficient. In addition, we show that a modification of the algorithm deals robustly with persistent malicious two-sided classification noise in the membership queries with the probability of a misclassification bounded below 1/2.

Original languageEnglish (US)
Title of host publicationProceedings of the 7th Annual Conference on Computational Learning Theory, COLT 1994
PublisherAssociation for Computing Machinery
Pages23-34
Number of pages12
ISBN (Electronic)0897916557
DOIs
StatePublished - Jul 16 1994
Event7th Annual Conference on Computational Learning Theory, COLT 1994 - New Brunswick, United States
Duration: Jul 12 1994Jul 15 1994

Publication series

NameProceedings of the Annual ACM Conference on Computational Learning Theory
VolumePart F129415

Other

Other7th Annual Conference on Computational Learning Theory, COLT 1994
CountryUnited States
CityNew Brunswick
Period7/12/947/15/94

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'CLASSIC learning'. Together they form a unique fingerprint.

  • Cite this

    Frazier, M., & Pitt, L. (1994). CLASSIC learning. In Proceedings of the 7th Annual Conference on Computational Learning Theory, COLT 1994 (pp. 23-34). (Proceedings of the Annual ACM Conference on Computational Learning Theory; Vol. Part F129415). Association for Computing Machinery. https://doi.org/10.1145/180139.174994