Research Showcase Agenda 2019

The human epigenome has been experimentally characterized by thousands of uniformly processed epigenomic and transcriptomic data sets. These datasets characterize a rich variety of biological activity, such as protein binding, chromatin accessibility, methylation, transcription, and histone modification, in hundreds of human cell lines and tissues ("biosamples"). However, due primarily to cost, the total number of assays that can be performed is limited to a small fraction of potential experiments. To address this challenge, we propose a deep neural network tensor factorization method, Avocado, that compresses epigenomic data into a dense, information-rich representation of the human genome. We show that the resulting model can impute tens of thousands of missing epigenomic experiments from the ENCODE compendium in an accurate, cell type specific, manner. Avocado also shows promise in less canonical imputation settings. For example, initial results have shown that a model trained on human epigenomics can be transferred over to other species, allowing for imputations of activity where no experimental data has been acquired yet for that species.

Systematic modeling of Alzheimer's Disease (AD) neuropathology based on brain gene expression would provide valuable insights into the disease. However, relative scarcity and regional heterogeneity of brain gene expression and neuropathology data sets obscure the ability to robustly identify expression markers. We propose MD-AD (Multi-task Deep learning for AD) to effectively combine heterogeneous AD data sets by simultaneously modeling multiple phenotypes using neural networks. In this talk, I will discuss how we can use MD-AD to effectively (i) impute missing phenotypes, (ii) capture relevant AD-phenotypes in the supervised embedding space represented by its last shared layer, and (iii) identify genes and pathways relevant in the model to highlight a potential molecular basis for AD neuropathology.

Machine learning (ML) is making an increasingly large impact in medicine, and promises to predict disease more quickly, inexpensively, and easily than ever before. For these promises to be fulfilled, the inputs to an ML algorithm must themselves be fast, inexpensive, or easy to acquire. This is often addressed by hand-picking input variables that are believed to have a low "cost" and high predictive value. The field of cost-sensitive ML builds algorithms that automate this feature selection step, automatically choosing the best subset of input variables to make a low-cost, high-accuracy prediction. We present what is to our knowledge the first detailed analysis of cost-sensitive learning in clinical settings, using the prediction of ICU mortality, the prediction of acute traumatic coagulopathy (ATC), and the prediction of outpatient survival as examples. We assign expert-curated costs to the features in each dataset, present a method called CoAI to make cost-sensitive predictions, and evaluate the method using realistic prediction budgets. CoAI dramatically reduces the time taken to make a prediction relative to existing mortality, ATC, and survival scores, while preserving or improving accuracy. CoAI integrates with existing ML packages with just a few lines of code. We believe it will help improve patient care in time-sensitive clinical prediction tasks in all areas of medicine.

We developed a method for estimating the distribution of errors for every residue-residue distance in an input protein structure and in structure ensembles. Specifically, we trained deep neural networks on beta carbon l-DDT score per residue and signed c-beta distance error distribution for each pair of residues. Our approach advances over previous error prediction methods in two ways. First, we estimate not only global and local coordinate coordinate error (LDDT scores), but are also the distribution of signed offsets for each pairwise distance. Second, our network uses both 3D convolution to access local atomic environments and 2D convolution to provide their global contexts. The fine-grained estimation generated by our framework can significantly improve the performance downstream tasks in multiple different aspects.

We introduce a novel approach to the problem of cardinality estimation over multijoin queries by focusing on using theoretically guaranteed upper bounds. Our approach leverages randomized hashing and data sketching to tighten these bounds beyond the current state of the art. We demonstrate that the bounds can be injected directly into the cost based query optimizer framework enabling it to avoid expensive physical join plans. We demonstrate a complex tradeoff space between the tightness of our bounds and the size and complexity of our data structures. We evaluate our methods on GooglePlus community graphs, and the Join Order Benchmark. In the presence of foreign key indexes, we demonstrate a 1.7x improvement in aggregate (time summed over all queries in benchmark) physical query plan runtime compared to plans chosen by Postgres using the default cardinality estimation methods. When foreign key indexes are absent, this advantage improves to over 10x.

