Keynote Speakers

Seiya Imoto (University of Tokyo)

Title: Constraint Optimal Search on Learning Bayesian Network Structure

Abstract: Classical approaches used to learn Bayesian network structure from data have disadvantages in terms of complexity and lower accuracy of their results. However, a recent empirical study has shown that a hybrid algorithm improves sensitively accuracy and speed: it learns a skeleton with an independency test (IT) approach and constrains on the directed acyclic graphs (DAG) considered during the search-and-score phase. Subsequently, we theorize the structural constraint by introducing the concept of super-structure S, which is an undirected graph that restricts the search to networks whose skeleton is a subgraph of S. We develop a super-structure constrained optimal search (COS): its time complexity is upper bounded by O(γmn), where γn < 2 depends on the maximal degree of S. Empirically, complexity depends on the average degree and sparse structures allow larger graphs to be calculated. Our algorithm is faster than an optimal search by several orders and even finds more accurate results when given a sound super-structure. Practically, S can be approximated by IT approaches; significance level of the tests controls its sparseness, enabling to control the trade-off between speed and accuracy. For incomplete super-structures, a greedily post-processed version (COS+) still enables to significantly outperform other heuristic searches. We also study an extension of COS. The COS algorithm remains limited even for sparse superstructures. To extend its feasibility, we propose to divide the super-structure into several clusters and perform an optimal search on each of them. Further, to ensure acyclicity, we introduce the concept of ancestral constraints (ACs) and derive an optimal algorithm satisfying a given set of ACs. Finally, we theoretically derive the necessary and sufficient sets of ACs to be considered for finding an optimal constrained graph. Empirical evaluations demonstrate that our algorithm can learn optimal Bayesian networks for some graphs containing several hundreds of vertices, and even for super-structures having a high average degree (up to four), which is a drastic improvement in feasibility over the previous optimal algorithm. Learnt networks are shown to largely outperform state-of-the-art heuristic algorithms both in terms of score and structural hamming distance.

Biography: Seiya Imoto is currently an associate professor of Human Genome Center, Institute of Medical Science, the University of Tokyo. He received the B.S., M.S., and Ph.D. degrees in mathematics from Kyushu University, Japan, in 1996, 1998 and 2001, respectively. His current research interests cover statistical analysis of high dimensional data by Bayesian approach, biomedical information analysis, microarray gene expression data analysis, gene network estimation and analysis, data assimilation in biological networks and computational drug target discovery.

Arthur Choi (UCLA)

Title: A Brief History of Belief Propagation

Abstract: Approximation algorithms for reasoning in Bayesian networks have seen wide applicability and successes in fields as diverse as artificial intelligence, machine learning, information theory, and statistical physics. Iterative belief propagation (IBP) in particular has in the past decade been one the most influential algorithms for approximate inference, enabling a number of applications, and further inspiring numerous generalizations and derivatives. In this talk, we provide a brief history of this influential algorithm from over the past few decades. We further highlight some of the more recent research results in analyzing, improving and applying iterative belief propagation, from UCLA's Automated Reasoning Group. This includes some recent successes in the UAI'10 probabilistic inference challenge.

Biography: Arthur Choi obtained his B.S. degree in computer science from Cornell University, Ithaca, New York, and his M.S. and Ph.D. degrees in computer science from the University of California, Los Angeles. He is currently a member of the Automated Reasoning Group, at UCLA. Arthur Choi's research interests include exact and approximate reasoning in Bayesian networks and probabilistic graphical models.

Adnan Darwiche (UCLA)

Title: Relax, Compensate and then Recover: A Theory of Anytime, Approximate Inference

Abstract: I will present in this talk a theory of anytime, approximate inference, which explains some of the most influential algorithms in probabilistic reasoning, yet is based on one of the older ideas in symbolic reasoning: Relaxations. According to this theory, the fundamental notion of approximation is that of "relaxing" logical constraints (equalities in particular) for the purpose of decomposing a problem into smaller pieces that can be solved independently. A second fundamental notion is that of "compensation", which calls for imposing weaker and, typically, probabilistic notions of equality to compensate for the relaxed equalities. The third fundamental notion of the presented theory is that of "recovery," where some of the relaxed equalities are incrementally recovered, based on an assessment of their impact on improving the quality of approximations. I will discuss how this theory subsumes one of the most influential algorithms in probabilistic inference: loopy belief propagation and some of its generalizations. I will also discuss the relationship between this theory and current developments in symbolic reasoning―in particular, how advances in knowledge compilation can impact the state of the art in approximate (and exact) probabilistic inference.

Biography: Dr. Darwiche is a professor and chairman of the computer science department at UCLA. He obtained his M.S. and Ph.D. degrees in computer science from Stanford University in 1989 and 1993, respectively. Dr. Darwiche is also the Editor in Chief for the Journal of Artificial Intelligence Research (JAIR) and a AAAI Fellow. Dr. Darwiche's research interests include probabilistic and symbolic reasoning, with their application to diagnosis, planning, and cognition, in addition to system design and analysis. His teaching interests include graduate and undergraduate courses in Artificial Intelligence, Probabilistic Reasoning, and Symbolic Reasoning. Dr. Darwiche directs the Automated Reasoning Group at UCLA.

Petri Myllymäki (University of Helsinki)

Title: Towards Objective Learning of Bayesian Networks

Abstract: Bayesian networks are popular probabilistic parametric models that are defined through acyclic directed graphs where the nodes represent the domain variables and the connecting edges define a set of conditional independence assumptions that restrict the set of probability distributions that can be represented by the model. We address the problem of learning such structures from data, and focus on the objective (non-informative) case where very little or no prior information is available about the domain the data is from. In this talk this problem is tackled by a scoring-based approach where the problem is split into two intertwined sub-tasks: the first task is to formulate a theoretically justifiable scoring function that defines a goodness criterion on the set of all possible Bayesian network structures, and the second task is to develop computationally feasible optimization algorithms that can find the optimal (or at least a good) model with respect to the selected goodness criterion. For solving the first task, we present an information-theoretic approach based on Rissanen’s Minimum Description Length (MDL) framework, and contrast it to the standard Bayesian approach based on the marginal likelihood criterion. We also briefly discuss recent optimization algorithms that have been developed for solving the second task.

Biography: Petri Myllymäki obtained his M.Sc. and Ph.D. degrees in Computer Science at University of Helsinki, where he became a Docent in computer science in 1999. Dr. Myllymäki is one of the co-founders and the current leader of the Complex Systems Computation (CoSCo) research group, and he has over 20 years of experience in research in the area of intelligent systems. His current special research interests are focused on Bayesian and information-theoretic modeling, in particular with Bayesian networks and other probabilistic models. He has been an editorial board member, program chair/committee member and reviewer for numerous international scientific journals, conferences and organizations, and he has published over 100 scientific articles in his research area. He is co-founder of Ekahau Inc. and has also been responsible for several applied research projects with other companies including Nokia, Elisa, BayesIT, M-Brain, Kone, StoraEnso, Space Systems Finland/European Space Agency, ABB and AlmaMedia, and the industrial co-operation has lead to a number of fielded applications and patents. Dr. Myllymäki is a professor at the Department of Computer Science of University of Helsinki, and he is also working as a programme director at Helsinki Institute for Information Technology (HIIT), a joint research institute of University of Helsinki and Aalto University.