טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentKhoury Lawrance
SubjectLearning with Errors in Answers to Membership Queries
DepartmentDepartment of Computer Science
Supervisor Professor Nader Bshouty


Abstract

We study Learning with equivalence and limited membership queries, where the query can answer "I don't know", and learning with equivalence and malicious membership queries where the query can lie.

We show

1.      If a class of concepts is learnable from equivalence and membership queries in polynomial time then it is learnable from equivalence and limited membership queries in polynomial time.

2.      If a class of concepts is learnable from  membership queries only in polynomial time then it is learnable from limited membership queries only in polynomial time.

3.      If a class of concepts is learnable from equivalence and membership queries in polynomial time then it is learnable from equivalence and malicious membership queries in polynomial time.

This closes the open problems that introduced by  Angluin, Krikis, Sloan and Tur'an in there article "Malicious omissions and errors in answering to membership queries".

We also consider limited membership query LMQK  for some set of sub-domains K. This query returns correct answers for all assignments that are in some sub-domain KЄK chosen by some adversary. We show that if K  (as concept class of Boolean functions) is learnable as disjoint DNF from membership and equivalence queries then learning with limited membership queries LMQK and equivalence queries is equivalent to learning with membership and equivalence queries.

Our algorithm can also handle lies in the equivalence queries.