CS Department Colloquium Series

Computer scientists have long known that randomness can be used to improve the performance of algorithms. A familiar application is the process of dimension reduction, in which a random map transports data from a high-dimensional space to a lower-dimensional space while approximately preserving some geometric properties. By operating with the compact representation of the data, it is possible to produce approximate solutions to certain large problems very efficiently.

It has been observed that dimension reduction has powerful applications in numerical linear algebra and numerical analysis. This talk will discuss randomized techniques for constructing standard matrix factorizations, such as the truncated singular value decomposition. In practice, the algorithms are so effective that they compete with—or even outperform—classical algorithms. These methods are already making a significant impact in large-scale scientific computing and learning systems.

Joint work with P.-G. Martinsson and N. Halko.

The recent success of machine learning (ML) in both science and industry has generated an increasing demand to support ML algorithms at scale. In this talk, I will discuss strategies to gracefully scale machine learning on modern parallel computational platforms. A common approach to such scaling is coordination-free parallel algorithms, where individual processors run independently without communication, thus maximizing the time they compute. However, analyzing the performance of these algorithms can be challenging, as they often introduce race conditions and synchronization problems.

In this talk, I will introduce a general methodology for analyzing asynchronous parallel algorithms. The key idea is to model the effects of core asynchrony as noise in the algorithmic input.  This allows us to understand the performance of several popular asynchronous machine learning approaches, and to determine when asynchrony effects might overwhelm them.  To overcome these effects, I will propose a new framework for parallelizing ML algorithms, where all memory conflicts and race conditions can be completely avoided. I will discuss the implementation of these ideas in practice, and demonstrate that they outperform the state-of-the-art across a large number of ML tasks on gigabyte-scale data sets.

Dimitris Papailiopoulos is a postdoctoral researcher in the Department of Electrical Engineering and Computer Sciences at UC Berkeley and a member of the AMPLab. His research interests span machine learning, coding theory, and parallel and distributed algorithms, with a current focus on coordination-free parallel machine learning, large-scale data and graph analytics, and the use of codes to speed up distributed computation. Dimitris completed his Ph.D. in electrical and computer engineering at UT Austin in 2014. At Austin he worked under the supervision of Alex Dimakis. In 2015, he received the IEEE Signal Processing Society, Young Author Best Paper Award.

Automatically describing the content of an image is a fundamental problem in artificial intelligence that connects computer vision and natural language processing.  In this talk, I'll present a generative model based on a deep recurrent architecture that combines recent advances in computer vision and machine translation and that can be used to generate natural sentences describing an image.  The model is trained to maximize the likelihood of the target description sentence given the training image.  Experiments on several datasets show the accuracy of the model and the fluency of the language it learns solely from image descriptions. Our model is often quite accurate, which we verify both qualitatively and quantitatively.

If time permits, I'll also describe an improvement on our basic image captioning approach that considers the discrepancy between how we train these models and how we actually use them at inference time, and how adding some exploration during training mitigates this problem.

Joint work with Oriol Vinyals, Alex Toshev, Dumitru Erhan, Navdeep Jaitly and Noam Shazeer.

