Structured Hidden Markov models: A general tool for modeling agent behaviors

Structured Hidden Markov Model (S-HMM) is a variant of Hierarchical Hidden Markov Model that shows interesting capabilities of extracting knowledge from symbolic sequences. In fact, the S-HMM structure provides an abstraction mechanism allowing a high level symbolic description of the knowledge embedded in S-HMM to be easily obtained. The paper provides a theoretical analysis of the complexity of the matching and training algorithms on S-HMMs. More specifically, it is shown that the Baum-Welch algorithm benefits from the so called locality property, which allows specific components to be modified and retrained, without doing so for the full model. Moreover, a variant of the Baum-Welch algorithm is proposed, which allows a model to be biased towards specific regularities in the training sequences, an interesting feature in a knowledge extraction task. Several methods for incrementally constructing complex S-HMMs are also discussed, and examples of application to non trivial tasks of profiling are presented.