Conference Agenda

Overview and details of the sessions of this conference. Please select a date or location to show only sessions at that day or location. Please select a single session for detailed view (with abstracts and downloads if available).

 
Session Overview
Session
MS139, part 2: Combinatorics and algorithms in decision and reason
Time:
Friday, 12/Jul/2019:
3:00pm - 5:00pm

Location: Unitobler, F-121
52 seats, 100m^2

Presentations
3:00pm - 5:00pm

Combinatorics and algorithms in decision and reason

Chair(s): Liam Solus (KTH Royal Institute of Technology, Sweden), Svante Linusson (KTH Royal Institute of Technology)

Combinatorial, or discrete, structures are a fundamental tool for modeling decision-making processes in a wide variety of fields including machine learning, biology, economics, sociology, and causality. Within these various contexts, the goal of key problems can often be phrased in terms of learning or manipulating a combinatorial object, such as a network, permutation, or directed acyclic graph, that exhibits pre-specified optimal features. In recent decades, major break-throughs in each of these fields can be attributed to the development of effective algorithms for learning and analyzing combinatorial models. Many of these advancements are tied to new developments connecting combinatorics, algebra, geometry, and statistics, particularly through the introduction of geometric and algebraic techniques to the development of combinatorial algorithms. The goal of this session is to bring together researchers from each of these fields who are using combinatorial or discrete models in data science so as to encourage further breakthroughs in this important area of mathematical research.

 

(25 minutes for each presentation, including questions, followed by a 5-minute break; in case of x<4 talks, the first x slots are used unless indicated otherwise)

 

On the Graphs of Graphical Models

Rina Dechter
Donald Bren School of Information and Computer Sciences, UC Irvine

Graphical models, including constraint networks, Bayesian networks, Markov random fields and influence diagrams, have become a central paradigm for knowledge representation and reasoning in artificial intelligence, and provide powerful tools for solving problems in numerous application areas. Reasoning over probabilistic graphical models typically involves answering inference queries, such as computing the most likely configuration (maximum a posteriori or MAP) or evaluating the marginals or the normalizing constant of a distribution (the partition function). Exact computation of such queries is known to be intractable in general, yet, the underlying graphs of graphical models provide a powerful tool that allow exploiting the problems structure in reasoning algorithms. In this talk I will provide an overview of how such graph parameters (e.g., tree-width, height, w-cutset) interact in their role for bounding graphical models complexity.

 

Causal Inference with Unknown Intervention Targets

Yuhao Wang
Massachusetts Institute of Technology

We consider the problem of estimating causal DAG models from a mix of observational and interventional data, when the intervention targets are partially or completely unknown. This problem is highly relevant for example in genomics, since gene knockout technologies are known to have off-target effects. In this paper, we characterize the interventional Markov equivalence class of DAGs that can be identified from interventional data with unknown intervention targets. In addition, we propose the first provably consistent algorithm for learning the interventional Markov equivalence class from such data. The proposed algorithm greedily searches over the space of permutations to minimize a novel score function. The algorithm is nonparametric, which is particularly important for applications to genomics, where the relationships between variables are often non-linear and the distribution non-Gaussian. We demonstrate the performance of our algorithm on synthetic and biological datasets.

 

On attempts to characterize facets of the chordal graph polytope

Milan Studeny
Academy of Sciences of the Czech Republic

Our idea of integer linear programming approach to structural learning decomposable graphical models, which are models described by undirected chordal graphs, is to encode them by special zero-one vectors, named characteristic imsets. It leads to the study of a special polytope, defined as the convex hull of all characteristic imsets for chordal graphs we name the chordal graph polytope (Studeny and Cussens; 2017). The talk will be devoted to the attempts to characterize theoretically all facet-defining inequalities for this polytope in order to utilize that in ILP-based procedures for learning decomposable models.