Spring 2012

ABSTRACT: Computer Science continues to have a very productive research agenda in its core areas, such as for building planetary-scale, parallel systems, improving software engineering, increasing the scale and utility of machine learning, and securing systems. However, Computer Science continues to be an expanding sphere, with its surface growing into ever more other domains. In this talk, based on my experiences at Google and IBM, I will discuss a few of the challenges in the core of computer science. But, I will mostly focus on computer science research opportunities at the edge of the expanding sphere—particularly, in education and healthcare. I will illustrate some of the more basic research challenges, but also discuss some of the engineering needs as advanced computing moves ever further into life’s most pervasive and important pursuits.

ABSTRACT: The idea of controlling objects by thought alone has long been a staple of science fiction novels and movies. However, the advent of brain-computer interfaces (BCIs) is rapidly making this idea a reality, with researchers demonstrating the control of cursors, prosthetic arms, wheelchairs, and robotic avatars all through brain signals. BCIs have now enabled communication in locked-in patients, helped restore movement in paralyzed and disabled individuals, and are increasingly being used in novel applications such as security, lie detection, alertness monitoring, entertainment, gaming, education, and human augmentation. This talk will provide an overview of recent developments in the field, with highlights from two approaches that my collaborators and I are exploring at the University of Washington: a non-invasive technique known as electroencephalography (EEG) for recording from the scalp and an invasive technique known as electrocorticography (ECoG) for recording from the brain surface. I will describe how devices such as a computer cursor, a prosthetic hand, and a humanoid robot can be controlled through motor imagery and stimulus-evoked potentials decoded from EEG and ECoG signals. The talk will conclude with a discussion of some of the moral and ethical issues we will have to confront as a society when BCIs start making the transition from the laboratory to our daily lives.

ABSTRACT: The decade-old Internet search outcomes, manifested in the document-centric form of “ten blue links,” are no longer sufficient for Internet users. Many studies have shown that when users are ushered off the conventional search result pages through blue links, their needs are often partially met at best in a “hit-or-miss” fashion. To tackle this challenge, we have designed Bing, Microsoft’s search engine, not just to navigate users to a landing page through a blue link but to continue engaging with users to clarify intent and facilitate task completion with Bing’s deep understanding of the underlying entities and domains of user interest. Powering this new paradigm is the Bing Dialog Model that consists of three building blocks: an indexing system that comprehensively collects information from the web and systematically harvests knowledge, an intent model that statistically infers user intent and predicts next action based on the harvested knowledge, and an interaction model that elicits user intent through mathematically optimized presentations of web information and knowledge that matches user needs. In this talk, I’ll describe the Bing Dialog Model in detail and demonstrate it in action through some innovative features, in particular applying social contexts and entity understanding for user task completion.

ABSTRACT: Crowd-powered systems combine computation with human intelligence, drawn from large groups of people connecting and coordinating online. These hybrid systems enable applications and experiences that neither crowds nor computation could support alone. Unfortunately, crowd work is error-prone and slow, making it difficult to incorporate crowds as first-order building blocks in software systems. I introduce computational techniques that decompose complex tasks into simpler, verifiable steps to improve quality, and optimize work to return results in seconds. These techniques advance crowdsourcing into a platform that is reliable and responsive to the point where crowds can be used in interactive systems. In this talk, I will present two crowd-powered systems to illustrate these ideas. The first, Soylent, is a word processor that uses paid micro-contributions to aid writing tasks such as text shortening and proofreading. Using Soylent is like having access to an entire editorial staff as you write. The second system, Adrenaline, is a camera that uses crowds to help amateur photographers capture the exact right moment for a photo. It finds the best smile and catches subjects in mid-air jumps, all in realtime. These systems point to a future where social and crowd intelligence are central elements of interaction, software, and computation.

ABSTRACT: The Internet offers users many opportunities for communicating and exchanging ideas, but abuse, censorship, and the manipulation of Internet traffic have put free and open communication at risk. Recent estimates suggest that spam constitutes about 95% of all email traffic; hundreds of thousands of online scam domains emerge every day; online social networks may be used to spread propaganda; and more than 60 countries around the world censor Internet traffic. In this talk, I will present approaches that we have developed to preserve free and open communication on the Internet in the face of these threats. First, I will describe the threat of message abuse (e.g., spam) and describe methods we have developed for mitigating it. I will briefly discuss a 13-month study of the network-level behavior of spammers, and present SNARE, a spam filtering system we developed that classifies email messages based on the network-level traffic characteristics of the email messages, rather than their contents. Next, I will turn to information censorship, and describe Collage, a system that circumvents censorship without arousing the suspicion of the censor. Finally, I will discuss the various forms of information manipulation, including the spread of propaganda in social networks and online “filter bubbles”. Although it is difficult to prevent all forms of manipulation, our goal is to make it more transparent to users. Towards this goal, I will describe my broader research agenda and plans, which aim to improve Internet transparency for aspects of Internet communication ranging from network performance to social media to search results using the aggregation of data from a wide variety of vantage points.

