A Spectral Algorithm for Inference in Hidden semi-Markov Models

Hidden semi-Markov models (HSMMs) are latent variable models which allow latent state persistence and can be viewed as a generalization of the popular hidden Markov models (HMMs). In this paper, we introduce a novel spectral algorithm to perform inference in HSMMs. Unlike expectation maximization (EM), our approach correctly estimates the probability of given observation sequence based on a set of training sequences. Our approach is based on estimating moments from the sample, whose number of dimensions depends only logarithmically on the maximum length of the hidden state persistence. Moreover, the algorithm requires only a few matrix inversions and is therefore computationally efficient. Empirical evaluations on synthetic and real data demonstrate the advantage of the algorithm over EM in terms of speed and accuracy, especially for large data sets.

• Publication year

  2014

• Venue

  International Conference on Artificial Intelligence and Statistics

• Publication date

  2014-07-12

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1407.3422
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Semi-Markov Switching Vector Autoregressive Model-Based Anomaly Detection in Aviation Systems

  2016cited by this paper
• Spectral learning of latent-variable PCFGs: algorithms and sample complexity

  2014cited by this paper
• Explicit-Duration Markov Switching Models

  2014cited by this paper
• A Tensor Spectral Approach to Learning Mixed Membership Community Models

  2013cited by this paper
• When are overcomplete topic models identifiable? uniqueness of tensor tucker decompositions with structured sparsity

  2013cited by this paper
• A tensor approach to learning mixed membership community models

  2013cited by this paper
• Discovering Anomalous Aviation Safety Events Using Scalable Data Mining Algorithms

  2013cited by this paper
• Detection of Precursors to Aviation Safety Incidents Due to Human Factors

  2013cited by this paper
• Bayesian nonparametric hidden semi-Markov models

  2012cited by this paper
• A Spectral Algorithm for Latent Junction Trees

  2012influential reference
• Aircraft anomaly detection using performance models trained on fleet data

  2012cited by this paper
• Bayesian reasoning and machine learning

  2012cited by this paper
• Learning Linear Bayesian Networks with Latent Variables

  2012cited by this paper
• A Spectral Algorithm for Latent Tree Graphical Models

  2011cited by this paper
• A Spectral Learning Algorithm for Finite State Transducers

  2011cited by this paper
• Multi-View Learning of Word Embeddings via CCA

  2011cited by this paper
• Hidden semi-Markov models

  2010cited by this paper
• UvA-DARE ( Digital Academic Repository ) Activity recognition using semi-Markov models on real world smart home datasets

  2010cited by this paper
• Predictive State Temporal Difference Learning

  2010cited by this paper
• Multiple kernel learning for heterogeneous anomaly detection: algorithm and aviation safety case study

  2010influential reference
• A Large-Scale Hidden Semi-Markov Model for Anomaly Detection on User Browsing Behaviors

  2009cited by this paper
• Reduced-Rank Hidden Markov Models

  2009cited by this paper
• Anomaly Detection and Diagnosis Algorithms for Discrete Symbol Sequences with Applications to Airline Safety

  2009cited by this paper
• Grammatical inference as a principal component analysis problem

  2009cited by this paper
• Tensor Decompositions and Applications

  2009cited by this paper
• An HDP-HMM for systems with state persistence

  2008cited by this paper
• Hidden semi-Markov model for anomaly detection

  2008cited by this paper
• Markov Chains and Mixing Times

  2008cited by this paper
• A spectral algorithm for learning Hidden Markov Models

  2008cited by this paper
• Hidden Semi-Markov Model Based Speech Synthesis System

  2006cited by this paper
• Learning nonsingular phylogenies and hidden Markov models

  2005cited by this paper
• An efficient forward-backward algorithm for an explicit-duration hidden Markov model

  2003cited by this paper
• Towards a standardized notation and terminology in multiway analysis

  2000cited by this paper
• Observable Operator Models for Discrete Stochastic Time Series

  2000cited by this paper
• A tutorial on hidden Markov models and selected applications in speech recognition

  1989cited by this paper
• Maximum likelihood from incomplete data via the EM - algorithm plus discussions on the paper

  1977cited by this paper
• Statistical Inference for Probabilistic Functions of Finite State Markov Chains

  1966cited by this paper

• A Review of Flight Abnormal Behavior Analysis and Trajectory Anomaly Detection Methods

  2026cites this paper
• Adaptive Regression Model Construction Based on the Functional Quality Analysis of the Sequence Segment Processing

  2025cites this paper
• Segmenting Input Data to Improve the Quality of Identification of Information Security Events

  2024cites this paper
• Detection of sedentary time and bouts using consumer-grade wrist-worn devices: a hidden semi-Markov model

  2024cites this paper
• Method for generating information sequence segments using the quality functional of processing models

  2024cites this paper
• An Advanced Segmentation Approach to Piecewise Regression Models

  2023cites this paper
• Reproducing kernels and choices of associated feature spaces, in the form of L2-spaces

  2022cites this paper
• Explicit-duration Hidden Markov Models for quantum state estimation

  2021cites this paper
• A review of change point detection methods

  2018cites this paper
• Reproducing kernels and choices of associated feature spaces, in the form of $L^{2}$-spaces

  2017cites this paper
• Double articulation analyzer with deep sparse autoencoder for unsupervised word discovery from speech signals

  2016cites this paper
• Dynamic Mode Decomposition with Reproducing Kernels for Koopman Spectral Analysis

  2016cites this paper
• Spectral Probablistic Modeling and Applications to Natural Language Processing

  2015cites this paper
• Spectral Learning of Large Structured HMMs for Comparative Epigenomics

  2015cites this paper
• Spectral Probabilistic Modeling and Applications to Natural Language Processing

  2013cites this paper
• Alma Mater Studiorum Università di Bologna Archivio istituzionale della ricerca

  year unknowncites this paper