# Maximum Likelihood Degrees and Critical Points Mini-Symposium

Information

Main Conference: SIAM Conference on Applied Algebraic Geometry

Date: August 3 to August 07, 2015

Location: NIMS and KAIST, Daejeon, Korea

Maximum likelihood estimation (MLE) is a fundamental problem in statistics. The maximum likelihood degree (ML-degree) of a statistical model gives an algebraic measure of the MLE's complexity. The ML-degree can be phrased as the number of critical points of the likelihood function for general data on the model. In this mini-symposium, we will have presentations on ML-degrees, Euclidean distance degrees, and methods to compute critical points.

Schedule

Tues. Aug. 4, 10:30—12:30. NIMS 1.

Xiaoxian Tang, Jose Israel Rodriguez, Serkan Hosten, Elizabeth Gross

Thurs. Aug. 6, 15:30—17:30. CAMP 1.

June Huh, Hwangrae Lee, Pierre­Jean Spaenlehauer, Mohab Safey EI Din

Fri. Aug. 7, 10:30—12:30. NIMS 1.

Fatemeh Mohammadi, Caroline Uhler, Piotr Zwiernik, Paolo Lella

Organizers

Jose Israel Rodriguez, Notre Dame.

Xiaoxian Tang, NIMS.

Speakers

Elizabeth Gross, San Jose State University.

Serkan Hosten, San Francisco State University.

June Huh, Princeton.

Hwangrae Lee, Pohang University of Science and Technology.

Paolo Lella, University of Trento.

Fatemeh Mohammadi, Institute of Science and Technology Austria.

Jose Israel Rodriguez, Notre Dame.

Mohab Safey El Din, Universite Pierre et Marie Curie (Paris 6).

Pierre-Jean Spaenlehauer, Inria Nancy Grand-Est.

Xiaoxian Tang, NIMS.

Caroline Uhler, Institute of Science and Technology Austria.

Piotr Zwiernik, University of California Berkeley.

Abstracts

Elizabeth Gross, San Jose State University.

Title: Model Selection in Systems Biology with Numerical Algebraic Geometry

Abstract: Researchers from scientific and medical disciplines are often interested in whether their hypotheses, translated into mathematical models, are compatible with available data. Model selection and hypothesis testing requires knowledge of parameter and variable values which are usually unavailable. Estimation of such parameters and hidden variables is a nonlinear optimization problem, which amounts to solving a system of polynomial equations. In this talk, we will present a systematic framework for determining if a mathematical model given by a polynomial system of first-order differential equations is compatible with limited data (i.e., unknown parameters or variables, and noisy data) using methods from numerical algebraic geometry.

This is joint work with Daniel Bates, Brent Davis, Heather Harrington, and Kenneth Ho.

Serkan Hosten, San Francisco State University.

ML Degree of Toric Models in Algebraic Statistics

The ML Degree of a toric variety is the Euler characteristic of a hypersurface associated to the log-likelihood function in that toric variety. Despite this general result, computing the ML degree of specific toric varieties is a challenge. We will report on progress for computing the ML degree of toric and related varieties that appear in algebraic statistics, such as hierarchical log-linear models.

June Huh, Princeton.

The likelihood correspondence and the maximum likelihood degree of the reciprocal linear forms

The critical points of a product of powers of polynomial functions are parametrized by a “likelihood correspondence”. In the special case of linear polynomials, one can recover the Poincaré polynomial of the associated complex hyperplane arrangement complement from the homology class of this variety in its natural embedding. We prove an analogous formula for the reciprocal plane, that is, the image of the arrangement complement under the reciprocal map, by computing its Chern-Schwartz-MacPherson class.

Joint work with Graham Denham.

Hwangrae Lee, Pohang University of Science and Technology.

Title: Euclidean Distance Degrees of Multiple Root Loci

Abstract : Univariate polynomials of a fixed degree form a projective space, and polynomials having a root of fixed multiplicity form a projective subvariety. We determine the Euclidean distance degree for such a variety, in both special and generic coordinates, and we present an algorithm for solving the ED problem exactly.

This is joint work with Bernd Sturmfels.

Paolo Lella, University of Trento.

Title: The maximum likelihood degree of Fermat hypersurfaces

Abstract: We study the critical points of the likelihood function over the Fermat hypersurface. This is a nice example of how algebro-geometric tools can contribute to the problem of maximum likelihood estimation. In particular, using a flat degeneration we show that the ML degree of the Fermat hypersurface can be determined considering special data on the model. Then, we exploit symmetries subdividing the problem into parallel subtasks and we develop algorithmic methods that allow to compute the ML degree in many cases.

