Discovering patterns in sequences of events

摘要

Given a sequence of events (or objects), each characterized by a set of attributes, the problem considered is to discover a rule characterizing the sequence and able to predict a plausible sequence continuation. The rule, called a sequence-generating rule, is nondeterministic in the sense that it does not necessarily tell exactly which event must appear next in the sequence, but rather, defines a set of plausible next events.The basic assumption of the methodology presented here is that the next event depends solely on the attributes of the previous events in the sequence. These attributes are either initially given or can be derived from the initial ones through a chain of inferences. Three basic rule models are employed to guide the search for a sequence-generating rule: decomposition, periodic, and disjunctive normal form (DNF). The search process involves simultaneously transforming the initial sequences to derived sequences and instantiating models to find the best match between the instantiated model and the derived sequence. A program, called SPARC/E, is described that implements most of the methodology as applied to discovering sequence generating rules in the card game Eleusis. This game, which models the process of scientific discovery, is used as a source of examples for illustrating the performance of SPARC/E.