PaperlayerView exact revision on arXiv

Source-linked AI summary

Positive-Unlabeled Learning with Non-Negative Risk Estimator

Ryuichi Kiryo, Gang Niu, Marthinus C. du Plessis, Masashi Sugiyama

arXiv:1703.00593v2cs.LGstat.ML

TL;DR

Unbiased PU learning can produce negative empirical risks with very flexible models, creating serious overfitting despite the target risk being non-negative. The paper proposes a non-negative risk estimator and a scalable optimization algorithm, showing that it avoids negative risks and supports flexible models while retaining comparable estimation-error guarantees.

  • Problem

    Unbiased PU risk estimators can become negative and unbounded below for very flexible models, causing overfitting; their guarantees also rely on controlling model complexity.

  • Method

    The paper proposes a non-negative risk estimator and a large-scale stochastic-optimization algorithm for minimizing unbiased and non-negative PU risks.

  • Results

    The non-negative estimator remains non-negative for flexible models, is more robust against overfitting, and has an estimation-error bound of the same order as unbiased counterparts.

  • Takeaways & Limitations

    The approach makes training very flexible models, including deep neural networks, possible with limited positive data.

  • Takeaways & Limitations

    Theoretical guarantees require assumptions including bounded model complexity, Lipschitz loss, and a known positive class prior.

Abstract

from arXiv · show

From only positive (P) and unlabeled (U) data, a binary classifier could be trained with PU learning, in which the state of the art is unbiased PU learning. However, if its model is very flexible, empirical risks on training data will go negative, and we will suffer from serious overfitting. In this paper, we propose a non-negative risk estimator for PU learning: when getting minimized, it is more robust against overfitting, and thus we are able to use very flexible models (such as deep neural networks) given limited P data. Moreover, we analyze the bias, consistency, and mean-squared-error reduction of the proposed risk estimator, and bound the estimation error of the resulting empirical risk minimizer. Experiments demonstrate that our risk estimator fixes the overfitting problem of its unbiased counterparts.

1 Introduction

PU learning trains binary classifiers from positive and unlabeled data, with unbiased risk estimators as the state of the art. This paper addresses their negative empirical risks under flexible models by proposing a non-negative estimator and scalable optimization algorithm.

  • PU learning primarily targets binary classification for retrieval and novelty or outlier detection, with applications also in matrix completion and sequential data.
  • Existing PU methods either identify likely negatives in U data before supervised learning or treat U data as negatively labeled with tuned weights.The first approach relies on heuristics, while the second requires computationally expensive weight tuning.
  • Unbiased PU learning avoids weight tuning by constructing unbiased risk estimators and is the current state of the art.The estimators differ in convexity properties depending on the loss function.
  • Flexible models can make unbiased empirical risks negative, even though the target risk is non-negative, causing an overfitting problem.In the worst case, an unbounded loss and an unrestricted model make the empirical risk unbounded below.
  • The proposed non-negative estimator is biased yet optimal for risk evaluation and retains estimation-error guarantees of the same order as unbiased counterparts when training classifiers.
  • A large-scale stochastic-optimization algorithm minimizes both unbiased and non-negative estimators while accepting any surrogate loss.

2 Unbiased PU learning

Unbiased PU learning estimates classification risk indirectly from positive and unlabeled samples rather than directly from positive and negative samples. Its estimators are unbiased and consistent, with convexity and performance advantages under stated loss, complexity, and sample-size conditions.

  • Problem setting: PU learning observes independent samples from the positive class-conditional density and the unlabeled marginal instead of negative samples.The class prior πp is assumed known throughout the paper.
  • Risk estimators: The risk R(g) combines positive and negative partial risks, while PU learning approximates the negative component indirectly from positive and unlabeled data.
  • Risk estimators: The empirical PU risk estimators are unbiased and consistent for popular loss functions as the positive, negative, and unlabeled sample sizes grow.Consistency is stated for fixed g as np, nn, and nu tend to infinity.
  • Convexity: The first estimator is non-convex under a symmetric loss condition, whereas the general estimator is convex when the loss satisfies a linear-odd condition.For unary losses, the linear-odd condition is both sufficient and necessary for convexity.
  • Estimation error: PU empirical risk minimization can have tighter estimation-error bounds than PN learning when πp/√np + 1/√nu < πn/√nn.This comparison assumes Lipschitz loss and Rademacher complexity decaying as O(1/√n).

3 Non-negative PU learning

