IT-Forum

Individuals of all genders invited to be a part of:
#StanfordToo: A Conversation about Sexual Harassment in Our Academic Spaces, where we will feature real stories of harassment at Stanford academic STEM in a conversation with Provost Drell, Dean Minor (SoM), and Dean Graham (SE3). We will have plenty of time for audience discussion on how we can take concrete action to dismantle this culture and actively work towards a more inclusive Stanford for everyone. While our emphasis is on STEM fields, we welcome and encourage participation from students, postdocs, staff, and faculty of all academic disciplines and backgrounds.

The availability of massive public image datasets appears to have hardly been exploited in image compression. In this work, we present a novel framework for image compression based on human image generation and publicly available images as "side information." Our framework consists of one human who describes images using text instructions to another, who is tasked with reconstructing the original image to the first human's satisfaction. These image reconstructions were then rated by human scorers on the Amazon Mechanical Turk platform and compared to reconstructions obtained by existing image compressors. While this setup lacks certain components typical of traditional compressors, the insights gained from these experiments offer a new perspective on designing image compressors of the future.

The Santa Clara Valley chapters of the IEEE Information Theory and Signal Processing societies are co-sponsors this event.

Universal learning is considered from an information theoretic point of view following the universal prediction approach pursued in the 90's by F&Merhav. Interestingly, the extension to learning is not straight-forward. In previous works we considered on-line learning and supervised learning in a stochastic setting. Yet, the most challenging case is batch learning where prediction is done on a test sample once the entire training data is observed, in the individual setting where the features and labels, both training and test, are specific individual quantities. This work provides schemes that for any individual data compete with a "genie" (or reference) that knows the true test label. It suggests design criteria and derive the corresponding universal learning schemes. The main proposed scheme is termed Predictive Normalized Maximum Likelihood (pNML). As demonstrated, pNML learning and its variations provide robust, "stable" learning solutions that outperforms the current leading approach based on Empirical Risk Minimization (ERM). Furthermore, the pNMLconstruction provides a pointwise indication for the learnability that measures the uncertainty in learning the specific test challenge with the given training examples - thus the learner knows when it does not know. The improved performance of the pNML, the induced learnability measure and its utilization are demonstrated in several learning problems including deep neural networks models.

Joint work with Yaniv Fogel and Koby Bibas

Positioning has been the Holy Grail of wireless sensing research with a wide range of applications from tracking virtual reality devices to in-body implants. However, despite two decades of active research, a widely deployable system with high accuracy has always been elusive. Wireless signals reflected from objects in the environment interfere with and distort the signal from the intended target device, corrupting the position estimates. In order to fight this 'multipath' phenomenon, previous approaches built specialized wireless devices with huge antenna arrays or large bandwidths making them impractical for ubiquitous deployment. In this talk, I will introduce a new technique called 'Synthetic Aperture Radio' that harnesses, rather than fighting, the multipath that naturally occurs in the environment and exploits the device motion that naturally occurs in these applications. By applying this technique, I have demonstrated the first real-time and centimeter-level accurate positioning system using standard, off-the-shelf WiFi radios. Building on synthetic aperture radio technique, I have developed practical positioning systems for indoor navigation, tracking virtual reality accessories and resource constrained devices like endoscopic capsules. Looking forward, these techniques lay a foundation for utilizing ubiquitous wireless devices for developing important machine vision applications in various domains like medical sensing, physical security and autonomous vehicles.

DNA based storage is a novel technology, where digital information is stored in synthetic DNA molecules. The recent advance in DNA sequencing methods and decrease in sequencing costs have paved the way for storage methods based on DNA. The natural stability of DNA molecules, (the genetic information from fossils is maintained over tens of thousands of years) motivate their use for long-term archival storage. Furthermore, because the information is stored on molecular levels, such storage systems have extremely high data densities. Recent experiments report data densities of 2 PB/gram, which corresponds to the capacity of a thousand conventional hard disk drives in one gram of DNA.

In this talk we present error-correcting codes for the storage of data in synthetic DNA. We investigate a storage model where data is represented by an unordered set of M sequences, each of length L. Errors within that model are a loss of whole sequences and point errors inside the sequences, such as insertions, deletions and substitutions. We derive Gilbert-Varshamov lower bounds and sphere packing upper bounds on achievable cardinalities of error-correcting codes within this storage model. We further propose explicit code constructions than can correct errors in such a storage system that can be encoded and decoded efficiently. Comparing the sizes of these codes to the upper bounds, we show that many of the constructions are close to optimal.

Compression has for decades served primarily the utilitarian purpose of enabling easier storage and transmission of data. Here however, I show how compression can be used to better understand biological processes and assist in data analysis.

First, I will demonstrate the relationship between lossy compression and understanding the perceptual characteristics of downstream agents. Quartz, my lossy compression program for next-generation sequencing quality scores counterintuitively improves SNP calling, despite discarding 95% of quality scores, showing the oversensitivity of variant callers to sequencer noise. More recently, I developed HyperMinHash, a lossy floating-point compression of the popular MinHash Jaccard index sketch, that reduces the space-complexity from log(n) to loglog(n) by using the understanding that MinHash cares less about large hash values than smaller ones.

