February 2013 - talks - lists.cs.princeton.edu

Colloquium Speaker Floraine Berthouzoz Mon March 4, 4:30pm
by Nicole E. Wagenblast 04 Mar '13

04 Mar '13

Procedural Instructions for People and Machines Floraine Berthouzoz , University of California, Berkeley Monday, March 4, 2013, 4:30pm Computer Science, 105 Procedural tasks such as following a recipe or editing an image are very common. They require a person to execute a sequence of operations (e.g. chop the onions, or sharpen the image) and people commonly use step-by-step tutorials to learn these tasks. We focus on the domain of photo manipulations and have developed tools and techniques to help people learn, compare and automate photo manipulation procedures. We present a demonstration-based system for automatically generating succinct step-by-step visual tutorials of photo manipulations. Our tutorials are quick to generate. Moreover, users are faster and make fewer errors with our tutorials compared to book and video tutorials. We also demonstrate a new interface that allows learners to browse, analyze and compare large collections (i.e. thousands) of photo manipulation tutorials based on their command-level structure. Finally, we present a framework for generating content-adaptive macros (programs) that can transfer complex photo manipulation procedures to new target images. Together these tools allow people to learn, compare and automate procedural knowledge. Floraine Berthouzoz is a Ph.D. candidate in the Computer Science Department at the University of California, Berkeley. Her research lies at the intersection of computer graphics and human-computer interactions, and aims at building tools that ultimately make it faster and easier for people to create high quality visual content. She has also developed a number of techniques that improve the way people learn procedural instructions. She is the recipient of a 2009 ETH Medal of Honor and a 2010 Google Anita Borg Memorial Scholarship. During her graduate studies, Floraine worked as a visiting researcher at the University of Tokyo, the Hebrew University, Columbia University and Adobe Systems. Floraine also co-founded CS KickStart, an outreach program for incoming undergraduate women. Since 2011, this program has significantly increased the number of undergraduate women pursuing computer science degrees at Berkeley.

1 1

A Bell preFPO
by Melissa M. Lawson 28 Feb '13

28 Feb '13

Ana Bell will present her preFPO on Friday March 1 (this Friday) at 10AM in room 302 (note room). The members of her committee are: Olga Troyanskaya, advisor; Mona Singh and Andrea LaPaugh, readers; Kai Li and Tom Funkhouser, nonreaders. Everyone is invited to attend her talk. Her abstract follows below. ----- Original Message ----- Title and Abstract: Integrating Genomic Data to Build Mechanistic Networks for Genes and Small Molecules The recent increase in interest in mining biological data has spurred the aggregation of genomic data from various model organisms into numerous databases. We want to integrate the data available for one of the more well studied organisms, saccharomyces cerevisiae (yeast), and to build mechanistic networks that present interactions between proteins and compounds (small molecules) so that we can accurately predict drug targets. To that end, we apply machine learning algorithms to the data to create the interaction network; a graph where nodes represent proteins or molecules and edges between nodes represent the probability that two nodes interact. Our two step integration process, where we first predict protein-protein interaction networks for various interaction types and then use these networks to predict protein-compound interaction networks, will provide detailed insight into how pathway level knowledge can be leveraged to predict small molecule level interactions. Recent years have also seen an explosion in plant genomics, as the difficulties inherent in sequencing and functionally analyzing these biologically and economically significant organisms have been overcome. Arabidopsis thaliana, a versatile model organism, represents an opportunity to evaluate the predictive power of biological network inference for plant functional genomics. We provide a compendium of functional relationship networks for A. thaliana leveraging data integration based on over 60 microarray, physical and genetic interaction, and literature curation datasets. These include tissue, biological process, and development stage specific networks, each predicting relationships specific to an individual biological context. These biological networks enable the rapid investigation of uncharacterized genes in specific tissues and developmental stages of interest and summarize a very large collection of A. thaliana data for biological examination. We found validation in the literature for many of our predicted networks, including those involved in disease resistance, root hair patterning, and auxin homeostasis.

1 1

Colloquium Speaker Ankur Moitra Wed Feb 27- 4:30pm
by Nicole E. Wagenblast 27 Feb '13

27 Feb '13

