Encoding data efficiently for many prediction tasks using universal features
Communication Complexity of Universal Features
Data Structures and AlgorithmsMachine Learning
Summary
This paper studies how to create compact data summaries that can be used to predict answers for many different questions later on. The authors design a method that encodes data using patterns from a selected small set of test functions, keeping the size of the summary small and predictable. They prove their encoding is as small as possible in the worst case, and also show ways to learn such summaries from unlabeled data. Their experiments demonstrate the tradeoff between summary size and prediction accuracy and connect their approach to ideas in neural autoencoders.
What this means in practice
- •For machine learning engineers: Create compact data representations that allow many prediction models to run efficiently without knowing the target task in advance.
- •For data compression teams: Design encodings of data optimized to support accurate evaluations for large families of functions, reducing storage while preserving predictability.
Authors
Lunjia Hu, Anish Jayant, Peter Li, Princewill Okoroafor, Abhishek Shetty
Abstract
Motivated by the notion of features from machine learning, we study the complexity of representing data that allows for evaluation with a given family of functions. Concretely, we consider a deterministic encoder that observes $X\sim D$ and produces a finite encoding before a task $f\in\mathcal{F}\subseteq\{0,1\}^{\mathcal{X}}$ is specified. For each task, a decoder must predict $f(X)$ with error at most $\varepsilon$ under $D$. We construct an encoder that outputs a representation with $O(d^{*}\log(1/\varepsilon))$ bits, where $d^{*}$ is the dual VC dimension of $\mathcal{F}$. Our encoder greedily selects $O((d^{*}/\varepsilon)\log(1/\varepsilon))$ functions from the class and uses their joint label pattern to produce the encoding. The key idea in our upper bound is a novel potential function argument, where we compare the entropy gained from each greedy selection with the number of patterns allowed by the dual VC dimension. We present lower bounds showing that the representation length achieved by our encoder is worst-case optimal for every $d^* \ge 1$ and $\varepsilon < 1/4$ up to a universal constant factor, and instance-wise optimal for every family $\mathcal{F}$ up to an $O(\log(1/\varepsilon))$ factor. We give two ways to learn the representation from unlabeled samples, with different guarantees on the representation size and sample complexity. Experimentally, we verify the greedy construction's accuracy-size tradeoff and explore its connection to neural sparse autoencoders.