M.Sc Student Bisht Laurence On Optimal Learning Algorithms for Multiplicity Automata Department of Computer Science Professor Nader Bshouty Abstract

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) ) f :SnF,  where S is some alphabet and F is a field. Our focus is to minimize the access to one or more of the following resources: Equivalence queries, Membership queries or Arithmetic operations in the field F. This is in particular interesting when the access to one or more of the above resources is significantly more expensive than to the others.

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.