Theory of Computing
-------------------
Title : Learning Restricted Models of Arithmetic Circuits
Authors : Adam Klivans and Amir Shpilka
Volume : 2
Number : 10
Pages : 185-206
URL : https://theoryofcomputing.org/articles/v002a010
Abstract
--------
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).