M.Sc Student | Bisht Laurence |
---|---|

Subject | On Optimal Learning Algorithms for Multiplicity Automata |

Department | Department of Computer Science |

Supervisor | Professor Nader Bshouty |

Full Thesis text |

*Computational Learning Theory* (COLT) is one of the theoretical
fields in Computer Science that is devoted to studying the design and analysis
of algorithms for predicting things, such as membership in a concept. Our
research was done in the *Exact Learning model*, introduced by Angluin and
Littlestone. In this model a *teacher* hides a *target function* *f*
that belongs to a class of functions *C*. The learner's (learning
algorithm) goal is to identify *f* efficiently. The learning process is
done through queries. In a *Membership Query*, the learner asks the
teacher for the value of the function on an assignment *a*, the teacher
returns *f(a)*. In an *Equivalence Query* the learner proposes a
hypothesis *h*, claiming that this hypothesis is logically equivalent to *f*,
the teacher returns "YES" if h ≡ f, or a counterexample *a*
that satisfies *h(a)*≠* f(a).*

We study polynomial time learning algorithms for the class of
Multiplicity Automata (MA) *f* :S^{*}
→ ** F** and Multiplicity Automata Function (MAF) )

We summarize our results in the following:

**Matrix Approach:** We apply new algebraic approach based on Matrix
Theory to simplify the algorithms and the proofs of their correctness.

**Arithmetic Complexity:** We improve the arithmetic complexity
of Exactly learning MA. We also learn MA with arithmetic complexity that is *independent*
of the alphabet size. We argue that the arithmetic complexity of this algorithm
is optimal.

**Equivalence Query Complexity: **We prove a tight bound on the minimal
number of equivalence queries and show an algorithm that achieves the bound.

**Membership Query Complexity:** We prove a lower bound on the number
of queries which is almost tight (up to log factor). This gives an almost tight
lower bound on the number of membership queries needed to learn MA.

**Results for MAF:** we also obtain results similar to the above for MAF.
We introduce a new representation of a MAF called the compressed MAF and use it
to show learnability that uses optimal number of equivalence queries and almost
optimal number of membership queries and arithmetic operations for MAF.