Learning with errors in answers to membership queries

摘要

We study the learning models defined in [D. Angluin, M. Krikis, R.H. Sloan, G. Turán, Malicious omissions and errors in answering to membership queries, Machine Learning 28 (2–3) (1997) 211–255]: 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 [D. Angluin, M. Krikis, R.H. Sloan, G. Turán, Malicious omissions and errors in answering to membership queries, Machine Learning 28 (2–3) (1997) 211–255].Our algorithm can also handle errors in the equivalence queries.