Joint work with Daniele Agostini, Davide Alberelli and Francesco Grande.

Fatemeh Mohammadi, Institute of Science and Technology Austria.

Title: A family of quasisymmetry models

Abstract: We present a one-parameter family of models for square contingency tables that interpolates between the classical quasisymmetry model and its Pearsonian analogue. Algebraically, this corresponds to deformations of toric ideals associated with graphs. Moreover we show that these models belong to a broader class of $\phi$-divergence QS models. Measures of divergence quantify the distance between two probability distribution. Our discussion of the statistical issues centers around maximum likelihood estimation.

The talk is based on joint work with Maria Kateri and Bernd Sturmfels.

Jose Israel Rodriguez, Notre Dame.

Title: Maximum Likelihood for Dual Varieties

Abstract: Maximum likelihood estimation (MLE) is a fundamental computational problem in statistics. In particular, MLE for statistical models with discrete data can studied from an algebraic statistics viewpoint. In this talk, we review such a viewpoint and give a formulation for maximum likelihood estimation in terms of dual varieties. With this description, the dual likelihood equations are defined. We show that solutions to the dual likelihood equations yields solutions for MLE.

Mohab Safey El Din, Universite Pierre et Marie Curie (Paris 6).

Title: On the Degree of Generalized Polar Varieties

Abstract: We consider the critical points of the restriction of a polynomial function to an algebraic set. These critical points are solutions of the defining equations of the considered algebraic set and minors of some jacobian matrix. This system defines a so-called generalized polar variety. Intrinsic estimates of the degree of this variety are of first importance. We essentially relate this degree to the degrees of the polar classes of the algebraic set under consideration. We also show how to obtain an algorithm that computes the critical locus in time which is polynomial in its cardinality.

Joint work with Pierre-Jean Spaenlehauer.

Pierre-Jean Spaenlehauer, Inria Nancy Grand-Est.

Title: Exact solutions in Structured Low-Rank Approximation

Abstract: Structured low-rank approximation is the problem of minimizing a weighted Frobenius distance to a given matrix among all matrices of fixed rank in a linear space of matrices. We study the critical points of this optimization problem from the viewpoint of exact algebraic algorithms and algebraic geometry. In particular, an indicator of the complexity of Gröbner bases algorithms and homotopy methods is the algebraic degree of this problem. This corresponds to the Euclidean Distance degree of a linear section of a determinantal variety. Using algebraic geometry, we present bounds on this degree in several cases. A particular focus lies on Hankel matrices, Sylvester matrices and generic linear spaces.

Joint work with Giorgio Ottaviani and Bernd Sturmfels.

Xiaoxian Tang, NIMS.

Title: Data-Discriminants of Likelihood Equations

Abstract: Maximum likelihood estimation (MLE) is a fundamental computational problem in statistics. An algebraic approach is to solve a very structured parameterized polynomial system called likelihood equations. The only solutions of the likelihood equations that are statistically meaningful are the positive solutions. In order to classify the data according to the number of real/positive solutions, we define the data-discriminant for the likelihood equations. We develop an algebraic probability 1 algorithm for computing data-discriminants. Experimental results show that, for the benchmarks we have tried, the algebraic probability 1 algorithm is more efficient than the standard elimination algorithm. Based on the computational results, we propose the real root classification conjecture for the 3 by 3 symmetric matrix model.

Joint work with Jose Israel Rodriguez

Caroline Uhler, Institute of Science and Technology Austria.

Title: Parameter estimation for linear Gaussian covariance models

Linear Gaussian covariance models are Gaussian models with linear constraints on the covariance matrix. Such models arise in many applications, such as stochastic processes from repeated time series data, Brownian motion tree models used for phylogenetic analyses and network tomography models used for analyzing the connections in the Internet. Maximum likelihood estimation in this model class leads to a non-convex optimization problem that typically has many local maxima. However, I will explain that the log-likelihood function is in fact concave over a large region of the positive definite cone. Using recent results on the asymptotic distribution of extreme eigenvalues of the Wishart distribution I will show that running any hill-climbing method in this region leads to the MLE with high probability.

This is joint work with Piotr Zwiernik and Donald Richards.

Piotr Zwiernik, University of California Berkeley.

Title: Brownian Motion Tree Models and their Geometry

Abstract: EA Brownian motion tree model on a tree T is a special Gaussian model closely linked to the graphical model on T, where the inner nodes are not observed. In this talk, I will present various ways of estimation for this model class both when T is known and when it is not known. Some of these results date back to Felsenstein (1971), but I will show how a geometric and algebraic understanding can give additional insight into the estimation process. Finally, I will discuss how to apply these results for estimating a phylogenetic tree for fruit flies.