Blame for code/notes/src/0210-data-selection-contamination.tex

\documentclass[11pt]{article}
\usepackage{common}
\begin{document}
\notehead{0210}{Data selection and contamination}{Batch M2, after 0206 and 0209. Companion notebook: \texttt{notebooks/0210-data-selection-contamination.ipynb} (closed forms against Monte Carlo and exact enumeration, a character $n$-gram language model with known membership; executed, 37 checks).}

\begin{problem}
\question{When data is chosen by a score computed from the same samples that are later used to judge it, which of its apparent properties are real, and how can we tell that an evaluation item was seen in training?}
Training data is selected twice: once at corpus scale (DeepSeekMath's fastText classifier recalls math pages from Common Crawl \cite{dsmath}) and once at problem scale (RL keeps problems whose pass rate lies in a band, 0206). Evaluation then asks two questions about the result: did the selected data help, and is the benchmark clean? Each question has a statistical trap. A classifier with a high AUC can still harvest mostly junk when the target is rare; a band computed from the same $G$ samples as the gradient reweights problems by the statistic that defines their gradient; ``unsolved problems improved'' can be pure regression to the mean; MinHash estimates a similarity, not containment, with an error that is a simple binomial; and negative log-likelihood (NLL) gaps detect membership only after intrinsic difficulty is cancelled. The answers below make each trap a formula and check it.
\end{problem}
\stepcounter{section}% the problem box counts as section 1: keeps every \S and notebook cross-reference stable

\section{Notation}
\begin{center}
\begin{tabular}{@{}p{0.36\linewidth}p{0.60\linewidth}@{}}
\toprule
Symbol & Meaning \\ \midrule
$\pi,\ M$ & fraction of relevant pages in the pool, pool size \\
$d',\ t$ & binormal separation of the classifier score, selection threshold \\
$\mathrm{TPR},\mathrm{FPR}$ & $\bar\Phi(t-d')$, $\bar\Phi(t)$ with $\bar\Phi=1-\Phi$ \\
$g,\ h$ & downstream gain of a selected relevant page, harm of a selected irrelevant one (to be measured) \\
$n,\ c,\ \hat p=c/n$ & samples per problem, successes, observed pass rate; $\hat g=\hat p(1-\hat p)$ (0206) \\
$J(A,B)=|A\cap B|/|A\cup B|$ & Jaccard similarity of shingle sets; $k$ = number of MinHash functions; $\hat J$ its estimate \\
$b,\,r$ & LSH bands and rows per band ($k=br$) \\
$\Delta,\ \sigma$ & NLL gap between non-members and members, within-group NLL standard deviation \\ \bottomrule
\end{tabular}
\end{center}

\section{Derivation}
\subsection{Classifier harvesting is a detection problem with a prior}
DeepSeekMath trains a fastText classifier on $500{,}000$ OpenWebMath pages (positives) against $500{,}000$ Common Crawl pages (negatives), ranks the deduplicated crawl by classifier score and keeps the top pages; in the first iteration the volume kept was chosen by pre-training experiments on the top $40$B, $80$B, $120$B and $160$B tokens, and the first iteration kept $40$B. Four iterations later the corpus is $35.5$M pages and $120$B tokens, and in the fourth iteration $98\%$ of the data had already been collected in the third \cite{dsmath}. In the abstract, with a pool in which a fraction $\pi$ is relevant, a classifier score $s\sim\mathcal N(d',1)$ for relevant and $\mathcal N(0,1)$ for other pages, and a threshold $t$,
\[
\mathrm{recall}=\bar\Phi(t-d'),\qquad
\mathrm{precision}=\frac{\pi\,\mathrm{TPR}}{\pi\,\mathrm{TPR}+(1-\pi)\,\mathrm{FPR}} .
\]
Precision depends on the prior $\pi$ and not only on the AUC $=\Phi(d'/\sqrt2)$. With $d'=2.5$ (AUC $0.962$) and $t=2$, recall is $0.69$, and precision is $0.235$ when $\pi=0.01$ but $0.884$ when $\pi=0.2$: the same classifier and threshold. The number that matters for web-scale harvesting ($\pi$ small) is therefore the precision at the chosen operating point, which is estimated by labelling a sample of the \emph{selected} pages; the training-set AUC says little. \ver{closed forms against $4\times10^6$ simulated pages: precision $0.2349$ (within $1.5\times10^{-4}$), recall $0.6915$ (within $2.7\times10^{-3}$).}

\textbf{Which threshold?} Let a selected relevant page add $g$ and an irrelevant one subtract $h$ (dilution of the token budget). The expected net gain is $G(t)=M[\pi\,\mathrm{TPR}(t)\,g-(1-\pi)\,\mathrm{FPR}(t)\,h]$; $G'(t)=0$ where the marginal page breaks even, i.e.\ where the posterior $\Pr[\text{relevant}\mid s=t]=h/(g+h)$. For the binormal model this is
\[
t^\star=\frac{d'}2+\frac1{d'}\ln\frac{(1-\pi)\,h}{\pi\,g}.
\]
It is a posterior cutoff: it moves with the prior and the harm ratio, not with the F1 score. With $\pi=0.01$, $g=h=1$: $t^\star=3.088$ against the max-F1 threshold $2.626$, and the gain per pool page at the F1 threshold is $2.2\times10^{-4}$ against $1.8\times10^{-3}$ at $t^\star$ (eight times lower). $g$ and $h$ are \emph{measured} by training, which is why DeepSeekMath chose the volume by pre-training experiments rather than by a classifier statistic. \ver{argmax of $G$ on a grid of $6\times10^4$ thresholds agrees with $t^\star$ to $4.8\times10^{-5}$; the posterior at $t^\star$ equals $h/(g+h)$ to $10^{-16}$.}

\textbf{Why iterate.} Positives in a cluster that the seed does not cover score like negatives. If a fraction $\kappa_r$ of relevant pages lies in clusters covered by the seed at round $r$ (score separation $d_{\mathrm{in}}$, the others $d_{\mathrm{out}}$) then $\mathrm{recall}_r=\kappa_r\bar\Phi(t-d_{\mathrm{in}})+(1-\kappa_r)\bar\Phi(t-d_{\mathrm{out}})$, and adding a fraction $\gamma$ of the uncovered clusters per round gives $\kappa_{r+1}=\kappa_r+\gamma(1-\kappa_r)$: recall increments shrink with ratio exactly $1-\gamma$, which is the diminishing yield seen in the fourth round. DeepSeekMath's re-seeding step is the domain rule: a domain with more than $10\%$ of its pages already collected is treated as mathematical and its mathematical URLs are annotated by hand \cite{dsmath}. \ver{toy with $d_{\mathrm{in}}=3,d_{\mathrm{out}}=0.5,\gamma=0.5$: recall $0.299,0.570,0.706,0.774,0.808$; increment ratios $0.5,0.5,0.5$.}

\subsection{Pass-rate band selection is importance weighting}
For a problem with true pass rate $p$ and $n$ samples, the mean-baseline gradient magnitude is $\hat g=\hat p(1-\hat p)$ with $\E\hat g=(1-\frac1n)p(1-p)$ (0206). Keeping the problem iff $\hat p\in[\mathrm{lo},\mathrm{hi}]$ multiplies its gradient by an indicator, so the effective weight of a problem is a function of its \emph{true} $p$:
\[
w_{\mathrm{same}}(p)=\frac{\E[\hat g\,\ind\{\hat p\in\mathrm{band}\}]}{p(1-p)},\qquad
w_{\mathrm{ind}}(p)=\Bigl(1-\frac1n\Bigr)\Pr[\hat p'\in\mathrm{band}],
\]
where $w_{\mathrm{ind}}$ is the weight if the band is decided from an independent pilot estimate $\hat p'$ (the indicator is then independent of $\hat g$). Both are exact finite sums over $c\sim\mathrm{Bin}(n,p)$. The difference is $\Cov(\hat g,\ind)/(p(1-p))$: selecting on a statistic correlated with the gradient's size reweights \emph{upwards}. For $n=8$ and the band $\hat p\in[1/8,6/8]$:
\begin{center}\small
\begin{tabular}{@{}rrrr@{}}
\toprule
$p$ & $w_{\mathrm{same}}$ & $w_{\mathrm{ind}}$ & ratio \\ \midrule
$0.02$ & $0.875$ & $0.131$ & $6.7$ \\
$0.10$ & $0.875$ & $0.498$ & $1.76$ \\
$0.50$ & $0.861$ & $0.841$ & $1.02$ \\
$0.90$ & $0.410$ & $0.164$ & $2.5$ \\
$0.98$ & $0.100$ & $0.009$ & $11$ \\ \bottomrule
\end{tabular}
\end{center}
A problem with $p=0.02$ is kept only when it happens to produce one success in eight samples, and then contributes the full gradient of an $\hat p=1/8$ problem, so its effective weight is nearly that of a mid-band problem. The band is therefore soft in the true pass rate; with the pool $p\sim\mathrm{Beta}(0.6,1.4)$ the fraction kept is $0.623$ (beta-binomial exact $0.623$), and $20.9\%$ of the kept problems have true $p$ outside the nominal band $[0.125,0.75]$. Choosing the band from a separate pilot estimate removes the covariance term but not the noise in $\hat p'$. \ver{exact sums at seven values of $p$; $w_{\mathrm{same}}(0.1)$ against $2\times10^6$ draws within $0.1\%$; beta-binomial band probability within $2.2\times10^{-4}$ of Monte Carlo.}

\subsection{Regression to the mean when the same samples select and evaluate}
Let $p\sim\mathrm{Beta}(a,b)$ and $c\mid p\sim\mathrm{Bin}(n,p)$. By conjugacy $p\mid c\sim\mathrm{Beta}(a+c,\,b+n-c)$, so
\[
\E[p\mid c]=\frac{a+c}{a+b+n}.
\]
Select the problems with $c=0$ (``unsolved'') and re-sample them with \emph{no training in between}: the pass rate is $a/(a+b+n)>0$, an apparent gain from nothing. With $(a,b,n)=(0.6,1.4,8)$: $c=0\to0.060$, $c=1\to0.160$ (observed $0.125$), $c=2\to0.260$ (observed $0.250$). The effect is large for the selected extreme and fades toward the pool mean $a/(a+b)=0.30$. If a training effect $+\tau(1-p)$ is applied to a random half of the selected $c=0$ problems and not to the other half, the naive before/after change on the trained half is $+0.088$, the untrained control moves by $+0.060$ with no intervention, and the difference-in-differences recovers the true $+0.028$. Hence: (i) select on one sample set and evaluate on a fresh one; (ii) report a held-out, untrained control selected by the same rule; (iii) never read a before/after change on a subset chosen by the ``before'' score as a training effect. \ver{$3\times10^6$ simulated problems: fresh pass rate given $c=0,1,2$ equals $(a+c)/(a+b+n)$ within $9\times10^{-5},3.5\times10^{-4},1.4\times10^{-4}$; DiD $+0.0282$ against true $+0.0282$.}

\subsection{MinHash and the Jaccard estimation error}
Let $h_1,\dots,h_k$ be independent uniformly random permutations of the shingle universe. For each, $\Pr[\min h_i(A)=\min h_i(B)]=J(A,B)$: the minimum over $A\cup B$ is attained at a uniformly random element of the union, and the two minima agree iff that element lies in $A\cap B$. Hence $k\hat J\sim\mathrm{Bin}(k,J)$,
\[
\E\hat J=J,\qquad\Var\hat J=\frac{J(1-J)}k,
\]
and for a $\pm\epsilon$ interval at $95\%$ the worst case $J=\tfrac12$ needs $k\ge z^2/(4\epsilon^2)$: $385$ for $\epsilon=0.05$, $2401$ for $0.02$, $9604$ for $0.01$. At the common $k=128$ the standard deviation is $0.035$ at $J=0.8$, so a pair with $J=0.75$ is flagged by the rule $\hat J\ge0.8$ with probability $0.090$ and a pair with $J=0.85$ is missed with probability $0.064$; the threshold is a soft boundary, and the notebook shows the exact binomial flag probability. \ver{$3000$ replications of $k=128$ random permutations: $\E\hat J$ within $4.4\times10^{-4}$ of $J=0.4286$, $\Var\hat J$ within $3.1\%$ of $J(1-J)/k$; exact flag probability at $J=0.75$ against $2\times10^6$ draws within $1.5\times10^{-4}$.} A practical linear hash $(ax+b)\bmod p$ is pairwise independent but not min-wise independent; its measured bias here is $+0.0037$ (MC s.e.\ $0.0008$), small and not zero.

\textbf{LSH banding.} Splitting $k=br$ hashes into $b$ bands of $r$ and calling two documents candidates if any band agrees in all $r$ rows gives $\Pr[\text{candidate}]=1-(1-J^r)^b$, an S-curve with knee near $(1/b)^{1/r}$; for $b=20,r=5$ it is $0.048,0.470,0.802,0.9996$ at $J=0.3,0.5,0.6,0.8$ and the knee is $0.549$. \ver{each value within Monte Carlo error of $4\times10^5$ simulated band draws.}

\textbf{Jaccard is not containment.} A benchmark item of $40$ shingles inside a web page of $2000$ shingles has $J=0.02$ although the item is \emph{entirely} contained, so a threshold of $0.8$ never flags it; the exact $n$-gram test used by DeepSeekMath (any text segment containing a $10$-gram that exactly matches a benchmark substring is removed, with exact matching for benchmark texts shorter than $10$ but at least $3$ grams \cite{dsmath}) is a containment test. Containment follows from Jaccard and the sizes, $|A\cap B|=J(|A|+|B|)/(1+J)$, but the estimator amplifies noise when $J$ is tiny: at $k=128$ the containment estimate for this example has mean $0.997$ and standard deviation $0.60$. Use MinHash for near-duplicate documents and an exact (or containment-oriented) match for ``does this page contain the problem''. \ver{identity exact to $10^{-9}$; $10^5$ draws of $\hat J$ at $k=128$; on real shingles ($5$-word shingles of a $600$-word document with $6\%$ word edits) exact $J=0.5872$ and MinHash($k=256$) mean $0.5844$.}

\subsection{Membership inference from NLL gaps}
Suppose member NLL is $\mathcal N(\mu-\Delta,\sigma^2)$ and non-member NLL is $\mathcal N(\mu,\sigma^2)$. The threshold test has
\[
\mathrm{AUC}=\Phi\Bigl(\frac\Delta{\sigma\sqrt2}\Bigr),\qquad\mathrm{TPR}@\mathrm{FPR}{=}f=\Phi\Bigl(\frac\Delta\sigma-z_{1-f}\Bigr).
\]
With $\Delta=0.30,\sigma=0.25$ nats: AUC $0.802$, TPR $0.130$ at $1\%$ FPR. Real examples differ in intrinsic difficulty $D_i\sim\mathcal N(0,s_D^2)$ that adds to \emph{both} groups; the raw-NLL AUC becomes $\Phi(\Delta/\sqrt{2(s_D^2+\sigma^2)})$, which is $0.600$ for $s_D=0.8$. A reference model whose NLL shares $D_i$ (trained on other data from the same source, noise $s_{\mathrm{ref}}=0.25$) gives the calibrated score $\mathrm{NLL}_{\mathrm{target}}-\mathrm{NLL}_{\mathrm{ref}}$ with AUC $\Phi(\Delta/\sqrt{2(\sigma^2+s_{\mathrm{ref}}^2)})=0.726$. \ver{closed forms against $4\times10^5$ simulated pairs: $0.8019$, TPR $0.130$, $0.5999$, $0.7257$, each within $0.003$.}

A concrete small model with known membership: a character $n$-gram language model (alphabet $12$, documents of $120$ characters drawn from an order-$2$ Markov source at a per-document temperature in $[0.4,2.5]$, $2000$ member, $2000$ non-member and $2000$ reference documents, add-$0.1$ smoothing):
\begin{center}\small
\begin{tabular}{@{}rrrr@{}}
\toprule
order & raw-NLL AUC & calibrated AUC & mean NLL gap (nats/char) \\ \midrule
1 & $0.506$ & $0.555$ & $0.0019$ \\
2 & $0.510$ & $0.675$ & $0.0154$ \\
3 & $0.559$ & $0.832$ & $0.1048$ \\
4 & $0.715$ & $0.923$ & $0.4656$ \\ \bottomrule
\end{tabular}
\end{center}
Membership signal grows with capacity to memorise (order $4$ has $20736$ contexts for about $2.3\times10^5$ training characters). Raw NLL is nearly blind at orders $1$--$2$ because the per-document temperature moves NLL far more than memorisation does, while the reference-calibrated score already detects the small order-$2$ overfit (AUC $0.675$): calibration is what turns a noisy gap into a usable test, which is why membership tests without a reference model are weak evidence of absence. The converse caution: an AUC near $0.5$ does not show a benchmark is clean (the model may generalise from near-duplicates), and an AUC above $0.5$ does not show that this \emph{item} was seen. \ver{the four-order table (single run, one seed; no confidence intervals computed, AUC standard error roughly $0.01$ at these sizes by the usual rank-statistic estimate, not computed here).}

\section{Boxed result}
\begin{result}
\begin{align*}
\mathrm{precision}&=\frac{\pi\,\mathrm{TPR}}{\pi\,\mathrm{TPR}+(1-\pi)\mathrm{FPR}},\qquad t^\star=\frac{d'}2+\frac1{d'}\ln\frac{(1-\pi)h}{\pi g},\\
w_{\mathrm{same}}(p)&=\frac{\E[\hat g\,\ind\{\hat p\in\mathrm{band}\}]}{p(1-p)}\ \ge\ w_{\mathrm{ind}}(p)\ \text{(in the table)},\qquad \E[p\mid c]=\frac{a+c}{a+b+n},\\
\E\hat J&=J,\ \ \Var\hat J=\frac{J(1-J)}k,\ \ |A\cap B|=\frac{J(|A|+|B|)}{1+J},\qquad
\mathrm{AUC}=\Phi\Bigl(\frac\Delta{\sqrt{2(\sigma^2+s^2)}}\Bigr),
\end{align*}
where $s^2=s_D^2$ for the raw NLL and $s^2=s_{\mathrm{ref}}^2$ for the reference-calibrated score.
\end{result}

\section{What breaks}
\begin{breaks}
\begin{tabular}{@{}p{0.27\linewidth}p{0.30\linewidth}p{0.37\linewidth}@{}}
\toprule
Failure & Assumption violated & Consequence \\ \midrule
Classifier chosen by AUC or training-set accuracy & prior $\pi$ of the target pool equals that of the labelled set & precision at the operating point can be $0.2$ at AUC $0.96$ \\
Threshold by F1 & $g=h$ and prior-balanced costs & loses eightfold gain in the example; gain must be measured by training \\
Classifier trained on a narrow seed & positives all lie near the seed & recall limited by coverage; iteration helps with diminishing returns $(1-\gamma)^r$ \\
Band from the same samples as the gradient & indicator independent of $\hat g$ & effective weight of rare-success problems is up to $11\times$ the independent-pilot weight; $21\%$ of kept problems lie outside the band \\
``Unsolved problems improved'' & selection independent of the evaluation sample & fake $+0.06$ gain with no training; use a fresh sample and an untrained control \\
Jaccard threshold as a contamination test & documents are near-duplicates & a fully contained item has $J=0.02$ and is missed; use exact $n$-gram containment \\
Few MinHash functions near the threshold & $\hat J$ precise & sd $0.035$ at $k=128$; $9\%$ of pairs at $J=0.75$ flagged \\
Linear hashes in place of permutations & min-wise independence & small bias ($+0.004$ here) \\
Raw NLL gap as membership evidence & items of equal difficulty & AUC $0.51$ at order $2$ although a calibrated score reaches $0.68$ \\
NLL test result read as proof for one item & population AUC speaks about individuals & item-level evidence needs a calibrated score and a multiple-testing correction \\ \bottomrule
\end{tabular}
\end{breaks}

\nextnote{With selection, evaluation and decontamination in place, the remaining question for the pipeline is what the \emph{trainer} does with the selected data. 0107 returns to the CISPO objective and adds the variant used for tool-using proof agents, where the sampler's ratio, the masking of tool tokens and the broadcast of one outcome to all tokens decide the gradient's variance.}

\begin{thebibliography}{9}
\bibitem{dsmath} Z.~Shao et al. DeepSeekMath. arXiv:2402.03300, Sec.~2.1 (fastText classifier on $500{,}000$ OpenWebMath positives and $500{,}000$ Common Crawl negatives; four iterations; $35.5$M pages, $120$B tokens; $98\%$ of the fourth-iteration data already collected in the third; domain rule with the $10\%$ criterion; $10$-gram exact-match decontamination). Read from the local copy \texttt{dsmath.txt}.
\bibitem{joulin} A.~Joulin, E.~Grave, P.~Bojanowski, T.~Mikolov. Bag of tricks for efficient text classification (fastText). arXiv:1607.01759. \emph{Cited as the classifier used in \cite{dsmath}; not read here.}
\bibitem{broder} A.~Z.~Broder. On the resemblance and containment of documents. Compression and Complexity of Sequences, 1997 (MinHash). \emph{Not on arXiv; not fetched; classical.}
\bibitem{shokri} R.~Shokri, M.~Stronati, C.~Song, V.~Shmatikov. Membership inference attacks against machine learning models. arXiv:1610.05820 (shadow models; the reference-model calibration used here is the same idea in its simplest form). \emph{Cited from memory; not re-read in this session.}
\end{thebibliography}
\end{document}