Algebraic Geometry of Hidden Markov and Related Models

This thesis embodies a collection of algebraic techniques and results on hidden Markov models, related models in quantum physics called Matrix Product State models, and finally discrete directed acyclic graphical models.;Chapter 1 explores the statistical problems of model selection and parameter identifiability from the perspective of algebraic geometry, in the case of hidden Markov models (HMMs) where all the hidden random variables are binary. Its main contributions are (1) a new parametrization for every such HMM via a birational map with an explicit inverse for recovering the hidden parameters in terms of observables, (2) a semialgebraic model membership test to determine if a discrete probability distribution can arise from such an HMM, and (3) minimal defining equations for the set of probability distributions arising from the 4-node fully binary model, com- prising 21 quadrics and 29 cubics, which were computed using Gröbner bases in the cumulant coordinates of Bernd Sturmfels and Piotr Zwiernik. The new model parameters in (1) are rationally identifiable in the sense of Seth Sullivant, Luis David Garcia-Puente, and Sarah Spielvogel, and each model's Zariski closure is therefore a rational projective variety of dimension 5. Gröbner basis computations for the model and its graph are found to be considerably faster using these parameters. In the case of two hidden states, (2) supersedes a previous algorithm of Alexander Schönhuth which is only generically defined, and the defining equations (3) yield new invariants for HMMs of all lengths ≥ 4. Such invariants have been used successfully in model selection problems in phylogenetics, and one can hope for similar applications in the case of HMMs.;In Chapter 2, we study the representational power of matrix product states (MPS) with binary virtual bonds for entangled qubit systems. We do this by giving polynomial expressions in a pure quantum state's amplitudes which hold if and only if the state is a translation invariant matrix product state or a limit of such states. For systems with few qubits, we give these equations explicitly, considering both periodic and open boundary conditions. Using the classical theory of trace varieties and trace algebras, we explain the relationship between MPS and hidden Markov models and exploit this relationship to derive useful parameterizations of MPS. We present four conjectures on the identifiability of MPS parameters.;Chapter 3 develops new parameters for use with directed acyclic graphical (DAG) models on discrete variables, which can simplify symbolic computations for tree models with hidden variables having more than two states. This development is the first step toward generalizing work of Smith and Zwiernik on binary trees, and makes it possible for some of the techniques used in Chapters 1 and 2 to be applied to graphical models with variables having more than two states.