Learning from positive and unlabeled data

SCAR makes labeling a constant thinning of the positives, so $g/c$ is the posterior. Every positive survives into the labeled set with probability $c$ and negatives never do, so$$p(s=1\mid x)=c\,p(y=1\mid x).$$So ranking by $g$ is ranking by the posterior, and a team that only needs a ranking never needs $c$. Also $g\le c$ everywhere: even where a point is certainly positive, a fraction $1-c$ of its copies stay unlabeled, which is why labeled-versus-unlabeled classifiers look badly calibrated. And the prevalence is $p(s=1)/c$, which exceeds the labeled share $n/m$, as it must.

Weighting turns any weighted learner into a PU learner. Instead of rescaling $g$, give the learner the data it would have seen with labels, in expectation. A labeled point enters as a positive with weight 1. An unlabeled point enters twice, as a positive with weight $w(x)$ and as a negative with weight $1-w(x)$, where Bayes on the event $s=0$ gives$$w(x)=p(y=1\mid x,s=0)=\frac{1-c}{c}\,\frac{g(x)}{1-g(x)}.$$The pair contributes the conditional mean of the loss given $x$ and $s=0$, so any empirical risk becomes an estimate of the fully labeled risk given $g$ and $c$, and any learner that takes per-example weights runs unchanged, each weight coming from a formula where the earlier biased SVM searched a grid.

C is read off held-out labeled points, and the recommended estimator is exact only for separable classes. The paper recommends $e_1$, the mean of $g$ over the labeled points of a validation set, for its low variance, arguing that $g(x)=c$ there because $y=1$. That argument substitutes the realized label for the posterior. Since labeled points follow the positive distribution,$$\mathbb E[e_1]=c\;\mathbb E\big[p(y=1\mid x)\mid y=1\big]\le c,$$with equality only for separable classes (the reading of Bekker and Davis). A low $e_1$ inflates $f=g/e_1$, the weights and the prevalence. My check with exact $g$, positives $N(\mu,1)$, negatives $N(-\mu,1)$, prevalence 0.3 and $c=0.5$: at $\mu=1$, $e_1\approx0.33$ and the prevalence estimate $n/(m\,e_1)\approx0.45$; at $\mu=2$, 0.475 and 0.316; at $\mu=3$ the bias is gone. The alternative $e_3=\max g$ is exact when some region is purely positive, but rests on one point. All of this treats $g$ as a probability, so it holds only as far as the scores are calibrated; logistic regression stays roughly calibrated even when misspecified, and the paper passes SVM scores through Platt scaling.

On one real task both methods nearly match full supervision, far more cheaply than the biased SVM. On transporter proteins with linear SVMs, F1 is 0.947 fully supervised, 0.931 for rescaled $g$, 0.942 weighted and 0.928 for the biased SVM, which needs 621 SVM fits per fold against 1 or 2. One data set and one learner show that the methods work and are cheap; they do not show how the methods rank in general.

Setting for the risk estimator. Now $X_p\sim p_p=p(x\mid y=+1)$ ($n_p$ points) and $X_u\sim p=\pi_pp_p+\pi_np_n$ ($n_u$ points) are independent, with $\pi_p$ known. With $R_p^\pm(g)=\mathbb E_p\,\ell(g(X),\pm1)$ and $R_u^-(g)=\mathbb E_X\,\ell(g(X),-1)$, the identity $\pi_np_n=p-\pi_pp_p$ removes the missing negatives, $\pi_nR_n^-=R_u^--\pi_pR_p^-$. Sample averages give the unbiased PU (uPU) estimator, and clipping the rewritten term gives non-negative PU (nnPU):$$\hat R_{pu}(g)=\pi_p\hat R_p^+(g)-\pi_p\hat R_p^-(g)+\hat R_u^-(g),\qquad \tilde R_{pu}(g)=\pi_p\hat R_p^+(g)+\max\big\{0,\;\hat R_u^-(g)-\pi_p\hat R_p^-(g)\big\}.$$The theory assumes $g$ and the loss are bounded (by $C_\ell$ for the loss) and $\pi_nR_n^-(g)\ge\alpha>0$.

A flexible model makes the unbiased risk negative by learning $s$ instead of $y$. The term $\hat R_u^--\pi_p\hat R_p^-$ estimates $\pi_nR_n^-\ge0$, but its two pieces average over different points. A model that can fit individual points scores the labeled positives high, which raises $\hat R_p^-$, and every unlabeled point low, positives included, which lowers $\hat R_u^-$. With the sigmoid loss this reaches the floor $\hat R_{pu}=-\pi_p$, and with an unbounded loss there is no floor. In the population this solution is impossible; on a sample it is the minimizer, and uPU's guarantees, which need a Rademacher complexity that decays with $n$, cannot exclude it. On MNIST even versus odd with 100 labeled positives, a linear model trains and tests fine, while a one-hidden-layer MLP drives the uPU training risk below zero as its test risk rises above that of fully supervised training on 100 positives and 50 negatives. A negative value of the term is pure sampling error, so clipping it is justified.

