CLASSIC learning

ABSTRACT

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 that membership queries alone are insufficient for polynomial time learning of CLASSIC sentences. Combined with earlier negative results of Cohen and Hirsh 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.

REFERENCES

• 1: Dana Angluin, Learning regular sets from queries and counterexamples, Information and Computation, v.75 n.2, p.87-106, November 1, 1987 [doi>10.1016/0890-5401(87)90052-6]
• 2: Dana Angluin, Learning with hints, Proceedings of the first annual workshop on Computational learning theory, p.167-181, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• 3: Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
• 4: D. Angluin. Requests for hints that return no hints. Technical report, Yale University, YALE/DCS/RR-647, 1988.
• 5: D. Angluin. Exact learning of /i-DNF formulas with malicious membership queries. Technical Report YALEU/DCS/TR-1020, Yale University, March 1994.
• 6: Dana Angluin , Mārtiņš Kriķis, Learning with malicious membership queries and exceptions (extended abstract), Proceedings of the seventh annual conference on Computational learning theory, p.57-66, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181015]
• 7: Dana Angluin , Donna K. Slonim, Randomly Fallible Teachers: Learning Monotone DNF with an Incomplete Membership Oracle, Machine Learning, v.14 n.1, p.7-26, Jan. 1994 [doi>10.1023/A:1022642604085]
• 8: Dana Angluin, Computational learning theory: survey and selected bibliography, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.351-369, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129746]
• 9: Howard W. Beck , Sunit K. Gala , Shamkant B. Navathe, Classification as a Query Processing Technique in the CANDIDE Semantic Data Model, Proceedings of the Fifth International Conference on Data Engineering, p.572-581, February 06-10, 1989
• 10: Daniel G. Bobrow and Terry Winograd. An overview of KRL, a knowledge representation language. Cognitive Science, 1(1):3-46, 1977.
• 11: Alexander Borgida , Ronald J. Brachman , Deborah L. McGuinness , Lori Alperin Resnick, CLASSIC: a structural data model for objects, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.58-67, June 1989, Portland, Oregon, United States
• 12: Alex Borgida. Description logics are not just for the flightless-birds: a new look at the utility and foundations of description logics. 1992.
• 13: Alex Borgida and Peter F. Patel-Schneider. A semantics and complete algorithm for subsumption in the CLASSIC description logic. Technical report, AT&T, 1992.
• 14: R. J. Brachman, R. E. Fikes, and H. J. Levesque. Krypton: A functional approach to knowledge representation. IEEE Computer, 16(10):67-73, 1983.
• 15: Zhixiang Chen , Wolfgang Maass, On-line learning of rectangles, Proceedings of the fifth annual workshop on Computational learning theory, p.16-28, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130387]
• 16: William W. Cohen , Haym Hirsh, Learnability of description logics, Proceedings of the fifth annual workshop on Computational learning theory, p.116-127, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130398]
• 17: William Cohen. Cryptographic limitations on learning one-clause logic programs. In Proceedings of the Tenth National Conference on Artificial Intelligence, Washington, D.C., 1993.
• 18: William Cohen. Pac-learning a restricted class of recursive logic programs. In Proceedings of the Tenth Natwnal Conference on Artificial Intelhgence, Washington, D.C., 1993.
• 19: William W. Cohen, Alex Borgida, and Haym Hirsh. Computing least common subsumers in description logics. In Proceedings of the Tenth National Conference on Artificial Intelligence, 1992.
• 20: William W. Cohen , Haym Hirsh, The Learnability of Description Logics with Equality Constraints, Machine Learning, v.17 n.2-3, p.169-199, Nov./Dec. 1994 [doi>10.1007/BF00993470]
• 21: William W. Cohen and Haym Hirsh. Learning the CLASSIC description logic: Theoretical and experimental results. In Principles of Knowledge Representation and Reasoning: Proceedings of the Fourth International Conference (KR94). Morgan Kaufmann, 1994.
• 22: Prem Devanbu , Ron Brachman , Peter G. Selfridge, LaSSIE: a knowledge-based software information system, Communications of the ACM, v.34 n.5, p.34-49, May 1991 [doi>10.1145/103167.103172]
• 23: Thomas Glen Dietterich, Bob London, Kenneth Clarkson, and Geoff Dromey. Learning and inductive inference. In The Handbook of Artificial Intelligence, Volume 3. William Kaufmann, 1982.
• 24: Sašo Džeroski , Stephen Muggleton , Stuart Russell, PAC-learnability of determinate logic programs, Proceedings of the fifth annual workshop on Computational learning theory, p.128-135, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130399]
• 25: Michael Frazier , Sally Goldman , Nina Mishra , Leonard Pitt, Learning from a consistently ignorant teacher, Proceedings of the seventh annual conference on Computational learning theory, p.328-339, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181170]
• 26: M. Frazier and C. D. Page. Learnability of recursive, non-determinate theories: Some basic results and techniques. In Thwd International Workshop on Inductive Logic Programming, 1993.
• 27: Michael Frazier and Leonard Pitt. Learning from entailment: An application to propositional horn sentences. In Proceedings of the Tenth Internation Conference on Machine Learmng, 1993.
• 28: David Haussler, Learning Conjunctive Concepts in Structural Domains, Machine Learning, v.4 n.1, p.7-40, October 1989 [doi>10.1023/A:1022601210986]
• 29: W. Hoeffding. Probability inequalities for sums of bounded random variables. J. of the Amer. Star. Assoc., 58(301):13-30, March 1963.
• 30: Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
• 31: S. Marcus, editor. Machine Learning: Special Issue on Knowledge Acquisition, volume 3/4. December 1989.
• 32: E. Mays, C. Apte, J. Griesmer, and J. Kastner. Organizing knowledge in a complex financial domain. IEEE Expert, pages 61-70, Fall 1987.
• 33: Stephen Muggleton, Inductive logic programming, New Generation Computing, v.8 n.4, p.295-318, 1991 [doi>10.1007/BF03037089]
• 34: C. D. Page and A. M. Frisch. Generalization and learnability: A study of constrained atoms. In S. H. Muggleton, editor, Inductive Logzc Programmmg, chapter 2, pp. 29-60. Academic Press, London, 1992.
• 35: Peter F. Patel-Schneider, A four-valued semantics for terminological logics, Artificial Intelligence, v.38 n.3, p.319-351, April 1989 [doi>10.1016/0004-3702(89)90036-2]
• 36: Ronald L. Rivest , Robert E. Schapire, Inference of finite automata using homing sequences, Information and Computation, v.103 n.2, p.299-347, April 1993 [doi>10.1006/inco.1993.1021]
• 37: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• 38: L. G. Valiant. Learning disjunctions of conjunctions. In Proceedings of the 9th International Joint Conference on Artificial Intelhgence, vol. 1, pages 560-566, Los Angeles, California, 1985. International Joint Committee for Artificial Intelligence.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Concept learning

General Terms:
Algorithms, Theory, Verification