Article On learning in the presence of unspecified attribute values Share on Authors: Nader H. Bshouty Department of Computer Science, University of Calgary, 2500 University Dr. N.W., Calgary, AB, Canada T2N 1N4 Department of Computer Science, University of Calgary, 2500 University Dr. N.W., Calgary, AB, Canada T2N 1N4View Profile , David K. Wilson Department of Computer Science, University of Calgary, 2500 University Dr. N.W., Calgary, AB, Canada T2N 1N4 Department of Computer Science, University of Calgary, 2500 University Dr. N.W., Calgary, AB, Canada T2N 1N4View Profile Authors Info & Claims COLT '99: Proceedings of the twelfth annual conference on Computational learning theoryJuly 1999 Pages 81–87https://doi.org/10.1145/307400.307415Published:06 July 1999 2citation198DownloadsMetricsTotal Citations2Total Downloads198Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Nader H. Bshouty Christino Tamon David K. Wilson Department of Computer Science The University of Calgary 2500 University Drive NW Calgary, Alberta, Canada T2N 1N4 e-mail:fbshouty, tamon, [email protected] Abstract We prove that strict width two branching programs or SW 2 (which are width two branching programs with exactly two sinks, as defined in [BDFP86]) are properly PAC learnable under any distribution. We also observe that PAC learning monotone width two branching programs (which are width two branching programs with exactly one rejecting sink) is as hard as learning DNF formulae. This work refines both the positive and negative results in [ERR95] and answers one of the open questions in that paper. 1 Introduction Many interesting results have been found due to the study of branching programs most notably by Barrington [B89] who demonstrated that a very restricted form (width five) can accept all languages contained in NC 1 . A branching program is a...

For two disjoint sets of variables, X and l', and a class of functions (', 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 ,aud equivalence queries.Boolean decision trees, LIT(.Y, @, {O, 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 atl 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 ICl is large, We show how to learn decision trees whose leaves