EXACT LEARNING VIA THE MONOTONE THEORY
| dc.contributor.author | Bshouty, Nader H. | eng |
| dc.date.accessioned | 2008-02-27T16:49:22Z | |
| dc.date.available | 2008-02-27T16:49:22Z | |
| dc.date.computerscience | 1999-05-27 | eng |
| dc.date.issued | 1993-09-01 | eng |
| dc.description.abstract | We study the learnability of concept classes from membership and equivalence queries. Using the partial order theory we develop the Monotone theory that gives new techniques for learning concepts over different domains. Applying the monotone theory to boolean functions we show that 1) Any boolean function is learnable as decision tree. 2) Any boolean function is either learnable as DNF or as CNF (or both). The first result solves the open problem of the learnability of decision trees and the second result gives more evidence that DNFs are not "very hard" to learn. The Monotone theory is based on the theory of partially ordered sets. Given a subclass of all isomorphic partial orders on a set $X$, we define the DNF, CNF and decision tree representations and specify conditions for which 1-2 are true. We show that under different choices of the set $X$, the partial order ($X,<=$), and the set of isomorphisms, we were able to find various learning algorithms for concepts with different representation. As an example, using the Hamming partial order over an abelian group with the set of all linear isomorphisms we show that decision trees over any alphabet $ SIGMA $ is learnable and any function $ f : SIGMA sup n -> SIGMA$ is learnable as a decision tree. | eng |
| dc.description.notes | We 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.ca | eng |
| dc.identifier.department | 1993-522-27 | eng |
| dc.identifier.doi | http://dx.doi.org/10.11575/PRISM/30477 | |
| dc.identifier.uri | http://hdl.handle.net/1880/45747 | |
| dc.language.iso | Eng | eng |
| dc.publisher.corporate | University of Calgary | eng |
| dc.publisher.faculty | Science | eng |
| dc.subject | Computer Science | eng |
| dc.title | EXACT LEARNING VIA THE MONOTONE THEORY | eng |
| dc.type | unknown | |
| thesis.degree.discipline | Computer Science | eng |
Files
License bundle
1 - 1 of 1