PaperlayerView exact revision on arXiv

Source-linked AI summary

Bayesian Nonparametric Hidden Semi-Markov Models

Matthew J. Johnson, Alan S. Willsky

arXiv:1203.1365v2stat.MEstat.APstat.ML

TL;DR

HDP-HMMs infer state complexity but retain restrictive geometric-duration Markov dynamics, motivating a more flexible sequential model. The paper introduces the HDP-HSMM and Gibbs samplers, demonstrating utility on synthetic and real data while supporting larger hierarchical models.

  • Problem

    HDP-HMMs retain geometric state durations and can suffer slow mixing from individually resampled, strongly correlated state sequences.

  • Method

    The paper combines explicit-duration semi-Markov modeling with Bayesian nonparametric state-complexity inference and develops weak-limit and direct-assignment Gibbs samplers.

  • Results

    Experiments on synthetic and real data demonstrate effective HDP-HSMM modeling and inference, including power-signal disaggregation.

  • Takeaways & Limitations

    HDP-HSMMs provide interpretable non-Markov duration modeling and can serve as semi-Markov components in larger hierarchical Bayesian models.

  • Takeaways & Limitations

    The paper does not investigate selecting observation and duration distribution classes, leaving those modeling choices to the user.

Abstract

from arXiv · show

There is much interest in the Hierarchical Dirichlet Process Hidden Markov Model (HDP-HMM) as a natural Bayesian nonparametric extension of the ubiquitous Hidden Markov Model for learning from sequential and time-series data. However, in many settings the HDP-HMM's strict Markovian constraints are undesirable, particularly if we wish to learn or encode non-geometric state durations. We can extend the HDP-HMM to capture such structure by drawing upon explicit-duration semi-Markovianity, which has been developed mainly in the parametric frequentist setting, to allow construction of highly interpretable models that admit natural prior information on state durations. In this paper we introduce the explicit-duration Hierarchical Dirichlet Process Hidden semi-Markov Model (HDP-HSMM) and develop sampling algorithms for efficient posterior inference. The methods we introduce also provide new methods for sampling inference in the finite Bayesian HSMM. Our modular Gibbs sampling methods can be embedded in samplers for larger hierarchical Bayesian models, adding semi-Markov chain modeling as another tool in the Bayesian inference toolbox. We demonstrate the utility of the HDP-HSMM and our inference methods on both synthetic and real experiments.

1. Introduction

The paper addresses HDP-HMM limitations by combining Bayesian nonparametric state-complexity inference with explicit-duration semi-Markov modeling and efficient Gibbs samplers.

  • HMMs impose geometric state durations and require the number of hidden states to be set before inference.
  • The HDP-HMM infers arbitrarily large state complexity but retains Markovian dynamics, which can create unnecessary states and rapid switching.
  • Sticky HDP-HMM discourages rapid switching through a global self-transition bias but still imposes geometric, non-state-specific durations.
  • The proposed HDP-HSMM combines Bayesian nonparametric inference of state complexity with general duration distributions and develops sampling methods for posterior inference.
  • Experiments on synthetic and real data evaluate sampler mixing, parameter and state-cardinality learning, sequence statistics, and power-signal disaggregation.

2. Background and Notation

The background introduces Bayesian HMMs, explicit-duration HSMMs, and HDP-HMMs, emphasizing HSMM duration flexibility and the computational trade-offs of inference.

  • 2.1 Basic Notation: An HMM represents sequential observations with hidden states forming a time-homogeneous Markov chain and state-specific emission distributions.
  • 2.1 Basic Notation: Bayesian HMMs treat model parameters as random variables, enabling uncertainty modeling and Bayesian model averaging at greater algorithmic cost.
  • 2.2 HSMMs: An explicit-duration HSMM draws a state-specific duration when a state is entered, keeps the state fixed until expiration, then transitions to another state.
  • 2.2 HSMMs: The HSMM super-state representation separates Markovian transitions from random-length observation segments, with self-transitions excluded in the described chain.
  • 2.2 HSMMs: Right-censored HSMMs allow the final segment to extend beyond the observed sequence, and the message recursion includes a survival-based censoring term.
  • 2.2 HSMMs: HSMM message passing costs O(T^2N+TN^2), compared with O(TN^2) for HMM message passing, reflecting the added duration flexibility.
  • 2.3 The HDP-HMM and Sticky HDP-HMM: The HDP-HMM places an HDP prior over an infinite state space, allowing inference over state complexity while linking transition rows through a shared β.
  • 2.3 The HDP-HMM and Sticky HDP-HMM: Collapsed HDP-HMM samplers resample transitions individually, and strong state-sequence correlations reduce mixing rates; weak-limit approximations improve mixing with little tail sacrifice.

