Learning Despite Complex Attribute Interaction: An Approach Based on Relational Operators

When shortage of knowledge prevents human experts from choosing good attributes to represent empirical observations, learning is difficult. Expressing concepts by using only primitive (low-level) attributes is intricate because the contribution of each attribute to the definition is almost unnoticeable. This aggravates attribute interaction, a situation where an attribute's effect on classification depends on the value of other attributes. When attribute interaction is complex, involving many combinations of several attributes, current learners cannot handle it. Such complex interaction appears in real-world domains (e.g., protein folding). These domains are not random; they have structure although it may be concealed by the complexity of the interactions. Concepts in these domains often have embedded, implicit structure, which may be revealed through explicit relations. Because of the existence of structure, there is still hope for learning despite complex attribute interaction if appropriate techniques are devised. The design of these techniques, however, must be guided by a required functionality: finding interactions, more precisely, finding relations. In particular, this thesis focuses on interactions due to complex relations among primitive attributes. Then, concepts can be simple in terms of relations, but complex in terms of primitive attributes. Such focus is motivated by relations that appear in protein folding and other domains. To facilitate learning when relations create complex interactions, an approach based on the algebraic notions of relation and relational operators is proposed. The approach is implemented in MRP, a learning system that relies on multidimensional relational projection to find relations and hence, find interactions that can be captured as relations among attributes. Synthetic and real-world problems are used to empirically evaluate MRP with respect to five classical and advanced machine learning systems. MRP's distinctive behavior is analyzed in terms of concept characteristics (such as DNF size, entropy, variation, and Fourier spectrum), and related to the system's performance in real-world domains. Finally, a small family of simplified versions of MRP is evaluated empirically to analyze what components of MRP are responsible for its improved performance, and this analysis is used to focus the proposal for future research directions and system extensions.

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

2015

Author dc:creator

• Perez, Eduardo

Contributors dc:contributor

• Rendell, Larry A.

• Artificial Intelligence

Language dc:language

eng

Identifier

(MiAaPQ)AAI9717326

OAI identifier oai:identifier

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