Abstract
We consider the problem of exact identification of classes of concepts using only equivalence queries. We define a combinatorial property,approximate fingerprints, of classes of concepts and show that no class with this property can be exactly identified in polynomial time using only equivalence queries. As applications of this general theorem, we show that there is no polynomial time algorithm using only equivalence queries that exactly identifies deterministic or nondeterministic finite state acceptors, context free grammars, or disjunctive or conjunctive normal form boolean formulas.
Article PDF
Similar content being viewed by others
References
Angluin, D. (1982a). Inference of reversible languages.J. ACM, 29, 741–765.
Angluin, D. (1982b). A note on the number of queries needed to identify regular languages.Information and Control,51, 76–87.
Angluin, D. (1987). Learning regular sets from queries and counterexamples.Information and Computation,75, 87–106.
Angluin, D. (1988a). Queries and concept learning.Machine Learning,2, 319–342.
Angluin, D. (1988b).Negative results for equivalence queries (Technical Report YALE/DCS/RR-648). Yale University, Department of Computer Science.
Angluin, D. (1988c).Equivalence queries and DNF formulas (Technical Report YALE/DCS/RR-659). Yale University, Department of Computer Science.
Angluin, D. (1989). Equivalence queries and approximate fingerprints.Proceedings of the Second Annual Workshop on Computational Learning Theory (pp. 134–145). Palo Alto, CA: Morgan Kaufmann.
Angluin, D., Hellerstein, L., & Karpinski (1989).Learning read-once formulas with queries (Technical Report UCB/CSD 89/528). University of California at Berkeley, Computer Science Division. (Also, Technical Report TR-89–050, International Computer Science Institute, Berkeley, California.)
Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. (1987). Occam's razor.Information Processing Letters,24, 377–380.
Hancock, T. (1989). Identifying decision trees with equivalence queries. Manuscript, Harvard University.
Haussler, D., Kearns, M., Littlestone, N., & Warmuth, M. (1988). Equivalence of models for polynomial learnability.Proceedings of the 1988 Workshop on Computational Learning Theory (pp. 42–55). Palo Alto, CA: Morgan Kaufmann.
Haussler, D., Littlestone, N., & Warmuth, M. (1988). Predicting {0, 1}-functions on randomly drawn points.Proceedings of the 29th Symposium on Foundations of Computer Science (pp. 100–109). Washington, DC: The Computer Society Press of the IEEE.
Ibarra, O. & Jiang, T. (1988). Learning regular languages from counterexamples.Proceedings of the 1988 Workshop on Computational Learning Theory (pp. 371–385). Palo Alto, CA: Morgan Kaufmann.
Kearns, M., & Valiant, L., (1989). Cryptographic limitations on learning boolean formulae and finite automata.Proceedings of the 21st ACM Symposium on Theory of Computing (pp. 433–444). New York, NY: The Association for Computing Machinery.
Littlestone, N., (1988). Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm.Machine Learning,2, 285–318.
Pitt, L., & Warmuth, M., (1988). Reductions among prediction problems: On the difficulty of predicting automata.Proceedings of the Third Annual Structure in Complexity Theory Conference (pp. 60–69). Washington, DC: The Computer Society Press of the IEEE.
Porat, S., & Feldman, J., (1988). Learning automata from ordered examples.Proceedings of the 1988 Workshop on Computational Learning Theory (pp. 386–396). Palo Alto, CA: Morgan Kaufmann.
Sakakibara, Y., (1988). Learning context-free grammars from structural data in polynomial time.Proceedings of the 1988 Workshop on Computational Learning Theory (pp. 330–344). Palo Alto, CA: Morgan Kaufmann.
Valiant, L., (1984). A theory of the learnable.C. ACM,27, 1134–1142.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Angluin, D. Negative results for equivalence queries. Mach Learn 5, 121–150 (1990). https://doi.org/10.1007/BF00116034
Issue date:
DOI: https://doi.org/10.1007/BF00116034
