IT-Forum

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.

Soft covering is a phenomenon whereby an i.i.d. distribution on sequences of a given length is approximately produced from a very structured generation process. Specifically, a sequence is drawn uniformly at random from a "codebook" of sequences and then corrupted by memoryless noise (i.e. a discrete memoryless channel, or DMC). Among other things, soft covering means that the codebook is not recognizable in the resulting distribution. The soft covering phenomenon occurs when the codebook itself is constructed randomly, with a correspondence between the codebook distribution, the DMC, and the target i.i.d. distribution, and when the codebook is large enough. Mutual information is the minimum exponential rate for the codebook size. We show the exact exponential rate of convergence of the approximating distribution to the target, as measured by total variation distance, as a function of the excess codebook rate above mutual information. The proof involves a novel Poisson approximation step in the converse.

Soft covering is a crucial tool for secrecy capacity proofs and has applications broadly in network information theory for analysis of encoder performance. Wyner invented this tool for the purpose of solving a problem he named "common information." The quantum analogue of Wyner's problem is "entanglement of purification," which is an important open problem with physical significance: What is the minimum entanglement needed to produce a desired quantum state spanning two locations? The literature on this problem identifies sufficient asymptotic rates for this question that are generally excessively high. I will make brief mention of how the soft covering principle might be utilized for a more efficient design in this quantum setting.

Automated decision making tools are currently used in high stakes scenarios. From natural language processing tools used to automatically determine one's suitability for a job, to health diagnostic systems trained to determine a patient's outcome, machine learning models are used to make decisions that can have serious consequences on people's lives. In spite of the consequential nature of these use cases, vendors of such models are not required to perform specific tests showing the suitability of their models for a given task. Nor are they required to provide documentation describing the characteristics of their models, or disclose the results of algorithmic audits to ensure that certain groups are not unfairly treated. I will show some examples to examine the dire consequences of basing decisions entirely on machine learning based systems, and discuss recent work on auditing and exposing the gender and skin tone bias found in commercial gender classification systems. I will end with the concept of an AI datasheet to standardize information for datasets and pre-trained models, in order to push the field as a whole towards transparency and accountability.