ORACLES AND QUERIES THAT ARE SUFFICIENT FOR EXACT LEARNING

Simple item page
dc.contributor.authorBshouty, Nader H.eng
dc.contributor.authorCleve, Richardeng
dc.contributor.authorTamon, Christinoeng
dc.contributor.authorKannan, Sampatheng
dc.date.accessioned2008-02-27T16:49:27Z
dc.date.available2008-02-27T16:49:27Z
dc.date.computerscience1999-05-27eng
dc.date.issued1994-04-01eng
dc.description.abstractWe show that the class of all circuits is exactly learnable in (randomized) expected polynomial-time using subset and superset queries. Subset and superset queries are a generalization of equivalence queries, where an instance of a negative counterexample is requested (for subset queries) or a positive counterexample is requested (for superset queries). Our result is a consequence of the following result which we consider to be of independent interest: the class of all circuits is exactly learnable in (randomized) expected polynomial-time with equivalence queries and the aid of an NP-oracle. This improves the previous result of Gavald\o'a\(ga' [G93] where a $SIGMA~pile {p above 3 }$-oracle and equivalence queries are required in place of the NP-oracle and equvalence queries, and the learning algorithm is deterministic. The hypothesis class for both of the above learning algorithms is the class of circuits of slightly larger (polynomially related) size. Also, the algorithms can be adapted to learn the class of DNF formulas with hypothesis class consisting of depth-3 $andsign - orsign - andsign$ formulas (by the work of Angluin [A90], this is optimal in the sense that the hypothesis class cannot be reduced to depth-2 DNF formulas). We also found deterministic learning algorithms that use \fImembership\fR queries and the NP-oracle for learning monotone boolean functions and the class 0(log $n$)-DNF $cap$ 0(log $n$)-CNF. The running time of these algorithms are polynomial in $n$, DNF size and CNF size of the target formula. Finally with an NP-oracle and membership queries, there is a randomized polynomial-time algorithm that learns any class that is learnable from membership queries with unlimited computational power.eng
dc.description.notesWe are currently acquiring citations for the work deposited into this collection. We recognize the distribution rights of this item may have been assigned to another entity, other than the author(s) of the work.If you can provide the citation for this work or you think you own the distribution rights to this work please contact the Institutional Repository Administrator at digitize@ucalgary.caeng
dc.identifier.department1994-538-7eng
dc.identifier.doihttp://dx.doi.org/10.11575/PRISM/30487
dc.identifier.urihttp://hdl.handle.net/1880/45748
dc.language.isoEngeng
dc.publisher.corporateUniversity of Calgaryeng
dc.publisher.facultyScienceeng
dc.subjectComputer Scienceeng
dc.titleORACLES AND QUERIES THAT ARE SUFFICIENT FOR EXACT LEARNINGeng
dc.typeunknown
thesis.degree.disciplineComputer Scienceeng
Files
Original bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
1994-538-7.pdf
Size:
273.25 KB
Format:
Adobe Portable Document Format
Description:
Download
Thumbnail Image
Name:
1994-538-7.ps.gz
Size:
86.75 KB
Format:
Unknown data format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.86 KB
Format:
Plain Text
Description:
Download
Collections
Science Research & Publications