Learning large-alphabet and analog circuits with value injection queries

Dana Angluin, James Aspnes, Jiang Chen, and Lev Reyzin. Learning large-alphabet and analog circuits with value injection queries. Machine Learning 72(1–2):113–138, August 2008 (COLT 2007 special issue). An earlier version appeared in Twentieth Annual Conference on Learning Theory, June 2007, pp. 51–65. Winner, Best Student Paper award.

Abstract

We consider the problem of learning an acyclic discrete circuit with n wires, fan-in bounded by k and alphabet size s using value injection queries. For the class of transitively reduced circuits, we develop the Distinguishing Paths Algorithm, that learns such a circuit using (ns)^O(k) value injection queries and time polynomial in the number of queries. We describe a generalization of the algorithm to the class of circuits with shortcut width bounded by b that uses (ns)^O(k+b) value injection queries. Both algorithms use value injection queries that fix only O(kd) wires, where d is the depth of the target circuit. We give a reduction showing that without such restrictions on the topology of the circuit, the learning problem may be computationally intractable when s = n^Θ(1), even for circuits of depth O(log n). We apply our large-alphabet learning algorithms to the problem of approximate learning of analog circuits and show that analog circuits with constant bounded fan-in, logarithmic depth, and constant bounded shortcut width whose gate functions satisfy a Lipschitz condition are approximately learnable in polynomial time using value injection queries. Finally, we consider models in which behavioral equivalence queries are also available, and extend and improve the learning algorithms of (Angluin et al., 2006) to handle general classes of gates functions that are polynomial time learnable from counterexamples.

• COLT 2007 proceedings version: PDF.
• Journal version: PDF.

BibTeX

@article{AngluinACR2008,
author = {Dana Angluin and James Aspnes and Jiang Chen and Lev Reyzin},
title = {Learning large-alphabet and analog circuits with value injection queries},
journal   = {Machine Learning},
volume    = {72},
number    = {1-2},
month     = aug,
year      = {2008},
pages     = {113-138},
}