In the second part of this talk, I show how we exploit the compressive structure of biological data to speed up similarity search. I prove that by organizing the database to facilitate clustered search, our time-complexity scales with metric entropy (number of covering hyperspheres) if the fractal dimension of a dataset is low. This is the key insight behind our compressively accelerated versions of standard tools in genomics (CORA, 10-100x speedup for all-mapping of NGS reads), metagenomics (MICA, 3.5x speedup Diamond), and chemical informatics (Ammolite, 150x speedup SMSD).

Modern cloud storage systems need to store vast amounts of data in a fault tolerant manner, while also preserving data reliability and accessibility in the wake of frequent server failures. Traditional MDS (Maximum Distance Separable) codes provide the optimal trade-off between redundancy and number of worst-case erasures tolerated. Minimum storage regenerating (MSR) codes are a special sub-class of MDS codes that provide mechanisms for exact regeneration of a single code-block by downloading the minimum amount of information from the remaining code-blocks. As a result, MSR codes are attractive for use in distributed storage systems to ensure node repairs with optimal repair- bandwidth. However, all known constructions of MSR codes require large sub-packetization levels (which is a measure of the granularity to which a single vector codeword symbol needs to be divided into for efficient repair). This restricts the applicability of MSR codes in practice.

This talk will present a lower bound that exponentially large sub- packetization is inherent for MSR codes. We will also propose a natural relaxation of MSR codes that allows one to circumvent this lower bound, and present a general approach to construct MDS codes that significantly reduces the required sub-packetization level by incurring slightly higher repair-bandwidth as compared to MSR codes.

The lower bound is joint work with Omar Alrabiah, and the constructions are joint work with Ankt Rawat, Itzhak Tamo, and Klim Efremenko.

Maximum likelihood estimation (MLE) is influential because it can be easily applied to generate optimal, statistically efficient procedures for broad classes of estimation problems. Nonetheless, the theory does not apply to modern settings --- such as problems with computational, communication, or privacy considerations --- where our estimators have resource constraints. In this talk, I will introduce a modern maximum likelihood theory that addresses these issues, focusing specifically on procedures that must be computationally efficient or privacy- preserving. To do so, I first derive analogues of Fisher information for these applications, which allows a precise characterization of tradeoffs between statistical efficiency, privacy, and computation. To complete the development, I also describe a recipe that generates optimal statistical procedures (analogues of the MLE) in the new settings, showing how to achieve the new Fisher information lower bounds.

While DNA sequencing technology has undergone a major revolution, the read lengths afforded by most current generation sequencing technologies still remain small (in the range of hundreds of DNA base-pairs). These short reads are then stitched together with algorithms that exploit the overlap between these reads in order to reconstruct the DNA. Long repeated regions of the DNA greater than this short read length, which are common, are not resolvable with this technology, requiring sequencers capable of accurate long reads. Nanopore sequencing promises to address this problem, by increasing the read lengths by orders of magnitude (up to 10K-100K bases). However, nanopore sequencers built to date, have higher error rates than the short-read technologies, which if unresolved could limit their applications. There are many algorithmic challenges in realizing this potential, due to many transformations between the DNA nucleotide and the nanopore current output. Impairments in nanopore sequencers include inter-symbol interference (multiple bases affect each observation), random channel variations, insertions/deletions and noise. In this talk we develop signal-level mathematical models for the nanopore channel, which allows us to develop information theoretic bounds for its decoding capability. We will apply these to some experimental nanopore sequencer data to develop some preliminary understanding of the trade-offs in their performance. We will also use the insights from this modeling to develop novel nanopore alignments techniques which we evaluate using real datasets.

This talk is joint work with Wei Mao, Dhaivat Joshi, Sreeram Kannan and Shunfu Mao.

Student evaluations of teaching (SET) are widely used in academic personnel decisions as a measure of teaching effectiveness. The way SET are used is statistically unsound--but worse, SET are biased and unreliable. Observational evidence shows that student ratings vary with instructor gender, ethnicity, and attractiveness; with course rigor, mathematical content, and format; and with students' grade expectations. Experiments show that the majority of student responses to some objective questions can be demonstrably false. A recent randomized experiment shows that giving students cookies increases SET scores. Randomized experiments show that SET are negatively associated with objective measures of teaching effectiveness and biased against female instructors by an amount that can cause more effective female instructors to get lower SET than less effective male instructors. Gender bias also affects how students rate objective aspects of teaching. It is not possible to adjust for the bias, because it depends on many factors, including course topic and student gender. Students are uniquely situated to observe some aspects of teaching and students' opinions matter. But for the purposes of evaluating and improving teaching quality, SET are biased, unreliable, and subject to strategic manipulation. Reliance on SET for employment decisions disadvantages protected groups and may violate federal law. For some administrators, risk mitigation might be a more persuasive argument than equity for ending reliance on SET in employment decisions: union arbitration and civil litigation over institutional use of SET are on the rise. Several major universities in the U.S. and Canada have already de-emphasized, substantially re-worked, or abandoned reliance on SET for personnel decisions.