[talks] 4:30pm Tue Apr 29 talk by Robert Nowak on network inference
Jennifer Rexford
jrex at CS.Princeton.EDU
Fri Apr 25 11:55:28 EDT 2008
*Speaker: *Robert Nowak, Professor of Engineering at the University
of Wisconsin-Madison
*Date: *Tuesday, April 29th
*Time: *4:30pm
*Room: *B205 ~ Equad
*Title: *Network Inference from Co-Occurrences
*Abstract: *The discovery of networks is a fundamental problem
arising in numerous fields of science and engineering, including
communication systems, biology, sociology, and neuroscience.
Unfortunately, it is often difficult to obtain data that directly reveal
network structure, and so one must infer a network from incomplete data.
This paper considers inferring network structure and transmission
pathways from ``co-occurrence'' data; observations that identify which
network components (e.g., routers, proteins) carry each transmission but
do not indicate the order in which they handle the transmission. Without
order information, the number of networks that are consistent with the
data grows exponentially with the size of the network. Yet, the basic
engineering/ evolutionary principles underlying most networks strongly
suggest that not all data-consistent networks are equally likely. In
particular, network components that co-occur in many observations are
probably closely connected. With this in mind, we model the
co-occurrence observations as independent realizations of a random walk
on the network graph, subjected to random permutations which account for
the lack of order information. The network can be estimated using this
model and the Maximum Likelihood (ML) criterion. The computational
complexity of direct ML estimation is combinatorial in the size of the
network, and so we derive a more efficient approach using an
Expectation-Maximization (EM) algorithm. The EM algorithm complexity is
combinatorial in the length of the transmission pathways, rather than
the size of the entire network. This is a significant improvement, but
the computational cost of the EM algorithm is still prohibitive for
large networks. For large-scale network inference, we propose a
polynomial-time Monte Carlo version of the EM algorithm which is
guaranteed to converge with high probability. Applications arising in
telecommunications, natural language processing, and systems biology
will be discussed.
* *
*Bio: *Robert Nowak received the B.S. (with highest distinction),
M.S., and Ph.D. degrees in electrical engineering from the University of
Wisconsin-Madison in 1990, 1992, and 1995, respectively. He was a
Postdoctoral Fellow at Rice University in 1995-1996, an Assistant
Professor at Michigan State University from 1996-1999, held Assistant
and Associate Professor positions at Rice University from 1999-2003, and
was a Visiting Professor at INRIA in 2001. Dr. Nowak is now the
McFarland-Bascom Professor of Engineering at the University of
Wisconsin-Madison. He has served as an Associate Editor for the IEEE
Transactions on Image Processing, and is currently an Associate Editor
for the ACM Transactions on Sensor Networks and the Secretary of the
SIAM Activity Group on Imaging Science. He has also served as a
Technical Program Chair for the IEEE Statistical Signal Processing
Workshop and the IEEE/ACM International Symposium on Information
Processing in Sensor Networks. Dr. Nowak received the General Electric
Genius of Invention Award in 1993, the National Science Foundation
CAREER Award in 1997, the Army Research Office Young Investigator
Program Award in 1999, the Office of Naval Research Young Investigator
Program Award in 2000, and IEEE Signal Processing Society Young Author
Best Paper Award in 2000. His research interests include statistical
signal processing, machine learning, imaging and network science, and
applications in communications, bio/medical imaging, and systems biology.
More information about the talks
mailing list