Learning Relational Concepts with the Spatiotemporal Multidimensional Relational Framework

The real world can be seen as containing sets of objects that have multidimensional properties and relations. Whether an agent is planning the next course of action in a task or making predictions about the future state of some object, useful task-oriented concepts are often encoded in terms of the complex interactions between the multi-dimensional attributes of subsets of these objects and of the relationships that exist between them. In this dissertation, I present the Spatiotemporal Multi-dimensional Relational Framework (SMRF), a data mining technique that extends the successful Spatiotemporal Relational Probability Tree models. From a set of labeled, multi-object examples of some target concept, the SMRF learning algorithm infers both the set of objects that participate in the concept, as well as the key object and relational attributes that characterize the concept. In contrast to other relational model approaches, SMRF trees do not require that categorical relations between objects be defined a priori. Instead, the learning algorithm infers these categories from the continuous attributes of the objects and relations in the training data. In addition, the SMRF approach explicitly acknowledges the covariant, multi-dimensional nature of attributes, such as position, orientation, and color, in the creation of these categories. I demonstrate the effectiveness of the learning algorithm in three-dimensional domains that contain groups of objects related in various ways according to color, orientation, and spatial location. The learning algorithm is further shown to be robust to the addition of various kinds of noise to the data. I compare SMRF to other related algorithms and show that it outperforms each of them substantially on relational classification tasks, especially when noise is added to the data. I also show that SMRF handles the addition of extra objects to problem domains much more efficiently than most of its competitors, which empirically exhibit polynomial and exponential increases in running time