Learning with malicious membership queries and exceptions (extended abstract)

ABSTRACT

We consider two issues in polynomial-time exact learning of concepts using membership and equivalence queries: (1) malicious errors in the answers to membership queries and (2) learning finite variants of concepts drawn from a learnable class.

REFERENCES

• 1: 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]
• 2: D. Angluin. Exact learning of p-DNF formulas with malicious membership queries. Technical Report YALEU/DCS/TR-1020, Yale University Department of Computer Science, March 1994.
• 3: D. Angluin and M. Krikis. Malicious membership queries and exceptions. Technical Report YALEU/DCS/TR-1019, Yale University Department of Computer Science, March 1994.
• 4: 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]
• 5: Raymond Board , Leonard Pitt, On the necessity of Occam algorithms, Theoretical Computer Science, v.100 n.1, p.157-184, June 22, 1992 [doi>10.1016/0304-3975(92)90367-O]
• 6: N. Bshouty. Exact learning via the monotone theory. In Proc. of the 3~th Symposium on the Foundations of Comp. Sci., pages 302-311. IEEE Computer Society Press, Los Alamitos, CA, 1993.
• 7: T. Dean, D. Angluin, K. Basye, S. Engelson, L. Kaelbling, E. Kokkevis, and O. Maron. Inferring finite automata with stochastic output functions and an application to map learning. In Proceedings of AAAI-92, pages 208-214. AAAI, 1992.
• 8: Sally A. Goldman , Michael J. Kearns , Robert E. Schapire, Exact identification of read-once formulas using fixed points of amplification functions, SIAM Journal on Computing, v.22 n.4, p.705-726, Aug. 1993 [doi>10.1137/0222047]
• 9: 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]
• 10: Dana Ron , Ronitt Rubinfeld, Learning fallible finite state automata, Proceedings of the sixth annual conference on Computational learning theory, p.218-227, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168336]
• 11: 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]
• 12: Robert H. Sloan , György Turán, Learning with queries but incomplete information (extended abstract), Proceedings of the seventh annual conference on Computational learning theory, p.237-245, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181128]
• 13: L. G. Valiant. Learning disjunctions of conjunctions. In Proceedzngs of the 9th International Joznt Conference on Artificial Intelligence, vol. 1, pages 560-566, Los Angeles, California, 1985. International Joint Committee for Artificial Intelligence.
• 14: Y. Zhuravlev and Y. Kogan. Realization of boolean functions with a small number of zeros by disjunctive normal forms, and related problems. Soviet Math. Doklady, 32:771-775, 1985.

INDEX TERMS

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

General Terms:
Algorithms, Theory, Verification