Mathematical background¶
This page states the identity the package rests on and the design results that
follow from it. The manuscript in ms/ gives the same material with proofs,
related work, and the empirical evaluation.
The estimand¶
Rows are units and columns are entities that carry an expensive label. With counts \(C\), row totals \(T_i = \sum_j c_{ij}\), and row shares \(V_{ij} = c_{ij}/T_i\), entity \(j\) carries a label \(a_j\) and the unit-level outcome is the share of activity on labeled entities:
With unit features \(X\), the estimand is the coefficient you would obtain by labeling every entity in the frame, \(\beta^* = (X^\top X)^{-1} X^\top y\).
The decomposition¶
Writing \(H = (X^\top X)^{-1} X^\top V\) with columns \(h_j\),
This is an identity. There is no error term, no distributional assumption, and no covariance to approximate. Entity \(j\)’s entire contribution is \(h_j a_j\), and \(h_j\) depends only on \((C, X)\), so it is known before any label is purchased.
The algebra carries a vector label \(a_j \in \mathbb{R}^q\) unchanged, giving \(\beta^* = \sum_j h_j a_j^\top\). A mutually exclusive taxonomy and a coder’s probability distribution over classes therefore need no special handling.
Unbiasedness¶
Sample entities with inclusion probabilities \(\pi_j\) and indicators \(I_j\) that do not depend on the unknown labels. Then
is design-unbiased, since \(\mathbb{E}[I_j/\pi_j] = 1\) and everything else is fixed. Unbiasedness is a constraint on the design rather than a property to hope for: it holds exactly when every entity with \(h_j \neq 0\) gets positive probability and enters with weight \(1/\pi_j\).
An entity nobody touched has \(h_j = 0\) and contributes nothing, so it may be left unlabeled at no cost in bias. That is the only case in which \(\pi_j = 0\) is correct.
Selecting the top \(K\) entities by any criterion assigns probability one
above the cut and zero below it. Its bias is \(-\sum_{j \notin S} h_j a_j\),
which depends on labels nobody bought and so cannot be estimated or bounded from
the data in hand. This is why fewlab.Ranking cannot be passed to an
estimator.
Which entities are worth labeling¶
For a positive semidefinite \(W\), the loss \(\operatorname{tr}[W(\widehat\beta - \beta^*)(\widehat\beta - \beta^*)^\top]\) has exact design risk under independent Bernoulli sampling
The criterion enters only through \(b_j\), and it has to be declared.
|
\(W\) |
\(b_j\) for a one-hot taxonomy |
|---|---|---|
|
\(I\) |
\(h_j^\top h_j = g_j^\top (X^\top X)^{-2} g_j\) |
|
\(X^\top X\) |
\(g_j^\top (X^\top X)^{-1} g_j\) |
|
\(LL^\top\) |
\(\lVert L^\top h_j \rVert^2\) |
|
see below |
\(\lVert v_j \rVert^2 - h_j^\top X^\top X h_j\) |
On a well-conditioned \(X^\top X\) the first three rank entities almost identically. They diverge when \(X^\top X\) is far from a scaled identity and the \(h_j\) span several directions, where they can disagree on roughly a fifth of a budget. There is no target-free answer.
When the choice cannot matter¶
If every \(h_j\) points in the same direction and entities differ only in magnitude, then \(b_j \propto \lVert h_j \rVert^2\) under every \(W\), every criterion induces the same ordering, and the estimand stops mattering. Expected counts of the form \(\text{activity}_i \times \text{popularity}_j\) produce exactly this degeneracy.
fewlab.direction_spectrum() reports it. Read it against a noise floor of
roughly \(1/\sqrt{\bar c}\) for average count \(\bar c\), because integer
counts inject spurious directions at that scale; an absolute cutoff would call
the same population more degenerate simply for being observed more heavily.
The optimal design¶
Minimizing the risk subject to \(\sum_j c_j \pi_j = K\) and \(\pi_j \le 1\) gives
for the \(\lambda\) that exhausts the budget. The cap is not a separate rule for large entities: the set on which it binds is the certainty core. The square root rule also settles the unbiasedness constraint by itself, since it gives strictly positive probability to every entity with \(b_j > 0\). A probability floor is therefore unnecessary, and any floor moves the design away from minimum risk.
Minimum cost for a risk ceiling¶
fewlab.min_cost_for_risk() solves the reverse problem:
Convexity and the stationarity conditions give the same capped square-root rule. For a proposed uncapped tail \(T\), the binding risk constraint determines
Sort by \(\sqrt{b_j/c_j}\), starting with an empty certainty core. Promote an entity only if its proposed probability exceeds one, and recompute the tail expression. This gives the global optimum in \(O(m\log m)\) time. With \(R=0\), label every positive-score entity with certainty. Zero-score entities never need labels for the declared loss.
Unit label norms give exact aggregate risk for a complete one-hot taxonomy. For an unknown binary indicator they bound its squared norm and therefore its risk. Estimated norms give a planning criterion rather than a guaranteed bound. A single contrast uses its variance (SE squared) as the ceiling; joint coefficient loss sums variances over coefficient and label columns. A zero contrast score does not imply zero contribution to every other coefficient, so the guarantee applies only to the declared estimand.
Use fewlab.Study.design_for_risk() followed by
study.draw(design, fixed_size=False) and the plain Horvitz-Thompson estimator.
The ceiling bounds label-sampling risk under independent draws. It excludes
regression uncertainty and realized errors and does not transfer automatically
to balanced draws, proxy residuals, or shrunken weights.
Certainty core with a uniform tail¶
Order \(b_1 \ge \cdots \ge b_m\), take the first \(H\) with certainty, and give the remainder \(p_H = (K-H)/(m-H)\). With \(S_H = \sum_{j>H} b_j\),
so the boundary follows from evaluating at most \(K\) cutoffs. Promoting one more entity pays exactly when \(b_{H+1} > S_H/(K-H)\).
This is exact for a Bernoulli tail. A fixed-size simple random tail instead uses centered contributions and a finite-population correction. Its variance can exceed this criterion when contributions have opposite signs.
Variance¶
The design covariance of \(\operatorname{vec}(\widehat\beta)\) is \(\sum_j \frac{1-\pi_j}{\pi_j} (a_j a_j^\top) \otimes (h_j h_j^\top)\), estimated without bias from the sample by \(\sum_{j \in S} \frac{1-\pi_j}{\pi_j^2} (a_j a_j^\top) \otimes (h_j h_j^\top)\).
This is exact under Poisson sampling. Fixed-size and balanced draws also depend on joint inclusion probabilities; the Poisson expression is not a universal upper bound for their variance. Use variance estimators appropriate to the draw, and do not interpret a variance ceiling as a confidence-interval coverage guarantee.
The total standard error has a second component the budget cannot touch:
Their ratio is a stopping rule. Estimate.diagnostics["variance_ratio"]
reports the share owed to the labeling budget.
When the label is a covariate¶
If the constructed share appears on the right-hand side of a regression rather
than the left, the guarantee fails: an unbiased noisy covariate attenuates its
own coefficient, and the attenuation shrinks with the labeling budget rather
than with the size of the panel. Because the design chose \(\pi\), the error
variance is known and the attenuation can be corrected. See
fewlab.estimate_share_effect().
References¶
Horvitz, D. G., & Thompson, D. J. (1952). A generalization of sampling without replacement from a finite universe.
Deville, J.-C., & Tillé, Y. (2004). Efficient balanced sampling: the cube method.
Deville, J.-C., & Särndal, C.-E. (1992). Calibration estimators in survey sampling.
Clark, R. G. (2022). Sample design for analysis using high-influence probability sampling.
Potter, F. (1990). A study of procedures to identify and trim extreme sampling weights.