Nonparametric semi-supervised learning of class proportions

Shantanu Jain; Martha White; Michael W. Trosset; Predrag Radivojac

Source-linked AI summary

Nonparametric semi-supervised learning of class proportions

Shantanu Jain, Martha White, Michael W. Trosset, Predrag Radivojac

arXiv:1601.01944v1Jan 8, 2016stat.MLcs.LG

TL;DR

The paper studies estimating positive and negative class priors from positive and unlabeled samples, where mixture proportions are generally not identifiable. It uses a canonical identifiable mixture form, theory-guided estimation algorithms, and class-prior-preserving transformations for high-dimensional data, with experiments on univariate and multivariate samples.

Problem
Estimating class priors from positive and unlabeled data is generally ill-defined because the mixture distribution may admit multiple mixing proportions.
Method
The paper models class-prior estimation as two-component mixture learning, uses a max-canonical form for identifiability, and applies transformations that preserve α∗ in lower-dimensional spaces.
Results
Experiments on univariate and multivariate data compare the proposed algorithms favorably with state-of-the-art supervised and unsupervised methods.
Takeaways & Limitations
The framework provides nonparametric class-prior estimation while retaining flexibility for arbitrary distributions and practical high-dimensional transformations.
Takeaways & Limitations
The transformation theory includes assumptions on sampling and, for one theorem, a continuous random variable with a probability density function.

Abstract

from arXiv · show

The problem of developing binary classifiers from positive and unlabeled data is often encountered in machine learning. A common requirement in this setting is to approximate posterior probabilities of positive and negative classes for a previously unseen data point. This problem can be decomposed into two steps: (i) the development of accurate predictors that discriminate between positive and unlabeled data, and (ii) the accurate estimation of the prior probabilities of positive and negative examples. In this work we primarily focus on the latter subproblem. We study nonparametric class prior estimation and formulate this problem as an estimation of mixing proportions in two-component mixture models, given a sample from one of the components and another sample from the mixture itself. We show that estimation of mixing proportions is generally ill-defined and propose a canonical form to obtain identifiability while maintaining the flexibility to model any distribution. We use insights from this theory to elucidate the optimization surface of the class priors and propose an algorithm for estimating them. To address the problems of high-dimensional density estimation, we provide practical transformations to low-dimensional spaces that preserve class priors. Finally, we demonstrate the efficacy of our method on univariate and multivariate data.

1. Introduction

Positive-unlabeled learning addresses settings where positive examples are available but unlabeled data mix positive and negative examples at unknown proportions. This paper formulates class-prior estimation as nonparametric two-component mixture learning, develops identifiability-based algorithms, and evaluates them on synthetic and real-world data.

Motivation: Positive-unlabeled datasets contain relatively few positive examples and many unlabeled examples whose positive and negative proportions are unknown.Such data arise when negative examples are expensive, unavailable, or cannot be inferred from failed or absent positive labels.
Motivation: Absence of a positive label cannot reliably be treated as a negative label in scientific and social-network applications.Examples include unsuccessful protein experiments and users who do not click a Facebook “like” button.
Problem formulation: The paper formulates estimating the positive fraction in unlabeled data as parameter learning in a two-component mixture model.The positive and negative distributions are mixture components, and the mixing proportion is the positive class prior.
Method: The formulation supports deterministic transformations that preserve mixing proportions, including mapping multivariate inputs to scalar distributions.This enables practical class-prior estimation when high-dimensional density estimation is difficult.
Contributions: The authors identify mixing-proportion identifiability as a central issue and propose maximum-likelihood algorithms informed by its theoretical analysis.Experiments on synthetic and real-world data provide evidence that the methodology is sound and effective.

2. Identifiability issues and the max-canonical form

The paper shows that unrestricted two-component mixture proportions are generally non-identifiable, then introduces a max-canonical form that restores identifiability without reducing the set of representable mixtures.