Samy Bengio (PhD in computer science, University of Montreal, 1993) is a research scientist at Google since 2007. Before that, he was senior researcher in statistical machine learning at IDIAP Research Institute since 1999. His most recent research interests are in machine learning, in particular deep learning, large scale online learning, image ranking and annotation, music and speech processing. He is action editor of the Journal of Machine Learning Research and on the editorial board of the Machine Learning Journal. He was associate editor of the journal of computational statistics, general chair of the Workshops on Machine Learning for Multimodal Interactions (MLMI'2004-2006), programme chair of the International Conference on Learning Representations (ICLR'2015-2016), programme chair of the IEEE Workshop on Neural Networks for Signal Processing (NNSP'2002), chair of BayLearn (2012-2015), and several times on the programme committee of several international conferences such as NIPS, ICML, ECML and ICLR. More information can be found on his website: http://bengio.abracadoudou.com.

Intelligent agents acting in the real world need advanced vision capabilities to perceive, learn from, reason about and interact with their environment. In this talk, I will explore the role that humans play in the design and deployment of computer vision systems. Large-scale manually labeled datasets have proven instrumental for scaling up visual recognition, but they come at a substantial human cost. I will first briefly talk about strategies for making optimal use of human annotation effort for computer vision progress. However, no dataset can foresee all the visual scenarios that a real-world system might encounter. I will argue that seamlessly integrating human expertise at runtime will become increasingly important for open-world computer vision. I will introduce, and demonstrate the effectiveness of, a rigorous mathematical framework for human-machine collaboration. Looking ahead, in order for such collaborations to become practical, the computer vision algorithms we design will need to be both efficient and interpretable. I will conclude by presenting a new deep reinforcement learning model for human action detection in videos that is efficient, interpretable and more accurate than prior art, opening up new avenues for practical human-in-the-loop exploration.

Olga Russakovsky recently completed her PhD in computer science at Stanford and is now a postdoctoral fellow at Carnegie Mellon University. Her research is in computer vision, closely integrated with machine learning and human-computer interaction. Her work was featured in the New York Times and MIT Technology Review. She served as a Senior Program Committee member for WACV’16, led the ImageNet Large Scale Visual Recognition Challenge effort for two years, and organized multiple workshops and tutorials on large-scale recognition at premier computer vision conferences ICCV’13, ECCV’14, CVPR’15, ICCV’15 and CVPR’16. In addition, she founded and directs the Stanford AI Laboratory’s outreach camp SAILORS (featured in Wired and published in SIGCSE’16) designed to expose high school students in underrepresented populations to the field of AI.

Machine learning is changing the way we do science. We want to study large datasets to shed light onto natural processes. (How do proteins function? How does the brain work?) To this end, we need tools to rapidly and iteratively explore hidden patterns in data. However, using machine learning to discover such patterns requires enormous effort and cross-disciplinary expertise. My goal is to develop easy-to-use machine learning tools that empower scientists to gain new insights from data. This requires research in automated algorithms, scalable software, and robust machine learning. These are the building blocks of effective machine learning tools.

Alp is a postdoctoral research scientist at the Data Science Institute and the department of Computer Science at Columbia University. He works with David Blei on developing scalable and robust machine learning tools. He collaborates with Andrew Gelman on the Stan probabilistic programming system. Alp received his Ph.D. from Yale University, where he was awarded the Becton prize for best thesis in engineering and applied science. He holds a B.A.Sc. from the University of Toronto.

One reason that analyzing text is hard is that it involves dealing with deeply entangled linguistic variables: objects like syntactic structures, semantic types, and discourse relations depend on one another in complex ways.  Our work tackles several facets of text analysis using joint modeling, combining model components both across and within the various subtasks of this analysis.  This model structure allows us to pass information between these entangled subtasks and propagate high-confidence predictions rather than errors.  Critically, our models have the capacity to learn key linguistic phenomena as well as other important patterns in the data; that is, linguistics tells us how to structure these models, then the data injects knowledge into them.  We describe state-of-the-art systems for a range of tasks, including syntactic parsing, entity resolution, and document summarization.

 

Greg is a Ph.D. candidate at UC Berkeley working on natural language processing with Dan Klein.  He is interested in building structured machine learning models for a wide variety of text analysis problems and downstream NLP applications.  His work is comprised of two broad thrusts: first, designing joint models that combine information across different tasks or different views of a problem, and second, building systems that strike a balance between being linguistically motivated and data-driven

Web services today want to support sophisticated queries, with stringent interactivity constraints. Many recent studies have argued that in-memory query execution is one of the keys to achieving query interactivity. However, as web services scale to larger data sizes, executing queries in memory becomes increasingly challenging. As a result, existing systems fall short of supporting sophisticated interactive queries at scale.

In this talk, we present Succinct, a distributed data store that supports functionality comparable to state-of-the-art NoSQL stores and yet, enables query interactivity for an order of magnitude larger data sizes than what is possible today (or, alternatively, up to two orders of magnitude faster queries at scale). Succinct accomplishes this by executing a wide range of queries -- e.g., search, range, and even regular expressions -- directly on compressed data. Succinct achieves scale by storing the input data in a compressed form, and interactivity by avoiding data scans and data decompression. We will also discuss how Succinct’s approach of executing queries on compressed data enables a new “lens” for exploring several classical systems problems -- e.g., failure recovery, load spikes during transient failures, skewed workloads, etc. --, and leads to previously unachievable operating points in the system design space. Succinct is open-sourced, and is already being adopted in production clusters of several large-scale web services.

Rachit Agarwal is a postdoc in AMPLab at UC Berkeley, where he leads the Succinct project along with Ion Stoica. His research focuses on the core problems in distributed data-intensive systems, with the goal of building systems that not only aim for practical impact but also have a strong theoretical foundation. He completed his PhD at UIUC, working with Brighten Godfrey and Matthew Caesar, and his undergraduate from IIT Kanpur. During his PhD, he received 2012 UIUC Rambus research award and 2010 Wang-Chung research award for outstanding performance in computer engineering research, and was listed in 2010 UIUC List of Teachers ranked as excellent.

 

Human attention is a scarce resource, but when available, it can also be wonderfully perceptive. My research seeks to understand: what does it take for mobile devices --- power-constrained as they are ---  to operate at the speed of human perception? And what new opportunities emerge as a result?

 Via a pair of vignettes, I illustrate two such low-latency mobile systems. The first focuses on app streaming, an emerging app execution model in which remote servers execute logic and rendering on behalf of thin clients. App streaming promises any device access to any app at any time. Unfortunately, the reality is that wide-area network latencies often exceed thresholds above which many interactive apps such as games tend to be deemed too slow. In response, I describe Outatime, a speculative execution system for app streaming that masks network latency.  In Outatime, the server renders speculative frames of future possible outcomes, delivering them to the client one entire roundtrip early, and recovers quickly from mis-speculations when they occur. Clients perceive little latency. Outatime has been implemented on two high-quality, commercially-released twitch-based games.  Users report strongly preferring Outatime to standard streaming, since Outatime delivers real-time interactivity as fast as --- and in some cases, even faster than --- traditional local client-side execution.

 In a second example of low-latency interaction, I describe a Kinect-like device tracking system, FAR. Unlike Kinect, FAR is portable, requiring only the phones in our hands. Yet FAR performs continuous, fast and accurate phone-to-phone localization that matches the (often very fast) speed and sensitivity of human movement.  In fact, FAR's accuracy is comparable to --- and in some cases, even superior to --- that of Kinect.  Lab trials and many real world deployments indicate that FAR can fully support dynamic human motion in real-time.

David Chu is a researcher in Microsoft's Mobility and Networking Research Group. His research interests are in mobile systems and applications, cyber-physical systems, sensing systems, ubiquitous computing and applied machine learning.  The main thrust of David's current work is toward low-latency perception-aligned mobile systems. He received the Best Paper award in MobiSys 2015, the Best Paper nomination in MobiSys 2012, the Best Demo award in MobiSys 2014, and the Best Demo nomination in SenSys 2011.  David's research has appeared on multiple occasions in tech news such as TechCrunch, PC Magazine, GameSpot, Ars Technia, Slashdot, The Verge, Engadget and Wired. At Microsoft, David has contributed to Windows and Windows Phone, Xbox and HoloLens. David received his B.S. from the University of Virginia in 2004; and his M.S. and Ph.D. from the University of California, Berkeley in 2005 and 2009, respectively, while an NSF Graduate Research Fellow.

Human cognition still sets the standard we aspire to in many areas of machine learning, including problems such as identifying causal relationships, acquiring and using language, and  learning concepts from a small number of examples. In these cases, human and machine learning can establish a mutually beneficial relationship: we can use the formal tools developed in machine learning to provide insights into human learning, and translate those insights into new machine learning systems. I will use the case of causal induction to illustrate the value of this approach, but also highlight some applications in language and concept learning. I will also argue that the same kind of mutually beneficial relationship could potentially exist between developing data-intensive approaches to cognitive science and making sense of large volumes of behavioral data in computer science.