Abstract
We study the average-case learnability of DNF formulas in the model of learning from uniformly distributed random examples. We define a natural model of random monotone DNF formulas and give an efficient algorithm which with high probability can learn, for any fixed constant γ> 0, a random t-term monotone DNF for any t = O(n 2 − γ). We also define a model of random nonmonotone DNF and give an efficient algorithm which with high probability can learn a random t-term DNF for any t=O(n 3/2 − γ). These are the first known algorithms that can successfully learn a broad class of polynomial-size DNF in a reasonable average-case model of learning from random examples.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aizenstein, H., Pitt, L.: On the learnability of disjunctive normal form formulas. Machine Learning 19, 183–208 (1995)
Angluin, D.: Queries and concept learning. Machine Learning 2, 319–342 (1988)
Angluin, D., Kharitonov, M.: When won’t membership queries help? J. Comput. & Syst. Sci. 50, 336–355 (1995)
Blum, A.: Learning a function of r relevant variables (open problem). In: Schölkopf, B., Warmuth, M.K. (eds.) COLT/Kernel 2003. LNCS (LNAI), vol. 2777, pp. 731–733. Springer, Heidelberg (2003)
Blum, A.: Machine learning: a tour through some favorite results, directions, and open problems. FOCS 2003 tutorial slides (2003), available at http://www-2.cs.cmu.edu/~avrim/Talks/FOCS03/tutorial.ppt
Blum, A., Burch, C., Langford, J.: On learning monotone boolean functions. In: Proc. 39th FOCS, pp. 408–415 (1998)
Blum, A., Furst, M., Jackson, J., Kearns, M., Mansour, Y., Rudich, S.: Weakly learning DNF and characterizing statistical query learning using Fourier analysis. In: Proc. 26th STOC, pp. 253–262 (1994)
Bollobas, B.: Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability. Cambridge University Press, Cambridge (1986)
Golea, M., Marchand, M., Hancock, T.: On learning μ-perceptron networks on the uniform distribution. Neural Networks 9, 67–82 (1994)
Hancock, T.: Learning kμ decision trees on the uniform distribution. In: Proc. Sixth COLT, pp. 352–360 (1993)
Jackson, J.: An efficient membership-query algorithm for learning DNF with respect to the uniform distribution. J. Comput. & Syst. Sci. 55, 414–440 (1997)
Jackson, J., Klivans, A., Servedio, R.: Learnability beyond ACo. In: Proc. 34th STOC (2002)
Jackson, J., Servedio, R.: Learning random log-depth decision trees under the uniform distribution. In: Schölkopf, B., Warmuth, M.K. (eds.) COLT/Kernel 2003. LNCS (LNAI), vol. 2777, pp. 610–624. Springer, Heidelberg (2003)
Jackson, J., Tamon, C.: Fourier analysis in machine learning. ICML/COLT 1997 tutorial slides (1997), available at http://learningtheory.org/resources.html
Kearns, M.: Efficient noise-tolerant learning from statistical queries. Journal of the ACM 45(6), 983–1006 (1998)
Kearns, M., Li, M., Pitt, L., Valiant, L.: Recent results on Boolean concept learning. In: Proc. Fourth Int. Workshop on Mach. Learning, pp. 337–352 (1987)
Kearns, M., Vazirani, U.: An Introduction to Computational Learning Theory. MIT Press, Cambridge (1994)
Klivans, A., O’Donnell, R., Servedio, R.: Learning intersections and thresholds of halfspaces. In: Proc. 43rd FOCS, pp. 177–186 (2002)
Kucera, L., Marchetti-Spaccamela, A., Protassi, M.: On learning monotone DNF formulae under uniform distributions. Inform. and Comput. 110, 84–95 (1994)
McDiarmid, C.: On the method of bounded differences. In: Surveys in Combinatoric 1989. London Mathematical Society Lecture Notes, pp. 148–188 (1989)
Servedio, R.: On learning monotone DNF under product distributions. In: Helmbold, D.P., Williamson, B. (eds.) COLT 2001 and EuroCOLT 2001. LNCS (LNAI), vol. 2111, pp. 473–489. Springer, Heidelberg (2001)
Valiant, L.: A theory of the learnable. CACM 27(11), 1134–1142 (1984)
Verbeurgt, K.: Learning DNF under the uniform distribution in quasi-polynomial time. In: Proc. Third COLT, pp. 314–326 (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jackson, J.C., Servedio, R.A. (2005). On Learning Random DNF Formulas Under the Uniform Distribution. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds) Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2005 2005. Lecture Notes in Computer Science, vol 3624. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11538462_29
Download citation
DOI: https://doi.org/10.1007/11538462_29
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28239-6
Online ISBN: 978-3-540-31874-3
eBook Packages: Computer ScienceComputer Science (R0)