Database applications are often developed with object-oriented languages while using relational databases as the backend. However, the characteristics of object-oriented database applications are often distinct enough from traditional database applications such that classical relational query optimization techniques often cannot speed up queries from such applications. To address this, we build chestnut, a data layout generator for in-memory object-oriented database applications. Given a memory budget, chestnut generates customized in-memory data layouts and query plans to answer queries written using object-oriented query interface. The chestnut-generated layout are designed to be efficient to answer such queries and it uses a novel enumeration and verification-based algorithm to generate query plans rather than rule-based approaches as in traditional query optimizers. We evaluated chestnut on four opensource web applications. The result shows that it can reduce average query processing time by over 3.6× (and up to 42×) as compared to other in-memory relational database engines.

Acyclic schemes have numerous applications in databases and in machine learning, such as improved design, more efficient storage, and increased performance for queries and machine learning algorithms. Multivalued dependencies (MVDs) are the building blocks of acyclic schemes. The discovery from data of both MVDs and acyclic schemes is more challenging than other forms of data dependencies, such as Functional Dependencies, because these dependencies do not hold on subsets of data, and because they are very sensitive to noise in the data; for example a single wrong or missing tuple may invalidate the schema. In this paper we present Maimon, a system for discovering approximate acyclic schemes and MVDs from data. We give a principled definition of approximation, by using notions from information theory, then describe the two components of Maimon: mining for approximate MVDs, then reconstructing acyclic schemes from approximate MVDs. We conduct an experimental evaluation of Maimon on 20 real-world datasets, and show that it can scale up to 1M rows, and up to 30 columns.

Deep learning (DL) models have achieved paradigm changing performance in many fields with high dimensional data, such as images, audio, and text. However, the black- box nature of deep neural networks is a barrier not just to adoption in applications such as medical diagnosis, where interpretability is essential, but also impedes diagnosis of under performing models. The task of diagnosing or explaining DL models requires the computation of additional artifacts, such as activation values and gradients. These artifacts are large in volume, and their computation, storage, and querying raise significant data management challenges. Here, we articulate DL diagnosis as a data management problem, and we propose a general, yet representative, set of queries to evaluate systems that strive to support this new workload. We further develop a novel data sampling technique that produce approximate but accurate results for these model debugging queries. Our sampling technique utilizes the lower dimension representation learned by the DL model and focuses on model decision boundaries for the data in this lower dimensional space. We evaluate our techniques on one standard computer vision and one scientific data set and demonstrate that our sampling technique outperforms a variety of state-of-the-art alternatives in terms of query accuracy.

Synthetic DNA has been gaining momentum as a potential storage medium for archival data storage. In this process, digital information is translated into sequences of nucleotides and the resulting synthetic DNA strands are then stored for later retrieval. While retrieval of individual digital files via PCR-based random access has been previously demonstrated, the physical limits and reliability of this process have not been thoroughly explored. Previous work recognized the importance of storage density for DNA to become a practical archival storage but did not explore PCR random access accuracy when accessing extremely small subsets of data from a dense, complex pool. This work examines the ability of PCR to recover files from pools of far greater complexity, ranging from over 10^6 to over 10^10 unique sequences per microliter. This work also examines the minimum physical redundancy needed to successfully recover desired files, the pattern at which DNA sequences are lost, and the affect sequencing coverage has on recovery. Regardless of how many unique sequences there are per microliter, or the size of the file accessed, we demonstrate a density of approximately 17 exabytes/g, nearly two orders of magnitude greater than prior work has shown.

We created a molecular tagging system using synthetic DNA-based tags designed for a portable, low-cost DNA sequencing device (Oxford Nanopore Technologies’ MinION). These tags are analogous to radio frequency identification (RFID) tags in the digital world, in that they encode only a short identifier and can be attached to objects to be re-identified later. In our system, digital information is converted to DNA not by synthesizing new DNA strands, but by the presence or absence of unique, pre-prepared molecular bits (molbits) representing 1’s and 0’s respectively. We have extensively designed these bits so they each produce visually unique data in the nanopore sequencing device, and developed deep learning classifiers to read the molecular tags rapidly with minimal amounts of data (seconds to minutes of sequencing), bringing costs down significantly.

