Efficiently Learning Monotone Decision Trees with ID3

<p>Since the Probably Approximately Correct learning model was introduced in 1984, there has been much effort in designing computationally efficient algorithms for learning Boolean functions from random examples drawn from a uniform distribution. In this paper, I take the ID3 information-gain-first classification algorithm and apply it to the task of learning monotone Boolean functions from examples that are uniformly distributed over {0,1}^n. I limited my scope to the class of monotone Boolean functions that can be represented as read-2 width-2 disjunctive normal form expressions. I modeled these functions as graphs and examined each type of connected component contained in these models, i.e. path graphs and cycle graphs. I determined the influence of the variables in the pieces of these graph models in order to understand how ID3 behaves when learning these functions. My findings show that ID3 will produce an optimal decision tree for this class of Boolean functions.</p>

Name thesis:degree_name

MS

Level thesis:degree_level

Immediate Access

Discipline thesis:degree_discipline

Computational Mathematics

Year dc:date.available

2015

Author dc:creator

• Thompson, Pamela

Contributors dc:contributor

• Karl Wimmer
• Jeffrey Jackson

• Boolean function
• DNF expression
• graph
• ID3
• monotone
• variable influence

Language dc:language

English

Repository record dc:identifier

https://dsc.duq.edu/etd/1280

OAI identifier oai:identifier

oai:dsc.duq.edu:etd-2296