article

Exact learning of DNF formulas using DNF hypotheses

Authors:

Lisa Hellerstein,

Vijay RaghavanAuthors Info & Claims

Journal of Computer and System Sciences, Volume 70, Issue 4

Pages 435 - 470

https://doi.org/10.1016/j.jcss.2004.10.001

Published: 01 June 2005 Publication History

Abstract

We show the following: (a) For any @e>0, log^(^3^+^@e^)n-term DNF cannot be polynomial-query learned with membership and strongly proper equivalence queries. (b) For sufficiently large t, t-term DNF formulas cannot be polynomial-query learned with membership and equivalence queries that use t^1^+^@e-term DNF formulas as hypotheses, for some @e<1 (c) Read-thrice DNF formulas are not polynomial-query learnable with membership and proper equivalence queries. (d) logn-term DNF formulas can be polynomial-query learned with membership and proper equivalence queries. (This complements a result of Bshouty, Goldman, Hancock, and Matar that logn-term DNF can be so learned in polynomial time.) Versions of (a)-(c) were known previously, but the previous versions applied to polynomial-time learning and used complexity theoretic assumptions. In contrast, (a)-(c) apply to polynomial-query learning, imply the results for polynomial-time learning, and do not use any complexity-theoretic assumptions.

References

[1]

{1} A. Aizenstein, T. Hegedus, L. Hellerstein, L. Pitt, Complexity theoretic hardness results for query learning, Comput. Complexity 7 (1) (1998) 19-53.]]

Digital Library

[2]

{2} D. Angluin, Queries and concept learning, Mach. Learning 2 (4) (1988) 319-342.]]

Digital Library

[3]

{3} D. Angluin, M. Kharitonov, When won't membership queries help?, J. Comput. System Sci. 50 (2) (1995) 336-355

Digital Library

[4]

{4} A. Beimel, F. Bergadano, N.H. Bshouty, E. Kushilevitz, S. Varricchio, On the applications of multiplicity automata in learning, in: IEEE Symposium on Foundations of Computer Science, 1996, pp. 349-358.]]

Digital Library

[5]

{5} U. Berggren, Linear time deterministic learning of k-term DNE in: Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, ACM Press, New York, 1993, pp. 37-40.]]

Digital Library

[6]

{6} A. Blum, Separating distribution-free and mistake-bound learning models over the Boolean domain, SIAM J. Comput. 23 (5) (1994) 990-1000.]]

Digital Library

[7]

{7} A. Blum, M. Furst, J. Jackson, M. Kearns, Y. Mansour, S. Rudich, Weakly learning DNF and characterizing statistical query learning using Fourier analysis, in: Proceedings of 26th ACM Symposium on Theory of Computing, 1994.]]

Digital Library

[8]

{8} A. Blum, S. Rudich, Fast learning of k-term DNF formulas with queries, J. Comput. System Sci. 51 (3) (1995) 367-373 1995.1075.]]

Digital Library

[9]

{9} N.H. Bshouty, Exact learning via the monotone theory, Inform. Comput. 123 (1) (1995) 146-153.]]

Digital Library

[10]

{10} N.H. Bshouty, A subexponential exact learning algorithm for DNF using equivalence queries, Inform. Process. Lett. 59 (1) (1996) 37-39.]]

Digital Library

[11]

{11} N.H. Bshouty, Simple learning algorithms using divide and conquer, Comput. Complexity 6 (1997) 174-194.]]

Digital Library

[12]

{12} N.H. Bshouty, Personal communication, 5 November 2003.]]

[13]

{13} N.H. Bshouty, L. Burroughs, On the proper learning of axis parallel concepts, J. Machine Learning Research 4 (Jun) (2003) 157-176.]]

Digital Library

[14]

{14} N.H. Bshouty, S.A. Goldman, T.R. Hancock, S. Matar, Asking questions to minimize errors, J. Comput. System Sci. 52 (2) (1996) 268-286

