Learning k-term monotone boolean formulae

Yoshifumi Sakai; Akira Maruoka

doi:10.1007/3-540-57369-0_39

Learning k-term monotone boolean formulae

Yoshifumi Sakai, Akira Maruoka

AGR - Agricultural Bioscience

Tohoku University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

5 Citations (Scopus)

Abstract

Valiant introduced a computational model of learning by examples, and gave a precise definition of learnability based on the model. Since then, much effort has been devoted to characterize learnable classes of concepts on this model. Among such learnable classes is the one, denoted k-term MDNF, consisting of monotone disjunctive normal form formulae with at most k terms. In literature, k-term MDNF is shown to be learnable under the assumption that examples are drawn according to the uniform distribution. In this paper we generalize the result to obtain the statement that k-term MDNF is learnable even if positive examples are drawn according to such distribution that the maximum of the ratio of the probabilities of two positive examples is bounded from above by some polynomial.

Original language	English
Title of host publication	Algorithmic Learning Theory - 3rd Workshop, ALT 1992, Proceedings
Editors	Shuji Doshita, Koichi Furukawa, Klaus P. Jantke, Toyaki Nishida
Publisher	Springer Verlag
Pages	197-207
Number of pages	11
ISBN (Print)	9783540573692
DOIs	https://doi.org/10.1007/3-540-57369-0_39
Publication status	Published - 1993
Event	3rd Workshop on Algorithmic Learning Theory, ALT 1992 - Tokyo, Japan Duration: 1992 Oct 20 → 1992 Oct 22

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	743 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	3rd Workshop on Algorithmic Learning Theory, ALT 1992
Country/Territory	Japan
City	Tokyo
Period	92/10/20 → 92/10/22

Access to Document

10.1007/3-540-57369-0_39

Cite this

Sakai, Y., & Maruoka, A. (1993). Learning k-term monotone boolean formulae. In S. Doshita, K. Furukawa, K. P. Jantke, & T. Nishida (Eds.), Algorithmic Learning Theory - 3rd Workshop, ALT 1992, Proceedings (pp. 197-207). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 743 LNAI). Springer Verlag. https://doi.org/10.1007/3-540-57369-0_39

Sakai, Yoshifumi ; Maruoka, Akira. / Learning k-term monotone boolean formulae. Algorithmic Learning Theory - 3rd Workshop, ALT 1992, Proceedings. editor / Shuji Doshita ; Koichi Furukawa ; Klaus P. Jantke ; Toyaki Nishida. Springer Verlag, 1993. pp. 197-207 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{c27807a85db64877a0ff5baeabf272b2,

title = "Learning k-term monotone boolean formulae",

abstract = "Valiant introduced a computational model of learning by examples, and gave a precise definition of learnability based on the model. Since then, much effort has been devoted to characterize learnable classes of concepts on this model. Among such learnable classes is the one, denoted k-term MDNF, consisting of monotone disjunctive normal form formulae with at most k terms. In literature, k-term MDNF is shown to be learnable under the assumption that examples are drawn according to the uniform distribution. In this paper we generalize the result to obtain the statement that k-term MDNF is learnable even if positive examples are drawn according to such distribution that the maximum of the ratio of the probabilities of two positive examples is bounded from above by some polynomial.",

author = "Yoshifumi Sakai and Akira Maruoka",

year = "1993",

doi = "10.1007/3-540-57369-0_39",

language = "English",

isbn = "9783540573692",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "197--207",

editor = "Shuji Doshita and Koichi Furukawa and Jantke, {Klaus P.} and Toyaki Nishida",

booktitle = "Algorithmic Learning Theory - 3rd Workshop, ALT 1992, Proceedings",

address = "Germany",

}

Sakai, Y & Maruoka, A 1993, Learning k-term monotone boolean formulae. in S Doshita, K Furukawa, KP Jantke & T Nishida (eds), Algorithmic Learning Theory - 3rd Workshop, ALT 1992, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 743 LNAI, Springer Verlag, pp. 197-207, 3rd Workshop on Algorithmic Learning Theory, ALT 1992, Tokyo, Japan, 92/10/20. https://doi.org/10.1007/3-540-57369-0_39

Learning k-term monotone boolean formulae. / Sakai, Yoshifumi; Maruoka, Akira.
Algorithmic Learning Theory - 3rd Workshop, ALT 1992, Proceedings. ed. / Shuji Doshita; Koichi Furukawa; Klaus P. Jantke; Toyaki Nishida. Springer Verlag, 1993. p. 197-207 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 743 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Learning k-term monotone boolean formulae

AU - Sakai, Yoshifumi

AU - Maruoka, Akira

PY - 1993

Y1 - 1993

N2 - Valiant introduced a computational model of learning by examples, and gave a precise definition of learnability based on the model. Since then, much effort has been devoted to characterize learnable classes of concepts on this model. Among such learnable classes is the one, denoted k-term MDNF, consisting of monotone disjunctive normal form formulae with at most k terms. In literature, k-term MDNF is shown to be learnable under the assumption that examples are drawn according to the uniform distribution. In this paper we generalize the result to obtain the statement that k-term MDNF is learnable even if positive examples are drawn according to such distribution that the maximum of the ratio of the probabilities of two positive examples is bounded from above by some polynomial.

AB - Valiant introduced a computational model of learning by examples, and gave a precise definition of learnability based on the model. Since then, much effort has been devoted to characterize learnable classes of concepts on this model. Among such learnable classes is the one, denoted k-term MDNF, consisting of monotone disjunctive normal form formulae with at most k terms. In literature, k-term MDNF is shown to be learnable under the assumption that examples are drawn according to the uniform distribution. In this paper we generalize the result to obtain the statement that k-term MDNF is learnable even if positive examples are drawn according to such distribution that the maximum of the ratio of the probabilities of two positive examples is bounded from above by some polynomial.

UR - http://www.scopus.com/inward/record.url?scp=84952051945&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84952051945&partnerID=8YFLogxK

U2 - 10.1007/3-540-57369-0_39

DO - 10.1007/3-540-57369-0_39

M3 - Conference contribution

AN - SCOPUS:84952051945

SN - 9783540573692

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 197

EP - 207

BT - Algorithmic Learning Theory - 3rd Workshop, ALT 1992, Proceedings

A2 - Doshita, Shuji

A2 - Furukawa, Koichi

A2 - Jantke, Klaus P.

A2 - Nishida, Toyaki

PB - Springer Verlag

T2 - 3rd Workshop on Algorithmic Learning Theory, ALT 1992

Y2 - 20 October 1992 through 22 October 1992

ER -

Sakai Y, Maruoka A. Learning k-term monotone boolean formulae. In Doshita S, Furukawa K, Jantke KP, Nishida T, editors, Algorithmic Learning Theory - 3rd Workshop, ALT 1992, Proceedings. Springer Verlag. 1993. p. 197-207. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-57369-0_39

Learning k-term monotone boolean formulae

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this