טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentOwshanko Avraham
SubjectLearning Finite Automata, Using Incomplete Membership
Queries
DepartmentDepartment of Computer Science
Supervisor Professor Nader Bshouty


Abstract

The problem of learning regular sets is among the most important problems in computational learning theory. In this work we address learning of regular sets in the exact model, with the aid of a fallible teacher. This class is efficiently learnable with the aid of an omniscient teacher, but not efficiently learnable using only counterexamples. The existence of such a perfect teacher is often considered impractical. Thus we investigate learning with the help a fallible teacher.


Learning in the exact model represents the situation in which the adversary has control of all the information that the learner gets. On the other hand, an omniscient teacher gives a very powerful boost to the learner. To reduce the constraint of perfect knowledge, we introduce a fallible teacher. This is a teacher that does not know all the answers, but only some of them. This teacher still does not make mistakes. So this teacher will either return the correct answer, or say that he/she does not know.


In this work, we propose a new variation of the incomplete model. Instead of having an online adversary, we consider the model where the adversary is offline, i.e. knows the teacher in advance. We show that this model is stronger than the existing offline adversary model, and we also show a separation between the incomplete model and the minimally adequate teacher model. The main result of this work is an algorithm for learning regular sets in the offline incomplete model, thus separating the incomplete model and the exact model.


All the separation results given here are for the proper models only, (models where all the hypothesis are regular sets). In the exact model, any halving algorithm can learn the target using standard halving techniques, thus learning regular sets asking 2nlog (n) equivalence queries and no membership queries  (where n is the size of the target automaton).