Much previous work in rule discovery has worked with impoverished domains describable as a list of <object, attribute> pairs. Such representations admit of relatively efficient algorithms, but are too poor to describe interesting features of the real world and of many logical systems. I will describe more recent work in the field of relational data mining that seeks to extend these algorithms to richer domains. Previous approaches to this problem have worked by searching the space of syntactically correct rule-statements for those that satisfy certain criteria. Their search is guided by linguistic and declarative bias; they hypothesize the possible rules in some order and then test each one.
I will argue that the space of possible rules is too large to be searched effectively in this manner, and propose an alternative, data-driven search paradigm, in which the search is guided not by relationships between the forms of the hypothesized rules, but by correlations in the data they represent. I will argue that such pattern-driven search enables the detection of far richer and more powerful hypotheses, including those involving equality and nested quantification.
I will present a prototype system that incorporates these ideas, and the results obtained when it is applied to the problem of detecting invariants in arbitrary planning worlds. Finally, I will discuss ways of extending the approach to more realistic domains, and of extending the discovery process by enabling it to create new concepts as necessary to better describe the data.