Learning a circuit by injecting values

ABSTRACT

We propose a new model for exact learning of acyclic circuits using experiments in which chosen values may be assigned to an arbitrary subset of wires internal to the circuit, but only the value of the circuit's single output wire may be observed. We give polynomial time algorithms to learn (1) arbitrary circuits with logarithmic depth and constant fan-in and (2) Boolean circuits of constant depth and unbounded fan-in over AND, OR, and NOT gates. Thus, both AC0 and NC1 circuits are learnable in polynomial time in this model. Negative results show that some restrictions on depth, fan-in and gate types are necessary: exponentially many experiments are required to learn AND/OR circuits of unbounded depth and fan-in; it is NP-hard to learn AND/OR circuits of unbounded depth and fan-in 2; and it is NP-hard to learn circuits of bounded depth and unbounded fan-in over AND, OR, and threshold gates, even when the target circuit is known to contain at most one threshold gate and that threshold gate has threshold 2. We also consider the effect of adding an oracle for behavioral equivalence. In this case there are polynomial-time algorithms to learn arbitrary circuits of constant fan-in and unbounded depth and to learn Boolean circuits with arbitrary fan-in and unbounded depth over AND, OR, and NOT gates. A corollary is that these two classes are PAC-learnable if experiments are available.

REFERENCES

• 1: Tatsuya Akutsu , Satoru Kuhara , Osamu Maruyama , Satoru Miyano, Identification of gene regulatory networks by strategic gene disruptions and gene overexpressions, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.695-702, January 25-27, 1998, San Francisco, California, United States
• 2: Dana Angluin , Michael Frazier , Leonard Pitt, Learning Conjunctions of Horn Clauses, Machine Learning, v.9 n.2-3, p.147-164, July 1992 [doi>10.1007/BF00992675]
• 3: Dana Angluin , Lisa Hellerstein , Marek Karpinski, Learning read-once formulas with queries, Journal of the ACM (JACM), v.40 n.1, p.185-210, Jan. 1993 [doi>10.1145/138027.138061]
• 4: Dana Angluin , Michael Kharitonov, When won't membership queries help?, Journal of Computer and System Sciences, v.50 n.2, p.336-355, April 1995
• 5: Nader H. Bshouty, Exact learning Boolean functions via the monotone theory, Information and Computation, v.123 n.1, p.146-153, Nov. 15, 1995 [doi>10.1006/inco.1995.1164]
• 6: Hideo Fujiwara, Logic testing and design for testability, MIT Press, Cambridge, MA, 1985
• 7: T. Ideker, V. Thorsson, and R. Karp. Discovery of regulatory interactions through perturbation: Inference and experimental design. In Pacific Symposium on Biocomputing 5, pages 302--313, 2000.
• 8: Jeffrey C. Jackson, An efficient membership-query algorithm for learning DNF with respect to the uniform distribution, Journal of Computer and System Sciences, v.55 n.3, p.414-440, Dec. 1997 [doi>10.1006/jcss.1997.1533]
• 9: Jeffrey C. Jackson , Adam R. Klivans , Rocco A. Servedio, Learnability beyond AC⁰, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510018]
• 10: Michael Kearns , Leslie Valiant, Cryptographic limitations on learning Boolean formulae and finite automata, Journal of the ACM (JACM), v.41 n.1, p.67-95, Jan. 1994 [doi>10.1145/174644.174647]
• 11: Michael Kharitonov, Cryptographic hardness of distribution-specific learning, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.372-381, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167197]
• 12: Nathan Linial , Yishay Mansour , Noam Nisan, Constant depth circuits, Fourier transform, and learnability, Journal of the ACM (JACM), v.40 n.3, p.607-620, July 1993 [doi>10.1145/174130.174138]
• 13: J. Naor , M. Naor, Small-bias probability spaces: efficient constructions and applications, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.213-223, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100244]
• 14: G. Seroussi and N. H. Bshouty. Vector sets for exhaustive testings of logic circuits. In IEEE Transactions on Information Theory, volume 34, pages 513--522, May 1988.
• 15: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation

General Terms:
Algorithms, Theory

Keywords:
circuit, gene regulatory network, learning