Article

Free access

Learning with malicious membership queries and exceptions (extended abstract)

Authors:

Dana Angluin,

Mārtiņš KriķisAuthors Info & Claims

COLT '94: Proceedings of the seventh annual conference on Computational learning theory

Pages 57 - 66

https://doi.org/10.1145/180139.181015

Published: 16 July 1994 Publication History

PDF eReader

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]

D. Angluin. Learning regular sets from queries and counterexamples. Inform. Compui., 75(2):87-106, November 1987.

Digital Library

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[4]

D. Angluin and D. K. Slonim. Randomly fallible teachers: learning monotone DNF with an incomplete membership oracle. Machine Learning, 14(1):7-26, 1994.

Digital Library

Google Scholar

[5]

R. Board and L. Pitt. On the necessity of Occam algorithms. Theoret. Comput. Sci., 100:157-184, 1992.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Google Scholar

[8]

S. A. Goldman, M. J. Kearns, and R. E. Schapire. Exact identification of read-once formulas using fixed points of amplification functions. SIAM J. Comput., 22(4):705-726, 1993.

Digital Library

Google Scholar

[9]

S. A. Goldman and H. D. Mathias. Learning k-term DNF formulas with an incomplete membership oracle. In Proc. 5th Annu. Workshop on Comput. Learning Theory, pages 77-84. ACM Press, New York, NY, 1992.

Digital Library

Google Scholar

[10]

D. Ron and R. Rubinfeld. Learning fallible finite state automata. In Proc. 6th Annu. Workshop on Comput. Learning Theory, pages 218-227. ACM Press, New York, NY, 1993.

Digital Library

Google Scholar

[11]

Y. Sakakibara. On learning from queries and counterexamples in the presence of noise. Inform. Proc. Lett., 37(5):279-284, March 1991.

Digital Library

Google Scholar

[12]

R. Sloan and G. Turan. Learning with queries but incomplete information. This proceedings.

Digital Library

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

Cited By

View all

Mubayi DTurán GZhao Y(2006)The DNF exception problemTheoretical Computer Science10.1016/j.tcs.2005.10.038352:1(85-96)Online publication date: 7-Mar-2006
https://dl.acm.org/doi/10.1016/j.tcs.2005.10.038
Guijarro DLavin VRaghavan V(2001)Monotone term decision listsTheoretical Computer Science10.5555/2780702.2781112259:1(549-575)Online publication date: 28-May-2001
https://dl.acm.org/doi/10.5555/2780702.2781112
Kwek S(2001)Learning Intermediate ConceptsAlgorithmic Learning Theory10.1007/3-540-45583-3_13(151-166)Online publication date: 31-Oct-2001
https://doi.org/10.1007/3-540-45583-3_13
Show More Cited By

Index Terms

Learning with malicious membership queries and exceptions (extended abstract)
1. Computing methodologies
  1. Machine learning

Recommendations

Malicious Omissions and Errors in Answers to Membership Queries

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

To study (...
Learning with errors in answers to membership queries

We study the learning models defined in [D. Angluin, M. Krikis, R.H. Sloan, G. Turan, Malicious omissions and errors in answering to membership queries, Machine Learning 28 (2-3) (1997) 211-255]: Learning with equivalence and limited membership queries ...
Oracles and queries that are sufficient for exact learning (extended abstract)
COLT '94: Proceedings of the seventh annual conference on Computational learning theory

We show that the class of all circuits is exactly learnable in randomized expected polynomial-time using subset and superset queries. This is a consequence of the following result which we consider to be of independent interest: circuits are exactly ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

COLT '94: Proceedings of the seventh annual conference on Computational learning theory

July 1994

376 pages

ISBN:0897916557

DOI:10.1145/180139

Chairman:
Manfred Warmuth
Univ. of California, Santa Cruz

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 July 1994

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

7COLT94

Sponsor:

7COLT94: 7th Annual Conference on Computational Learning Theory

July 12 - 15, 1994

New Jersey, New Brunswick, USA

Acceptance Rates

Overall Acceptance Rate 35 of 71 submissions, 49%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
61
Total Downloads

Downloads (Last 12 months)31
Downloads (Last 6 weeks)12

Reflects downloads up to 04 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Mubayi DTurán GZhao Y(2006)The DNF exception problemTheoretical Computer Science10.1016/j.tcs.2005.10.038352:1(85-96)Online publication date: 7-Mar-2006
https://dl.acm.org/doi/10.1016/j.tcs.2005.10.038
Guijarro DLavin VRaghavan V(2001)Monotone term decision listsTheoretical Computer Science10.5555/2780702.2781112259:1(549-575)Online publication date: 28-May-2001
https://dl.acm.org/doi/10.5555/2780702.2781112
Kwek S(2001)Learning Intermediate ConceptsAlgorithmic Learning Theory10.1007/3-540-45583-3_13(151-166)Online publication date: 31-Oct-2001
https://doi.org/10.1007/3-540-45583-3_13
Goldman SKwek SScott SFreund YSchapire R(1997)Learning from examples with unspecified attribute values (extended abstract)Proceedings of the tenth annual conference on Computational learning theory10.1145/267460.267504(231-242)Online publication date: 1-Jul-1997
https://dl.acm.org/doi/10.1145/267460.267504
Angluin DKriķis MSloan RTurán G(1997)Malicious Omissions and Errors in Answers to Membership QueriesMachine Language10.1023/A:100731141125928:2-3(211-255)Online publication date: 1-Sep-1997
https://dl.acm.org/doi/10.1023/A%3A1007311411259
Mathias H(1997)A Model of Interactive TeachingJournal of Computer and System Sciences10.1006/jcss.1997.149154:3(487-501)Online publication date: 1-Jun-1997
https://dl.acm.org/doi/10.1006/jcss.1997.1491
Frazier MPitt L(1996)Classic learningMachine Language10.1007/BF0011400925:2-3(151-193)Online publication date: 1-Dec-1996
https://dl.acm.org/doi/10.1007/BF00114009
Mathias HMaass W(1995)DNF—if you can't learn'em, teach'emProceedings of the eighth annual conference on Computational learning theory10.1145/225298.225325(222-229)Online publication date: 5-Jul-1995
https://dl.acm.org/doi/10.1145/225298.225325
Blum AChalasani PGoldman SSlonim DMaass W(1995)Learning with unreliable boundary queriesProceedings of the eighth annual conference on Computational learning theory10.1145/225298.225310(98-107)Online publication date: 5-Jul-1995
https://dl.acm.org/doi/10.1145/225298.225310
Goldreich ORubinfeld RSudan M(1995)Learning polynomials with queries: The highly noisy caseProceedings of IEEE 36th Annual Foundations of Computer Science10.1109/SFCS.1995.492485(294-303)Online publication date: 1995
https://doi.org/10.1109/SFCS.1995.492485
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Malicious Omissions and Errors in Answers to Membership Queries

Learning with errors in answers to membership queries

Oracles and queries that are sufficient for exact learning (extended abstract)