# DIMACS Discrete Math/Theory of Computing Seminar

## Title:

On applications of multiplicity automata in learning

## Speaker:

- Amos Beimel
- DIMACS

## Place:

- DIMACS Center, CoRE Building, Seminar Room 431
- Rutgers University

## Time:

- 4:30 PM
- Tuesday, November 19, 1996

Abstract:
(Note: this talk will not assume knowledge about computational
learning theory)

Recently the learnability of multiplicity automata attracted a lot of
attention, mainly because of its implications on the learnability of
several classes of DNF formulae. In this talk we further study the
learnability of multiplicity automata. Our starting point is a known
theorem from automata theory relating the number of states in a
minimal multiplicity automaton for a function f to the rank of a
certain matrix F. With this theorem in hand we obtain the following
results:

1. A new simple algorithm for learning multiplicity automata.
As a result, we improve the complexity for all classes that use the
previously known algorithms and also obtain the best query complexity
for several classes known to be learnable by other methods such as
decision trees and polynomials over GF[2].

2. We prove the learnability of some new classes that were not known
to be learnable before. Most notably, the class of polynomials over
finite fields, the class of bounded-degree polynomials over infinite
fields, the class of XOR of terms, a class of generalized decision
trees, and some classes of boxes in high dimensions.

3. While multiplicity automata were shown to be useful to prove the
learnability of some subclasses of DNF formulae and various other
classes, we study the limitations of this method. We prove that this
method cannot be used to resolve the learnability of some other open
problems such as the learnability of general DNF formulae. These
results are proven by exhibiting functions in the above classes that
require multiplicity automata with super-polynomial number of states.

The talk is based on joint works with Francesco Bergadano,
Nader H. Bshouty Eyal Kushilevitz and Stefano Varricchio.

Document last modified on November 7, 1996