Learnability of description logics

ABSTRACT

This paper considers the learnability of subsets of first-order logic. Piror work has established two boundaries of learnability: Haussler [1989] has shown that conjunctions in first-order logic cannot be learned in the Valiant model, even if the form of the conjunction is highly restricted; on the other hand, Valiant [1984] has shown that propositional conjunctions are learnable. In this paper, we study the learnability of the restricted first-order logics known as description logics. Description logics are also subsets of predicate calculus, but are expressed using a different syntax, allowing a different set of syntactic restrictions to be explored. In this paper, we first define a simple description logic, summarize some results on its expressive power, and then analyze its learnability. It is shown that the full logic cannot be tractably learned; however, syntactic restrictions that enable tractable learning exist. The learnability results hold even if the alphabets of primitive classes and roles (over which descriptions are constructed) are infinite; our positive result thus generalizes not only the result of Valiant [1984] on learning monomials to learning concepts in our (conjunctive) first order language, but also the result of Blum [1990] on learning monomials over infinite attribute spaces.

REFERENCES

• Beck et al., 1989: 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
• Bergamaschi et al., 1988: Sonia Bergamaschi , Flavio Bonfatti , Claudio Sartori, Entity-Situation: A Model for the Knowledge Representation Module of a KBMS, Proceedings of the International Conference on Extending Database Technology: Advances in Database Technology, p.578-582, March 14-18, 1988
• Blum, 1990: A. Blum, Learning boolean functions in an infinite attribute space, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.64-72, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100224]
• Blumer et al., 1986: A Blumer , A Ehrenfeucht , D Haussler , M Warmuth, Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.273-282, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12158]
• Borgida and Patel-Schneider, in preparation: A. Borgida and P. F. Patel-Schneider. A semantics and complete algorithm for subsumption in the CLASSIC description logic. In preparation.
• Borgida et al., 1989: 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
• Brachman et al., 1983: R. J. Brachman, R. E. Fikes, and H. J. Levesque. Krypton: A functional approach to knowledge representation. IEEE Computer, 16(10):67-73, 1983.
• Cohen and Hirsh, in preparation: W. Cohen and H. Hirsh. Learning in description logics using least common subsumers. In preparation.
• Cohen et al., 1992: 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, San Jose, California, 1992. MIT Press.
• Devanbu et al., 1991: 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]
• Dietterich et al., 1982: Thomas Glen Dietterich, Bob London, Kenneth Clarkson, and Geoff Dromey. Learning and inductive inference. In Paul Cohen and Edward A. Feigenbaum, editors, The Handbook of Artificial Intelligence, Volume III. William Kaufmann, Los Altos, CA, 1982.
• Edelman and Owsnicki, 1986: Jürgen Edelmann , Bernd Owsnicki-Klewe, Data Models in Knowledge Representation System: A Case Study, GWAI-86 und 2. Österreichische Artificial-Intelligence-Tagung, p.69-74, September 22-26, 1986
• Haussler, 1989: David Haussler, Learning Conjunctive Concepts in Structural Domains, Machine Learning, v.4 n.1, p.7-40, October 1989 [doi>10.1023/A:1022601210986]
• Helmbold et al., 1990: David Helmbold , Robert Sloan , Manfred K. Warmuth, Learning Nested Differences of Intersection-Closed Concept Classes, Machine Learning, v.5 n.2, p.165-196, Jun. 1990 [doi>10.1023/A:1022696716689]
• Hopcroft and Ullman, 1979: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• Kearns and Valiant, 1989: M. Kearns , L. G. Valiant, Crytographic limitations on learning Boolean formulae and finite automata, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.433-444, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73049]
• Kearns et al., 1987: Micheal Kearns, Ming Li, Leonard Pitt, and Les Valiant. Recent results in boolean concept learning. In Proceedings of the Fourth International Workshop on Machine Learning, Ithaca, New York, 1987. Morgan Kaufmann.
• Littlestone, 1988: 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]
• Mays et al., 1987: E. Mays, C. Apte, J. Griesmer, and J. Kastner. Organizing knowledge in a complex financial domain. IEEE Expert, pages 61-70, Fall 1987.
• Patel-Schneider, 1984: P. F. Patel-Schneider. Small can be beautiful in knowledge representation. In Proceedings of the IEEE Workshop on Principles of Knowledge-Based Systems, pages 11-16, Denver, Colorado, 1984.
• Patel-Schneider, 1989: 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]
• Pitt and Warmuth, 1988: L. Pitt and M. K. Warmuth. Reductions among prediction problems: On the difficulty of predicting automata. In Proceedings of the 3rd Annual IEEE Conference on Structure in Complexity Theory, Washington, D.C., 1988. Computer Society Press of the IEEE.
• Rivest, 1987: Ronald L. Rivest, Learning Decision Lists, Machine Learning, v.2 n.3, p.229-246, November 1987 [doi>10.1023/A:1022607331053]
• Schewe, 1989: Klaus-Dieter Schewe, Variant Construction Using Constraint Propagation Techniques over Semantic Networks, 5. Österreichische Artificial Intelligence-Tagung, p.188-197, September 28-30, 1989
• Valiant, 1984: 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]
• Woods and Schmolze, 1992: W. A. Woods and J. G. Schmolze. The KL-ONE family. Computers And Mathematics With Applications, 23(2-5), March 1992.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic

General Terms:
Algorithms, Theory, Verification