*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.