Spring 2013

Our new approach appears to be working. Between 2006 and 2007, enrollment in CS50 more than doubled from 132 to 282 (+114%). Between 2007 and 2008, enrollment increased another 17% to 330, though even more striking was that year’s 48% increase in female enrollment. In 2010, enrollment surpassed 1996’s peak. And in 2012, the course became the second-largest course on campus, with an enrollment of 714.

We present in this talk what we have done and why we have done it. And we offer a look at CS50x, Harvard College’s first course to be offered on an even larger scale via edX.

In this talk, I will first present a broad perspective of our research on human-powered data management, and I will describe some systems and applications that have motivated our research. I will then present details of one of the problems we have addressed: filtering large data sets with the aid of humans. Finally I will argue that human-powered data management is an area in its infancy, by describing a number of open problems I intend to address in my future research program.

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, statistics and optimization. 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 the popular Latent Dirichlet Allocation model (and others too). 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 optimization, including vertex sparsification and lower bounds for linear programs via information theory.

I will begin with a gentle introduction to the diversity and scale of ENCODE data and a brief overview of robust, statistical methods that I developed for automated detection of DNA binding sites of regulatory proteins from massive collections of noisy, experimental data. Regulatory proteins can perform multiple functions by interacting with and co-binding DNA with different combinations of other regulatory proteins. I developed a novel discriminative machine learning formulation based on regularized rule-based ensembles that was able to sort through the combinatorial complexity of possible regulatory interactions and learn statistically significant item-sets of co-binding events at an unprecedented level of detail. I discovered a large number of novel pairwise and higher-order interactions, several of which were experimentally validated. I found extensive evidence that regulatory proteins could switch co-binding partners at different sets of regulatory domains within a single cell-type and across different cell-types thereby affecting patterns of other chemical modifications to DNA and regulating different functional categories of target genes. Finally, I will present a novel approach that we developed to exploit ENCODE data to significantly improve interpretation of human disease studies. Massive case-control studies involving comparative analysis of DNA sequences of diseased and healthy individuals have been reasonably successful at identifying genomic variants (mutations) associated with various human diseases. However, understanding the functional impact of these mutations has been very challenging. Using functional elements discovered from ENCODE data, we were able to identify and prioritize functional variants, provide a functional annotation for up to 81% of all publicly available disease-associated variants and generate new hypotheses by integrating multiple sources of data.

Together, these efforts take us one step closer to learning unified models of regulatory mechanisms in humans in order to improve our system-level understanding of cellular processes and complex diseases.

Such network, when applied at the huge scale, is able to learn abstract concepts in a much more general manner than previously demonstrated. Specifically, we find that by training on 10 million unlabeled images, the network produces features that are very selective for high-level concepts such as human faces and cats. Using these features, we also obtain breakthrough performance gains on several large-scale computer vision tasks.

Thanks to its scalability and insensitivity to modalities, our framework is also used successfully to achieve performance leaps in other domains, such as speech recognition and natural language understanding.

In this talk, I will describe new systems and theory for delivering high availability to users, inspired by real-world debacles, some of which are unknown to the public. A unifying approach in my research is to integrate theoretical innovations into the final stages of system design, giving robust guarantees that are also practical. First, I will describe a system that allows any Internet service to tolerate arbitrary faults scalably on read-mostly workloads, as well as new algorithms to scale this fault tolerance to a million nodes on general workloads. Then, I will describe an indexing technique used by database systems to increase transaction concurrency, and theoretically explain why it failed for one company, leading to the design of new data structures that are being incorporated into algorithms textbooks. I will also briefly discuss my other work on high availability, such as a system for saving energy on enterprise desktops, and my ongoing work on a system for rich analysis of globally distributed, real-time data.

The main goal of the second part of the talk is to convert the theory developed in first part into (usable) algorithms. Specifically I shall provide a general recipe to derive efficient online learning algorithms for various online learning problems starting from the sequential complexity tools provided in the first part. Most existing online learning algorithms can be seen as arising out of this recipe. Several new and efficient online learning algorithms are also developed based on this recipe. Specifically we shall see how the recipe provides us with new algorithms for online matrix prediction problems, online link classification problems and new projection free online convex optimization algorithms.

Our modeling strategy relies on the integration of genome-scale datasets of various types, including temporal activity of individual components, probabilities for physical interactions between components, and causal relationships (i.e., perturbing component “A” affects the activity of “B”). The model inference is done iteratively such that putative key regulators are automatically chosen for perturbation experiments, which then serve for validating, refining and annotating the model. Formulating the ensuing data as network structures allows us to use graph-theoretic optimization algorithms as a modeling tool. For instance, we have developed an algorithm that combines a global optimization objective (directed Steiner trees) with a local one (shortest paths), proven its approximation bounds, and adapted its implementation for handling large-scale and real-world biological data.

Using this strategy, we investigated the differentiation of naïve T cells into autoimmune-inducing Th17 T helper cells, which, despite enormous clinical importance, remain poorly understood. We computationally derived and then experimentally validated a temporal model of the regulatory network that controls the differentiation process. The network consists of two self-reinforcing, but mutually antagonistic, modules that control the Th17 phenotype and collectively achieve appropriate balance between Th17 cells and other competing T cell lineages. Specifically, we identified several molecular circuits that are crucial to blocking the pathogenesis of Th17-dependent autoimmunity by shifting the balance toward the differentiation of immunosuppressive T cells. Overall, our study identified 41 regulatory molecules that affect Th17 differentiation, characterized their interactions, and highlighted novel drug targets for a host of autoimmune diseases.

Database cracking removes completely the need for index-tuning in database systems. With database cracking indices are built incrementally, adaptively and on demand; each query is seen as an advice on how data should be stored. With each incoming query, data is reorganized on-the-fly as part of query processing, while future queries exploit and continuously enhance this knowledge. Autonomously, adaptively and without any external human administration, the database system quickly adapts to a new workload and reaches optimal performance when the workload stabilizes.