Digital Library

[15]

{15} A. Chandra, G. Markowsky, On the number of prime implicants, Discrete Math. 24 (1978) 7-11.]]

Digital Library

[16]

{16} O. Ekin, S. Foldes, E Hammer, L. Hellerstein, Equational theories of Boolean functions, Discrete Math. 211 (2000) 27-51.]]

Digital Library

[17]

{17} T. Hegedus, Generalized teaching dimensions and the query complexity of learning, in: Proceedings of the Eighth Annual Conference on Computational Learning Theory (COLT'95), ACM Press, New York, 1995, pp. 108-117.]]

Digital Library

[18]

{18} L. Hellerstein, On generalized constraints and certificates, Discrete Math. 226 (1-3) (2001) 211-232.]]

Digital Library

[19]

{19} L. Hellerstein, K. Pillaipakkamnatt, V. Raghavan, D. Wilkins, How many queries are needed to learn?, J. ACM 43 (5) (1996) 840-862.]]

Digital Library

[20]

{20} L. Hellerstein, V. Raghavan, Exact learning of DNF formulas using DNF hypotheses, in: Proceedings of the 34th Annual Symposium on Theory of Computing (STOC), 2002, pp. 465-473.]]

Digital Library

[21]

{21} J.C. Jackson, An efficient membership-query algorithm for learning DNF with respect to the uniform distribution, J. Comput. System Sci. 55 (3) (1997) 414-440

Digital Library

[22]

{22} A. Klivans, R. Servedio, Learning DNF in time 2o(n1/3), in: Proceedings of the 33rd Annual Symposium on Theory of Computing (STOC), 2001.]]

Digital Library

[23]

{23} J. Kobler, W. Lindner, Oracles in ΣP2 are sufficient for exact learning, in: Proceedings of the Eighth International Workshop on Algorithmic Learning Theory (ALT), 1997, pp. 277-290.]]

Digital Library

[24]

{24} E. Kushilevitz, A simple algorithm for learning o(log n)-term DNF, Inform. Process. Lett. 61 (6) (1997) 289-292.]]

Digital Library

[25]

{25} N. Linial, Y. Mansour, N. Nisan, Constant depth circuits, Fourier transform and learnability, J. ACM 40 (3) (1993) 607-620.]]

Digital Library

[26]

{26} W.J. Masek, Some NP-complete set covering problems, unpublished manuscript, 1979.]]

[27]

{27} D.E. Muller, F.P. Preparata, Bounds to complexities of networks for sorting and for switching, J. ACM 22 (1975) 195-201.]]

Digital Library

[28]

{28} M. Naor, L.J. Schulman, A. Srinivasan, Splitters and near-optimal derandomization, in: IEEE Symposium on Foundations of Computer Science, 1995, pp. 182-191.]]

Digital Library

[29]

{29} C.H. Papadimitriou, Computational Complexity, Addison-Wesley, Reading, MA, 1994.]]

[30]

{30} C.H. Papadimitriou, M. Yannakakis, On limited nondeterminism and the complexity of the VC-dimension, J. Comput. System Sci. 53 (2) (1996) 161-170.]]

Digital Library

[31]

{31} K. Pillaipakkamnatt, V. Raghavan, On the limits of proper learnability of subclasses of DNF formulas, Mach. Learning 25 (2-3) (1996) 237-263.]]

Digital Library

[32]

{32} N. Pippenger, Galois theory for minors of finite functions, Discrete Math. 254 (2002) 405-419.]]

[33]

{33} J. Tarui, T. Tsukiji, Learning DNF by approximating inclusion-exclusion formulae, in: Proceedings of the IEEE Conference on Computational Complexity, 1999, pp. 215-220.]]

Digital Library

[34]

{34} C. Umas, The minimum equivalent DNF problem and shortest implicants, in: IEEE Symposium on Foundations of Computer Science, 1998, pp. 556-563.]]

Digital Library

[35]

