Using decision trees as a concept description language, we examine the time
complexity for learning Boolean functions with polynomial-sized disjunctiv
e normal form expressions when feature construction is performed on an init
ial decision tree containing only primitive attributes. A shortcoming of se
veral feature-construction algorithms found in the literature is that it is
difficult to develop time complexity results for them. We illustrate a way
to determine a limit on the number of features to use for building more co
ncise trees within a standard amount of time. We introduce a practical algo
rithm thar forms a finite number of features using a decision tree in a pol
ynomial amount of time. We show empirically that our procedure forms many f
eatures that subsequently appear in a tree and the new features aid in prod
ucing simpler trees when concepts are being learned from certain problem do
mains. Expert systems developers can use a method such as this to create a
knowledge base of information that contains specific knowledge in the form
of If-Then rules.