Feature construction: An analytic framework and an application to decision trees

While similarity-based learning (SBL) methods can be effective for acquiring concept descriptions from labeled examples, their success largely depends upon the quality of the features used to describe the examples. When a learning problem uses low-level features, the complexity of the concept-membership function can make SBL inaccurate, expensive, or simply impossible. One way to overcome this limitation is through feature construction: the construction of new features by the application of constructive operators to existing features. Feature construction can result in an improved instance space in which the concept-membership function is better behaved relative to the inductive biases of SBL algorithms. Feature construction, however, is computationally difficult, primarily because of the intractably large space of potential new features. To assist in the study and advancement of feature construction methods, this thesis presents a feature construction framework based on the aspects of (1) need detection, (2) constructor selection, (3) constructor generalization, and (4) feature evaluation. This framework was used to analyze eight existing systems (BACON, BOGART, DUCE, FRINGE, MIRO, PLSO, STAGGER, and STABB) and to identify promising approaches to feature construction. The framework also served as the basis for the design of CITRE, an inductive system that constructs new features using decision tress. CITRE was tested on five learning problems: l-term kDNF Boolean functions, tic-tac-toe classification, mushroom classification, voting-record classification, and chess-end-game classification. The results demonstrate CITRE's potential for significantly improving hypothesis accuracy and conciseness. The results also reveal substantial benefits obtainable by using simple domain-knowledge constraints and constructor generalization during feature construction.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2011

Author dc:creator

• Matheus, Christopher John

Contributors dc:contributor

• Rendell, Larry A.

• Artificial Intelligence
• Computer Science

Statement dc:rights

• Copyright 1990 Matheus, Christopher John

Language dc:language

eng

Identifier

AAI9021727
(UMI)AAI9021727

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/23122