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 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Angluin, D. (1987). Learning regular sets from queries and counterexamples. Information and Computation, 75(2), 87–106.
Angluin, D. (1988a). Learning with hints. Proceedings of the 1988 Workshop on Computational Learning Theory(pp. 167–181). San Mateo, CA: Morgan Kaufmann.
Angluin, D. (1988b). Queries and concept learning. Machine Learning, 2(4), 319–342.
Angluin, D. (1988c). Requests for hints that return no hints. Technical report YALEU/DCS/RR-647, Yale University.
Angluin, D. (1992). Computational learning theory: survey and selected bibliography. Proceedings of the Twenty Fourth Annual ACM Symposium on Theory of Computing (pp. 351–369). Victoria, BC: ACM Press.
Angluin, D. (1994). Exact learning of µ-DNF formulas with malicious membership queries. Technical Report YALEU/DCS/TR-1020, Yale University.
Angluin, D., Frazier, M., & Pitt, L. (1992). Learning conjunctions of Horn clauses. Machine Learning, 9, 147–164.
Angluin, D. & Kharitonov, M. (1995). When won't membership queries help? Journal of Computer and System Sciences, 50.
Angluin, D. & Kriķis, M. (1994). Learning with malicious membership queries and exceptions. Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory (pp. 57–66). New York: ACM Press.
Angluin, D. & Laird, P. (1988). Learning from noisy examples. Machine Learning, 2(4), 343–370.
Angluin, D. & Slonim, D. K. (1994). Randomly fallible teachers: learning monotone DNF with an incomplete membership oracle. Machine Learning, 14(1), 7–26.
Auer, P. (1993). On-line learning of rectangles in noisy environments. Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory (pp. 253–261). New York: ACM Press.
Beck, H., Gala, H., & Navathe, S. (1989). Classification as a query processing technique in the CANDIDE semantic model. Data Engineering Conference (pp. 572–581). Los Angeles, CA.
Blum, A. & Chalasani, P. (1992). Learning switching concepts. Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory (pp. 231–242). New York: ACM Press.
Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1989). Learnability and the Vapnik-Chervonenkis dimension. Journal of the ACM, 36(4), 929–965.
Bobrow, D. G. & Winograd, T. (1977). An overview of KRL, a knowledge representation language. Cognitive Science, 1(1), 3–46.
Borgida, A. (1992). Description logics are not just for the flightless-birds: a new look at the utility and foundations of description logics. Preprint. Borgida, A., Brachman, R. J., McGuinness, D. L., & Resnick, L. (1989). CLASSIC: A structural data model for objects. Proceedings of SIGMOD-89 Portland, Oregon.
Borgida, A. & Patel-Schneider, P. F. (1992). A semantics and complete algorithm for subsumption in the CLASSIC description logic. Technical report, AT&T.
Brachman, R. J., Fikes, R. E., & Levesque, H. J. (1983). Krypton: A functional approach to knowledge representation. IEEE Computer, 16(10), 67–73.
Chen, Z. & Maass, W. (1994). On-line learning of rectangles and unions of rectangles. Machine Learning, 17(2/3), 23–50.
Cohen, W. (1993a). Cryptographic limitations on learning one-clause logic programs. Proceedings of the Tenth National Conference on Artificial Intelligence. Washington, D.C.
Cohen, W. (1993b). Pac-learning a restricted class of recursive logic programs. Proceedings of the Tenth National Conference on Artificial Intelligence. Washington, D.C.
Cohen, W. W., Borgida, A., & Hirsh, H. (1992). Computing least common subsumers in description logics. Proceedings of the Tenth National Conference on Artificial Intelligence.
Cohen, W. W. & Hirsh, H. (1994a). Learnability of description logics with equality constraints. Machine Learning, 17(2/3), 169–199. Special issue on Computational Learning Theory: COLT'92.
Cohen, W. W. & Hirsh, H. (1994b). Learning the CLASSIC description logic: Theoretical and experimental results. Principles of Knowledge Representation and Reasoning: Proceedings of the Fourth International Conference (KR94): Morgan Kaufmann.
Cohen, W. W. & Page, C. D. Jr. (1994). Polynomial learnability and inductive logic programming: Methods and results. Submitted for publication.
Dalal, M. & Etherington, D. (1992). Tractable approximate deduction using limited vocabulary. In CSCSI-92 Vancouver.
Decatur, S. E. (1993). Statistical queries and faulty PAC oracles. Proceedings of the Sixth Annual ACMConference Computational Learning Theory (pp. 262–268). New York: ACM Press.
Devanbu, P., Brachman, R. J., Selfridge, P., & Ballard, B. (1991). LaSSIE: A knowledge-based software information system. Communications of the ACM, 35(5).
Dietterich, T. G., London, B., Clarkson, K., & Dromey, G. (1982). Learning and inductive inference. In The Handbook of Artificial Intelligence, Volume 3. William Kaufmann.
D¢zeroski, S., Muggleton, S., & Russell, S. (1992). Pac-learnability of logic programs. Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory (pp. 128–135). New York: ACM Press.
Frazier, M., Goldman, S., Mishra, N., & Pitt, L. (1994). Learning from a consistently ignorant teacher. Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory (pp. 328–339). New York: ACM Press. To appear, Information and Computation.
Frazier, M. & Page, C. D. (1993). Learnability of recursive, non-determinate theories: Some basic results and techniques. Third International Workshop on Inductive Logic Programming.
Frazier, M. & Pitt, L. (1993). Learning from entailment: An application to propositional horn sentences. Proceedings of the Tenth International Conference on Machine Learning (pp. 120–127). San Mateo, CA: Morgan Kaufmann.
Haussler, D. (1989). Learning conjunctive concepts in structural domains. Machine Learning, 4(1), 7–40.
Haussler, D., Littlestone, N., & Warmuth, M. K. (1994). Predicting {0, 1} functions on randomly drawn points. Information and Computation, 115(2), 284–293.
Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301), 13–30.
Kearns, M. & Li, M. (1993). Learning in the presence of malicious errors. SIAM Journal on Computing, 22, 807–837.
Kearns, M. & Valiant, L. G. (1994). Cryptographic limitations on learning Boolean formulae and finite automata. Journal of the ACM, 41(1), 67–95.
Littlestone, N. (1988). Learning when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning, 2, 285–318.
Mays, E., Apte, C., Griesmer, J., & Kastner, J. (Fall 1987). Organizing knowledge in a complex financial domain. IEEE Expert, (pp. 61–70).
Muggleton, S. (1991). Inductive logic programming. New Generation Computing, 8, 295–318.
Page, C. D. & Frisch, A. M. (1992). Generalization and learnability: A study of constrained atoms. In S. H. Muggleton (Ed.), Inductive Logic Programming chapter 2. London: Academic Press.
Page, C. D. (1993). Anti-unification in constraint logics: Foundations and applications to learnability in first-order logic, to speed-up learning, and to deduction. PhD thesis, University of Illinois at Urbana-Champaign.
Patel-Schneider, P. F. (1989). A four-valued semantics for terminological logics. Artificial Intelligence, 38, 319–351.
Pitt, L. & Warmuth, M. K. (1990). Prediction preserving reducibility. Journal of Computer and System Sciences, 41(3), 430–467. Special issue for the Third Annual Conference of Structure in Complexity Theory.
Rivest, R. L. & Schapire, R. E. (1993). Inference of finite automata using homing sequences. Information and Computation, 103(2), 299–347.
Ron, D. & Rubinfeld, R. (1993). Learning fallible finite state automata. Proceedings of the Sixth Annual ACM Conference Computational Learning Theory (pp. 218–227). New York: ACM Press.
Schapire, R. E. (1990). The strength of weak learnability. Machine Learning, 5(2), 197–227.
Shackelford, G. & Volper, D. (1988). Learning k-DNF with noise in the attributes. Proceedings of the 1988 Workshop on Computational Learning Theory (pp. 97–103). San Mateo, CA: Morgan Kaufmann.
Sloan, R. (1988). Types of noise in data for concept learning. Proceedings of the 1988 Workshop on Computational Learning Theory (pp. 91–96). San Mateo, CA: Morgan Kaufmann.
Sloan, R. H. & Turán, G. (1994). Learning with queries but incomplete information. Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory (pp. 237–245). New York: ACM Press.
Valiant, L. G. (1984). A theory of the learnable. Communications of the ACM, 27(11), 1134–1142.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Frazier, M., Pitt, L. Classic Learning. Machine Learning 25, 151–193 (1996). https://doi.org/10.1023/A:1026443024002
Issue Date:
DOI: https://doi.org/10.1023/A:1026443024002