Technical Report MSC-2007-14

Title: On Optimal Learning Algorithms for Multiplicity Automata
Authors: Laurence S. Bisht
Supervisors: Nader H. Bshouty
Abstract: In computational learning theory, learning the class Multiplicity Automata (MA) and Multiplicity Automata Function (MAF) over any field from membership (substitution) and equivalence queries is considered one of the most interesting problems studied in the literature. This class includes many interesting classes such as: decision trees, disjoint DNF, O(log n)-term DNF, multivariate polynomials, DFA, boxes and more. We study polynomial time learning algorithms for Multiplicity Automata (MA) and Multiplicity Automata Function (MAF). We introduce efficient algorithms in several conditions. 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. This is in particular interesting when access to one or more of the above resources is significantly more expensive than the others.

We apply new algebraic approach based on Matrix Theory to simplify the algorithms and the proofs of their correctness. We improve the arithmetic complexity of the problem and argue that it is almost optimal. Then we prove tight bound for the minimal number of equivalence queries and show an algorithm that achieves the bound. Regarding membership queries we prove almost (up to log factor) tight bound for the number of membership queries needed to learn MA.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2007
To the main CS technical reports page

Computer science department, Technion