For a fixed classifier, clipping costs an exponentially small bias. The estimators differ only on the event $D^-(g)$ where $\hat R_u^--\pi_p\hat R_p^-<0$, where the clip adds at most $C_\ell\pi_p$; $D^-$ is a lower-tail event for a bounded-difference statistic with mean at least $\alpha$, so McDiarmid gives$$\Pr(D^-(g))\le\Delta_g=\exp\!\Big(-\frac{2(\alpha/C_\ell)^2}{\pi_p^2/n_p+1/n_u}\Big),\qquad 0\le\mathbb E\tilde R_{pu}(g)-R(g)\le C_\ell\pi_p\Delta_g,$$and $\tilde R_{pu}\to R$ at the CLT rate. The clip matters for the trained classifier, chosen from the data exactly where the term would have gone negative.

Clipping lowers the MSE by at least three times the squared amount clipped. Write $A=\pi_p\hat R_p^+$ and $B=\hat R_u^--\pi_p\hat R_p^-$, so $\hat R_{pu}=A+B$ and $\tilde R_{pu}=A+B_+$. Expanding both squared errors, everything off $D^-$ cancels:$$\mathrm{MSE}(\hat R_{pu})-\mathrm{MSE}(\tilde R_{pu})=\int_{D^-}(2A+B-2R)\,B\,dF.$$Since $B<0$ on $D^-$, the gain is at least $3\int_{D^-}B^2$ once $A-R\le B$ there. A symmetric loss, $\ell(t,+1)+\ell(t,-1)=1$, rewrites the error of $A$ as $A-R=B-2\mathbb EB+(R_u^--\hat R_u^-)$, which is at most $B$ when $\mathbb EB\ge\alpha$ and the unlabeled average is within $2\alpha$ of its mean. The assumption $n_u\gg n_p$ is used here: with many unlabeled points the unlabeled average is accurate, so a negative $B$ comes from the positive sample, and correcting it moves the estimate toward $R$.

The estimation-error bound matches uPU's in order, and the gap in constants is a proof artifact. The clipped risk is not an average of per-point losses, so symmetrization does not apply directly. The inequality $|\max\{0,z\}-\max\{0,z'\}|\le|z-z'|$ splits a difference of clipped risks into three differences of ordinary partial risks, each handled by symmetrization and Talagrand contraction for an $L_\ell$-Lipschitz loss. Contraction with the absolute value inside the supremum costs a factor 2. For $\tilde g_{pu}=\arg\min_{\mathcal G}\tilde R_{pu}$ and $g^*=\arg\min_{\mathcal G}R$ over a class closed under negation, with probability at least $1-\delta$,$$R(\tilde g_{pu})-R(g^*)\le16L_\ell\pi_p\,\mathfrak R_{n_p,p_p}(\mathcal G)+8L_\ell\,\mathfrak R_{n_u,p}(\mathcal G)+2C'_\delta\chi+2C_\ell\pi_p\Delta,$$with $\chi=2\pi_p/\sqrt{n_p}+1/\sqrt{n_u}$, $C'_\delta=C_\ell\sqrt{\ln(1/\delta)/2}$ and $\Delta$ the bound of Step 6 with $\alpha$ from the infimum over the class, against uPU's 8 and 4 with no $\Delta$ term. The authors say plainly that the difference comes from proof technique and says nothing about which minimizer is better. For deep networks, whose Rademacher complexity does not decay at these sample sizes, both bounds are vacuous, so the case for nnPU rests on the experiments.

On a mini-batch where the term goes negative, the algorithm steps to raise it, and this fixes deep PU training. Clipping alone gives zero gradient on a batch where it binds, leaving the model where it overfit. Algorithm 1 computes $r_i=\hat R_u^-(g;X_u^i)-\pi_p\hat R_p^-(g;X_p^i)$ on each mini-batch; if $r_i\ge-\beta$ it takes an ordinary step on $\hat R_{pu}$, and otherwise a step of size $\gamma\eta$ along $-\nabla_\theta(\pi_p\hat R_p^--\hat R_u^-)$, which raises $r_i$ and undoes the memorization on that batch. With $\beta=0$, $\gamma=1$ and 1,000 labeled positives, uPU overfits on all four data sets (MNIST, epsilon, 20News, CIFAR-10) and nnPU does not, beating fully supervised learning with $n_n=(\pi_n/2\pi_p)^2n_p$ negatives on three and tying on 20News. With $\pi_p$ misspecified from $0.8\pi_p$ to $1.2\pi_p$, underestimates hurt more than overestimates; the authors explain that a larger prior makes the clip bind more often, moving the method further from the overfitting uPU at the cost of more bias.