Bayesian Nonparametric Learning of Complex Dynamical Phenomena by Emily B. Fox S.B., Electrical Engineering, Massachusetts Institute of Technology, 2004 M.Eng., Elect. Eng. and Comp. Sci., Massachusetts Institute of Technology, 2005 E.E., Electrical Engineering, Massachusetts Institute of Technology, 2008 Submitted to the Department of Electrical Engineering and Computer Science in partial fulfillment of the requirements for the degree of ARCHIES Doctor of Philosophy in Electrical Engineering and Computer Science MAS ACHUSETTS tNSTTiMJTF- OFTECHNOLOGY at the Massachusetts Institute of Technology September 2009 SEP 3 0 2009 @ 2009 Massachusetts Institute of Technology LIBRARIES All Rights Reserved. Signature of Author: Department f Electrical Engineering and Computer Science July 31, 2009 Certified by: Alan S. Willsky Edwin Sibley Webster Professor of Electrical Engineering and Computer Science Thesis Co-Supervisor Certified by. John W. Fisher III Principal Research Scientist / ,. Thesis Co-Supervisor Accepted by: Terry P. Orlando Professor of Electrical Engineering and Computer Science Chair, Committee for Graduate Students Bayesian Nonparametric Learning of Complex Dynamical Phenomena by Emily B. Fox To be submitted to the Department of Electrical Engineering and Computer Science in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy in Electrical Engineering and Computer Science Abstract The complexity of many dynamical phenomena precludes the use of linear models for which exact analytic techniques are available. However, inference on standard non- linear models quickly becomes intractable. In some cases, Markov switching processes, with switches between a set of simpler models, are employed to describe the observed dynamics. Such models typically rely on pre-specifying the number of Markov modes. In this thesis, we instead take a Bayesian nonparametric approach in defining a prior on the model parameters that allows for flexibility in the complexity of the learned model and for development of efficient inference algorithms. We start by considering dynamical phenomena that can be well-modeled as a hidden discrete Markov process, but in which there is uncertainty about the cardinality of the state space. The standard finite state hidden Markov model (HMM) has been widely applied in speech recognition, digital communications, and bioinformatics, amongst other fields. Through the use of the hierarchical Dirichlet process (HDP), one can examine an HMM with an unbounded number of possible states. We revisit this HDP- HMM and develop a generalization of the model, the sticky HDP-HMM, that allows more robust learning of smoothly varying state dynamics through a learned bias to- wards self-transitions. We show that this sticky HDP-HMM not only better segments data according to the underlying state sequence, but also improves the predictive per- formance of the learned model. Additionally, the sticky HDP-HMM enables learning more complex, multimodal emission distributions. We demonstrate the utility of the sticky HDP-HMM on the NIST speaker diarization database, segmenting audio files into speaker labels while simultaneously identifying the number of speakers present. Although the HDP-HMM and its sticky extension are very flexible time series mod- els, they make a strong Markovian assumption that observations are conditionally inde- pendent given the discrete HMM state. This assumption is often insufficient for captur- ing the temporal dependencies of the observations in real data. To address this issue, we develop extensions of the sticky HDP-HMM for learning two classes of switching I ------\----r-----i;-r~-i~r~--,_ ~i:~ n -r-.-~:----^-r--(~~~ ~i1l~~l~~li;~-~~~~; ~_i-: dynamical processes: the switching linear dynamical system (SLDS) and the switching vector autoregressive (SVAR) process. These conditionally linear dynamical models can describe a wide range of complex dynamical phenomena from the stochastic volatility of financial time series to the dance of honey bees, two examples we use to show the power and flexibility of our Bayesian nonparametric approach. For all of the presented models, we develop efficient Gibbs sampling algorithms employing a truncated approx- imation to the HDP that allows incorporation of dynamic programming techniques, greatly improving mixing rates. In many applications, one would like to discover and model dynamical behaviors which are shared among several related time series. By jointly modeling such sequences, we may more robustly estimate representative dynamic models, and also uncover in- teresting relationships among activities. In the latter part of this thesis, we consider a Bayesian nonparametric approach to this problem by harnessing the beta process to allow each time series to have infinitely many potential behaviors, while encouraging sharing of behaviors amongst the time series. For this model, we develop an efficient and exact Markov chain Monte Carlo (MCMC) inference algorithm. In particular, we exploit the finite dynamical system induced by a fixed set of behaviors to efficiently compute acceptance probabilities, and reversible jump birth and death proposals to explore new behaviors. We present results on unsupervised segmentation of data from the CMU motion capture database. Thesis Supervisors: Alan S. Willsky Professor of Electrical Engineering and Computer Science John W. Fisher III Principal Research Scientist Acknowledgments Everything should be made as simple as possible, but not simpler. attributed to Albert Einstein Aerodynamically the bumblebee shouldn't be able to fly, but the bumblebee doesn't know that so it goes on flying anyway. Mary Kay Ash This thesis marks the culmination of an intense though incredibly gratifying journey at MIT that started nearly a decade ago. I look fondly upon my years as an undergraduate student at the Institution, but it was my time as a graduate student that was the most formative and rewarding. Academically, this is in large part due to the interactions I had with my advisor, Professor Alan Willsky. Alan's incredible breadth and depth of knowledge have been an inspiration to me and of great importance in shaping the research contained in this thesis. No matter how many times I ventured away from the group's core areas, Alan was always right there still actively (and energetically!) following and providing context for the ideas. My co-advisor, Dr. John Fisher, has provided, in addition to many good laughs and distractions from work, illumination into my research through many insightful questions; he was also readily available to answer all of my many questions. In addition to my interactions with Alan and John, the other students in the Stochastic Systems Group (SSG), both past and present, have played a pivotal role in my graduate studies. My long-time officemates-Kush Varshney, Pat Kreidl, and Jason Williams-provided stimulating conversations and tolerated my incessant inter- ruptions. My new officemate, Matt Johnson, has quickly filled those shoes since Pat and Jason graduated. We have had many interesting discussions on Bayesian statistics and I look forward to continued collaborations. I also want to thank Myung Jin Choi, Venkat Chandrasekaran, Vincent Tan, and Ying Liu for enlivening SSG with Friday poker night and other group events. Along those lines, I thank members of CSAIL, such as Mike Siracusa, Gerald Dalley, Wanmei Ou, and Thomas Yeo, for sharing in "vulturing" trips and our ensuing lunch conversations. I am particularly indebted to Mike Siracusa who, in addition to many illuminating discussions on Markov switching processes, went above and beyond in helping me with computing issues. We made a fabulous, and seemingly automatic, grouplet and SSG seminar pairing. I must highlight Erik Sudderth, a former SSG member, for the exceptional guidance and mentoring he has provided me during my graduate studies. I can attribute my i _I _ ___ _(1_ __ _/_ ;I__~_~_~l_ __ i__iliijii~_ii__iLC_____~i~__~~;1_1_~ ~I~ ~il---_iini..-. ACKNOWLEDGMENTS exposure to Bayesian nonparametrics to Erik, who examined such methods during the latter part of his thesis. Although our collaborations started only after he left MIT, Erik has contributed significantly to the work presented herein. He has taught me a great deal about persistence (no pun intended regarding Chapter 3) and thorough analysis of results. My thesis committee, Professor Munzer Dahleh and Princeton University's Professor David Blei, also provided thoughtful suggestions that continue to guide my research and help make the work understandable to both the System Identification and Machine Learning communities. In addition to Alan's courses on recursive estimation and stochastic systems, Munzer's exceptional instruction of the course on dynamic systems and control was pivotal in building my foundation for studying the dynamical models presented in this thesis. I have also had the honor of working with Professor Michael Jordan at UC Berkeley. During my many visits to Berkeley, and through a massive number of emails, this bi- coastal collaboration has provided me with invaluable guidance on my work in Bayesian nonparametrics and insight into the fields of Machine Learning and Statistics. Addi- tionally, I am deeply indebted to Mike for his extensive editing of papers that comprise a good portion of this thesis. Another contributing factor outside of MIT's campus was my time interning at MIT Lincoln Laboratory, specifically working on target tracking, that set me on this hunt for flexible descriptions of Markov switching models. Without the inspiration of that application, and discussions with Keh Ping Duhn, David Choi, and Daniel Rudoy, I likely would not have taken the path I did. On a more personal note, I would like to thank my family for their support during my nine-year adventure 3,000 miles away from home. I would especially like to acknowledge my mom who has always supported my pursuits, however offbeat and incomprehensible they were to her (e.g., ice hockey, pole vaulting, and needless to say, anything having to do with math.) My stepdad, who has a Ph.D. in chemistry, has been a refuge at home in understanding logical reasoning while my dad has taught me the value of adventure and optimism. My siblings, Ben and Nathan, have each been there for me in incredible ways. I also must thank all of my friends, especially Melanie Rudoyl and Erin Aylward, for their never-ending support, encouragement, and distractions. Finally, this endeavor would have been infinitely more challenging without the love and support of Wes McKinney2. 1Yes, there are two Rudoys in one acknowledgments section. 2For him, I must thank Jim Munkres who taught the topology course in which we met. Contents Abstract Acknowledgments List of Figures List of Algorithms List of Tables Notational Conventions 1 Introduction 1.1 Thesis Organization and Overview of Methods and Contributions . . 1.1.1 Chapter 2: Background ....................... 1.1.2 Chapter 3: The Sticky HDP-HMM . ................ 1.1.3 Chapter 4: Bayesian Nonparametric Learning of SLDS ...... 1.1.4 Chapter 5: Sharing Features among Dynamical Systems with Beta Processes ............................ 1.1.5 Chapter 6: Contributions and Recommendations ......... 1.1.6 Appendices .............................. 2 Background 2.1 The Bayesian Framework .......................... 2.1.1 Modeling via Exchangeability . ................... 2.2 Exponential Families ............................. 2.2.1 Properties of the Canonical Exponential Family .......... 2.2.2 Interpretation as Linearly Constrained Maximum Entropy Dis- tribution ............................... 2.2.3 Examples ............................... 2.3 Sufficient Statistics .............................. 2.4 Incorporating Prior Knowledge ....................... 0 CONTENTS 2.4.1 Conjugate Priors . ............ . . . . 50 2.4.2 Multinomial Observations . . . . . . . . 52 2.4.3 Gaussian Observations . . . . . . . . .. 53 2.4.4 Multivariate Linear Regression Model . 55 2.5 Graphical Models ........... ...... 57 2.5.1 A Brief Overview . ............ 57 2.5.2 Directed Graphical Models . . . . . . . 58 2.5.3 Undirected Graphical Models ...... 60 2.5.4 Belief Propagation . ........... 62 2.6 Hidden Markov Model . ............. 66 2.6.1 Forward-Backward Algorithm ...... 67 2.6.2 Viterbi Algorithm . ........... 69 2.7 State Space Models ........ . .. .. 71 . . . . . . . . . . . . . 2.7.1 Standard Discrete-Time Linear-Gaussian State Space Formulation 71 2.7.2 Vector Autoregressive Processes ..... 72 . . . . .. . . . . . . . 2.7.3 Switching Linear Dynamic Systems ... 72 2.7.4 Stochastic Realization Theory ...... .S. ....s. . . . . . . . 73 2.7.5 Kalman Filtering and Smoothing . ... 76 . . . . . . . . . . ... 2.8 Markov Chain Monte Carlo . . . . . . . . ... 80 2.8.1 Monte Carlo Integration . ........ 80 2.8.2 The Metropolis-Hastings Algorithm . . 81 2.8.3 Gibbs Sampling ............. 83 . . . . . . . . . . . . 2.8.4 Auxiliary, Blocked, and Collapsed Gibbs Samplers ........ 86 2.9 Bayesian Nonparametric Methods ......... ...... .. . ... 91 2.9.1 Dirichlet Processes . . . . . . . . .... ... . . . . . . . .. 92 2.9.2 Dirichlet Process Mixture Models . . . . ..... . .. . . . . . .. 96 2.9.3 Hierarchical Dirichlet Processes ..... . . ... . . . . . . .. 98 2.9.4 Beta Process . . .............. ...... . ... .. 102 3 The Sticky HDP-HMM 107 3.1 The HDP-HMM and Its Sticky Extension . . . . . . . . . . . 109 3.1.1 Chinese Restaurant Franchise with Loyal Customers . . . 111 3.1.2 Sampling via Direct Assignments . . . . . . . . . . .. 114 3.1.3 Blocked Sampling of State Sequences . . . . . . . . . . . . 115 3.1.4 Hyperparameters ..... .................. 117 3.2 Experiments with Synthetic Data . . . . . . . . . . ... 117 3.2.1 Gaussian Emissions . .... ................. 119 3.2.2 Multinomial Emissions . . . . . . . . . . . . . ....... 124 3.2.3 Comparison to Independent Sparse Dirichlet Prior . . . . 125 3.3 Multimodal Emission Densities . . . . . . . . . ... 126 3.3.1 Direct Assignment Sampler . . . . . . . . ... 127 3.3.2 Blocked Sampler . ... ................... 128 CONTENTS U 3.4 Assessing the Multimodal Emissions Model . ............... 128 3.4.1 Mixture of Gaussian Emissions . .................. 128 3.5 Speaker Diarization ................... ... .. .. . . 132 3.6 Discussion and Future Work ................... ..... . 137 4 Bayesian Nonparametric Learning of SLDS 141 4.1 The HDP-SLDS and HDP-AR-HMM Models . .............. 143 4.1.1 Posterior Inference of Dynamic Parameters . ........... 145 Conjugate Prior on {A(k), (k)} .......... ......... 147 Alternative Prior - Automatic Relevance Determination . . . . 147 Measurement Noise Posterior ................... . . 152 4.1.2 Gibbs Sampler ........... ... . . . ....... . 153 Sampling Dynamic Parameters {A(k) , E(k) } ............ 153 Sampling Measurement Noise R (HDP-SLDS only) . ....... 154 Block Sampling zl:T . .................. ...... 154 Block Sampling X1:T (HDP-SLDS only) . ............. 154 Sequentially Sampling Zl:T (HDP-SLDS only) . .......... 155 4.2 Results ....... ............ . .......... 156 4.2.1 MNIW prior ................... ........ . 156 4.2.2 ARD prior ................... ......... . 160 4.2.3 Dancing Honey Bees ................... ...... 163 4.3 Model Variants ....... ..... .. . .... ......... 169 4.3.1 Shared Dynamic Matrix, Switching Driving Noise ......... 169 4.3.2 Fixed Dynamic Matrix, Switching Driving Noise . ........ 174 4.4 Discussion and Future Work ................... ...... 181 5 Sharing Features among Dynamical Systems with Beta Processes 183 5.1 Describing Multiple Time Series with Beta Processes . .......... 184 5.2 MCMC Methods for Posterior Inference . ................. 186 5.2.1 Sampling binary feature assignments . ............... 187 5.2.2 Sampling dynamic parameters and transition variables ...... 191 5.2.3 Sampling the IBP and Dirichlet transition hyperparameters . . . 192 5.3 Synthetic Experiments ................................. . 194 5.4 Motion Capture Experiments . .................. ..... 198 5.5 Discussion and Future Work ................... ...... 203 6 Contributions and Recommendations 205 6.1 Summary of Methods and Contributions . ................. 205 6.2 Suggestions for Future Research ................... .... 207 6.2.1 Inference on Large-Scale Data ................... . 207 6.2.2 Alternative Dynamic Structures . ................. 208 6.2.3 Bayesian Nonparametric Variable-Order Markov Models ..... 209 6.2.4 Alternatives to Global Clustering . ................. 210 i lU CONTENTS 6.2.5 Asymptotic Analysis . .................. .... .. 210 A Sticky HDP-HMM Direct Assignment Sampler 213 A.1 Sticky HDP-HMM .................. . . . . . 213 A.1.1 Sampling zt .................. . . . . . 213 A.1.2 Sampling ................... .... . 217 A.1.3 Jointly Sampling mjk, wjt, and jk . . . . . . . . . 218 A.2 Sticky HDP-HMM with DP emissions ....... . . . . . 220 B Sticky HDP-HMM Blocked Sampler 223 B.1 Sampling P, w, and .......................... 223 B.2 Sampling Zl:T for the Sticky HDP-HMM ................ 224 B.3 Sampling (zl:T, Sl:T) for the Sticky HDP-HMM with DP emissions . 224 B.4 Sam pling 0 ....... .. ....................... 225 B.4.1 Non-Conjugate Base Measures ................. 225 C Hyperparameters 227 C.1 Posterior of (a + ) ........................ . . . . . 227 C.2 Posterior of y ........ ................... . . . . . 229 C.3 Posterior of o ....... .................... . . . . . 230 C.4 Posterior of p ........ ................... . . . . . 231 D HDP-SLDS and HDP-AR-HMM Message Passing 233 D.1 Mode Sequence Message Passing for Blocked Sampling . . . . 233 D.2 State Sequence Message Passing for Blocked Sampling . ... 234 D.3 Mode Sequence Message Passing for Sequential Sampling 237 E Derivation of Maneuvering Target Tracking Sampler 243 E.1 Chinese Restaurant Franchise ....... ........... 244 E.2 Normal-Inverse-Wishart Posterior Update ........... 244 E.3 Marginalization by Message Passing . ...... ....... 245 E.4 Combining Messages . ...................... 245 E.5 Joining Distributions that Depend on ut . . . . . . . . .. 248 E.6 Resulting (ut, zt) Sampling Distributions . . . . . . . . .. 248 F Dynamic Parameter Posteriors 251 F.1 Conjugate Prior - MNIW . . . . . . . . . . . . .. 251 F.2 Non-Conjugate Independent Priors on A(k), E(k), and f(k) . . 254 F.2.1 Normal Prior on A(k) . ..... ............ 254 F.2.2 Inverse Wishart Prior on E(k) . ..... ........ 255 F.2.3 Normal Prior on p(k) .. ... ............... 255 Bibliography 257