{35} C. Umas, Hardness of approximating Σp2 minimization problems, in: Proceedings of IEEE Symposium on Foundations of Computer Science, 1999, pp. 465-474.]]

Digital Library

Cited By

Ding N(2019)On Exactly Learning Disjunctions and DNFs Without Equivalence QueriesComputing and Combinatorics10.1007/978-3-030-26176-4_13(153-165)Online publication date: 29-Jul-2019
https://dl.acm.org/doi/10.1007/978-3-030-26176-4_13
Becker BEhlers RLewis MMarin P(2012)ALLQBF solving by computational learningProceedings of the 10th international conference on Automated Technology for Verification and Analysis10.1007/978-3-642-33386-6_29(370-384)Online publication date: 3-Oct-2012
https://dl.acm.org/doi/10.1007/978-3-642-33386-6_29
Dachman-Soled DServedio R(2011)A canonical form for testing boolean function propertiesProceedings of the 14th international workshop and 15th international conference on Approximation, randomization, and combinatorial optimization: algorithms and techniques10.5555/2033252.2033293(460-471)Online publication date: 17-Aug-2011
https://dl.acm.org/doi/10.5555/2033252.2033293
Show More Cited By

Index Terms

Exact learning of DNF formulas using DNF hypotheses
1. Computing methodologies
  1. Machine learning
2. Theory of computation
  1. Computational complexity and cryptography
    1. Interactive proof systems
    2. Proof complexity
  2. Logic
    1. Proof theory

Recommendations

Exact learning of DNF formulas using DNF hypotheses
STOC '02: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing
(MATH) We show the following:
- For any ε < 0, (log n)(3 + ε)-term DNF cannot be polynomial-query learned with membership and strongly proper equivalence queries.
- For any function f(n) ε o [box] (/frac√n \over log n) [end-box] , m-term DNF formulas ...
Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds
13th International Workshop on Randomization and Computation Random 09

The area of derandomization attempts to provide efficient deterministic simulations of randomized algorithms in various algorithmic settings. Goldreich and Wigderson introduced a notion of “typically-correct” deterministic simulations, which are allowed ...
Pseudorandomness for read-k DNF formulas
SODA '19: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms

The design of pseudorandom generators and deterministic approximate counting algorithms for DNF formulas are important challenges in unconditional derandomization. Numerous works on these problems have focused on the subclass of small-read DNF formulas, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Computer and System Sciences

Journal of Computer and System Sciences Volume 70, Issue 4

Special issue on COLT 2002

June 2005

164 pages

ISSN:0022-0000

Issue’s Table of Contents

Copyright © Elsevier Inc. © 2004.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 June 2005

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ding N(2019)On Exactly Learning Disjunctions and DNFs Without Equivalence QueriesComputing and Combinatorics10.1007/978-3-030-26176-4_13(153-165)Online publication date: 29-Jul-2019
https://dl.acm.org/doi/10.1007/978-3-030-26176-4_13
Becker BEhlers RLewis MMarin P(2012)ALLQBF solving by computational learningProceedings of the 10th international conference on Automated Technology for Verification and Analysis10.1007/978-3-642-33386-6_29(370-384)Online publication date: 3-Oct-2012
https://dl.acm.org/doi/10.1007/978-3-642-33386-6_29
Dachman-Soled DServedio R(2011)A canonical form for testing boolean function propertiesProceedings of the 14th international workshop and 15th international conference on Approximation, randomization, and combinatorial optimization: algorithms and techniques10.5555/2033252.2033293(460-471)Online publication date: 17-Aug-2011
https://dl.acm.org/doi/10.5555/2033252.2033293
Hoory SMargalit O(2008)Finding the Rare CubeProceedings of the 19th international conference on Algorithmic Learning Theory10.1007/978-3-540-87987-9_29(344-358)Online publication date: 12-Oct-2008
https://dl.acm.org/doi/10.1007/978-3-540-87987-9_29

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents