Learning Matrix Functions over Rings

Let R be a commutative Artinian ring with identity and let X be a finite subset of R . We present an exact learning algorithm with a polynomial query complexity for the class of functions representable as f(x) = Π _i=1 ⁿ A _i (x _i ), where, for each 1 ≤ i ≤ n , A _i is a mapping A _i : X → R ^{mi× mi+1} and m ₁ = m _n+1 = 1 . We show that the above algorithm implies the following results: 1. Multivariate polynomials over a finite commutative ring with identity are learnable using equivalence and substitution queries. 2. Bounded degree multivariate polynomials over Z _n can be interpolated using substitution queries. 3. The class of constant depth circuits that consist of bounded fan-in MOD gates, where the modulus are prime powers of some fixed prime, is learnable using equivalence and substitution queries. Our approach uses a decision tree representation for the hypothesis class which takes advantage of linear dependencies. This paper generalizes the learning algorithm for automata over fields given in [BBB+]. Received January 28, 1997; revised May 29, 1997, June 18, 1997, and June 26, 1997.