(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.