New Algorithms for Nonnegative Matrix Factorization and Beyond Ankur Moitra , Institute for Advanced Studies Wednesday, Februar y 27, 2013, 4:30pm Computer Science 105 Machine learning is a vibrant field with many rich techniques. However, these approaches are often heuristic: we cannot prove good bounds on either their performance or their running time except in limited settings. This talk will focus on designing algorithms whose performance can be analyzed rigorously. As an example of this project, I will describe my work on the nonnegative matrix factorization problem, which has important applications throughout machine learning (and theory). As is often the case, this problem is NP-hard when considered in full generality. However, we introduce a sub-case called separable nonnegative matrix factorization that we believe is the right notion in various contexts. We give a polynomial time algorithm for this problem, and leverage this algorithm to efficiently learn the topics in a Latent Dirichlet Allocation model (and beyond). This is an auspicious example where theory can lead to inherently new algorithms that have highly-practical performance on real data sets. I will also briefly describe some of my other work on learning, including mixtures of Gaussians and robust linear regression, as well as promising directions for future work. Ankur Moitra is an NSF CI Fellow at the Institute for Advanced Study, and also a senior postdoc in the computer science department at Princeton University. He completed his PhD and MS at MIT in 2011 and 2009 respectively, where he was advised by Tom Leighton. He received a George M. Sprowls Award (best thesis) and a William A. Martin Award (best thesis) for his doctoral and master's dissertations. He has worked in numerous areas of algorithms, including approximation algorithms, metric embeddings, combinatorics and smoothed analysis, but lately has been working at the intersection of algorithms and learning.

1 2

Colloquium Speaker John Paisley Mon Feb 25, 4:30pm
by Nicole E. Wagenblast 25 Feb '13

25 Feb '13

Bayesian Nonparametric Models and "Big Data" John Paisley , University of California, Berkeley Monday, February 25, 2013, 4:30pm Computer Science Small Auditorium, Room 105 Bayesian nonparametrics is an area in machine learning in which models grow in size and complexity as data accrue. As such, they they are particularly relevant to the world of "Big Data", where it may be difficult or even counterproductive to fix the number of parameters a priori. A stumbling block for Bayesian nonparametrics has been that their algorithms for posterior inference generally show poor scalability. In this talk, we tackle this issue in the domain of large-scale text collections. Our model is a novel tree-structured model in which documents are represented by collections of paths in an infinite-dimensional tree. We develop a general and efficient variational inference strategy for learning such models based on stochastic optimization, and show that with this combination of modeling and inference approach, we are able to learn high-quality models using millions of documents. John Paisley received the B.S.E. (2004), M.S. (2007) and Ph.D. (2010) in Electrical & Computer Engineering from Duke University, where his advisor was Lawrence Carin. He was a postdoctoral researcher with David Blei in the Computer Science Department at Princeton University, and currently with Michael Jordan in the Department of EECS at UC Berkeley. He works on developing Bayesian models for machine learning applications, particularly for dictionary learning and topic modeling.

1 2

C Park preFPO
by Melissa M. Lawson 21 Feb '13

21 Feb '13

Chris Park will present his preFPO on Tuesday February 26 at 1:30PM in Room 402. The members of his committee are: Olga Troyanskaya, advisor; Mona Singh and Kai Li, readers; Rob Schapire and Moses Charikar, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ---------------------------------------------------------------- Title: Inferring gene function and heterogeneous gene networks from genomic data Abstract With the advancement of quantitative biology, there has been a dramatic increase in functional genomic data. Using these genomic datasets which includes protein-protein interaction, gene expression, localization, and gene knockout studies has enabled researchers to construct functional gene networks. In functional gene networks, each edge represents the probabilistic support for a functional relationship between two genes. However in practice, the goal of biology is to understand further depth of the function and relationship between genes, beyond the abstract notion of a functional relation. In this work, we expand the depth and breadth of functional gene networks. First, we demonstrate that functional gene networks can improve the transfer of gene annotations between organisms to allow prediction algorithms to identify additional genes participating in biological processes that are not already well studied. We apply our novel functional knowledge transfer method to accurately predict novel gene functions across six diverse organisms. Second, biomolecular pathways are built from diverse types of pairwise interactions, ranging from physical protein-protein interactions and modifications to indirect regulatory relationships. One goal of systems biology is to bridge three aspects of this complexity: the growing body of high-throughput data assaying these interactions; the specific interactions in which individual genes participate; and the genome-wide patterns of interactions in a system of interest. Here, we describe methodology for predicting specific types of biomolecular interactions, beyond functional relationship, using high-throughput genomic data in both yeast and human. Ultimately, our work provides further insight into the genetic wiring of the cell enabled by large-scale machine learning with genome-wide biological data.

