Similarity-Based Alignment and Generalization

Abstract. We present a novel approach to learning predictive sequential models, called similarity-based alignment and generalization, which incorporates in the induction process a specific form of domain knowledge derived from a similarity metric of the points in the input space. When applied to Hidden Markov Models, our framework yields a new class of learning algorithms called SimAlignGen. We discuss the application of our approach to the problem of programming by demonstration–the problem of learning a procedural model of a user’s behavior by observing the interaction an application GUI. We describe in detail the SimIOHMM, a specific instance of SimAlignGen that extends the known Input-Output Hidden Markov Model (IOHMM). We use the SimIOHMM in empirical evaluations that demonstrates the dependence of the prediction accuracy on the introduced similarity bias, as well as the computational gains over the IOHMM.