  The hidden Markov model (HMM) is a widely-used generative model that copes
with sequential data, assuming that each observation is conditioned on the
state of a hidden Markov chain. In this paper, we derive a novel algorithm to
cluster HMMs based on the hierarchical EM (HEM) algorithm. The proposed
algorithm i) clusters a given collection of HMMs into groups of HMMs that are
similar, in terms of the distributions they represent, and ii) characterizes
each group by a "cluster center", i.e., a novel HMM that is representative for
the group, in a manner that is consistent with the underlying generative model
of the HMM. To cope with intractable inference in the E-step, the HEM algorithm
is formulated as a variational optimization problem, and efficiently solved for
the HMM case by leveraging an appropriate variational approximation. The
benefits of the proposed algorithm, which we call variational HEM (VHEM), are
demonstrated on several tasks involving time-series data, such as hierarchical
clustering of motion capture sequences, and automatic annotation and retrieval
of music and of online hand-writing data, showing improvements over current
methods. In particular, our variational HEM algorithm effectively leverages
large amounts of data when learning annotation models by using an efficient
hierarchical estimation procedure, which reduces learning times and memory
requirements, while improving model robustness through better regularization.