3. Models

The paper develops explicit-duration HSMM-based models that combine Bayesian nonparametric state complexity with directly modeled, potentially non-geometric state durations. These models also extend to factorial structures for source separation and disaggregation.

  • HSMM construction: Explicit-duration HSMMs eliminate self-transitions so duration distributions directly model state-duration statistics.Allowing self-transitions would make explicit durations fail to represent state-duration statistics directly.
  • Scope: The paper leaves selection of observation and duration distribution classes to flexible modeling choices for particular datasets.It identifies model selection as a fundamental challenge in generative modeling but does not investigate that selection problem.
  • Finite Bayesian HSMM: The finite Bayesian HSMM combines Bayesian HMMs with semi-Markov state durations and serves as the model generalized to the HDP-HSMM.Its generative process places priors H and G on observation and duration parameters and uses off-diagonal transition distributions.
  • HDP-HSMM: The HDP-HSMM ties transition distributions hierarchically while adding duration distributions and eliminating self-transitions in the super-state sequence.The model observes a finite prefix of an infinite observation sequence and uses β-mediated hierarchical ties to encourage a small, consistent set of visited states.
  • Factorial structure: Factorial HSMM and HDP-HSMM structures combine independently evolving component chains whose emissions are combined into observations.Each component can use prior duration information, and each component HSMM is not restricted to a fixed number of states.
  • Factorial structure: These factorial models support source separation and disaggregation while representing uncertainty and using prior information about component durations.The paper demonstrates a factorial HDP-HSMM for disaggregating home power signals.

4. Inference Algorithms

The paper develops Gibbs samplers for finite Bayesian HSMMs and two HDP-HSMM variants, addressing inference complications caused by duration modeling and removed self-transitions. It also discusses sampler tradeoffs and changepoint information for improving efficiency.

  • Sampler development: The inference framework begins with a finite Bayesian HSMM sampler, then develops weak-limit and collapsed HDP-HSMM Gibbs samplers.The collapsed sampler parallels the direct assignment sampler, while the weak-limit sampler parallels weak-limit inference for the HDP-HMM and its sticky extension.
  • Inference design: Auxiliary variables restore effective conjugacy for exact, fast Gibbs steps after self-transition elimination breaks conjugacy with the HDP prior.The complication arises because self-transitions are forbidden in the super-state sequence.
  • Sampler tradeoffs: The direct assignment sampler integrates out the transition matrix and observation and duration parameters but requires sequential label resampling because integration couples label variables.The weak-limit sampler represents latent components under an adjustable finite HDP approximation and supports block resampling.
  • Efficiency: Changepoint side-information can be leveraged to greatly accelerate inference.The paper presents this as an additional efficiency technique at the end of the inference discussion.

4.1 A Gibbs Sampler for the Finite Bayesian HSMM

The finite Bayesian HSMM sampler iteratively samples latent states, transition parameters, emission parameters, and duration parameters. Message passing enables blocked sampling of the full state sequence together with posterior segment durations.

  • Gibbs sampler: The finite Bayesian HSMM Gibbs sampler iteratively samples the state sequence, transition rows, emission parameters, and duration parameters from their conditional distributions.The duration prior is represented by G, while observation and duration parameters are sampled according to their chosen priors.
  • Parameter updates: Conditional sampling of emission and duration parameters reduces to standard problems under suitable priors, while transition-row sampling is straightforward for Dirichlet off-diagonal priors.Hierarchically tied transition rows in the weak-limit HDP-HSMM require additional care.
  • Blocked state sampling: HSMM message passing extends HMM blocked state sampling by also sampling posterior duration variables.The key additional challenge is sampling segment durations jointly with the blocked state sequence.
  • Message passing: Backward messages yield the conditional distribution for the initial state, assuming the observation sequence begins at a segment boundary.The initial-state expression conditions on F0 = 1 and suppresses parameter conditioning.
  • Duration sampling: After sampling the initial state, the same messages efficiently sample its posterior duration using the duration prior and likelihood terms for the corresponding observation segments.The procedure then treats the state after the sampled duration as the next initial state and repeats until the whole label sequence is sampled.

