fewlab: fewest items to label for most efficient unbiased OLS

Buy the labels that buy the smallest standard error.

You have a usage matrix: rows are people, columns are things they used. Websites, merchants, products, surnames. You want to regress something about the column on features of the row, but finding out what the column is costs money, and you cannot afford all of them.

On a real browsing panel, labeling 250 of 34,078 domains recovers the same regression coefficients as labeling all of them, with a ninth of the error that spending the same 250 labels at random would give. The estimate stays exactly unbiased and reports a standard error you can put in a table.

Contents:

• Quickstart
  • Build a study
  • Design, draw, estimate
  • Choose a risk ceiling instead of a budget
  • Two standard errors
  • Rankings are not samples
  • Choosing the criterion
• Examples
  • Try it in your browser
  • A browsing panel
  • Costs that differ by entity
  • A mutually exclusive taxonomy
  • A transparent design for a labeling vendor
  • Fewest labels for a fixed precision
  • Comparing against a random baseline
• API Reference
  • Study
  • Influence
  • Designs
  • Estimation
  • Labels as covariates
  • Counts
  • Balanced sampling
  • Calibration
  • Fewest labels for a fixed standard error
• Mathematical background
  • The estimand
  • The decomposition
  • Unbiasedness
  • Which entities are worth labeling
  • When the choice cannot matter
  • The optimal design
  • Minimum cost for a risk ceiling
  • Certainty core with a uniform tail
  • Variance
  • When the label is a covariate
  • References
• Evaluation
  • What is measured
  • Reproducing it

Why it works

Write \(V\) for row shares and \(A\) for entity labels. The complete-label regression coefficient is

\[\beta^* = (X^\top X)^{-1} X^\top V A = \sum_j h_j a_j^\top\]

exactly, with no error term. Entity \(j\)’s entire contribution is \(h_j a_j^\top\), and \(h_j\) is computable from usage counts and features before a single label is bought. Everything else follows: the optimal inclusion probabilities, the certainty core, and the standard errors.

Two goals, and neither is traded for the other. Unbiasedness is a constraint: every contributing entity gets positive probability and reciprocal weight. Minimum standard error is what you optimize subject to it.

Installation

pip install fewlab

Requires Python 3.12 or later, numpy and pandas.

Evidence

The numbers above come from Evaluation, which scores every design against a population whose labels are all known, so there is a fixed truth to be measured against. Reproduce it with python benchmarks/make_exhibits.py.

License

MIT