Introduction

Hidden Markov models (HMMs) were introduced in the 1960s by Baum and Petrie (1966), first in the case of discrete observations. They have become classical tools to analyze time series whose dynamics can be explained by those of a hidden process. The model is composed of two sets of random variables that are two linked dynamical stochastic processes: one hidden and one observed. This family of models was originally popularized by applications in speech recognition (Baker 1975) and later in other domains like genomics (Churchill 1989). In parallel, developments were achieved in computational statistics to make statistical estimation possible. At the beginning of the 1980s, it was observed that the Markovian assumption on hidden state dynamics was not satisfied in the context of speech recognition. Thus, different relaxations of this assumption were proposed, leading to explicit duration HMMs (Ferguson 1980, ED-HMMs), reformulated shortly after in their modern, more parsimonious form by Russell and Moore (1985). More general semi-Markov models were introduced by Murphy (2002), as an extension of so-called segment HMMs, which are themselves generalizations of ED-HMMs.

Concomitantly with those generalizations of HMMs leading progressively to HSMMs, focusing on refinements on how state and sojourn durations at the current jump depend on the same quantities as the previous jump, HMMs underwent developments on modeling dependencies between several interacting chains, which is the subject of Chapter 3 in this book. These developments were once again motivated by applications in speech or video processing and oriented toward two directions: representing coupling of (shared) hidden states through observations (Ghahramani and Jordan 1997) or directly coupling through states, keeping observations conditionally independent given their unique associated hidden state (Brand et al. 1997).

Markov processes are also a key concept in control problems, whenever stochastic effects have an impact on the dynamics of the system states, or on the efficiency of actions taken to control the system, or even on both aspects. To account for such stochastic effects, Markov decision processes were introduced in the 1950s (Bellman 1958). In cases where the system state cannot be observed directly, but only indirectly through stochastic functions of the state process as in HMMS, the appropriate formalism to address control is that of partially observed MDPs (POMDPs), introduced by Åström (1965). Actually, in such models, "states" in the sense of HMMS may never be observed but POMDPs encompass states and observations into a broader concept of partially observed states. Some extensions of control problems to partially observed semi-Markov dynamics were introduced in the 1990s (Puterman 1994); they are presented in this book under the more general framework of impulse controlled piecewise-deterministic Markov processes.

In parallel with these theoretical developments, the application fields of HSMMs have largely expanded. Speech recognition is less present nowadays but HSMMs have successfully been applied in numerous other domains. This is well illustrated in the introduction of the book by Yu (Yu 2016), where the author presents an overview of the main areas of application up to 2016, covering almost 40 fields. In recent years, HSMMs have been applied to activities recognition for humans (van Kuppevelt et al. 2019; Cavallo et al. 2022; Thornton et al. 2023) and animals (Ruiz-Suarez et al. 2022; Koslik et al. 2023), as well as eye-movement analysis (Olivier et al. 2022; Gao et al. 2023). Seismology (Pertsinidou et al. 2017), epidemiology (Touloupou et al. 2020), occupational health (Haji-Maghsoudi et al. 2021), cardiovascular disease screening (Oliveira et al. 2018), neurophysiology (Chakravarty et al. 2019), plant growth (Mészáros et al. 2020; Labadie et al. 2023) and ecology (Nicol et al. 2022) also exploited the flexibility of HSMMs. Controlled versions of HMM or HSMM have been recently applied to reliability and safety (Srinivasan and Parlikad 2014; Zhang and Revie 2016), path planning for automated vehicles (Bravo et al. 2019), healthcare (Skandari and Shechter 2021; Fatemi et al. 2022; Liu et al. 2022; Garcia et al. 2024; de Saporta et al. 2024) and health economics (Cao et al. 2016; Mohammadi et al. 2023).

This book is written by a consortium of French researchers as part of the project Hidden Semi-Markov Models: INference, Control and Applications (HSMM-Inca) funded by the French Agence Nationale de la Recherche (ANR, grant ANR-21-CE40-005). This consortium is a unique group of researchers with a long experience of statistics, probability, inference and control for temporal and spatial processes. It also has expertise on the modeling and inference of hidden dynamic processes in health, ecology and natural risks.

We have written this book to offer an accessible introduction to the framework of HSMMs, covering the main methods and theoretical results for maximum likelihood estimation in HSMMs, together with an opening onto new, less classical related topics such as multichain HSMM and controlled HSMM. This book unifies and generalizes existing results. It is also complementary to more detailed textbooks such as Barbu and Limnios (2009) and Yu (2016) that go deeper into technical details but stay focused on classical HSMM.

This book is primarily intended for master and PhD students, researchers and academic faculty in the fields of statistics, applied probability, graphical models, computer science and connected domains. It is also meant to be accessible to practitioners involved in modeling, analysis or control of time series in the fields of reliability, theoretical ecology, signal processing, finance, medicine, epidemiology, etc.

The book is organized as follows. Chapter 1 introduces the general HSMM formalism and well-known particular cases. Then, it introduces maximum likelihood estimation (MLE) for HSMMs: likelihood expression and evaluation, asymptotic properties of the MLE and EM algorithm for MLE computation. Finally, it presents recent results on the definition of reliability indicators and an extensive review of how to introduce mixed effects into HSMM components.

Chapter 2 provides an overview of the packages and software (primarily in R and Python) dedicated to the estimation, simulation and application of HSMMs and other types of Markovian models that are central to the themes of the subsequent chapters.

Chapter 3 defines the framework of multichain HMM that enables us to present in a unified way existing models from literature and also generalize them. It illustrates how such models can be used to model dynamics in ecology and epidemiology. Then, it discusses inference of multichain HMM in the context of the EM algorithm.

Chapter 4 deals with the introduction of the semi-Markov assumption in multichain HMMs. It proposes a sound formalization of two classes of models that extend standard and general semi-Markov models to the multichain setting. Then, it considers the hidden framework and builds various classes of multichain HSMMs that generalize some MHMM structures defined in Chapter 3.

Chapter 5 focuses on the evaluation of the time complexity of marginal inference calculated with the forward-backward algorithm. It presents an algebraic formalism that leads to writing the forward-backward algorithm and calculating its complexity by counting the multiplications, with the same approach for several models studied in the previous chapters. It also shows how the sparsity of the transition matrices leads to a reduction of this complexity.

Chapter 6 focuses on controlled HSMMs. The chapter starts with a step-by-step introduction to the Markov decision processes (MDPs) formalism and progressively introduces partial observation semi-Markov assumption and continuous time to present the current available methods for controlled HSMMs.

This book presents distinct definitions, models and issues, which despite their differences share some common features. To guide the reader through this diversity of approaches, two simple case studies have been selected as toy examples, which are used during the course of the different chapters to illustrate the different notions and approaches, enabling an intuitive understanding before entering into the technique. They illustrate distinct extensions of HSMMs, like inference with covariates, multichain setting and linking with decision-making. The first one is referred to as Squirrel and the second as Deer. Both are models in behavioral ecology and introduced in Chapter 1. Chapters 2 and Chapter 6 present numerical illustrations of the two toy examples and provide the code for reproducing it.

Throughout the book, we also present open questions on the different aspects of HSMMs covered in the chapters. We hope we have created a source of inspiration for future research.

I.1. References

1. Åström, K.J. (1965). Optimal control of Markov processes with incomplete state information. Journal of Mathematical Analysis and Applications, 10(1), 174-205.
2. Baker, J. (1975). The DRAGON system - An overview. IEEE Transactions on Acoustics, Speech, and Signal Processing, 23(1), 24-29.
3. Barbu, V.S. and Limnios, N. (2009)....