2. Identifiability issues and the max-canonical form: Unrestricted mixing proportions are generally non-identifiable because a mixture can correspond to multiple component-proportion parameterizations.Identifiability requires a one-to-one mapping from (α, µ0) to the mixture distribution.
2. Identifiability issues and the max-canonical form: Theorem 3 constructs a restricted family Q0 whose mixtures match those of the unrestricted family while making the mixing proportion identifiable.Thus, restricting the negative-component family preserves modeling flexibility while resolving non-identifiability.
2. Identifiability issues and the max-canonical form: For any mixture, the valid proportions form an interval (0, α∗], so likelihood-based estimation can yield equally likely solutions across that interval.The likelihood is expected to remain flat over the valid interval and deteriorate after α∗.
2. Identifiability issues and the max-canonical form: For α < α∗, the negative component is itself a non-trivial mixture containing µ1, and the overestimate α∗ − α smoothly reflects that contamination.The theorem relates α∗ − α to the proportion of µ1 in µ0.
2. Identifiability issues and the max-canonical form: The canonical choice α∗ = max A(µ, µ1, Pall 0) selects the largest valid positive-component proportion and a negative component not containing the positive component.The paper interprets this as selecting the most separated component representation.
2. Identifiability issues and the max-canonical form: The result builds on Blanchard et al. (2010) by additionally showing no modeling flexibility is lost and by quantifying error when µ0 is outside Q0.The interval characterization also directly informs the algorithm developed later.
2.1 Proof of Theorem 3: When densities exist, the canonical proportion is α∗ = inf{f(x)/f1(x) : x ∈ X, f1(x) > 0}.This density expression characterizes the endpoint of the valid-proportion interval.
2.1 Proof of Theorem 3: The proof establishes that the unrestricted family is non-identifiable, whereas identifiability is equivalent to the mixture family being disjoint from the negative-component family.Lemma 5 gives the general equivalence F(P0, µ1) identifiable iff F(P0, µ1) ∩ P0 = ∅.

3. Algorithm development

The algorithm estimates class priors by optimizing a kernel-based mixture representation over proportion level sets. It then detects the endpoint α∗ from the resulting likelihood surface, while max-canonical constraints make optimization tractable.

3. Algorithm development: Kernel components can be Gaussian-based for continuous data or multinomial for discrete data, allowing the representation to cover common density and mass-function settings.The kernels may use learned or predefined centers, including observations as centers in kernel density estimation.
3. Algorithm development: The method represents the component density f1 with reweighted kernels using β, with the implied positive-class proportion α = Σ_i β_i w_i.The β weights are constrained so the resulting component functions remain valid densities or mass functions.
3. Algorithm development: The objective combines likelihood terms for the component sample and mixture sample, targeting β values that minimize KL divergence to the true distributions.The direct plug-in mixture estimate cannot be used in the likelihood because β cancels algebraically, so an auxiliary construction is used.
3. Algorithm development: Although the component-sample likelihood may be non-concave, enforcing the max-canonical form avoids this optimization issue.The mixture-sample likelihood is concave, whereas the other term can contain both concave and convex components.
3. Algorithm development: AlphaMax estimates α∗ by evaluating likelihoods over candidate proportions and selecting the point with the largest slope change after curve smoothing.The algorithm uses median smoothing of nearby likelihood values before computing slope differences.
3. Algorithm development: The optimized likelihood surface is expected to be flat through α∗ and deteriorate beyond it, making the endpoint detectable from the surface shape.Level-set constraints turn the relevant optimization into a concave maximization.

4. Transformations that preserve α∗

The paper develops transformations from high-dimensional data to univariate representations while preserving the canonical mixing proportion α∗. A probabilistic classifier provides a concrete transformation that also supports later classification.

4. Transformations that preserve α∗: High-dimensional kernel density estimation motivates the transformation because density estimation becomes difficult in high-dimensional or structured spaces.The paper contrasts the proposed classifier-based reduction with product kernels and notes curse-of-dimensionality issues.
4. Transformations that preserve α∗: The implicit labeling process assigns observations to component, mixture, or neither sample through S ∈ {0, 1, 2}, with failed labeling producing dropped observations.S = 1 yields the component sample, S = 0 the mixture sample, and S = 2 excludes the observation from both.
4. Transformations that preserve α∗: The sampling assumptions require S = 2 to depend on X and to occur with nonzero probability; otherwise the mixture and component distributions cannot satisfy the required conditions.In particular, allowing every mixture-population point to be sampled creates inconsistent assumptions.
4. Transformations that preserve α∗: The proposed probabilistic-classifier transformation preserves α∗, so class-prior estimation can be performed after reducing multivariate data to one dimension.The preservation theorem is stated for continuous variables but can be generalized to discrete or mixed variables.
4.1 General theorem for univariate transforms: The transformation τ(x) = p(S = 1|X = x, S ∈ {0, 1}) preserves α∗ because it is a one-to-one transformation of the density ratio f(x)/f1(x).The constant c in the equivalent expression can be estimated from the mixture-to-component sample-size ratio.
4.1 General theorem for univariate transforms: The general theorem shows that arbitrary transformations provide an upper bound on the original α∗, while one-to-one transformations of the density ratio achieve equality.The proof uses the mixture representation of τ(X) and the nonnegative residual component to establish the bound.