1 0

reminder: talk now (3pm) on flow-cut gaps and network coding in room 402
by Jennifer Rexford 05 Feb '13

05 Feb '13

Speaker: Anna Blasiak, Cornell Title: Flow-Cut Gaps and Network Coding Date/time: 3-4pm on Tuesday February 5 Place: 402 in the CS building Abstract: The classic max-flow min-cut theorem states that in a network with one source and one sink, the amount of information that can be sent from the source to the sink is equal to the minimum capacity of a set of edges separating the source from the sink. This equivalence allows for efficient computation of both parameters. Modifying traffic demands, constraints, and optimization functions yields many variations of the max-flow problem. In all of these variations there is a corresponding cut minimization problem whose optimal value serves as an upper bound on the max-flow. But unlike the single source-sink version, the cut upper bound is rarely equal to the max-flow. The flow-cut gap, the worst possible ratio between the max-flow rate and the cut upper bound, is an important area of study for developing approximation algorithms and gaining a better understanding of network flow. Related to the max-flow problem is the network coding rate, the maximum transmission rate of information in networks whose nodes can perform nontrivial encoding and decoding operations on incoming messages. The network coding rate is always as big as the max-flow rate and can be much larger. A spectacular result of network coding theory is that in the multicast problem, a setting with a large flow-cut gap, the coding rate is always equal to the cut bound. This talk considers the relations between the flow rate, coding rate, and cut bounds for multicommodity flow problems. I present new coding-cut gaps, the worst-case ratio between the coding rate and cut upper bound. Further, I show that there exist paradigms apart from multicast in which coding can bridge the flow-cut gap. Specifically, in the network that provides the largest known separation (Saks et al.) between the maximum multicommodity flow and multicut, the coding rate is equal to the multicut. This is joint work with Robert Kleinberg (Cornell University) and Eyal Lubetzky (Microsoft Research Redmond).

1 0

3pm Tue Feb 5 talk on flow-cut gaps *rescheduled: was originally Thu Feb 7*
by Jennifer Rexford 02 Feb '13

02 Feb '13

Speaker: Anna Blasiak, Cornell Title: Flow-Cut Gaps and Network Coding Date/time: 3-4pm on Tuesday February 5 Place: 402 in the CS building Abstract: The classic max-flow min-cut theorem states that in a network with one source and one sink, the amount of information that can be sent from the source to the sink is equal to the minimum capacity of a set of edges separating the source from the sink. This equivalence allows for efficient computation of both parameters. Modifying traffic demands, constraints, and optimization functions yields many variations of the max-flow problem. In all of these variations there is a corresponding cut minimization problem whose optimal value serves as an upper bound on the max-flow. But unlike the single source-sink version, the cut upper bound is rarely equal to the max-flow. The flow-cut gap, the worst possible ratio between the max-flow rate and the cut upper bound, is an important area of study for developing approximation algorithms and gaining a better understanding of network flow. Related to the max-flow problem is the network coding rate, the maximum transmission rate of informati! on in networks whose nodes can perform nontrivial encoding and decoding operations on incoming messages. The network coding rate is always as big as the max-flow rate and can be much larger. A spectacular result of network coding theory is that in the multicast problem, a setting with a large flow-cut gap, the coding rate is always equal to the cut bound. This talk considers the relations between the flow rate, coding rate, and cut bounds for multicommodity flow problems. I present new coding-cut gaps, the worst-case ratio between the coding rate and cut upper bound. Further, I show that there exist paradigms apart from multicast in which coding can bridge the flow-cut gap. Specifically, in the network that provides the largest known separation (Saks et al.) between the maximum multicommodity flow and multicut, the coding rate is equal to the multicut. This is joint work with Robert Kleinberg (Cornell University) and Eyal Lubetzky (Microsoft Research Redmond).

1 0