Non-negative PU learning prevents the empirical risk from following unbiased PU risk into negative values, addressing overfitting with flexible models. The section also presents a stochastic large-scale algorithm and compares nnPU experimentally with uPU and PN.

  • 3.1 Motivation: The convergence rate from approximating the negative risk with N data is O_p(π_n/√n_n), while using P and U data gives O_p(π_p/√n_p + 1/√n_u).The latter can yield a tighter uniform deviation bound when π_p/√n_p + 1/√n_u < π_n/√n_n.
  • 3.1 Motivation: A flexible multilayer perceptron with 500 times more parameters than total P and N examples exposes severe uPU overfitting.On training data, uPU risk decreases faster than PN risk, while on test data uPU risk does not decrease.
  • 3.1 Motivation: Unbiased PU risk can become negative with highly flexible models, motivating an explicit non-negativity constraint.The issue arises from a partial risk on positive data treated as negative data, which can make the empirical risk unbounded below.
  • 3.2 Non-negative risk estimator: The nnPU estimator keeps training risk from decreasing with uPU after a certain epoch and prevents the corresponding test-risk increase.At the end of the experiment, nnPU achieves the lowest test risk.
  • 3.3 Implementation: The proposed large-scale algorithm uses stochastic optimization and supports any surrogate loss for minimizing unbiased or non-negative PU risk.It processes shuffled P and U data in mini-batches and adjusts updates when the negative partial risk falls below a tolerance threshold.

4 Theoretical analyses

The analysis characterizes the proposed estimator’s bias, MSE behavior, consistency, and classifier estimation error under explicit assumptions. It shows convergence to the true risk and provides conditions under which non-negative estimation improves MSE.

  • Bias and consistency: The estimator is generally biased because it is pointwise no smaller than the unbiased estimator, although it converges to the true risk.For fixed g, the estimator converges at the optimal rate O(πp/√np + 1/√nu).
  • Bias and consistency: The estimator’s bias decays exponentially as the numbers of positive and unlabeled samples increase, under a positive-risk assumption.The analysis uses χnp,nu = 2πp/√np + 1/√nu to characterize finite-sample behavior.
  • Estimation error: Theorem 4 bounds the resulting empirical risk minimizer’s estimation error under Lipschitz loss, a positive lower-risk condition, and a hypothesis class closed under negation.The proof uses Rademacher complexities and a different complexity bound because the maximum operator makes the estimator non-pointwise.
  • Consistency: The estimator is consistent: R(egpu) → R(g∗), and under the specified convex-loss condition, the empirical minimizer converges to g∗.For bounded-norm linear models, the convergence rate is Op(πp/√np + 1/√nu).

5 Experiments

Experiments compare PN, unbiased PU, and non-negative PU learning on benchmark datasets using deep neural networks. Unbiased PU overfits, whereas nnPU fixes this problem and performs competitively with or better than PN under limited negative data.

  • Experimental setup: The benchmark setup used 1,000 positive examples for PN and uPU, while nnPU used the same positive and unlabeled sample sizes as uPU.P and U data were dependent for uPU and nnPU because their risk estimators do not require independence.
  • Deep neural networks: uPU overfit training data, while nnPU fixed this problem across the benchmark experiments.Figure 2 reports means and standard deviations of training and test risks from 10 random samplings.
  • Deep neural networks: Given limited N data, nnPU outperformed PN on MNIST, epsilon, and CIFAR-10, and was comparable to PN on 20News.The experiments used deep neural-network models across these benchmark datasets.
  • Class-prior misspecification: Figure 3 evaluates nnPU when the class-prior estimate π′p ranges from 0.8πp to 1.2πp.The experiments simulate errors in estimating πp during PU learning.
  • Class-prior misspecification: Using π′p slightly larger than πp can lower test risks because it increases nnPU’s separation from uPU despite introducing additional bias.Under-misspecification generally hurt more than over-misspecification on MNIST, while effects differed across datasets.

6 Conclusions

The paper proposes a non-negative PU risk estimator that avoids negative empirical risks and is more robust against overfitting. Theory and experiments support using flexible models, including deep neural networks, with limited positive data.

  • Conclusions: The proposed estimator remains non-negative for flexible models, unlike its unbiased counterparts.The paper also develops a large-scale PU learning algorithm and presents theoretical and experimental analyses.
  • Conclusions: The estimator makes training very flexible models with limited positive data possible by improving robustness against overfitting.The conclusion identifies extension to semi-supervised learning as a future direction.

