Workflow Inference: What to Do with One Example and no Semantics}

Contents

It is much easier to get human experts to provide example action sequences than declarative representations of either the semantics of the atomic actions in the sequences or the workflow used to generate the sequences. To address this particular instance of the knowledge acquisition bottleneck, this paper describes an algorithm called Workflow Inference from Traces (WIT) that learns workflows from a single action-sequence (trace) without the need for action semantics (i.e., preconditions or effects). WIT is based on model merging techniques borrowed from the grammar induction literature. It starts with a workflow that generates just the observed trace, generalizing with each merge. Prior to the merging phase, an alphabet of action types is created in which similar action instances are grouped according to their input/output characteristics in the trace. It is a sequence of tokens in this alphabet that is merged. We empirically evaluate the performance of WIT using a novel measure of similarity between workflows. This evaluation takes place in an instance of the well-known domain proposed by Berners-Lee, Hendler, and Lassila in which actions correspond to accessing web services.