Hidden Semi-Markov Models (HSMMs) have been extensively used for diverse applications where the objective is to analyze time series whose dynamics can be explained by a hidden process.
A Comprehensive Guide to HSMM offers an accessible introduction to the framework of HSMM, covering the main methods and theoretical results for maximum likelihood estimation in HSMM. It also includes a unique review of existing R and Python software for HSMM estimation. The book then introduces less classical related topics, such as multi-chain HSMM and controlled HSMM, with an emphasis on the challenges related to computational complexity.
This book is primarily intended for master's 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 and epidemiology.
Table of Contents:
Introduction xi
Benoîte DE SAPORTA, Jean-Baptiste DURAND, Alain FRANC and Nathalie PEYRARD
Chapter 1 Monochain HSMM 1
Jean-Baptiste DURAND, Alain FRANC, Nathalie PEYRARD, Nicolas VERGNE and Irene VOTSI
1.1. Introduction 1
1.2. HSMM framework 2
1.2.1. Intuitive presentation with the Squirrel toy example 2
1.2.2. General HSMM framework 4
1.2.3. Standard HSMM 7
1.2.4. Explicit duration HMM 10
1.2.5. Hmm 11
1.3. Inferential topics for HSMMs 11
1.3.1. Likelihood evaluation 12
1.3.2. Asymptotic properties of the MLE 15
1.3.3. EM algorithm 16
1.3.4. Smoothing and filtering probabilities 19
1.3.5. State restoration 20
1.4. Two toy examples reappearing throughout the book 22
1.4.1. Squirrel toy example 22
1.4.2. Deer toy example 23
1.5. Reliability 24
1.5.1. Rate of occurrence of failures 25
1.5.2. Mean time to failure 26
1.6. Introducing mixed effects into HSMMs 27
1.6.1. Mixed HSMMs explained with the Squirrel example 28
1.6.2. Mixed effects for real-valued observations with the Deer example 32
1.6.3. Dynamic covariates: toward an alternative representation of HSMMs 33
1.6.4. Model selection issues for fixed and random effects 35
1.6.5. Mixed models in the HMM/HSMM literature 35
1.7. Conclusion/discussion 38
1.8. Notations 39
1.9. Acknowledgments 40
1.10. Appendix: EM algorithm for a monochain HMM 40
1.10.1. E step 41
1.10.2. M step 42
1.11. References 43
Chapter 2 Review of HSMM R and Python Softwares 47
Caroline BÉRARD, Marie-Josée CROS, Jean-Baptiste DURAND, Corentin LOTHODÉ, Sandra PLANCADE, Ronan TRÉPOS and Nicolas VERGNE
2.1. Introduction 47
2.2. Software around HSMMs: state of the art 48
2.2.1. R packages 49
2.2.2. Python packages 54
2.2.3. Other relevant software 57
2.3. Comparative overview: R and Python packages for HSMM 62
2.3.1. General comparison 62
2.3.2. Sojourn durations 63
2.3.3. Observations 65
2.4. Illustration of the use of two packages for the toy examples 66
2.4.1. Docker image 66
2.4.2. Python package edhsmm on toy model Squirrel 67
2.4.3. R package hhsmm on deers 71
2.5. Conclusion 75
2.6. References 75
Chapter 3 Multichain HMM 79
Hanna BACAVE, Jean-Baptiste DURAND, Alain FRANC, Nathalie PEYRARD, Sandra PLANCADE and Régis SABBADIN
3.1. Introduction 79
3.2. Different concepts of MHMM 81
3.2.1. General MHMM 81
3.2.2. MHMM with conditional independencies 83
3.2.3. Case 1 of MHMM-CI: 1to1-MHMM-CI 85
3.2.4. Case 2 of MHMM-CI: FHMM 88
3.3. Examples of models of class 1to1-MHMM-CI 90
3.3.1. Structures obtained by coupling 91
3.3.2. Applications 93
3.4. Metapopulation dynamics and MHMM 96
3.5. Parameter inference in MHMMs with the EM algorithm 98
3.5.1. Case of general MHMMs 100
3.5.2. Case of 1to1-MHMM-CI 100
3.5.3. Case of FHMM 105
3.5.4. MHMM parameterization for continuous observations 105
3.6. Approximate inference in MHMMs 106
3.6.1. State of the art of approximate inference for CHMMs 108
3.6.2. State of the art of approximate inference for FHMMs 110
3.7. Discussion and conclusion 111
3.8. Notations 113
3.9. References 114
Chapter 4 Multichain HSMM 117
Jean-Baptiste DURAND, Nathalie PEYRARD, Sandra PLANCADE and Régis SABBADIN
4.1. Multichain HSMM in literature 117
4.2. Formalization of an explicit duration coupled semi-Markov model with interaction at jump events 118
4.2.1. Definition based on literal hypotheses 119
4.2.2. Generative definition using a time indexed representation 119
4.2.3. Graphical representation 121
4.3. Definition of coupled SMM classes based on a time-indexed representation 122
4.3.1. Limitations of the (Z, E, R) representation 122
4.3.2. Hazard rate representation 123
4.3.3. Definition and formalization of a class of coupled standard SMMs 124
4.3.4. Extension to general semi-Markov property 132
4.3.5. Other uses of time-indexed representation 132
4.4. Extension of some MHMM classes to semi-Markov framework 133
4.4.1. Generative definition of MHSMM classes 133
4.4.2. Graphical representation of MHSMM classes 134
4.4.3. About inference 136
4.5. Discussion and conclusion 136
4.6. Notations 136
4.7. Appendix: proof of proposition 1 138
4.8. References 142
Chapter 5 The Forward-backward Algorithm with Matrix Calculus 143
Alain FRANC
5.1. Introduction 144
5.2. UHMDs, with elimination and marginalization algorithms 145
5.2.1. Un-normalized heterogeneous Markov-based distribution 145
5.2.2. Elimination algorithm 146
5.2.3. Marginalization algorithm 148
5.3. Complements on the complexity of elimination and marginalization algorithms for an UHMD 150
5.3.1. Multichain UHMD 151
5.3.2. Sparsity 152
5.3.3. Independence between chains in an UHMD 153
5.4. Hidden Markov model 154
5.4.1. Computing the probability of the observations 155
5.4.2. Smoothing and EM algorithm 156
5.4.3. Presentation of the general approach 157
5.4.4. Sparsity of the transition matrix 158
5.5. Multichain hidden Markov models 159
5.5.1. General MHMM 160
5.5.2. A hierarchy of models 162
5.5.3. Correspondence between hidden and observed variables: 1to1-MHMM-CI 163
5.6. Hidden semi-Markov models 166
5.6.1. General SMM as an MM in calendar time 167
5.6.2. General HSMM in calendar time 168
5.6.3. Computing the probability of the observations 169
5.6.4. Particular cases of HSMM 170
5.6.5. Explicit duration hidden Markov model 170
5.7. Multichain HSMM 172
5.7.1. 1to1-J-MHSMM-CI 172
5.7.2. Multichain ED-HMM with conditional independence 175
5.7.3. Different geometries of coupling 176
5.8. Conclusions and perspectives 176
5.9. Notations 178
5.10. Acknowledgments 179
5.11. Appendix: Viterbi algorithm and most likely state 179
5.11.1. UHMD in a commutative semi-ring 180
5.11.2. Setting the problem 181
5.11.3. Computing the probability of the most likely state 182
5.11.4. Recovering the most likely state 183
5.12. References 184
Chapter 6 Controlled Hidden Semi-Markov Models 185
Alice CLEYNEN, Benoîte DE SAPORTA, Orlane ROSSINI, Régis SABBADIN and Amélie VERNAY
6.1. Introduction 185
6.2. Markov decision processes 186
6.2.1. MDP definition 187
6.2.2. Control for MDPs 188
6.2.3. Partially observed Markov decision processes 194
6.2.4. Solution algorithms for MDPs and POMDPs 199
6.3. Piecewise deterministic Markov processes 200
6.3.1. PDMP definition 200
6.3.2. Impulse control for PDMPs 210
6.4. Controlled PDMPs as members of the MDP family 215
6.4.1. Controlled PDMPs as MDPs 216
6.4.2. Partially observed controlled PDMPs as POMDPs 220
6.5. Concluding remarks and open questions 222
6.5.1. Open questions in impulse control of PDMPs that might be tackled from the MDP perspective 222
6.5.2. Interesting questions in MDPs arising from converted PDMPs 223
6.6. Notations 223
6.7. Acknowledgments 225
6.8. References 226
List of Authors 231
Index 233
About the Author :
Nathalie Peyrard is Senior Scientist at INRAE, Toulouse, France. Her research includes computational statistics in models with latent variables, with applications in ecology.
Benoîte de Saporta is Professor of Applied Mathematics at the University of Montpellier, France. Her research includes applied probability (Markov processes, optimal stochastic control) and statistics (inference for partially hidden processes).
