# 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

Download@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},
}

Consolidated BibTeX file

Return to James Aspnes's publications

Return to James Aspnes's home page