[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/1132516.1132600acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
Article

Learning a circuit by injecting values

Published: 21 May 2006 Publication History

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]
T. Akutsu, S. Kuhara, O. Maruyama, and S. Miyano. Identification of gene regulatory networks by strategic gene disruptions and gene overexpressions. In SODA '98: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 695--702, Philadelphia, PA, USA, 1998. Society for Industrial and Applied Mathematics.
[2]
D. Angluin, M. Frazier, and L. Pitt. Learning conjunctions of Horn clauses. Machine Learning, 9:147--164, 1992.
[3]
D. Angluin, L. Hellerstein, and M. Karpinski. Learning read-once formulas with queries. J. ACM, 40:185--210, 1993.
[4]
D. Angluin and M. Kharitonov. When won't membership queries help? J. Comput. Syst. Sci., 50(2):336--355, 1995.
[5]
N. H. Bshouty. Exact learning boolean functions via the monotone theory. Inf. Comput., 123(1):146--153, 1995.
[6]
H. Fujiwara. Logic Testing and Design for Testability. MIT Press, 1986.
[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]
J. C. Jackson. An efficient membership-query algorithm for learning DNF with respect to the uniform distribution. J. Comput. Syst. Sci., 55(3):414--440, 1997.
[9]
J. C. Jackson, A. R. Klivans, and R. A. Servedio. Learnability beyond AC0. In STOC '02: Proceedings of the thirty-fourth annual ACM symposium on Theory of computing, pages 776--784, New York, NY, USA, 2002. ACM Press.
[10]
M. Kearns and L. Valiant. Cryptographic limitations on learning boolean formulae and finite automata. J. ACM, 41(1):67--95, 1994.
[11]
M. Kharitonov. Cryptographic hardness of distribution-specific learning. In STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 372--381, New York, NY, USA, 1993. ACM Press.
[12]
N. Linial, Y. Mansour, and N. Nisan. Constant depth circuits, Fourier transform, and learnability. Journal of the ACM, 40(3):607--620, 1993.
[13]
J. Naor and M. Naor. Small-bias probability spaces: Efficient constructions and applications. In ACM Symposium on Theory of Computing, pages 213--223, 1990.
[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. Commun. ACM, 27:1134--1142, 1984.

Cited By

View all

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing
May 2006
786 pages
ISBN:1595931341
DOI:10.1145/1132516
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 May 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. circuit
  2. gene regulatory network
  3. learning

Qualifiers

  • Article

Conference

STOC06
Sponsor:
STOC06: Symposium on Theory of Computing
May 21 - 23, 2006
WA, Seattle, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25
57th Annual ACM Symposium on Theory of Computing (STOC 2025)
June 23 - 27, 2025
Prague , Czech Republic

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)3
  • Downloads (Last 6 weeks)0
Reflects downloads up to 25 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2012)Restriction accessProceedings of the 3rd Innovations in Theoretical Computer Science Conference10.1145/2090236.2090239(19-33)Online publication date: 8-Jan-2012
  • (2009)Completing networks using observed dataProceedings of the 20th international conference on Algorithmic learning theory10.5555/1813231.1813248(126-140)Online publication date: 3-Oct-2009
  • (2009)Completing Networks Using Observed DataAlgorithmic Learning Theory10.1007/978-3-642-04414-4_14(126-140)Online publication date: 2009
  • (2008)Learning large-alphabet and analog circuits with value injection queriesMachine Learning10.1007/s10994-008-5048-872:1-2(113-138)Online publication date: 21-Mar-2008
  • (2008)Optimally Learning Social Networks with Activations and SuppressionsProceedings of the 19th international conference on Algorithmic Learning Theory10.1007/978-3-540-87987-9_24(272-286)Online publication date: 12-Oct-2008
  • (2007)Learning Large-Alphabet and Analog Circuits with Value Injection QueriesLearning Theory10.1007/978-3-540-72927-3_6(51-65)Online publication date: 2007

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media