Access Restriction

Author Angluin, Dana ♦ Aspnes, James ♦ Chen, Jiang ♦ Reyzin, Lev
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Alphabet Size ♦ Time Polynomial ♦ Acyclic Discrete Circuit ♦ Value Injection Query ♦ Analog Circuit ♦ Algorithm Use Value Injection Query ♦ Target Circuit ♦ Behavioral Equivalence Query ♦ Learning Algorithm ♦ Approximate Learning ♦ Gate Function ♦ General Class ♦ Learning Problem ♦ Distinguishing Path Algorithm ♦ Shortcut Width ♦ Polynomial Time ♦ Lipschitz Condition
Description 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 then apply our largealphabet learning algorithms to the problem of approximate learning of analog circuits whose gate functions satisfy a Lipschitz condition. Finally, we consider models in which behavioral equivalence queries are also available, and extend and improve the learning algorithms of [7] to handle general classes of gate functions that are polynomial time learnable from counterexamples.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2007-01-01
Publisher Institution In Twentieth Annual Conference on Learning Theory