Tuesday, March 1, 2016 - 12:00
Statistical Methods for Differential Network Analysis
Speaker: Ali Shojaie (UW)
Location: CSE 305
Recent evidence suggests that changes in biological networks, e.g., rewiring or disruption of key interactions, may be associated with development of complex diseases. These findings have motivated new research initiatives in computational and experimental biology that aim to obtain condition-specific estimates of biological networks, e.g. for normal and tumor samples, and identify differential patterns of connectivity in such networks, known as "differential network analysis”.
In this talk, I will present new methods based on graphical models and statistical learning, to jointly learn networks of interactions among components of biological systems in heterogeneous populations, and to formally test whether the observed differences in interaction patterns are statistically significant or are due to randomness in estimation procedures.
Tuesday, February 16, 2016 - 12:00
Deep Neural Network for Fast Object Detection and Newtonian Image Understanding
Speaker: Mohammad Rastegari (AI2)
Location: CSE 305
In this talk, I introduce G-CNN, an object detection technique based on Convolutional Neural Networks (CNNs), which works without proposal algorithms. G-CNN starts with a multi-scale grid of fixed bounding boxes. We train a regressor to move and scale elements of the grid towards objects iteratively. G-CNN models the problem of object detection as finding a path from a fixed grid to boxes tightly surrounding the objects. G-CNN with around 180 boxes in a multi-scale grid performs comparably to Fast R-CNN which uses around 2K bounding boxes generated with a proposal technique. This strategy makes detection faster by removing the object proposal stage as well as reducing the number of boxes to be processed. Next, I discuss on a challenging problem of predicting the dynamics of objects in static images. Given a query object in an image, our goal is to provide a physical understanding of the object in terms of the forces acting upon it and its long term motion as response to those forces. Direct and explicit estimation of the forces and the motion of objects from a single image is extremely challenging. We define intermediate physical abstractions called Newtonian scenarios and introduce Newtonian Neural Network (N3) that learns to map a single image to a state in a Newtonian scenario.
Tuesday, February 2, 2016 - 12:00
Structured Learning Algorithms for Entity Linking and Semantic Parsing
Speaker: Ming-Wei Chang, Microsoft Research
Location: CSE 305
Recent advances on natural language processing have made a lot of impact to the fields of information extraction and retrieval. Specifically, tasks like entity linking and semantic parsing are crucial to search engine applications such as question answering and document understanding. These tasks often require structured learning models, which make predictions on multiple interdependent variables. In this talk, we argue that carefully designed structured learning algorithms play a crucial role for entity linking and semantic parsing. In particular, we will first present structured learning models for entity linking, where the models jointly detect mentions and disambiguate entities. We then show that a novel staged search procedure for question semantic parsing can significantly improve knowledge base question answering systems. Finally, I will discuss some challenges and opportunities for machine learning techniques for general semantic parsing tasks.
Tuesday, January 12, 2016 - 12:00
Discovering Hidden Structure in the Sparse Regime
Speaker: Sham Kakade
Location: Gates Commons
In many applications, we face the challenge of modeling the hidden interactions between multiple observations (e.g. discovering clusters of points in space or learning topics in documents). Furthermore, an added difficulty is that our datasets often have empirical distributions which are heavy tailed tailed (e.g. problems in natural language processing). In other words, even though we have large datasets, we are often in a sparse regime where there is a large fraction of our items that have only been observed a few times (e.g. Zipf's law which states that regardless of how big our corpus of text is, a large fraction of the words in our vocabulary will only be observed a few times). The question we consider is how to learn a model of our data when our dataset is large and yet is sparse.
We provide an algorithm for learning certain natural latent variable models applicable to this sparse regime, making connections to a body of recent work in sparse random graph theory and community detection. We also discuss the implications to practice.
Tuesday, June 2, 2015 - 12:30
Statistical machine learning methods for the analysis of large networks
Speaker: Edo Airoldi
Location: CSE 305
Network data -- i.e., collections of measurements on pairs, or tuples, of units in a population of interest -- are ubiquitous nowadays in a wide range of machine learning applications, from molecular biology to marketing on social media platforms. Surprisingly, assumptions underlying popular statistical methods are often untenable in the presence of network data. Established machine learning algorithms often break when dealing with combinatorial structure. And the classical notions of variability, sample size and ignorability take unintended connotations. These failures open to door to a number of technical challenges, and to opportunities for introducing new fundamental ideas and for developing new insights. In this talk, I will review open statistical and machine learning problems that arise when dealing with large networks, mostly focusing on modeling and inferential issues, and provide an overview of key technical ideas and recent results and trends.
Edo Airoldi received a PhD from Carnegie Mellon University in 2007, working at the intersection of statistical machine learning and computational social science with Stephen Fienberg and Kathleen Carley. His PhD thesis explored modeling approaches and inference strategies for analyzing social and biological networks. Until December 2008, he was a postdoctoral fellow in the Lewis-Sigler Institute for Integrative Genomics and the Department of Computer Science at Princeton University working with Olga Troyanskaya and David Botstein. They developed mechanistic models of regulation, leveraging of high-thoughput technology, to gain insights into aspects of cellular dynamics that are not directly measurable at the desired resolution, such as growth rate. He joined the Statistics Department at Harvard University in 2009.
Tuesday, May 19, 2015 - 12:30
Diverse Particle Selection for High-Dimensional Inference in Graphical Models
Speaker: Erik Sudderth, Brown University
Location: CSE 305
Rich graphical models for real-world scene understanding encode the shape and pose of objects via high-dimensional, continuous variables. We describe a particle-based max-product inference algorithm which maintains a diverse set of posterior mode hypotheses, and is robust to initialization. At each iteration, the set of particle hypotheses is augmented via stochastic proposals, and then reduced via an optimization algorithm that minimizes distortions in max-product messages. Our particle selection metric is submodular, and thus efficient greedy algorithms have rigorous optimality guarantees. By avoiding the stochastic resampling steps underlying standard particle filters, we also avoid common degeneracies where particles collapse onto a single hypothesis. Our approach significantly outperforms previous particle-based algorithms in the estimation of human pose from single images, and the prediction of protein side-chain conformations.
Erik B. Sudderth is an Assistant Professor in the Brown University Department of Computer Science. He received the Bachelor's degree (summa cum laude, 1999) in Electrical Engineering from the University of California, San Diego, and the Master's and Ph.D. degrees (2006) in EECS from the Massachusetts Institute of Technology. His research interests include probabilistic graphical models; nonparametric Bayesian methods; and applications of statistical machine learning in computer vision and the sciences. He received an NSF CAREER award, and was named one of "AI's 10 to Watch" by IEEE Intelligent Systems Magazine
Wednesday, May 6, 2015 - 12:30
Graphical Modeling with the Bethe Approximation
Speaker: Tony Jebara, Department of Computer Science, Columbia University
Location: Room CSE 305, Allen Center
Inference (a canonical problem in graphical modeling)
recovers a probability distribution over a subset of variables in a given
model. It is known to be NP-hard for graphical models with cycles and
large tree-width. Learning (another canonical problem) reduces to
iterative marginal inference and is also NP-hard. How can we
efficiently tackle these problems in practice? We will discuss the
Bethe free energy as an approximation to the intractable partition
function. Heuristics like loopy belief propagation (LBP) are often
used to optimize the Bethe free energy. Unfortunately, in general, LBP
may not converge at all, and if it does, it may not be to a global
optimum. To do marginal inference, we instead explore a more
principled treatment of the Bethe free energy using discrete
optimization. We show that in attractive loopy models we can find the
global optimum in polynomial time even though the resulting landscape
is non-convex. To generalize to mixed loopy models, we use
double-cover methods that bound the true Bethe global optimum in
polynomial time. Finally, to do learning, we combine Bethe
approximation with a Frank-Wolfe algorithm in the convex dual which
circumvents the intractable partition function. The result is a new
single-loop learning algorithm which is more efficient than previous
double-loop methods that interleaved iterative inference with
iterative parameter updates. We show applications of these methods in
friendship link recommendation, in social influence estimation, in
computer vision, and in power networks. We also combine the approaches
with sparse structure learning to model several years of Bloomberg
data. These graphical models capture financial and macro-economic
variables and their response to news and social media topics.
Tuesday, January 27, 2015 - 12:30
Degree, curvature, and mixing of random walks on the phylogenetic subtree-prune-regraft graph, and what it tells us about phylogenetic inference via MCMC
Speaker: Erick Matsen, Fred Hutchinson Cancer Research Center http://matsen.fhcrc.org/
Location: CSE 305
Statistical phylogenetics is the inference of a tree structure representing evolutionary history using biological sequence data (such as from DNA) under a likelihood model of sequence evolution. All such inferences perform either heuristic search or Markov chain Monte Carlo (MCMC) on a graph built with the various trees as vertices and edges representing tree modifications. Because this graph is connected with nonzero transition probabilities, MCMC is guaranteed to work in the large time limit, although inference using a finite number of steps is determined by mixing properties of MCMC on the graph. However, almost nothing is known about the large-scale structure of, or properties of random walks on, the relevant graphs. In this talk, I will first demonstrate significant graph effects on phylogenetic inference using the subtree-prune-regraft (SPR) graph, which is a popular such graph involving reconnection of subtrees of a tree in a different location. I will then recap what is known about degrees in the SPR graph and describe our work on Ricci-Ollivier curvature for representative pairs of phylogenetic trees, and give evidence that degree and curvature essentially determine the behavior of the simple lazy random walk on the SPR graph.
This work is joint with my postdoc Chris Whidden.
Tuesday, January 13, 2015 - 12:30
Driving Time Variability Prediction Using Mobile Phone Location Data
Speaker: Dawn Woodard, Cornell University
Location: CSE 305
We introduce a method to predict the variability in (probability distribution of) driving time on an arbitrary route in a road network at a given time, using mobile phone GPS data. Although commercial mapping services currently provide a high-quality estimate of driving time on a given route, there can be considerable uncertainty in that prediction due for example to unknown timing of traffic signals, uncertainties in traffic congestion levels, and differences in driver habits. For this reason, a distribution prediction can be more valuable than a deterministic prediction of driving time, by accounting not just for the measured traffic conditions and other available information, but also for the presence of unmeasured conditions that also affect driving time. Accurate distribution predictions can be used to report variability to the user, to provide risk-averse route recommendations, and as a part of vehicle fleet decision support systems. Simple approaches to distribution prediction assume independence in driving time across road segments and as a result dramatically underestimate the variability in driving time. We propose a method that accurately accounts for dependencies in
driving time across road segments, and apply it to large volumes of mobile phone GPS data from the Seattle metropolitan region.
Tuesday, November 4, 2014 - 12:30
Speaker: Yi Chang, Yahoo! Research
Location: CSE 305