Learning monotone log-term DNF formulas

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Learning monotone log-term DNF formulas

Full text

Pdf (716 KB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the seventh annual conference on Computational learning theory table of contents

New Brunswick, New Jersey, United States

Pages: 165 - 172

Year of Publication: 1994

ISBN:0-89791-655-7

Authors

Yoshifumi Sakai	Graduate School of Information Sciences, Tohoku University, Sendai 980-77, Japan
Akira Maruoka	Graduate School of Information Sciences, Tohoku University, Sendai 980-77, Japan

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 21, Citation Count: 3

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/180139.181095 What is a DOI?

ABSTRACT

Based on the uniform distribution PAC learning model, the learnability for monotone disjunctive normal form formulas with at most O(logn) terms (O(logn)-term MDNF) is investigated. Using the technique of restriction, an algorithm that learns O(logn)-term MDNF in polynomial time is given.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Michele Flammini , Alberto Marchetti-Spaccamela , Luděk Kučera, Learning DNF formulae under classes of probability distributions, Proceedings of the fifth annual workshop on Computational learning theory, p.85-92, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130395]
	2	Qian Ping Gu , Akira Maruoka, Learning monotone Boolean functions by uniformly distributed examples, SIAM Journal on Computing, v.21 n.3, p.587-599, June 1992 [doi>10.1137/0221037]
	3	M. Kearns , M. Li , L. Pitt , L. Valiant, On the learnability of Boolean formulae, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.285-295, January 1987, New York, New York, United States [doi>10.1145/28395.28426]
	4	Ludek Kucera , Alberto Marchetti-Spaccamela , Marco Protasi, On the Learnability of DNF Formulae, Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.347-361, July 11-15, 1988
	5	Takeshi Ohguro and Akira Maruoka, A learning algorithm for monotone k-term DNF, in Proceedings of FUJITSU IIAS-SIS Workshop on Computational Learning Theory, 1989.
	6	Leonard Pitt , Leslie G. Valiant, Computational limitations on learning from examples, Journal of the ACM (JACM), v.35 n.4, p.965-984, Oct. 1988 [doi>10.1145/48014.63140]
	7	Yoshifumi Sakai , Akira Maruoka, Learning k-Term Monotone Boolean Formulae, Proceedings of the Third Workshop on Algorithmic Learning Theory, p.197-207, October 20-22, 1992
	8	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]
	9	Karsten Verbeurgt, Learning DNF under the uniform distribution in quasi-polynomial time, Proceedings of the third annual workshop on Computational learning theory, p.314-326, August 06-08, 1990, Rochester, New York, United States

CITED BY 3

	Nader H. Bshouty, Simple learning algorithms using divide and conquer, Proceedings of the eighth annual conference on Computational learning theory, p.447-453, July 05-08, 1995, Santa Cruz, California, United States
	Nader H. Bshouty , Christino Tamon, On the Fourier spectrum of monotone functions, Journal of the ACM (JACM), v.43 n.4, p.747-770, July 1996
	Rocco A. Servedio, On learning monotone DNF under product distributions, Information and Computation, v.193 n.1, p.57-74, 25 August 2004