4.2 A Weak-Limit Gibbs Sampler for the HDP-HSMM

The weak-limit sampler replaces the infinite HDP transition structure with a finite HSMM approximation, while auxiliary variables restore conjugacy lost by eliminating self-transitions. The resulting Gibbs procedure supports efficient block sampling and exhibits fast mixing in the reported comparisons.

  • Weak-limit approximation: The weak-limit construction uses finite L-dimensional Dirichlet transition rows tied by shared weights β, yielding a finite representation of the transition matrix.The approximation also permits block sampling of the entire label sequence.
  • Weak-limit approximation: The finite HSMM approximation modifies inference because transition rows are coupled through β rather than mutually independent.This dependence creates conjugacy issues under the hierarchical Dirichlet prior.
  • Conjugacy and augmentation: Eliminating self-transitions prevents the transition-row posterior from retaining a Dirichlet form, so direct conjugate resampling is unavailable.The additional 1/(1−π11) likelihood factors create the difficulty.
  • Conjugacy and augmentation: Auxiliary geometric variables ρi restore conjugacy, allowing the transition parameters to be updated with simple Gibbs steps.The variables are independently drawn with success parameter 1−π11.
  • Empirical behavior: The auxiliary-variable sampler mixes rapidly and reaches the potential scale reduction factor’s asymptotic value of unity faster than the Metropolis-Hastings comparison.The figures also report greater execution efficiency for the auxiliary-variable sampler.
  • Extensions: The full weak-limit HDP-HSMM incorporates the auxiliary variables through a graphical model and is evaluated alongside a direct-assignment alternative supplied for theoretical completeness.The direct-assignment sampler may be useful when insufficient data make marginalization important for mixing or marginal-likelihood estimation.

4.3 A Direct Assignment Sampler for the HDP-HSMM

The direct-assignment sampler resamples HDP-HSMM state labels at the segment level, combining transition, observation, and duration contributions. Auxiliary segment counts preserve conjugacy for the global HDP weights β.

  • Sampler scope: The direct-assignment approach is presented as theoretically complete and potentially useful when marginalization is needed because latent parameters are weakly informed.The paper’s experiments use the weak-limit sampler instead.
  • Sampler construction: The direct-assignment sampler represents auxiliary variables while marginalizing the diagonal transition entries, enabling direct resampling of the global weights β.This extends the finite-setting augmentation to the infinite transition matrix.
  • State-label resampling: Changing a state assignment can alter contiguous segments, so the HDP-HSMM score includes between one and three segment terms depending on merges with adjacent segments.Transition scores at the chain’s start and end are excluded.
  • State-label resampling: For a candidate state label, the resampling score combines left-transition, right-transition, observation, and duration predictive terms.The observation term covers all data in the candidate segment, while the duration term depends on same-label segments and duration hyperparameters.
  • State-label resampling: The sampler’s transition terms account for self-transition elimination through rescaled denominators and indicator corrections for exchangeable neighboring transitions.The indicators are needed because the two transition probabilities are not independent.
  • Auxiliary counts: Each segment receives an auxiliary count ρs that is independent of the data and preserves HDP conjugacy for resampling β.The total auxiliary count supplies the statistics used in the standard HDP-HMM update.

4.4 Exploiting Changepoint Side-Information

Known possible changepoints can restrict HDP-HSMM inference to candidate state boundaries and durations. This reduces message-passing complexity when the candidate set is much smaller than the sequence length.

  • Candidate boundaries: Observation-based changepoint detection can rule out many non-changepoints, dividing the label sequence into blocks whose labels are sampled instead.The power disaggregation application uses inexpensive changepoint detection to construct candidate boundaries.
  • Restricted message passing: Backward messages sum over candidate durations using likelihood, duration-prior, and censoring terms, with duration probabilities renormalized over the allowed set.Forward sampling is modified analogously to consider only possible durations.
  • Restricted message passing: The direct-assignment sampler can operate on the block label sequence, resampling each block’s label while allowing merges with adjacent blocks.This replaces elementwise label resampling with block-level updates.

