45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04) Learning with Errors in Answers to Membership Queries (Extracted Abstract) Rome, Italy October 17-October 19 ISBN: 0-7695-2228-9
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2004.37
We study the learning models defined in [AKST97]: Learning with equivalence and limited membership queries and learning with equivalence and malicious membership queries. We show that if a class of concepts that is closed under projection is learnable in polynomial time using equivalence and (standard) membership queries then it is learnable in polynomial time in the above models. This closes the open problems in [AKST97]. Our algorithm can also handle errors in the equivalence queries.
Citation:
Laurence Bisht, Nader H. Bshouty, Lawrance Khoury, "Learning with Errors in Answers to Membership Queries (Extracted Abstract)," focs, pp.611-620, 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb