Order Determination for Hidden Markov and Related Models

Harvard University, Cambridge MA

Investigators

Abstract

Hidden Markov models (HMMs) are powerful tools for processing time series data and are widely used in scientific and engineering applications, including speech recognition, machine translation, computational biology, cryptanalysis, and finance. The fundamental components of an HMM include the noisy observations and the corresponding hidden states. In most applications, the number of hidden states (the order of the HMM) is not known beforehand but conveys important information about the underlying process. For example, in molecular biology, the total number of hidden states may be the number of distinct 3D conformations of a protein; in chemistry, the total number of hidden states may be the number of distinct chemical species in an organic reaction. This project plans to investigate order determination for HMMs, finite mixture models, and hierarchical HMMs; the latter two models are special cases and extensions of HMMs. The project aims to develop a consistent and competitive method for order selection. In addition to a thorough theoretical investigation, comprehensive numerical studies and applications in biology and chemistry will be conducted. The project will not only significantly advance the theoretical understanding of HMMs, but also provide powerful tools for researchers to analyze data. The data applications will help advance molecular biology and biochemistry. The project also aims to support and train undergraduate and graduate students, with special attention being given to recruiting students from under-represented groups into statistics and related fields. Education at the undergraduate and graduate levels will be integrated into the research activities. The project will establish the marginal likelihood method as a consistent and competitive order selection method for HMMs, finite mixture models, and hierarchical HMMs. Five research studies will be carried out, enumerated as follows. (1) Investigate the order of HMMs, where the goal is to identify and develop consistent methods for HMM order determination. (2) Investigate order selection issues in finite mixture models. Finite mixture models can be reformulated as special types of HMMs. The goal is to develop a method for consistently estimating the number of mixture components. (3) Investigate order determination of hierarchical HMMs, where multiple HMMs are linked through a hierarchical structure. The aim here is to identify and develop consistent methods for determining the order of hierarchical HMMs, taking special effort to address the challenging issue that multiple HMMs often have quite diverse characteristics, such as lengths. (4) Study computational challenges and investigate and implement efficient computational methods for the order determination of HMM and related models, including the implementation and release of an open source, publicly available R package. (5) Apply the new method to ion channel data and single-molecule data on co-translational protein targeting. The PI also plans to develop courses that introduce and guide students in HMMs, mixture models, and hierarchical HMMs. The success of the proposed research will develop a theoretical basis and associated methodology for consistent order determination of HMMs and related models. The research achievements and the education components will broadly impact the analysis of HMMs, hierarchical HMMs, and model selection and also help train a new generation of scholars and researchers in the field. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.