Please use this identifier to cite or link to this item: http://hdl.handle.net/1880/45747
Title: EXACT LEARNING VIA THE MONOTONE THEORY
Authors: Bshouty, Nader H.
Keywords: Computer Science
Issue Date: 1-Sep-1993
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.
URI: http://hdl.handle.net/1880/45747
Appears in Collections:Bshouty, Nader

Files in This Item:
File Description SizeFormat 
1993-522-27.pdf207.71 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.