CLASSIC learning

Michael Frazier, Leonard Pitt

Research output: Contribution to journalArticlepeer-review


Description logics, also called terminological logics, are commonly used in knowledge-based systems to describe objects and their relationships. We investigate the learnability of a typical 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 a prediction hardness result for the more traditional membership queries that convey information about specific individuals). We show that membership queries alone are insufficient for polynomial time learning of CLASSIC sentences. Combined with earlier negative results (Cohen & Hirsh, 1994a) 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. Other extensions are considered.

Original languageEnglish (US)
Pages (from-to)151-193
Number of pages43
JournalMachine Learning
Issue number2-3
StatePublished - 1996


  • Description logic
  • Knowledge acquisition
  • Polynomial-time learning
  • Queries
  • Subsumption

ASJC Scopus subject areas

  • Software
  • Artificial Intelligence


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

Cite this