Many domains ranging from molecular systems to medical diagnostics rely on microfluidic devices for automation to increase experimental throughput, reduce human error, and enable novel and complex application spaces. We have developed a full-stack digital microfluidic platform called PurpleDrop to address the need for low cost, multipurpose, accessible and fully automated microfluidic technologies. This talk will give an introduction to microfluidics and its many potential applications, provide an overview of the PurpleDrop platform, and discuss future directions of this technology.

Engineering gene sequences with defined functional properties is a major goal of synthetic biology. Gradient ascent-style optimization of the input pattern through a deep learning model shows promise for sequence generation. The generated sequences can however get stuck in local minima, have low diversity and their fitness depends heavily on initialization. Here, we develop deep exploration networks (DENs), a generative model tailor-made for exploring an input space to minimize the cost of a neural network fitness predictor. By making the network compete with itself to promote sequence diversity during training, we obtain generators capable of sampling hundreds of thousands of high-fitness sequences. We demonstrate DENs in the context of alternative polyadenylation. Using DENs, we engineered polyadenylation signals with more than 10-fold higher selection odds than gradient ascent-generated patterns, and validated their performance experimentally.

We introduce the largest and most diverse collection of rectified stereo image pairs to the research community, KeystoneDepth, consisting of tens of thousands of stereographs of historical people, events, objects, and scenes between 1860 and 1963. Leveraging the Keystone-Mast raw scans from the California Museum of Photography, we apply multiple processing steps to produce clean stereo image pairs, complete with calibration data, rectification transforms, and depthmaps. A second contribution is a novel approach for view synthesis that runs at real-time rates on a mobile device, simulating the experience of looking through an open window into these historical scenes. We produce results for thousands of antique stereographs, capturing many important historical moments.

Basketball is a very immersive sport and the closer you are to the court, the better the experience. Current technologies allow a limited immersion into basketball games in either as a VR experience or as a 3D visualization of a highlight after a volumetric reconstruction. Both these approaches however require manual installation of expensive equipment. What if we could convert our favorite player in 3D performing an action based on a single video? In this project, we present a system that converts a basketball video highlight of a specific player into a dynamic 3D mesh of the player.

We address the dual problems of novel view synthesis and environment reconstruction from hand-held RGBD sensors. Our contributions include 1) modeling highly specular objects, 2) modeling inter-reflections and Fresnel effects, and 3) enabling surface light field reconstruction with the same input needed to reconstruct shape alone. In cases where scene surface has a strong mirror-like material component, we generate highly detailed environment images, revealing room composition, objects, people, buildings, and trees visible through windows. Our approach yields state of the art view synthesis techniques, operates on low dynamic range imagery, and is robust to geometric and calibration errors.

Despite advances in dependency parsing, languages with small treebanks still present challenges. We assess recent approaches to multilingual contextual word representations (CWRs), and compare them for crosslingual transfer from a language with a large treebank to a language with a small or nonexistent treebank, by sharing parameters between languages in the parser itself. We experiment with a diverse selection of languages in both simulated and truly low-resource scenarios, and show that multilingual CWRs greatly facilitate low-resource dependency parsing even without crosslingual supervision such as dictionaries or parallel text. Furthermore, we examine the non-contextual part of the learned language models (which we call a "decontextual probe") to demonstrate that polyglot language models better encode crosslingual lexical correspondence compared to aligned monolingual language models. This analysis provides further evidence that polyglot training is an effective approach to crosslingual transfer.