A Supplementary experimental results

The appendix extends Figure 1 by including the zero-one loss. Its risk curves generally resemble those for the sigmoid loss but are less smooth, making sigmoid-loss curves more visually appealing for illustration.

  • Figure 4 extends Figure 1 by including the zero-one loss.
  • Zero-one-loss risk curves generally look similar to sigmoid-loss curves but are less smooth.
  • Sigmoid-loss risk curves are used as the more visually appealing illustrative results.

B.1 Proof of Lemma 1

The proof characterizes when the non-negative estimator differs from the unbiased estimator and shows that its bias is positive exactly when this difference occurs with non-zero probability.

  • The measure of D−(g) is non-zero if and only if the non-negative estimator differs from the unbiased estimator with non-zero probability.
  • The proof establishes these claims using the estimator's unbiasedness and its equality with the unbiased estimator on D+(g).
  • The bias of the non-negative estimator is positive if and only if D−(g) has non-zero measure.
  • The concentration argument assumes the loss is bounded between 0 and Cℓ and applies McDiarmid's inequality.

B.2 Proof of Theorem 2

The proof derives deviation bounds for the non-negative risk estimator by controlling how much it changes when positive or unlabeled samples are replaced and by combining concentration arguments.

  • The first deviation bound follows from these bounded changes and concentration.
  • Replacing one positive sample changes the estimator by at most 2Cℓ/np, while replacing one unlabeled sample changes it by at most Cℓ/nu.
  • The second deviation bound combines the probability that the two estimators differ with the concentration of the unbiased estimator around the true risk.
  • The estimator discrepancy has probability at most ∆g.

B.3 Proof of Theorem 3

The proof represents the true, unbiased, and non-negative risks through shared terms, then analyzes their squared-error difference using the positive-part transformation and properties of D−(g).

  • The risks are represented as R(g)=E[A+B], bRpu(g)=A+B, and eRpu(g)=A+B+.
  • The positive-part term is defined by B+=max{0,B}, replacing negative values of B with zero.
  • The mean-squared-error comparison is decomposed into an expectation involving (A+B)^2 versus (A+B+)^2 and a term involving the bias difference.
  • On D−(g), the non-negative estimator equals A, which supports the algebraic reduction used in the proof.
  • The theorem is completed by establishing the resulting bound under the assumption that D−(g) has positive probability.
  • For 0≤β≤Cℓπp, the event B<−β is contained in D−(g) and is equivalent to eRpu(g)−bRpu(g)>β.

B.4 Proof of Lemma 5

The proof establishes a uniform deviation bound for the non-negative PU risk estimator by decomposing deviations, applying concentration and symmetrization, and controlling the resulting complexities. It also addresses shifted losses and composite function classes before deriving the estimation-error bound.

  • Final bound: The resulting uniform deviation bound combines the preceding inequalities and yields the estimation-error bound for the empirical risk minimizer.The proof invokes Lemma 5 and the minimizing property eR_pu(ĝ_pu) ≤ eR_pu(g*) to establish the final bound.
  • Proof strategy: The proof first separates the uniform estimation error into empirical fluctuation and bias terms.The decomposition bounds sup_g |eR_pu(g) − R(g)| by the sum of sup_g |eR_pu(g) − E[eR_pu(g)]| and sup_g |E[eR_pu(g)] − R(g)|.
  • Proof strategy: McDiarmid’s inequality provides a high-probability bound for the uniform empirical deviation, with a single-sided concentration inequality.The text explicitly distinguishes this concentration result from the double-sided uniform deviation and from the non-uniform deviation in Theorem 2.
  • Symmetrization: A ghost sample and Jensen’s inequality enable symmetrization of the expected uniform deviation.The absolute value and supremum are treated as convex, allowing the deviation to be related to differences between the original sample and an independent ghost sample.
  • Loss transformation: The proof decomposes sample differences using the 1-Lipschitz property of max{0, z}, then handles the original loss by shifting it so that ˜ℓ(0, y) = 0.This permits Rademacher variables to be attached to loss differences and allows the expectations to be reduced to Rademacher complexities.
  • Complexity control: Talagrand’s contraction lemma transfers the Rademacher-complexity bounds from composite loss classes to the original function class.The shifted loss retains the original loss’s Lipschitz constant, while closure of G under negation is used in the final transformation.
Loading 1703.00593v2…