|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.
|Copyright||The 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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2007/MSC/MSC-2007-14), 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