Priberam Machine Learning Lunch Seminar
Speaker: Mário Figueiredo (IT)
Venue: IST Alameda, Sala PA2 (Edifício de Pós-Graduação)
Date: Tuesday, December 14th, 2010
Time: 13:00
Lunch will be provided
Title: Network Inference from Co-occurences
Abstract:
Inferring network structures is a central problem arising in numerous fields of science and technology, including communication systems, biology, sociology, and neuroscience. Unfortunately, it is often difficult, or impossible, to obtain data that directly reveal the underlying network structure, and so one must infer a network from incomplete data. In this talk, we will look at the problem of inferring network structure from ``co-occurrence" observations.
These observations identify which network components (e.g., switches and
routers, in a communications network, or genes, in a gene regulatory network) co-occur in a path, but do not indicate the order in which they occur in that path. Without order information, the number of networks that are consistent with the data grows exponentially with the size of the network (i.e., the number of nodes). Yet, the basic engineering/evolutionary principles underlying most
networks strongly suggest that not all networks consistent with the observations are equally likely. In particular, nodes that often co-occur are probably closer than nodes that rarely co-occur. This rationale suggests modeling co-occurrence observations as independent realizations of a Markovian random walk on the network, subjected to a random permutation to account for the lack of order information. Treating permutations as missing data, allows deriving
an expectation-–maximization (EM) algorithm for estimating the random walk parameters. The model and EM algorithm significantly simplify the problem, but the computational complexity of the reconstruction process does grow exponentially in the length of each transmission path. For networks with long paths, the exact E-step may be computationally intractable. We thus propose a polynomial-time Monte Carlo EM algorithm based on importance sampling and derive conditions that
ensure convergence of the algorithm with high probability. Finally, we
report simulations and experiments with Internet measurements and inference of biological networks that demonstrate the promise of this approach.
The work reported in this talk was done in collaboration with Prof.
Michael Rabbat (McGill University, Canada) and Prof. Robert D. Nowak (University of Wisconsin, USA).
--
Bio: Mário A. T. Figueiredo received EE, MSc, PhD, and "Agregado"
degrees in electrical and computer engineering, all from Instituto Superior Técnico (IST), Technical University of Lisbon (TULisbon), Portugal, in 1985, 1990, 1994, and 2004, respectively. Since 1994, he has been with the faculty of the Department of Electrical and Computer
Engineering, IST. He is also area and group coordinator at Instituto de
Telecomunicações, a private not-for-profit research institution. Mário
Figueiredo spent sabbatical leaves at the Department of Computer Science
and Engineering, Michigan State University, and the Department
of Electrical and Computer Engineering, University of Wisconsin-Madison,
in 1998 and 2005, respectively. He is a Fellow of the IEEE and of the IAPR (International Association for Pattern Recognition) and a member of the Image, Video, and Multidimensional Signal Processing Technical Committee of the IEEE.
Mário Figueiredo's scientific interests include image processing and analysis, pattern recognition, statistical learning, and optimization. He received the 1995 Portuguese IBM Scientific Prize and the 2008 UTL/Santander-Totta Scientific Prize. He is/was associate editor of the following journals: IEEE Transactions on Image Processing, IEEE Transactions on Pattern Analysis and Machine Intelligence (IEEE-TPAMI), IEEE Transactions on Mobile Computing, Pattern Recognition Letters, and Signal Processing. He is/was guest co-editor of special issues of the IEEE-TPAMI, the IEEE Transactions on Signal Processing, and the IEEE Journal of Selected Topics in Signal Processing. Mário Figueiredo was a co-chair of the 2001 and 2003 Workshops on Energy Minimization Methods in Computer Vision and Pattern Recognition, and has served as a member of organizing/program/technical/scientific committees of many
international conferences, including ICIP, ICASSP, CVPR, ICML,
ICPR, NIPS, IGARSS, MLSP, IJCNN, and others.
