טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentBennet Rotem
SubjectImproved Learning with Corrupt Oracles
DepartmentDepartment of Computer Science
Supervisor Professor Nader Bshouty


Abstract

In most real life situations, the EXACT learning protocol suffers from some limitations, which obstruct the practical use of the overly ``neat" theoretical results from the literature. One such limitation is when the oracle is corrupt; that is, either malicious - might make mistakes, or limited - might answer ``I don't know". Another realistic constraint is that of ``attribute-efficiency" - the learner typically sees each example as composed of many irrelevant attributes, which should thus be

distinguished from the relevant ones in order to enable capturing the exact concept .


In this research we study learning attribute-efficiently with corrupt oracles. For each of the possible corruptions and learning scenarios we describe a generic scheme that enables learning in these cases using modifications of the standard learning algorithms .


When learning with a limited membership oracle, the learner is sometimes allowed to learn non-strictly, and output a hypothesis equivalent to the target function only on the non-corrupt instances. We prove that efficient non-strict learnability implies efficient strict learnability. Our reduction between the models , shown to be optimal, improves significantly over previously known reductions .


We conclude by presenting an adaptation of Bshouty's ``Monotone theory" to using a limited membership oracle for learning concept classes such as CDNF (and DT). By this we demonstrate that utilizing the unique properties of specific concept classes can be used to develop specific algorithms for learning with corrupt

oracles, whose complexity is superior compared to the algorithms achieved using any known generic scheme .