Abstract
An algorithm is presented for learning the class of Boolean formulas that are expressible as conjunctions of Horn clauses. (A Horn clause is a disjunction of literals, all but at most one of which is a negated variable.) The algorithm uses equivalence queries and membership queries to produce a formula that is logically equivalent to the unknown formula to be learned. The amount of time used by the algorithm is polynomial in the number of variables and the number of clauses in the unknown formula.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Angluin, D. (1988). Learning with hints. InProceedings of the 1988 Workshop on Computational Learning Theory (pp. 167–181). Boston, MA: Morgan Kaufmann.
Angluin, D. (1988). Queries and concept learning.Machine Learning, 2, 319–342.
Angluin, D. (1988).Requests for hints that return no hints (Technical Report YALE/DCS/RR-647). Department of Computer Science, Yale University.
Angluin, D. (1990). Negative results for equivalence queries.Machine Learning, 5, 121–150.
Angluin, D., Frazier, M., & Pitt, L. (1990). Learning conjunctions of Horn clauses. InProceedings of the 31st Annual Symposium on Foundations of Computer Science (pp. 186–192). St. Louis, MO: IEEE Computer Society Press.
Angluin, D., Hellerstein, L., & Karpinski, M. (1989).Learning read-once formulas with queries (Technical Report, University of California at Berkeley, Report No. 89/528). (Also, International Computer Science Institute Technical Report TR-89-050. To appear,JACM.)
Angluin, D. & Kharitonov, M. (1991). When won't membership queries help? InProceedings of the Twenty Third Annual ACM Symposium on Theory of Computing (pp. 444–454). New Orleans, LA: ACM Press.
Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. (1989). Learnability and the Vapnik-Chervonenkis dimension.J. ACM, 36, 929–965.
Ehrenfeucht, A. & Haussler, D. (1988). Learning decision trees from random examples. InProceedings of the 1988 Workshop on Computational Learning Theory (pp. 182–194). Boston, MA: Morgan Kaufmann.
Haussler, D. (1988). Quantifying inductive bias: AI learning algorithms and Valiant's learning framework.Artificial Intelligence, 36, 177–221.
Haussler, D. (1989). Learning conjunctive concepts in structural domains.Machine Learning, 4, 7–40.
Haussler, D., Littlestone, N., & Warmuth, M.K. (1988). Predicting {0, 1} functions on randomly drawn points. InProceedings of the 29th Annual Symposium on Foundations of Computer Science (pp. 100–109). Washington, D.C.: IEEE Computer Society Press.
Jones, N.D. & Laaser, W.T. (1977). Complete problems for deterministic polynomial time.Theoretical Computer Science, 3, 107–113.
Kearns, M., Li, M., Pitt, L., & Valiant, L.G. (1987). On the learnability of Boolean formulae. InProceedings of the Nineteenth Annual ACM Symposium on Theory of Computing (pp. 285–295). New York, NY: ACM Press.
Kearns, M. & Valiant, L.G. (1989). Cryptographic limitations on learning boolean formulae and finite automata. InProceedings of the Twenty First Annual ACM Symposium on Theory of Computing (pp. 433–444). Seattle, WA: ACM Press.
Littlestone, N. (1988). Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm.Machine Learning, 2, 285–318.
Pitt, L. & Warmuth, M.K. (1990). Prediction-preserving reducibility.J. of Computer and System Sciences, 41, 430–467.
Rivest, R.L. (1987). Learning decision lists.Machine Learning, 2, 229–246.
Valiant, L.G. (1985). Learning disjunctions of conjunctions. InProceedings of the 9th International Joint Conference on Artificial Intelligence (pp. 560–566). Los Angeles, CA.
Valiant, L.G. (1984). A theory of the learnable.Communications of the ACM, 27, 1134–1142.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Angluin, D., Frazier, M. & Pitt, L. Learning conjunctions of Horn clauses. Mach Learn 9, 147–164 (1992). https://doi.org/10.1007/BF00992675
Issue Date:
DOI: https://doi.org/10.1007/BF00992675