We incorporate morphological supervision into character language models (CLMs) via multitasking and show that this addition improves bits-per-character (BPC) performance across 24 languages, even when the morphology data and language modeling data are disjoint. Analyzing the CLMs shows that inflected words benefit more from explicitly modeling morphology than uninflected words, and that morphological supervision improves performance even as the amount of language modeling data grows. We then transfer morphological supervision across languages to improve language modeling performance in the low-resource setting.

When reading text, humans make commonsense inferences that frame their understanding of the narrative being presented. For machines to achieve this capability, they must be able to acquire relevant and correct commonsense for an unbounded set of situations. We cast the problem of commonsense acquisition as knowledge base construction and investigate whether large-scale language models can effectively learn to generate the knowledge necessary to automatically construct a commonsense knowledge base.

Existing open-domain question answering (QA) models are not suitable for real-time usage because they need to process several long documents on-demand for every input query. In this paper, we introduce the query-agnostic indexable representation of document phrases that can drastically speed up open-domain QA and also allows us to reach long-tail targets. In particular, our dense-sparse phrase encoding effectively captures syntactic, semantic, and lexical information of the phrases and eliminates the pipeline filtering of context documents. Leveraging optimization strategies, our model can be trained in a single 4-GPU server and serve entire Wikipedia (up to 60 billion phrases) under 2TB with CPUs only. Our experiments on SQuAD-Open and CuratedTREC show that our model is more accurate than previous state of the arts with 6000x reduced computational cost, which translates into at least 58x faster end-to-end inference benchmark on CPUs.

Many scientific experiments proceed by repeatedly measuring some quantity of interest, and then testing whether the measured value differs from some known control. Choosing the number of repeated measurements (replicates) is an important part of the experimental design process. However, the correct number of replicates depends on the difference between the true value and the control - also known as the effect size - which is unknown to the experimenter. When many related experiments are run simultaneously (the setting of multiple hypothesis testing), we can reframe this experimental design question as a problem of learning properties of a mixture distribution. In this talk, I will describe a method to estimate the number of effect sizes above some threshold, even before we have enough replicates to identify whether any measured value differs significantly from the control. Such an estimate would enable better experimental design.

Objects are a powerful way to model both the world and tasks in the world. Many impressive results and techniques in robotics make heavy use of objects, most common for specification of the task (reward) and in physics simulators for learning and planning. Despite this, there is little work general object perception: most vision algorithms are designed and trained for datasets with limited ranges of objects. In this ongoing work, we build a perception system for model-free and model-based learning and control algorithms that works on broad ranges of objects by using simulations to generate large datasets. Building on SSC segmentation of new objects, we examine pose estimation and model reconstruction of new objects.

This talk discusses how to make federated learning robust to corrupted updates sent by the participating devices. The proposed approach relies on a new robust aggregation oracle based on the geometric median, which returns an aggregate using a constant (3-5) number of calls to a secure average oracle. The talk finally looks at experimental results on linear models and deep neural networks in tasks from computer vision and natural language processing.

Humans can continuously draw upon previous experiences to accelerate the learning of new tasks, thereby requiring minimal resources and data. Endowing artificial agents with similar capabilities is essential for rapid learning in settings with scarce, expensive, or sensitive data. Some examples include robotics where data collection is expensive, machine translation involving low-resource languages, and personalized recommendation where user data is scarce and sensitive.Meta-learning (or learning to learn) has emerged as a promising framework for acquiring aforementioned inductive capabilities. Despite an explosion of empirical work, there is little formal understanding about meta-learning. In this talk, I will describe how popular meta-learning algorithms can be formalized as bi-level optimization problems. This allows for development of a new class of algorithms that draw upon the idea of implicit differentiation. These algorithms provably enjoy better computational and memory complexity compared to current approaches, and also obtain state of the art results for recognizing novel objects with few examples.

Abstract forthcoming.

Domains from molecular systems (like DNA storage!) to medical diagnostics rely on microfluidic devices for automation. This doesn’t just make things faster; it’s essential to minimizing human error and enabling new, more complex applications. The PurpleDrop hardware and Puddle software aim to make microfluidic automation cheaper, more reliable, and easier to use.