5. Related work

Related work connects class-prior estimation to sample-selection bias, positive-unlabeled learning, probability-mixture theory, and asymmetric label noise. The paper positions its contribution around identifiable nonparametric mixture estimation and a practical estimator.

5. Related work: Earlier sample-selection-bias methods estimate differing class priors between labeled and unlabeled data but assume labeled data contain both positive and negative examples.
5. Related work: Elkan and Noto (2008) and Phillips et al. (2009) studied positive-unlabeled learning through relationships between traditional and labeled-versus-unlabeled classifiers.Elkan and Noto (2008) proposed class-prior estimators assuming a non-traditional classifier can learn the probability that a point is labeled.
5. Related work: Scott and Blanchard’s theoretical work established general non-identifiability and α∗, while their infimum-based estimator was not known to yield a practical algorithm for computing α∗.The paper further identifies the valid mixing proportions as an interval and uses that structure for algorithm development.
5. Related work: Theoretical results were later extended to classification with asymmetric label noise by Scott et al. (2013).
5. Related work: Class-prior estimation can also be formulated as parameter learning in two-component mixture models, where many existing methods are based on EM and its variants.Finite-mixture identifiability has been extensively studied, and observing samples from both a mixture and one component simplifies the problem.

6. Empirical investigation

Experiments evaluate AlphaMax and competing estimators on controlled synthetic, multivariate, and real-world data. AlphaMax performs especially well when component separation is low and on real-life data, where it outperforms the alternatives on most data sets.

Experimental design: For multivariate data, prediction-score distributions from a classifier trained on positive versus unlabeled data were transformed into univariate samples for estimation.The same classifier-based construction was used for real-life data sets.
Experimental design: The experiments compared AlphaMax with Elkan-Noto, GMM, transformed GMM, and two Lemma 4-based baselines across synthetic and real-world settings.The pdf ratio and cdf-based approaches were derived from theoretical properties of the canonical mixing proportion.
Synthetic data: All methods generally performed well on univariate mixtures, but estimation became harder when component separation or the component-sample size was small.AlphaMax showed evidence of strong performance on data sets with low separation between mixing components.
Analysis procedure: AlphaMax identifies an inflection point at the end of an initial flat region in log-likelihood functions, while box plots visualize estimate variance.An interior-point method was used for the level-set optimization, and alternative optimization approaches provided no gains.
Multivariate synthetic data: Synthetic multivariate results showed generally good performance with large component samples and sensitivity across all procedures when component samples were small.The multivariate-to-univariate transformation did not negatively influence AlphaMax or GMM.
Real-life data: AlphaMax outperformed the remaining methods on 10 of 12 real-life data sets, with 8 statistically significant results.The evaluation used mean absolute error from the true mixing proportion.

7. Conclusions

The work develops identifiable, nonparametric class-prior estimation for positive-unlabeled data and supports it with class-prior-preserving transformations and favorable comparisons on univariate and multivariate samples. The authors identify several extensions aimed at improving estimate quality and handling noisy or biased data.

AlphaMax was compared favorably with state-of-the-art supervised and unsupervised procedures on univariate and multivariate samples.
The methodology addresses high-dimensional density estimation by transforming multivariate data into univariate samples while preserving class priors.
Future improvements include larger-α regularization, more sophisticated kernel-density estimation, better inflection-point heuristics, and reliability estimates for identified proportions.
The conclusion reports visual evaluations using box plots and log-likelihood plots for synthetic, multivariate, and UCI data sets.
Extending the methodology to noisy and biased data remains future work.