Learning with queries but incomplete information (extended abstract)

ABSTRACT

We investigate learning with membership and equivalence queries assuming that the information provided to the learner is incomplete. By incomplete we mean that some of the membership queries may be answered by “I don't know.” This model is a worst-case version of the incomplete membership query model of Angluin and Slonim. It attempts to model practical learning situations, including an experiment of Lang and Baum that we describe, where the teacher may be unable to answer reliably some queries that are critical for the learning algorithm. We present algorithms to learn monotone k-term DNF with membership queries only, and to learn monotone DNF with membership and equivalence queries. Compared to the complete information case, the query complexity increases by an additive term linear in the number of “I don't know” answers received. We also observe that the blowup in the number of queries can in general be exponential for both our new model and the incomplete membership model.

REFERENCES

• 1: J. R. Anderson. Cognitive Psychology and Its Implications. W. H. Freeman and Company, 1980.
• 2: D. Angluin. Learning k-term DNF formulas using queries and counterexamples. Technical Report YALEU/DCS/RR-559, Yale University Department of Computer Science, 1987.
• 3: 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]
• 4: Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
• 5: D. Angluin. Exact learning of/~-DNF forumlas with malicuous memebership queries. Technical Report YALEU/DCS/TR-1020, Yale University Department of Computer Science, Mar. 1994.
• 6: Dana Angluin , Michael Frazier , Leonard Pitt, Learning Conjunctions of Horn Clauses, Machine Learning, v.9 n.2-3, p.147-164, July 1992 [doi>10.1007/BF00992675]
• 7: Dana Angluin , Lisa Hellerstein , Marek Karpinski, Learning read-once formulas with queries, Journal of the ACM (JACM), v.40 n.1, p.185-210, Jan. 1993 [doi>10.1145/138027.138061]
• 8: 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]
• 9: D. Angluin and M. Kri~is. Malicious membership queries and exceptions. Technical Report YALEU/DCS/RT- 1019, Yale University Department of Computer Science, Mar. 1994.
• 10: 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]
• 11: Peter Auer , Philip M. Long, Simulating access to hidden information while learning, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.263-272, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195152]
• 12: E. B. Baum. Neural net algorithms that learn in polynomial time from examples and queries. IEEE Transactions on Neural Networks, 2(1):5-19, 1991.
• 13: Ulf Berggren, Linear time deterministic learning of k-term DNF, Proceedings of the sixth annual conference on Computational learning theory, p.37-40, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168309]
• 14: N. Bshouty. Exact learning via the monotone theory. In Proc. of the 34th Symposium on the Foundations of Comp, Sci., pages 302-311. IEEE Computer Society Press, 1993.
• 15: Nader H. Bshouty , Thomas R. Hancock , Lisa Hellerstein, Learning Boolean read-once formulas over generalized bases, Journal of Computer and System Sciences, v.50 n.3, p.521-542, June 1995 [doi>10.1006/jcss.1995.1042]
• 16: William Joseph Bultman, Topics in the theory of machine learning and neural computing, University of Illinois at Chicago, Chicago, IL, 1991
• 17: Sally A. Goldman , H. David Mathias, Learning k-term DNF formulas with an incomplete membership oracle, Proceedings of the fifth annual workshop on Computational learning theory, p.77-84, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130394]
• 18: K. J. Lang and E. B. Baum. Query learning can work poorly when a human oracle is used. In International Joint Conference on Neural Networks, Beijing, 1992.
• 19: Wolfgang Maass , György Turán, Lower Bound Methods and Separation Results for On-Line Learning Models, Machine Learning, v.9 n.2-3, p.107-145, July 1992 [doi>10.1007/BF00992674]
• 20: Yasubumi Sakakibara, On learning from queries and counterexamples in the presence of noise, Information Processing Letters, v.37 n.5, p.279-284, March 14, 1991 [doi>10.1016/0020-0190(91)90220-C]
• 21: Robert Sloan, Types of noise in data for concept learning, Proceedings of the first annual workshop on Computational learning theory, p.91-96, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Theory, Verification