Current statistical tools place the burden of valid, reproducible statistical analyses on the user. Users must have deep knowledge of statistics to not only identify their research questions, hypotheses, and domain assumptions but also select valid statistical tests for their hypotheses. As quantitative data become increasingly available in all disciplines, data analysis will continue to become a common task for people who may not have statistical expertise. Tea, a high-level declarative language for automating statistical test selection and execution, abstracts the details of analyses from users, empowering them to perform valid analyses by expressing their goals and domain knowledge. In this talk, I will discuss the design and implementation of Tea, lessons learned through the process, and other ongoing work in this vein.

While data visualizations play a crucial role in gaining insights from data, creating useful visualizations from a complex data set is far from an easy task. In particular, in order to create an effective visualization, the user need to both (1) understand functionality provided by existing data visualization libraries and prepare the input data to match the data shape required by the library, and (2) utilize design knowledge to improve the effectiveness of the visualization. In fact, both of the tasks assume programming knowledge from the user, and this knowledge barrier prevents non-experts to create insightful data visualizations for their tasks. Our work aims to automate the data visualization pipeline by automatically synthesizing programs that can query databases, prepare data, and plot effective visualization from user demonstration. In this talk, we will present two synthesis-based tools for data analysis and data visualization. First, we will present Falx, a visualization by demonstration tool that automatically infers data preparation and visualization scripts by allowing user to sketch how to visualize a small subset of the input data. Then, we will present our visualization reasoning engine Draco, which utilizes logic rules represented design guidelines to verify and optimize data visualizations. We will demonstrate how these tools can be applied to solve competing problems non-expert users posted in Vega-Lite/R/Excel forums and Stack Overflow.

Existing distributed storage systems do not meet the needs of real-time interactive apps. These apps feature small groups of users making concurrent modifications, tight responsiveness bounds, and wide-area distribution. As a result, they need a storage system that provides simultaneous access to multiple versions of shared state, where the versions trade off consistency and staleness, and there are versions representing the extreme ends of the consistency/staleness spectrum. This talk motivates and outlines Hercules, a distributed storage system that meets these needs using client-side caching.

In this talk, I’ll describe the design and implementation of a consistent and fault-tolerant metadata index for a scalable block storage system. The key idea underlying our system is the use of fine-grained replicated system machines, wherein every key-value pair in the index is treated as a separate replicated machine. Compared with the traditional coarse-grained sharding design, this approach allows for flexible and dynamic scheduling of operations on the metadata service and enables effective use of the storage and compute resources. To realize it, we co-design the consensus protocol with the data store and streamline the operation of the per-key replicated state machine. The resulting system demonstrates that fine-grained replicated state machines can provide significant performance benefits in both controlled testbeds as well as in production deployments.

Traditionally, the high cost of network communication between servers has hidden the impact of cross-core coordination in replicated systems. However, new technologies like kernel-bypass networking and faster network links, have exposed hidden bottlenecks in distributed systems. This talk explores how to build multicore-scalable, replicated storage systems. We introduce a new guideline for their design, called the Zero-Coordination Principle. We use this principle to design a new multicore-scalable, in-memory, replicated, key-value store, called Meerkat. Unlike existing systems, Meerkat eliminates all cross-core and cross-replica coordination, both of which pose a scalability bottleneck. Our experiments found that Meerkat is able to scale up to 80 hyper-threads and execute 8.3 million transactions per second. Meerkat represents an improvement of 12× on state-of-the-art, fault-tolerant, in-memory, transactional storage systems built using leader-based replication and a shared transaction log.

Writing correct distributed systems code is difficult, especially for novice programmers. The inherent asynchrony and need for fault-tolerance make errors almost inevitable. Industrial-strength testing and model checking have been shown to be effective at uncovering bugs, but they come at a cost ― in both time and effort ― that is far beyond what students can afford. To address this, we have developed an efficient model checking framework and visual debugger for distributed systems, with the goal of helping students find and fix bugs in near real-time. We identify two novel techniques for reducing the search state space to more efficiently find bugs in student implementations. We report our experiences using these tools to help over two hundred students build a correct, linearizable, fault-tolerant, dynamically-sharded key-value store.

