Learning Monotone DNF from a Teacher that Almost Does Not Answer Membership Queries.

Saved in:

Bibliographic Details
Title:	Learning Monotone DNF from a Teacher that Almost Does Not Answer Membership Queries.
Authors:	Bshouty, Nader H., Eiron, Nadav
Source:	Journal of Machine Learning Research. Winter2003, Vol. 3 Issue 1, p49. 9p.
Subjects:	Algorithms, Mathematical models of learning
Abstract:	We present results concerning the learning of Monotone DNF (MDNF) from Incomplete Membership Queries and Equivalence Queries. Our main result is a new algorithm that allows efficient learning of MDNF using Equivalence Queries and Incomplete Membership Queries with probability of p = 1 - 1/poly(n; t) of failing. Our algorithm is expected to make This text does not convert into ASCII.txt queries, when learning a MDNF formula with t terms over n variables. Note that this is polynomial for any failure probability p = 1 - 1/poly(n; t). The algorithm's running time is also polynomial in t; n; and 1/(1 - p). In a sense this is the best possible, as learning with p = 1 - 1/ω(poly(n; t)) would imply learning MDNF, and thus also DNF, from equivalence queries alone. [ABSTRACT FROM AUTHOR]
	Copyright of Journal of Machine Learning Research is the property of Microtome Publishing and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database:	Engineering Source

Description
Abstract:	We present results concerning the learning of Monotone DNF (MDNF) from Incomplete Membership Queries and Equivalence Queries. Our main result is a new algorithm that allows efficient learning of MDNF using Equivalence Queries and Incomplete Membership Queries with probability of p = 1 - 1/poly(n; t) of failing. Our algorithm is expected to make This text does not convert into ASCII.txt queries, when learning a MDNF formula with t terms over n variables. Note that this is polynomial for any failure probability p = 1 - 1/poly(n; t). The algorithm's running time is also polynomial in t; n; and 1/(1 - p). In a sense this is the best possible, as learning with p = 1 - 1/ω(poly(n; t)) would imply learning MDNF, and thus also DNF, from equivalence queries alone. [ABSTRACT FROM AUTHOR]
ISSN:	15324435