Learning Arithmetic Circuits via Partial Derivatives

摘要

We present a polynomial time algorithm for learning several models of algebraic 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 the first polynomial time algorithm for learning depth three multilinear arithmetic circuits. In addition, we give the first polynomial time algorithms for learning restricted algebraic branching programs and noncommutative arithmetic formulae. Previously only restricted 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 arithmetic circuits' partial derivatives with the "multiplicity automata" techniques due to Beimel et al [BBB+00].