A Comprehensive Guide to HSMM

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