ABSTRACT: Suppose we are given a gigantic communication network, but are only interested in a small number of nodes (clients). There are many routing problems we could be asked to solve for our clients. Is there a much smaller network – that we could write down on a sheet of paper and put in our pocket – that approximately preserves all the relevant communication properties of the original network? As we will demonstrate, the answer to this question is YES, and we call this smaller network a vertex sparsifier. In fact, if we are asked to solve a sequence of optimization problems characterized by cuts or flows, we can compute a good vertex sparsifier ONCE and discard the original network. We can run our algorithms (or approximation algorithms) on the vertex sparsifier as a proxy – and still recover approximately optimal solutions in the original network. This novel pattern saves both space (because the network we store is much smaller) and time (because our algorithms run on a much smaller graph). Additionally, we apply these ideas to obtain a master theorem for graph partitioning problems – as long as the integrality gap of a standard linear programming relaxation is bounded on trees, then the integrality gap is at most a logarithmic factor larger for general networks. This result implies optimal bounds for many well studied graph partitioning problems as a special case, and even yields optimal bounds for more challenging problems that had not been studied before.

ABSTRACT: I will discuss three classical statistical problems for which the computational perspective unlocks insights into the fundamental nature of these tasks; additionally, our solutions suggest new algorithmic approaches to coping with the increasing size of real-world datasets. The first problem is the basic task of finding correlated vectors. Given a set of n binary vectors, with the promise that some pair is r-correlated, can one find the correlated pair faster than simply searching all O(n^2) pairs? We give a surprisingly simple algorithm for finding such a pair in time poly(1/r)*n^1.6, which is the first sub-quadratic time algorithm for this task with a polynomial dependence on the correlation, and improves upon the prior best of n^(2-O(r)), given by the Locality Sensitive Hashing approach. This result can be leveraged to yield significantly improved algorithms for several important problems in learning theory, including the problems of learning juntas, and learning parities with noise. The second problem we consider is recovering the parameters of a mixture of Gaussian distributions. Given data drawn from a single Gaussian distribution, the sample mean and covariance of the data trivially yield good estimates of the parameters of the true distribution; if, however, some of the data points are drawn according to one Gaussian, and the rest of the data points are drawn according to a different Gaussian, how can one recover the parameters of each Gaussian component? This problem was first proposed by Pearson in the 1890’s, and, in the last decade, has been revisited by computer scientists. In a pair of papers with Adam Kalai and Ankur Moitra, we give the first polynomial-time algorithm for this problem that has provable success guarantees. The final problem, investigated in a series of papers with Paul Valiant, considers the tasks of estimating a broad class of statistical properties, which includes entropy, various distance metrics between pairs of distributions, and support size. Our estimators are the first proposed estimators for these properties which achieve small error using a sub-linear number of samples, and are based on a novel approach of approximating the portion of the distribution from which one draws no samples. There are several implications of our results, including resolving the sample complexity of the `distinct elements problem’ (i.e. given a vector of length n, how many random indices must one query to accurately estimate the number of distinct elements?); we show that on the order of n/log n queries is both necessary, and sufficient, improving upon the prior lower-bounds, and contradicting the previously widely-held belief that O(n) samples are necessary.

ABSTRACT: Cloud computing promises virtually unlimited scalability and high availability at low cost. However, it is commonly believed that a system’s consistency must be relaxed in order to achieve these properties. We evaluated existing commercial cloud offerings for transactional workloads and found that consistency is indeed expensive and limits scalability in these systems. Because of this expense, many systems designers have chosen to provide only relaxed consistency guarantees, if any. This choice, however, makes such systems inappropriate for many mission critical applications. This dichotomy is based on unrealistically pessimistic assumptions about Big Data environments. First, it assumes that consistency is an all or nothing decision that must be applied uniformly to all data in a system.
Secondly, even in situations where strong consistency is required, previous transaction commit protocols were based on worst-case assumptions regarding the likelihood of conflicts. In thi s talk, I describe two techniques that build on a more nuanced view of consistency requirements and the costs of maintaining them.
I first describe Consistency Rationing, which builds on inventory holding models used in Operations Research to help classify and manage data based on their consistency requirements. Consistency Rationing exploits the fact that for some data the cost of maintaining consistency outweighs the benefit obtained by avoiding inconsistencies. In the second part of the talk, I present a new optimistic commit protocol for the wide-area network. For a long time, synchronized wide-area replication was considered to be infeasible with strong consistency. With MDCC I will show how we can achieve strong consistency with similar response-time guarantees as eventual consistency in the normal operational case. This work was done as part of a larger project around Big Data management. At the end of the talk, I will provide an overview of some of my other projects and give an outline for future work.

ABSTRACT: Latent variable models are widely used in applications to automatically recover simple underlying signals from noisy high-dimensional data. The challenge in estimating such models stems from the presence of hidden (unobserved) variables, and typical local search methods used for this task (e.g., E-M) generally lack basic performance guarantees such as statistical consistency and computational efficiency. In this talk, I will discuss recent developments in linear algebraic methods for learning certain classes of latent variable models, including parameter estimation for hidden Markov models, and structure learning of latent variable tree models. Unlike the local search heuristics, the proposed linear algebraic methods come with statistical and computational efficiency guarantees under mild conditions on the data distribution. Central to the new techniques is the characterization of the models in terms of low-order moments (e.g., averages, correlations) of observable variables, which are readily estimated from data.
This talk is based on various joint works with Anima Anandkumar, Kamalika Chaudhuri, Sham Kakade, Le Song, and Tong Zhang.

ABSTRACT: Real-time depth sensors reliably capture both geometry and motion at remarkably high resolution, regardless of a subject’s appearance or the illumination of the environment. While the subtlest human body deformations and facial expressions can be recovered, only partial information is available at a time and the input data is typically noisy. The key to obtaining a complete digitization from incomplete 3D scans is to establish full correspondences throughout the entire recording while modeling the deformed shape in occluded regions using optimal geometric priors. I will first present a highly robust general-purpose non-rigid registration algorithm that is capable of accurately finding dense correspondences despite consecutive scans undergoing significantly large and complex deformations. I will explain why it is important to simultaneously couple the optimization of correspondence positions, warping field, and overlapping regions. In the second part of the talk, I will focus on a fully integrated system for real-time facial animation using depth sensors and discuss two novel data-driven techniques: one that effectively extracts high-level expression semantics for retargeting and one that significantly improves robustness to unforeseen occlusions and severe noise using probabilistic animation priors. I will give a live demonstration using Microsoft’s Kinect sensor and show how low-quality input data can be effectively mapped to realistic facial expressions. Going beyond computer graphics and vision, I will show several applications in science where my technique has been successfully applied, such as radiation oncology and cardiac surface mechanics. I believe that these foundational tools for data-driven performance capture will be key to collecting massive data sets of detailed dynamic geometry and real-time analysis of performance data in everyday surroundings.

ABSTRACT: The emergence of modern geometry acquisition devices, such as the Kinect, and the appearance of large-scale shape repositories, such as the Google Warehouse, are revolutionizing computer graphics, making three-dimensional content ubiquitous. The need for algorithms that understand and intelligently process 3D shapes is thus greater than ever. In this talk, I will describe a new generation of algorithms that analyze and synthesize complex three-dimensional shapes. The algorithms are based on probabilistic models that reason about both geometry and semantics. In contrast to traditional approaches that consider individual shapes in isolation and require laborious hand-tuning, these algorithms learn from collections of shapes. Specifically, I will present a data-driven shape segmentation technique that outperforms all previous approaches to shape segmentation. I will then describe a shape synthesis technique that can construct high-quality novel shapes from complex domains, such as aircraft, ships, and furniture. Finally, I will discuss new opportunities for geometry processing and 3D modeling enabled by these algorithms.

ABSTRACT: The choice between Byzantine and crash fault tolerance is viewed as a fundamental design decision when building fault tolerant systems. We show that this dichotomy is not fundamental, and present a unified model of fault tolerance in which the number of tolerated faults of each type is a configuration choice. Additionally, we observe that a single fault is capable of devastating the performance of existing Byzantine fault tolerant replication systems. We argue that fault tolerant systems should, and can, be designed to perform well even when failures occur. In this talk I will expand on these two insights and describe our experience leveraging them to build a generic fault tolerant replication library that provides flexible fault tolerance and robust performance. We use the library to build a (Byzantine) fault tolerant version of the Hadoop Distributed File System.

ABSTRACT: The real world is full of sounds: a babbling brook winding through a tranquil forest, an agitated shopping cart plunging down a flight of stairs, or a falling piggybank breaking on the ground. Unfortunately virtual worlds simulated by current simulation algorithms are still inherently silent. Sounds are added as afterthoughts, often using “canned sounds” which have little to do with the animated geometry and physics. While recent decades have seen the dramatic success of 3D computer animation, our brain still expects a full spectrum of sensations. The lack of realistic sound rendering methods will continue to cripple our ability to enable highly interactive and realistic virtual experiences as computers become faster. In this talk, I will introduce my attempts to change that. My research on physics-based sound rendering aims to enable future virtual experiences with simulated images, motion, and sound are synchronized and highly engaging. Exploring this direction raises lots of unique challenges for computer simulation. I will illustrate ways in which we have addressed them for two major classes of sound-producing objects: solids and liquids. Finally, I will briefly overview some of my other graduate work on robot learning, scientific computing, and Internet routing, and outline my future plans.