5. Experiments

The experiments evaluate HDP-HSMM samplers on synthetic and real data, showing efficient inference, recovery of non-geometric durations and state structure, and improved power disaggregation.

  • Sampler comparisons: The HDP-HSMM direct assignment sampler performs similarly to the Sticky HDP-HMM sampler on HMM-generated data, while the weak limit sampler mixes much faster.Each weak limit iteration is approximately 50x faster in the reported Python implementations.
  • Synthetic data: On HSMM-generated data, the Poisson-HDP-HSMM learns duration, transition, and emission parameters, whereas the HDP-HMM retains high state-sampling error.The experiment uses four-state HSMM data with Poisson durations and 2-dimensional mixture-of-Gaussian emissions across 25 Gibbs runs.
  • Synthetic data: The HDP-HSMM posterior concentrates on the true number of states, while the HDP-HMM frequently fails to identify state cardinality.This comparison is shown for data generated by a four-state Poisson-HSMM.
  • Synthetic data: A negative-binomial HDP-HSMM learns an HMM from HMM-generated data by concentrating at r = 1, with only a slight mixing-time loss relative to the HDP-HMM.Because r = 1 corresponds to geometric durations, the duration family can represent the HMM case while retaining non-geometric alternatives.
  • Power disaggregation: First-difference thresholding reduces potential changepoints from 5000 to 100-200, speeding state-sequence resampling by orders of magnitude.The resulting changepoints organize observed jumps into explanations based on individual device models.
  • Power disaggregation: In power disaggregation, Bayesian approaches outperform the EM-based approach, and adding duration structure and prior information yields a significant performance increase for HDP-HSMM.The models estimate individual-device power signals from aggregated whole-home consumption; the task is motivated by energy-efficiency benefits of device-level information.
  • Power disaggregation: The nonparametric prior is especially important for lighting, whose power modes arise from uncertain combinations of switched-on lights.For other devices, duration statistics provide a strong clue for disaggregation, while Bayesian inference and duration modeling remain central benefits.

6. Conclusion

The paper introduces HDP-HSMM models and two Gibbs samplers that combine explicit-duration semi-Markov modeling with Bayesian nonparametric inference, and demonstrates their utility on synthetic and real data.

  • Conclusion: The HDP-HSMM and its weak limit and direct assignment samplers support Bayesian nonparametric learning with non-Markov duration statistics.The methods are applicable in supervised and unsupervised settings and can be incorporated into larger hierarchical models.
  • Conclusion: The authors demonstrate the models and inference algorithms with synthetic and real experiments and position them as tools for sequential learning problems.The stated scope includes constructing and performing inference in larger hierarchical models.

Appendix A. Power Disaggregation Priors

The appendix specifies device-informed priors for observation levels and durations, including Gaussian emissions, negative-binomial durations, and sticky-HDP-HMM comparisons.

  • Prior construction: Power-disaggregation priors encode rough device power levels and duration statistics, with refrigerator regimes including off, on, and high modes.The priors use hand-set parameters to represent rough means and variances for device-mode durations and emissions.
  • Observation priors: Observation distributions use Gaussian state-specific means with fixed variances, while Gaussian priors govern the latent means.The notation Gauss(µ0, σ2) denotes a prior with mean µ0 and fixed observation variance σ2.
  • Duration priors: Negative-binomial duration priors draw a latent success parameter p from a Beta distribution while fixing r; r = 1 gives geometric durations.This parameterization supports device-specific duration modeling while retaining the geometric-duration case.
  • Comparison priors: Factorial Sticky HDP-HMM priors reuse the HDP-HSMM observation priors and set state-specific sticky biases to match expected HDP-HSMM durations.The appendix points to Figure 20 for example real-data observation sequences.
  • Scope boundary: Automatically learning hyperparameter mixtures is identified as a natural extension left for future work.The experiments instead emphasize the HDP-HSMM and sampling inference using hand-set prior structure.
Loading 1203.1365v2…