ON LEARNING DECISION TREES WITH LARGE OUTPUT DOMAINS

Simple item page
dc.contributor.authorBshouty, N.eng
dc.contributor.authorTamon, C.eng
dc.contributor.authorWilson, D.eng
dc.date.accessioned2008-02-27T16:49:36Z
dc.date.available2008-02-27T16:49:36Z
dc.date.computerscience1999-05-27eng
dc.date.issued1995-05-01eng
dc.description.abstractFor two disjoint sets of variables, X and Y, and a class of functions C, we define DT(X,Y,C) to be the class of all decision trees over X whose leaves are functions from C over Y. We study the learnability of DT(X,Y,C) using membership and equivalence queries. Boolean decision trees, DT(X,$empty$,{0,1}), were shown to be exactly learnable in [Bs93] but does this imply the learnability of decision trees that have non-boolean leaves? A simple encoding of all possible leaf values will work provided that the size of C is reasonable. Our investigation involves several cases where simple encoding is not feasible, i.e., when | C | is large. We show how to learn decision trees whose leaves are learnable concepts belonging to a class C, DT(X,Y,C), when the separation between the variables X and Y is known. A simple algorithm for decision trees whose leaves are constants, DT(X,$empty$,C), is also presented. Each case above requires at least s separate executions of the algorithm from [Bs93] where s is the number of distinct leaves of the tree but we show that if C is a bounded lattice, DT(X,$empty$,C) is learnable using only one execution of this algorithm.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.department1995-567-19eng
dc.identifier.doihttp://dx.doi.org/10.11575/PRISM/30482
dc.identifier.urihttp://hdl.handle.net/1880/45750
dc.language.isoEngeng
dc.publisher.corporateUniversity of Calgaryeng
dc.publisher.facultyScienceeng
dc.subjectComputer Scienceeng
dc.titleON LEARNING DECISION TREES WITH LARGE OUTPUT DOMAINSeng
dc.typeunknown
thesis.degree.disciplineComputer Scienceeng
Files
Original bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
1995-567-19.pdf
Size:
253.86 KB
Format:
Adobe Portable Document Format
Description:
Download
Thumbnail Image
Name:
1995-567-19.ps.gz
Size:
91.71 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