##
This **preview** shows page *1-2-3-4-5*
out of 15 **pages**.

*View Full Document*

End of preview. Want to read all 15 pages?

Upload your study docs or become a GradeBuddy member to access this document.

View Full Document**Unformatted text preview:**

Learning Large-Alphabet and Analog Circuitswith Value Injection QueriesDana Angluin1, James Aspnes1,⋆, Jiang Chen2,⋆⋆, and Lev Reyzin1,⋆ ⋆ ⋆1Computer Science Department, Yale University{angluin,aspnes}@cs.yale.edu, [email protected] for Computational Learning Systems, Columbia [email protected] We consider the problem of learning an acyclic discrete cir-cuit with n wires, fan-in bounded by k and alphabet size s using valueinjection queries. For the class of transitively reduced circuits, we de-velop the Distinguishing Paths Algorithm, that learns such a circuit us-ing (ns)O(k)value injection queries and time polynomial in the numberof queries. We describe a generalization of the algorithm to the class ofcircuits with shortcut width bounded by b that uses (ns)O(k+b)valueinjection queries. Both algorithms use value injection queries that fi xonly O(kd) wires, where d is the dep th of the target circuit. We give areduction showing that without such restrictions on the topology of thecircuit, the learning problem may be computationally intractable whens = nΘ(1), even for circuits of dept h O(log n). We then apply our large-alphabet learning algorithms to the problem of approximate learning ofanalog circuits whose gate functions satisfy a Lipschitz condition. Fi-nally, we consider models in which behavioral equivalence queries arealso available, and extend and improve the learning algorithms of [5]to h andle general classes of gates functions that are polynomial t imelearnable from counterexamples.1 IntroductionWe consider learning large-alphab e t and analo g acyclic circuits in the valueinjection model introduced in [5]. In this model, we may inject values of ourchoice on any subset of wires, but we can only observe the one output of thecircuit. However, the value injection query algorithms in that paper for booleanand constant alphabet networks do not lift to the case when the s iz e of thealphabet is polynomial in the size of the circuit.One motivation for studying the boolean network model includes gene reg-ulatory networks. In a boolean model, each node in a gene regulatory networkcan represent a gene whose state is either active or inactive. However, genes mayhave a large number of states of activity. Co ns tant-alphabet network models⋆Supported in part by NSF grant CNS-0435201.⋆⋆Supported in part by a research contract from Consolidated Edison.⋆ ⋆ ⋆Supported by a Yahoo! Research Kern Family Scholarship.may not adequately capture the information present in these networks, whichmotivates our interest in larger alphabets.Akutsu et al. [2] and Ideker, Thorsson, and Karp [9 ] consider the discoveryproblem that models the experimental capability of gene disruption and over-expression. In such ex periments, it is desirable to manipulate as few genes aspossible. In the particular models considered in these papers, node states arefully observable – the ge ne expressio n data gives the state of every node in thenetwork at every time step. Their results show that in this model, for boundedfan-in or sufficiently restricted g e ne functions, the problem of learning the struc-ture of a network is tractable.In contrast, there is a mple evidence that learning boolean circuits solelyfrom input-output behaviors may be computationally intractable. Kearns andValiant [12] show that specific c ryptographic assumptions imply that NC1 cir-cuits and TC0 circuits are not PAC learnable in po lynomial time. These negativeresults have been strengthened to the setting of PAC learning with membershipqueries [6], even with respect to the uniform distribution [13]. Furthermore,positive learnability r esults exist o nly for fairly limited classes, including pro po -sitional Horn formulas [3], general read once Boolean formulas [4 ], and decisiontrees [7], and those for specific dis tributions, including AC0 circuits [14], DNFformulas [10], and AC0 cir c uits with a limited number of majority gates [11].3Thus, Angluin et al. [5] look at the relative contributions of full observationand full control of learning boolean networks. Their model of value injectionallows full control and restricted observation, and it is the model we study inthis paper. Interestingly, their results show that this model gives the learnerconsiderably more power than with only input-output behaviors but less thanthe power with full observation. In particular, they show that with value injectionqueries, NC1 circuits and AC0 circuits are exa c tly learnable in polynomial time,but their negative results show that depth limitations are necessary.A second motivation behind our work is to study the rela tive importance o fthe parameters of the models for learnability results. The impact of alphabetsize on learnability beco mes a natural point of inquiry, and ideas from fixedparameter tractability are very relevant [8, 15].2 Preliminaries2.1 CircuitsWe give a general definition of acyclic circuits whose w ires carry values from a se tΣ. For each nonnegative integer k, a gate function of arity k is a function fromΣkto Σ. A circuit C consists of a finite set of wires w1, . . . , wn, and for eachwire wi, a gate function giof arity kiand an ordered ki-tuple wσ(i,1), . . . , wσ(i,ki)of wires, the inputs of wi. We define wnto be the output wire of the circuit.We may think of wires as outputs of gates in C.3Algorithms in both [14] and [11] for learning AC0 circuits and their variants ru n inquasi-polynomial time.The unpruned graph of a circuit C is the directed graph whos e verticesare the wires and whose edges are pa irs (wi, wj) such that wiis an input of wjinC. A wire wiis output-connected if there is a dir ected path in the unprunedgraph from that wire to the output wire. Wires that are not output-connectedcannot a ffect the output value of a circuit. The graph of a circuit C is thesubgraph of its unpruned graph induced by the output-connected wires.A circuit is acyclic if its graph is acyclic. In this paper we consider onlyacyclic circuits. If u and v are vertices such that u 6= v and there is a directedpath from u to v, then we say that u is an ancestor of v and that v is adescendant of u. T he depth of an output-connected wire wiis the length ofa longest path from wito the output wire wn. The depth of a circuit is themaximum depth of any output-connected wire in the circuit. A wire with noinputs is an input wire; its default value is given by its gate function, whichhas arity 0