Algebraic Statistics Seminar, Spring 2014

Organizational notes:
The seminar/reading group usually meets Wednesdays at 3:30; though the room is reserved 3:15-4:45pm. We may start a few minutes earlier or later from time to time; this will be announced in the schedule.
Sign up for the seminar mailing list here.

Date & Time Location Speaker/Title
Wednesday, Jan 29,
3:30 pm
E1 121 Organizational meeting.

Main reading topics chosen: 2/12 and 2/19, we will read the papers that explain in detail Theorem 1.2.17 in "Lecture notes in algebraic statistics" book. These papers are about transportaion polytopes and implications for Markov bases for tables. Then, we will continue with discussion of Graver bases, and encoding graph properties with ideals (specifics later). Furhter topics will be chosen in March or April.

Wednesday, Feb 12,
3:30 pm
E1 121 Dane Wilburne, IIT Applied Math
Reading/discussion: Integer programming, transportation problems, tables, and Markov bases.

Despina and Dane are leading the discussion of the following paper: All linear and integer programs are slim 3-way transportation programs by De Loera and Onn.
See also this survey paper (arXiv:1307.0124) and this summary of applications to Markov bases (additional reference: arXiv:math/0207200).

(For those who didn't attend Fall 2013 seminar, and wish to look up relevant background on Markov bases, see Sections 1.1. and 1.2. of "lecture notes in algebraic statistics", and also "Algebraic algorithms for sampling from conditional distributions" (Diaconis-Sturmfels '98) - link to the paper was posted on the Fall 2013 page, and the book is available online (pdf).)

Wednesday, Feb 19,
3:30 pm
E1 121 Despina Stasi, IIT Applied Math
Reading/discussion: Integer programming, transportation problems, tables, and Markov bases.
Continued from 2/12.
We will be focusing on the construction in the proof of the main theorem and one of its important consequences for Markov bases. As a reference for the latter please see: Markov bases of three-way tables are arbitrarily complicated, (De Loera and Onn 2006).

Wednesday, Feb 26,
3:30 pm
E1 121 Hisayuki Hara, Niigata University, Japan.
Implementation of Markov basis Technologies

The methodology of Markov basis initiated by Diaconis and Sturmfels (1998) stimulated active research on Markov bases for more than a decade. It also motivated improvements of algorithms for Gr\"obner basis computation for toric ideals, such as those implemented in 4ti2. At present, however, explicit forms of Markov bases are known only for some relatively simple models, such as the decomposable models of contingency tables. Furthermore general algorithms for Markov bases computation often fail to produce Markov bases even for moderate-sized models in a practical amount of time. Hence so far we could not perform exact tests based on Markov basis methodology for many important practical problems. In this talk we introduce some alternative methods for running Markov chain instead of using a Markov basis. The first one is to use a Markov subbasis for connecting only practical fibers. The second one is to use a lattice basis which is an integer kernel of a design matrix. We also discuss connecting tables whose cell counts are restricted to zero or one by using Graver basis.

(Note: Prof. Hara is visiting us for a few days; note that he is an author of the "Markov bases in Algebraic Statistics" book.)

Wednesday, Mar 5,
3:30 pm
E1 121 Despina Stasi, Applied Mathematics, Illinois Institute of Technology.
The beta model for hypergraphs and its connection to some open discrete problems

We define and study the beta model for hypergraphs, an exponential family of probability distributions for hypergraphs, whose natural sufficient statistic vector is the degree sequence of the hypergraph.

Wednesday, Mar 12,
3:30 pm
E1 121 Dane Wilburne, IIT Applied Math
Working seminar
k-core decomposition of a graph

**Monday, Mar 24
4:40 pm
LS 152 Bernd Sturmfels, University of California, Berkeley
The Euclidean Distance Degree
Applied Mathematics Colloquium

The nearest point map of a real algebraic variety with respect to Euclidean distance is an algebraic function. The Euclidean distance degree is the number of critical points of this optimization problem. We focus on varieties seen in engineering applications, and we discuss exact computational methods. Our running example is the Eckart-Young Theorem which states that the nearest point map for low rank matrices is given by the singular value decomposition.
This is joint work with Jan Draisma, Emil Horobet, Giorgio Ottaviani, Rekha Thomas.
Wednesday, Apr 2,
**4:40 pm
E1 121 Charles Wampler, Technical Fellow, General Motors Research and Development Center, Warren, MI
Numerical Real Algebraic Geometry with Applications to Kinematics
Applied Mathematics Colloquium

