Algebraic Statistics in Europe
Mikhail Belkin: Algebraic-geometric methods for learning Gaussian mixture models
The study of Gaussian mixture distributions goes back to the late 19th century, when Pearson introduced the method of moments to analyze the statistics of a crab population. They have since become one of the most popular tools of modeling and data analysis, extensively used in speech recognition and other fields. Yet their properties are still not well understood. Widely used algorithms, such as Expectation Maximization (EM) often fail even on simple generated data and their theoretical properties are often unclear. In my talk I will discuss certain theoretical aspects of the problem of learning Gaussian mixtures. In particular, I will discuss our recent result, which, in a certain sense, completes work on an active recent topic in theoretical computer science by establishing quite general conditions for polynomial learnability of mixtures by using techniques of algebraic geometry.
Cristiano Bocci: Advances in model identifiability: Bernoulli, tensors, and beyond
In this talk I will show how the concept of weakly-defective varieties can give informations on the identifiability of statistical models. Then, using these varieties, I will show some recent result that improves previous bounds on the identifiability of Bernoulli and other statistical models.
Manfred Deistler: Generalized linear dynamic factor models - the single and the mixed frequency case
We consider generalized linear dynamic factor models. These models have been developed recently and they are used for high dimensional time series in order to overcome the “curse of dimensionality”. We present a structure theory with emphasis on the zeroless case, which is generic in the setting considered. Modelling of the latent variables is decomposed into two steps, first the transformation of the latent variables to static factors by a linear static transformation. Then, in the second step, modelling of the static factors as a possibly singular autoregressive process. The (generalized) Yule–Walker equations are used for parameter estimation. The Yule–Walker equations do not necessarily have a unique solu- tion in the singular case, and the resulting complexities are examined with a view to find a stable and coprime system. Finally, some preliminary results for the mixed frequency case are presented.
This is joint work with B.D.O. Anderson, E. Felsenstein, B. Funovits, and M. Zamani.
Alex Engstroem: Higher connectivity and expansion of fiber graphs of Gröbner bases
The Metropolis-Hastings algorithm is commonly employed to run random walks on graphs to estimate different statistics. Properties of the underlying graph will determine the efficiency of the algorithm. Diaconis and Sturmfels invented a method to use fiber graphs of Gröbner bases in this context. These graphs are connected, but more refined structural information is missing in general.
A graph is k-connected if you have to remove at least k vertices to have it fall apart. The minimal degree of a graph is an upper bound for the connectivity. I have conjectured that this bound is realized for fiber graphs of reduced Gröbner bases, and I will discuss two results supporting the conjecture. The first is by my student Samu Potka, who has proven it for graphs from contingency tables. The second result is that large fiber graphs essentially have a huge part that is D/2-connected where D is the maximal degree. Maximal -- not minimal!
I will also report on results on expansion properties of fiber graphs.
Robin Evans: Algebraic constraints on marginalized DAGs
Directed acyclic graphs (DAGs) are a popular tool for modelling because they impose simple conditional independence constraints, their modular structure lends itself to computational efficiency, and they link easily to causal methods. However if some of the variables in a DAG are unobserved, the simplicity of these constraints is lost: in particular, we may encounter algebraic (equality) constraints on the joint distribution which do not correspond to conditional independences, as well as semi-algebraic (inequality) constraints. In this talk we focus on the former.
We provide a class of graphs, called mDAGs, which is sufficient to describe the set of possible models induced by marginalizing a DAG, whilst making no assumption about the state space of the unobserved variables. We define a suitable Markov property for this class. Previously known algebraic constraints on this class of models consist of conditional independences and so-called Verma constraints.
Models defined by these algebraic constraints have recently been described in the work of Richardson, Robins and Shpitser, using their nested Markov property. In a large class of mDAG models, called decomposable, we characterize the algebraic constraints induced by the mDAG Markov property, finding that they consist of precisely the same constraints as the nested Markov property. Therefore the nested Markov model is 'complete' in these cases, in the sense that it represents all algebraic constraints. We also see that in non-decomposable models, any algebraic constraints missed by the nested Markov property must have a character quite distinct from conditional independences and Verma constraints.
Jesus Fernandez: An approach to phylogenetics by means of algebraic geometry
In phylogenetics, the goal is to reconstruct the ancestral relationships among organisms. These relationships are represented by means of a phylogenetic tree, whose interior nodes represent ancestors of the current species. Nowadays, large amount of data obtained by sequencing the genomes of the species is available and the field of phylogenetics tries to infer phylogenetic trees relating a group of species from their DNA sequences.
Biologists and mathematicians have contributed to reconstructing these phylogenetic trees, but many theoretical questions still remain open. The use of algebraic and geometric tools can help to solve some of these questions. Phylogenetic reconstruction tools often use a molecular model of evolution on a tree. We will recall how these evolutionary models lead naturally to algebraic varieties. Then we will try to understand how the polynomials vanishing on these varieties can contribute to phylogenetic reconstruction and how tools from algebraic geometry and group theory can assist to the understanding of more theoretical questions, as identifiability or model selection problems.
The results of the talk are taken from [PS05], [CFS07], [CFS08], [CFS11], [KDGC], [CKFS11].
[CFS07] M Casanellas and J Fernández-Sánchez. Performance of a new invariants method on homogeneous and nonhomogeneous quartet trees. Mol. Biol. Evol., 24(1):288-293, 2007.
[CFS08] M Casanellas and J Fernández-Sánchez. Geometry of the Kimura 3-parameter model. Adv.in Appl. Math, 41:265-292, 2008.
[CFS11] M Casanellas and J Fernández-Sánchez. Relevant phylogenetic invariants of evolutionary models. Journal de Mathamatiques Pures et Appliques, Volume 96, Issue 3, 2011, 207–229
[CKFS11] M Casanellas, A Kedzierska, and J Fernández-Sánchez. The space of phylogenetic mixtures of equivariant models. Preprint, 2012.
[KDGC] A Kedzierska, M Drton, R Guig o, and M Casanellas. SPIn: model selection for phylogenetic mixtures via linear invariants. Mol. Biol. Evol., 29(3): 929-937, 2012
[PS05] L Pachter and B Sturmfels, editors. Algebraic Statistics for computational biology. Cambride University Press, November 2005. ISBN 0-521-85700-7.
Christian Haase: Some facets of marginal polytopes
Raymond Hemmecke: Graver bases for N-fold 4-block matrices
In this talk we consider Graver bases for certain structured matrices that arise as problem matrices in integer programming. The structure of the Graver bases allows the construction of a poly-time algorithm for certain separable convex minimization problems. From a statistical point of view, one can use these Graver bases efficiently for sampling, although their sizes increase exponentially with N.
Stephan Huckeman: Asymptotic inference under curvature: circles, tree and shape spaces
Data on manifold (stratified) spaces are abundant, e.g. (three dimensional landmark) shape spaces (and phylogenetic tree spaces). Intrinsic zero and higher dimensional data descriptors live again on manifold (stratified) spaces. The intrinsic mean is just a point in the original space, a geodesic first principal component is a point in a space of geodesics, etc. Inference on such descriptors is based on determining their asymptotic distribution.
The classical central limit theorem (CLT) states that suitably translated and root n rescaled independent sample means tend to a multivariate Gaussian. Essentially under three conditions this translates to manifold stratified spaces: Uniqueness, manifold stability (i.e. that the mean is assumed on the highest dimensional stratum) and omitting of the cut locus (i.e. no mass near the cut locus of the mean). We investigate "manifold stability" on shape and tree spaces and "omitting the cut locus" on circles.
Franz Kiraly: Matrix completion
Matrix Completion is the estimation task of reconstructing a matrix of known rank from a fixed subset of its entries, possibly measured with noise. It is of high applied interest, for example applied as recommendation or prediction strategy in low-rank parametric models.
In my talk, I will present the problem of Matrix Completion and show how it is generatively algebraic and combinatoric. By using basic methods from algebraic geometry, I will derive an algebraic formulation of the matrix completion problem and show how the problem is parameterized by the combinatorics. I will show how this can be used to derive novel theoretical results on the identifiability of matrix completion, and novel algebraic combinatoric algorithms to address the problem.
Abraham Martin del Campo: Normality of the Toric Homogeneous Markov Chain model
In 2011, Hara and Takemura suggested a Markov Chain Monte Carlo (MCMC) approach to a goodness-of-fit test using Markov bases on the toric homogeneous Markov chain (THMC) model and gave a full description of the Markov bases for the two-state THMC model which does not depend on time. Inspired by their work, we studied algebraic and combinatorial properties of the toric homogeneous Markov chain model. In particular, we give a bound on the number of vertices of the polytope associated to the model which does not depend on the time. Based on our computations, we also conjecture the stabilization of the f-vector of the polytope, analyze the normality of the semigroup, and give conjectural bounds on the degree of the Markov bases.
Hugo Maruri-Aguilar: The algebraic method for experimental designs
Continuing on the seminal work of Gianni Pistone and Henry Wynn, we have recently explored different ways of describing models stemming from algebra in experimental designs. A simple description of a model is given by its weighted total degree, and another recent description of a model is given in terms of the complexity of the model border. We describe and present in some detail when these two descriptions coincide.
This is joint work with Henry Wynn (LSE) and Eduardo Saenz (La Rioja).
Fero Matus: On models given by conditional independence constraints
Conditional independence constraints have been credited for providing meaningful definitions of families of multivariate discrete or Gaussian probability distributions. If such a family has additional properties it can be sometimes described in more detail. We will recall a few instances of results in this directions and related open problems of algebraic flavor. The talk will be based mostly on the manuscript "On conditional independence and log-convexity" (http://www.imstat.org/aihp/accepted.html).
Giovanni Pistone: Examples of toric models for Markov chains
Fabio Rapallo: Max-plus objects to study the complexity of graphs
Given an undirected graph $G$, we define a new object $H_G$, called the mp-chart of $G$, in the max-plus algebra. We use it, together with the max-plus permanent, to describe the complexity of graphs. We show how to compute the mean and the variance of $H_G$ in terms of the adjacency matrix of $G$ and we give a central limit theorem for $H_G$. Finally, we show that the mp-chart is easily tractable also for the complement graph.
Johannes Rauh: Positive margins and primary decomposition
(joint work with T. Kahle and S. Sullivant)
We study random walks on contingency tables with fixed marginals, corresponding to a (log-linear) hierarchical model. If the set of allowed moves is not a Markov basis, then there exist tables with the same marginals that are not connected. We study linear conditions on the values of the marginals that ensure that all tables in a given fiber are connected. We show that many graphical models have the positive margins property, which says that all fibers with strictly positive marginals are connected by the quadratic moves that correspond to conditional independence statements.
Tamas Rudas: Log-linear models without an overall effect
Log-linear models without an overall effect arise naturally in machine learning (feature selection), in many problems of official statistics (e.g., the analysis of congenital abnormalities) or in market research (market basket analysis). Some of the properties of these families of distributions are quite surprising, both from the algebraic and the stochastic points of view. Algebraically, the models can be expressed using a set of generalized odds ratios, out of which there is exactly one that is non-homogeneous. Poisson and multinomial likelihoods under such models are not equivalent, sufficient statistics are not preserved in the maximum likelihood estimates, and the existence of a factorization of a model does not imply likelihood independence of the components. Computing maximum likelihood estimates under the models without an overall effect is not straightforward, as the standard IPF or GIS algorithms do not apply and IIS, used in machine learning, may produce erroneous results. A new generalization of the IPF algorithm is presented that gives the MLEs and also parameter estimates, for these models.
This is joint work with Anna Klimova (University of Washington)
Eduardo Saenz De Cabezon Irigaray: Algebraic analysis of system reliability
Every coherent system has an associated monomial ideal. The study of the algebraic structure of the ideal gives us a method for evaluating the reliability of the system. In this talk we will present the basics of the method, its advantages and drawbacks together with some results obtained on several relevant systems.
Milan Stehlik: The algebraic methods for extremes
During the talk we will discuss the algebraic basis for extreme modelling and inference. In particular we will show the importance of groups for inference function. Also we will discuss the group of max-automorphisms on R in relation to asymptotic behavior of order statistics. Examples will be given.
Milan Studeny: Remarks on integer linear programming approach to learning graphical models
The basic idea of a geometric approach to statistical learning graphical models is to represent them by certain special integral vectors (= lattice points). The talk will be about learning Bayesian network structure from (complete) data(base) by the method of score-maximization. Specifically, if the vector representative is chosen properly, it allows one to re-formulate the task of finding the global maximum of the score over BN structures as an integer linear programming problem. I will review some recent attempts at learning Bayesian network structure by the integer-linear programming approach and indicate what are relevant (open) mathematical questions or (implementation) problems to be solved.
Volkmar Welker: Partial orders from statistical ranking model
In this talk we discuss two directions for extend statistical ranking models to a prediction of a partially ordered set. First, we study algebraic aspects of ranking models under constraints (joint work with Sturmfels). Second, we study the expressivity of ranking models under thresholding (joint with Cheng, Huellermeier, Waegeman).
Piotr Zwiernik: Group structures for Gaussian models of chain graphs without flags
In our previous project we analysed the group of linear transformations which stabilizes a given Gaussian model of an undirected graph. This group was then used in the analysis of
robustness of arbitrary equivariant estimators. In the present project we generalize this work to arbitrary chain graphs without flags, which includes both the undirected graphs and directed acyclic graphs. The main obstacle is that typically more than one chain graph defines the same model. We show that the structure of the group is relatively simple but it requires passing to the unique maximal chain graph without flags, which was discussed for example by Milan Studený and Alberto Roverato. We then show that this can be made more efficient for directed acyclic graphs using their structural imsets.