Inference in Hidden Markov Models

Contents
Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . V
Contributors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IX
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 What Is a Hidden Markov Model? . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Beyond Hidden Markov Models . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Examples. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.1 Finite Hidden Markov Models. . . . . . . . . . . . . . . . . . . . . . . 6
1.3.2 Normal Hidden Markov Models . . . . . . . . . . . . . . . . . . . . . 13
1.3.3 Gaussian Linear State-Space Models . . . . . . . . . . . . . . . . . 15
1.3.4 Conditionally Gaussian Linear State-Space Models . . . . 17
1.3.5 General (Continuous) State-Space HMMs . . . . . . . . . . . . 24
1.3.6 Switching Processes with Markov Regime. . . . . . . . . . . . . 29
1.4 Left-to-Right and Ergodic Hidden Markov Models . . . . . . . . . . . 33
2 Main Definitions and Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.1 Markov Chains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.1.1 Transition Kernels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.1.2 Homogeneous Markov Chains . . . . . . . . . . . . . . . . . . . . . . . 37
2.1.3 Non-homogeneous Markov Chains . . . . . . . . . . . . . . . . . . . 40
2.2 Hidden Markov Models. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.2.1 Definitions and Notations . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.2.2 Conditional Independence in Hidden Markov Models . . . 44
2.2.3 Hierarchical Hidden Markov Models . . . . . . . . . . . . . . . . . 46
Part I State Inference
XII Contents
3 Filtering and Smoothing Recursions . . . . . . . . . . . . . . . . . . . . . . . 51
3.1 Basic Notations and Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.1.1 Likelihood . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.1.2 Smoothing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.1.3 The Forward-Backward Decomposition . . . . . . . . . . . . . . . 56
3.1.4 Implicit Conditioning (Please Read This Section!) . . . . . 58
3.2 Forward-Backward. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.2.1 The Forward-Backward Recursions . . . . . . . . . . . . . . . . . . 59
3.2.2 Filtering and Normalized Recursion . . . . . . . . . . . . . . . . . . 61
3.3 Markovian Decompositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.3.1 Forward Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.3.2 Backward Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.4 Complements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4 Advanced Topics in Smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.1 Recursive Computation of Smoothed Functionals . . . . . . . . . . . . 77
4.1.1 Fixed Point Smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.1.2 Recursive Smoothers for General Functionals . . . . . . . . . 79
4.1.3 Comparison with Forward-Backward Smoothing . . . . . . . 82
4.2 Filtering and Smoothing in More General Models . . . . . . . . . . . . 85
4.2.1 Smoothing in Markov-switching Models . . . . . . . . . . . . . . 86
4.2.2 Smoothing in Partially Observed Markov Chains . . . . . . 86
4.2.3 Marginal Smoothing in Hierarchical HMMs . . . . . . . . . . . 87
4.3 Forgetting of the Initial Condition . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.3.1 Total Variation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.3.2 Lip*****z Contraction for Transition Kernels . . . . . . . . . . . 95
4.3.3 The Doeblin Condition and Uniform Ergodicity . . . . . . . 97
4.3.4 Forgetting Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
4.3.5 Uniform Forgetting Under Strong Mixing Conditions . . . 105
4.3.6 Forgetting Under Alternative Conditions . . . . . . . . . . . . . 110
5 Applications of Smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.1 Models with Finite State Space . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.1.1 Smoothing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
5.1.2 Maximum a Posteriori Sequence Estimation . . . . . . . . . . 125
5.2 Gaussian Linear State-Space Models . . . . . . . . . . . . . . . . . . . . . . . 127
5.2.1 Filtering and Backward Markovian Smoothing . . . . . . . . 127
5.2.2 Linear Prediction Interpretation . . . . . . . . . . . . . . . . . . . . . 131
5.2.3 The Prediction and Filtering Recursions Revisited . . . . . 137
5.2.4 Disturbance Smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
5.2.5 The Backward Recursion and the Two-Filter Formula . . 148
5.2.6 Application to Marginal Filtering and Smoothing in
CGLSSMs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
6 Monte Carlo Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
6.1 Basic Monte Carlo Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
6.1.1 Monte Carlo Integration. . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
6.1.2 Monte Carlo Simulation for HMM State Inference . . . . . 163
6.2 A Markov Chain Monte Carlo Primer . . . . . . . . . . . . . . . . . . . . . . 166
6.2.1 The Accept-Reject Algorithm . . . . . . . . . . . . . . . . . . . . . . . 166
6.2.2 Markov Chain Monte Carlo . . . . . . . . . . . . . . . . . . . . . . . . . 170
6.2.3 Metropolis-Hastings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
6.2.4 Hybrid Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
6.2.5 Gibbs Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
6.2.6 Stopping an MCMC Algorithm. . . . . . . . . . . . . . . . . . . . . . 185
6.3 Applications to Hidden Markov Models . . . . . . . . . . . . . . . . . . . . 186
6.3.1 Generic Sampling Strategies . . . . . . . . . . . . . . . . . . . . . . . . 186
6.3.2 Gibbs Sampling in CGLSSMs . . . . . . . . . . . . . . . . . . . . . . . 194
7 Sequential Monte Carlo Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 209
7.1 Importance Sampling and Resampling. . . . . . . . . . . . . . . . . . . . . . 210
7.1.1 Importance Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
7.1.2 Sampling Importance Resampling . . . . . . . . . . . . . . . . . . . 211
7.2 Sequential Importance Sampling. . . . . . . . . . . . . . . . . . . . . . . . . . . 214
7.2.1 Sequential Implementation for HMMs . . . . . . . . . . . . . . . . 214
7.2.2 Choice of the Instrumental Kernel . . . . . . . . . . . . . . . . . . . 218
7.3 Sequential Importance Sampling with Resampling . . . . . . . . . . . 231
7.3.1 Weight Degeneracy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
7.3.2 Resampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
7.4 Complements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
7.4.1 Implementation of Multinomial Resampling . . . . . . . . . . . 242
7.4.2 Alternatives to Multinomial Resampling. . . . . . . . . . . . . . 244
8 Advanced Topics in Sequential Monte Carlo . . . . . . . . . . . . . . . 251
8.1 Alternatives to SISR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
8.1.1 I.I.D. Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
8.1.2 Two-Stage Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
8.1.3 Interpretation with Auxiliary Variables . . . . . . . . . . . . . . . 260
8.1.4 Auxiliary Accept-Reject Sampling . . . . . . . . . . . . . . . . . . . 261
8.1.5 Markov Chain Monte Carlo Auxiliary Sampling . . . . . . . 263
8.2 Sequential Monte Carlo in Hierarchical HMMs . . . . . . . . . . . . . . 264
8.2.1 Sequential Importance Sampling and Global Sampling . 265
8.2.2 Optimal Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
8.2.3 Application to CGLSSMs. . . . . . . . . . . . . . . . . . . . . . . . . . . 274
8.3 Particle Approximation of Smoothing Functionals . . . . . . . . . . . 278