| In this dissertation, we investigate the problem of "descriptive" learning---that is, 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: by enumeration of syntactic forms followed by verification against the data. Such methods are both slow and restricted in the types of rules they can find.;We present a series of descriptive-learning algorithms that belong to 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. Our systems work by exploiting anomalies in this data: They hypothesize that patterns that are very unlikely to have arisen by chance represent features of the domain.;We describe separate data-driven methods for rule-discovery in propositional and in relational domains. We also present refinements to our relational rule-discovery system that make possible, first, the automatic identification and exploitation of variable-type information, and second, the use of dynamic, "just-in-time" object sampling to increase efficiency at little cost in accuracy.;We apply our methods to the problem of finding planning invariants---formulae that are true in every reachable state of a planning world---which require richly-expressive languages to describe. Previous automatic invariant-discovery methods have worked by deduction from the operators. We show how our discovery methods provide a novel inductive approach to this problem, and can find invariants from nothing but a few reachable-state descriptions. We demonstrate that the number and types of laws we discover are comparable to those discovered by systems that require complete operator descriptions in addition to state descriptions. |