The Linux kernel is one of the most widely used pieces of software today. One of the reasons for its success is its focus on extensibility - kernel behavior can be modified to adapt to different applications’ needs. At the same time, safety is critical in the kernel, and developers are forced to be conservative about what extensions to implement in order to ensure the safety of the whole kernel. For certain types of extensions, such as file systems, one option is to run code in userspace. However, even with optimizations, this approach adds unacceptable performance overhead for most use cases. This talk proposes a framework that enables developers to write Linux file systems in the kernel using Rust, interfacing with a modified version of the in-kernel portion of FUSE. By relying on compile-time safety properties and a message-passing based interface design, this framework can eliminate some classes of bugs with negligible performance overhead. Preliminary results show that a file system implemented using this framework has nearly identical performance to its C counterpart.

Wearable computing platforms, such as smartwatches and head-mounted mixed reality displays, demand new input devices for high-fidelity interaction. We present AuraRing, a wearable magnetic tracking system designed for tracking fine-grained finger movement. The hardware consists of a ring with an embedded electromagnetic transmitter coil and a wristband with multiple sensor coils. By measuring the magnetic fields at different points around the wrist, AuraRing estimates the five degree-of-freedom pose of the ring. We develop two different approaches to pose reconstruction—a first-principles iterative approach and a closed-form neural network approach. Notably, AuraRing requires no runtime supervised training, ensuring user and session independence. AuraRing has a resolution of 0.1mm and a dynamic accuracy of 4.4mm, as measured through a user evaluation with optical ground truth. The ring is completely self-contained and consumes just 2.3mW of power.

Sugar rich diets and poor dental hygiene promotes formation of a biofilm (plaque) that strongly adheres to the dental enamel surface and produces organic acid. The acid contributes to demineralization of the exterior tooth enamel and can lead to dental cavities. Measuring plaque’s acidity level can help predict early stages of tooth decay. Our device, O-pH, is a spot based optical pH device that uses changes in the spectral fluorescence of FDA allowed fluorescein dye to measure acidity levels in difficult to access dental locations such as occlusal fissures. A prototype has been developed using filtered photodiodes to and predicts pH over a pH range (4 to 7) with a 0.94 correlation coefficient.

Rapid diagnostic tests provide point-of-care medical diagnosis without the need for sophisticated laboratory equipment, making them especially useful for community healthcare workers (CHWs) in low-resource settings. Because the procedure for completing a malaria RDT (mRDT) is error-prone, particularly when it comes to interpreting the test result, CHWs are often asked to carry completed mRDTs back to their supervisors. Doing so makes the mRDTs susceptible to deterioration and introduces inefficiencies in the CHWs' workflow. In this work, we propose a smartphone-based mRDT capture app that facilitates the collection of high-quality photographs of mRDTs to support CHWs in the field. Our app does not require an external adapter to control the image capture environment, as in prior work, but instead provides real-time guidance using image processing to get the best photograph possible. We deployed our app to CHWs and their supervisors to assess its efficacy and usability. We found that our app provided 98.1% sensitivity and 99.7% specificity against direct interpretations of the mRDTs. We also found that CHWs were able to capture high-quality images of mRDTs within 19 seconds while providing both them and their supervisors with more confidence about their workflow.

Current automatic cough counting systems can determine how many coughs are present in an audio recording. However, they cannot determine who produced the cough. This limits their usefulness as most systems are deployed in locations with multiple people (i.e., a smart home device in a four-person home). Although previous work has been evaluated on forced coughs, no model exists for natural coughs collected in-the-wild. Because limited natural cough data exists, preventing model overfitting is challenging. In this work, we overcome this problem by using multitask learning, where the second task is speaker verification. Our model achieves 82.15% classification accuracy among four users on a natural, in-the-wild cough dataset, outperforming human evaluators on average by 9.82%.