Recently, numerical algorithms have been developed for computing cell decompositions of the real points in complex algebraic curves and surfaces. These algorithms operate in the spirit of Morse theory by introducing a real projection and using numerical algebraic geometry to find the critical sets where the topology of the real fibers of the projection change. After slicing the set between critical points to get the generic behavior in each interval, one uses continuation to the critical points to determine how the pieces glue together to make the whole set. After a brief review of the state of the art in this approach, we will concentrate on how these methods apply to several examples from the kinematics of mechanism design and robot control. The methods have general applicability wherever polynomial systems arise, such as in chemistry, biology, statistics, and economics. The underlying algorithms are freely available in an open-source software package, Bertini, co-authored by the speaker.

Wednesday, Apr 9,
3:30 pm
E1 121 Kawkab Alhejoj, IIT Applied Math
Algebraic statistics and phylogenomics: an introduction

Emerging field of phylogenomics integrates two major disciplines: genomics (the study of the structure and function of genes and genomes) and phylogenetics (the study of the hierarchical evolutionary relationships among organisms and their genomes). The goal of phylogenomics is to identify the common ancestry of organisms and understand their evolution through analysis of genomes.
This presentation has three parts: we will begin by reviewing the hypothesis testing ( chi-square test). Second part offers definitions of the relevant biological terminology. In Part three we describe a simple example of a statistical model for inferring information about the genetic code.

Wednesday, Apr 16,
3:30 pm
E1 121 Jose Rodriguez, University of California, Berkeley
Numerical Algebraic Geometry for Maximum Likelihood Estimation

Numerical algebraic geometry is a growing area of applied algebra that involves describing solutions of polynomial systems of equations. This area has already had an impact in kinematics, statistics, PDE's, and pure math. In this talk we focus on using numerical algebraic geometry for maximum likelihood estimation in algebraic statistics.
In the first half, we will introduce a concrete example and develop background information. In the second half, we present computational results consisting of Maximum Likelihood degrees for matrices with rank constraints and present the surprising theoretical result of maximum likelihood duality.

Wednesday, Apr 23,
3:30 pm
E1 121 Dane Wilburne, IIT Applied Math
The polynomial method in combinatorial optimization: Connections to semi-definite programming and algebraic geometry

The goal of this talk is to explore the polynomial method and relate this topic to the course material in Math 535. Broadly speaking, we will study how to encode combinatorial optimization problems in terms of systems of polynomial equations, how a famous result in algebraic geometry guarantees the existence of a certificate of infeasibility if a given problem is infeasible, and how this allows us to appeal to the well-understand theory of semi-definite programming to solve our given combinatorial optimization problem. We will also discuss results concerning the computational complexity of the certificate of infeasibility.
Main reference: arXiv:0706.0578.

Wednesday, Apr 30,
3:30 pm
E1 121 David Haws, IBM Research
Polyhedral approaches to learning Bayesian networks

This talk will cover descriptions of probabilistic conditional independence (CI) models and learning graphical models which has applications in biology (epistasis, gene regulatory networks, protein signaling, systems biology), Markov random processes, probabilistic reasoning, artificial intelligence and more. Given observed data, the goal is to find the CI structure which best explains the data. I will motivate the problem with some interesting biological applications. Next, I will quickly overview graphical approaches to the description of CI structures. Then, I will describe an algebraic description of CI structures introduced by Studeny et al. which has many elegant properties, suitable for applications of linear programming methods. The remainder of the talk will be devoted to linear optimization approaches to learning Bayesian networks, which are special graphical models.

Speaker bio: David Haws is currently a Postdoctoral Researcher at IBM T.J. Watson Research Center in the Computational Genomics group. David recieved his Ph.D. in Mathematics from U.C. Davis working in the area of combinatorial optimaztion and polyhedral geometry. David's current interests includes, machine learning, genomic selection, graphical models, computational genomics & biology, phylogenetics, polyhedral geometry, and topological data analysis. In general his research lies in the intersection of applications, algorithms, and theory and binding these topics together is a deep knowledge of data analysis and computation.

May 19-22 WH:Auditorium An international conference on algebraic statistics, AS2014, will take place right here on campus!
See website for schedule, details, contact information, registration, etc. IIT graduate students who are interested in helping out with the conference will have registration fees waived. Contact Prof. Petrović for more details.

Previous semesters: Fall 2013.
For More Information Contact: Sonja Petrović or Despina Stasi