Laws in Logical Worlds

Revision with unchanged content. We investigate the problem of descriptive learning--learning rules that describe the underlying structure of a domain--in rich, qualitative worlds. Previous approaches to this problem have searched for laws in top-down, enumerative fashion. We present algorithms that belong to an alternative, data-driven search paradigm. In our algorithms, search is guided not by relationships between the forms of the hypothesized rules, but by correlations in the data they represent. We exploit anomalies in this data, hypothesizing that that patterns that are unlikely to have arisen by chance must represent features of the domain. We describe data-driven methods that discover rules in both propositional and relational domains. We apply our methods to the problem of finding planning invariants: formulae that are true in every reachable state of a planning world. Our methods provide a novel inductive approach to this problem. They find invariants from just a few reachable-state descriptions. They discover laws comparable in quality and complexity to those discovered by specialized planning-invariant discovery systems that require a far greater deal of specialized knowledge about the domain.