M.Sc Student | Owshanko Avraham |
---|---|

Subject | Learning Finite Automata, Using Incomplete Membership Queries |

Department | Department of Computer Science |

Supervisor | Professor Nader Bshouty |

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 2*n*∙*log*
(*n*) equivalence queries and no membership queries (where *n* is
the size of the target automaton).