Published: September 28, 2006

**Keywords:**learning, exact learning, arithmetic circuit, partial derivative, multiplicity automata

**ACM Classification:**I.2.6, F.2.2

**AMS Classification:**68Q32

**Abstract:**
[Plain Text Version]

We present a polynomial time algorithm for learning a large class of
algebraic models of computation. We show that any arithmetic circuit
whose partial derivatives induce a low-dimensional vector space is
exactly learnable from membership and equivalence queries. As a
consequence, we obtain polynomial-time algorithms for learning
restricted algebraic branching programs as well as noncommutative
set-multilinear arithmetic formulae. In addition, we observe that the
algorithms of Bergadano et al. (1996) and Beimel et al. (2000)
can be used to learn depth-3 set-multilinear
arithmetic circuits. Previously only versions of depth-2 arithmetic
circuits were known to be learnable in polynomial time. Our learning
algorithms can be viewed as solving a generalization of the well known
*polynomial interpolation problem* where the unknown polynomial
has a succinct representation. We can learn representations of
polynomials encoding *exponentially* many monomials. Our
techniques combine a careful algebraic analysis of the partial
derivatives of arithmetic circuits with “multiplicity automata”
learning algorithms due to Bergadano et al. (1997) and
Beimel et al. (2000).