TL;DR
This paper introduces a novel "sequence breaking framework" to improve the initialization of Expectation-Maximization (EM) algorithms for Hidden Semi-Markov Models (HSMMs) with multiple categorical sequences. By intelligently breaking down observed sequences and using these segments to guide initial parameter estimates, the method significantly enhances the likelihood found by the EM algorithm and speeds up convergence.
What Problem Does This Paper Address?
Hidden Semi-Markov Models (HSMMs) are powerful tools for modeling sequential data where the duration spent in a state isn't fixed (unlike standard Hidden Markov Models). However, a major challenge in using HSMMs, particularly for complex data like multiple, categorical sequences, is the Expectation-Maximization (EM) algorithm's sensitivity to initial parameter values. Poor initialization can lead the EM algorithm to converge to suboptimal solutions (local maxima of the likelihood function), hindering the model's performance. Existing methods for initializing HSMMs, like simple parameter jittering, are often insufficient for complex scenarios. This paper aims to address this by proposing a more robust and effective initialization strategy.
Methods
The core contribution is a new initialization strategy called the sequence breaking framework. This framework comprises two main algorithms:
- HighLikelihoodSearch: This is the overarching strategy. It involves randomly selecting subsets of observed sequences and using the
SequenceBreakingalgorithm to generate corresponding hidden state sequences. These generated state sequences, along with the observed data, are then used to compute initial model parameters via Maximum Likelihood Estimation (MLE) (leveraging Proposition 1, which states that MLEs for EDHMMs can be derived from conditional empirical frequencies). This initial set of parameters is then fed into the standard EM algorithm to find a local maximum of the likelihood for the entire dataset. This process is repeated multiple times to increase the chances of finding a good local maximum. - SequenceBreaking: This algorithm takes an observed sequence and "breaks" it into several pieces by randomly choosing transition points. For each piece, it assigns a hidden state, ensuring that consecutive states are different (as per EDHMM transition matrix constraints). This process effectively generates plausible hidden state sequences from observed data, which are crucial for the
HighLikelihoodSearchto derive meaningful initial parameters.
The paper also compares this new method against a "jittered-centers" approach, which involves slightly perturbing parameters around their default values, a common practice for HMMs.
Datasets
The authors evaluate their method on three datasets:
- D(a): An artificial dataset consisting of 100 sequences, each of length 100, with 5 clusters and 5 observed parameters.
- D(an): An artificial dataset derived from D(a) by randomly replacing 20% of the observations with noise.
- D(r): A real-world dataset comprising 2390 sequences of varying lengths (average length 17, std dev 8) related to the number of words skipped during an ocular saccade task. This dataset has 5 clusters and 5 observed parameters.
Key Insights and Ideas
- Intelligent Initialization is Key: The paper strongly reinforces the idea that for complex models like HSMMs, the initialization strategy is not a minor detail but a critical factor determining the quality of the final model.
- Leveraging Data Structure: The "sequence breaking" approach cleverly uses the structure of the observed data to infer plausible hidden state sequences, which in turn leads to better initial parameter estimates than random perturbations.
- Bridging the Gap: The method effectively bridges the gap between observed data and hidden states by creating synthetic, yet data-informed, state sequences for initialization.
- Generalizability: While the paper focuses on Explicit Duration HMMs (EDHMMs), the underlying principle of using observed data to guide initialization is likely applicable to more general HSMM formulations.
Key Results
- Improved Likelihood: The sequence breaking framework consistently found higher maximum likelihoods across all three datasets compared to the jittered-centers method. For instance, on dataset D(a), the mean log-likelihood was -15448 for sequence breaking versus -15452 for jittered-centers (a significant difference).
- Faster Convergence: The sequence breaking initialization led to significantly faster convergence of the EM algorithm. On average, it required 133 fewer iterations for D(a), 305 fewer for D(an), and 44 fewer for D(r).
- Local Performance: In local analyses (examining performance across blocks of initializations), sequence breaking outperformed jittered-centers in 9 out of 10 blocks for D(a) and D(an), and 6 out of 10 for D(r).
Limitations and Future Work
- Parameter α: The number of sequences to sample (α) in the
HighLikelihoodSearchcan be seen as a control for the randomness of initial parameters. A higher α leads to initial parameters that are closer to the "real" ones, but this might also reduce the exploration of the parameter space. - Data Dependency: The authors acknowledge that initialization techniques are data-dependent, suggesting the need to test the sequence breaking framework on more diverse datasets.
- Alternative Initialization Methods: They propose exploring other initialization techniques like Stochastic EM or Classification EM to further understand the framework's relevance.
- Heuristics for Early Detection: A potential future direction is developing heuristics to quickly identify "bad candidates" (initializations that are unlikely to lead to good solutions) to save computational time.
- Continuous Data: The current work focuses on discrete categorical observations, but the authors note that the framework is generalizable to continuous observations.
Summary updated