PaperlayerView exact revision on arXiv

Source-linked AI summary

Mixture Proportion Estimation via Kernel Embedding of Distributions

Harish G. Ramaswamy, Clayton Scott, Ambuj Tewari

arXiv:1603.02501v2cs.LGstat.ML

TL;DR

MPE estimates a component weight in a mixture, an important step in several weakly supervised learning settings. This paper proposes an RKHS mean-embedding algorithm with convergence guarantees under distributional conditions and competitive benchmark performance.

  • Problem

    MPE lacks an efficient, provably convergent solution in the general non-parametric setting with minimal assumptions, although the proportion is not identifiable without assumptions.

  • Method

    The method embeds distributions in an RKHS, uses the C-distance and its empirical surrogate, and estimates the proportion through efficient quadratic-programming-based procedures.

  • Results

    The proposed estimators converge to the true proportion under separability, and the algorithms perform comparably to or better than other methods on all datasets except mushroom.

  • Takeaways & Limitations

    The paper provides an efficient MPE approach with convergence guarantees under certain distributional conditions and demonstrates effectiveness on benchmark datasets.

  • Takeaways & Limitations

    A specific convergence rate is unavailable without further assumptions because the constants depend on the separability parameters α and β.

Abstract

from arXiv · show

Mixture proportion estimation (MPE) is the problem of estimating the weight of a component distribution in a mixture, given samples from the mixture and component. This problem constitutes a key part in many "weakly supervised learning" problems like learning with positive and unlabelled samples, learning with label noise, anomaly detection and crowdsourcing. While there have been several methods proposed to solve this problem, to the best of our knowledge no efficient algorithm with a proven convergence rate towards the true proportion exists for this problem. We fill this gap by constructing a provably correct algorithm for MPE, and derive convergence rates under certain assumptions on the distribution. Our method is based on embedding distributions onto an RKHS, and implementing it only requires solving a simple convex quadratic programming problem a few times. We run our algorithm on several standard classification datasets, and demonstrate that it performs comparably to or better than other algorithms on most datasets.

1. Introduction

MPE estimates a component’s weight in a mixture and supports several weakly supervised learning tasks. The paper addresses the lack of an efficient, provably convergent general non-parametric method under minimal assumptions.

  • MPE estimates the weight of a component distribution from samples drawn from the mixture and component.
  • MPE is a key step in weakly supervised learning, including learning from positive and unlabelled samples and learning with noisy labels.
  • Without assumptions on the mixture and components, the mixture proportion is not identifiable.
  • Existing methods provide conditional convergence results, but no efficient and provable general non-parametric method with minimal assumptions was known.
  • The paper proposes an efficient RKHS-based algorithm with convergence rates, avoiding conditional-probability estimation and performing comparably to or better than prior algorithms on most datasets.
  • The paper develops the C-distance, separability-based estimators, convergence analyses, an implementation, related-method comparisons, and experiments.

2. Problem Setup and Notations

The problem models the observed distribution as a mixture of component distributions and estimates the corresponding mixing proportion. The setup uses RKHS mean embeddings and convex sets of valid empirical distributions.

  • F is modeled as a convex mixture of distributions G and H, with κ∗ determining the target mixture proportion.
  • Given samples from F and H, MPE estimates κ∗.
  • An RKHS kernel mapping φ represents each distribution P by its mean embedding φ(P), satisfying EX∼P f(X) = ⟨f, φ(P)⟩H.
  • The empirical distributions induced by the samples form convex sets, with the sample-based set CS contained in the corresponding population set C.
  • The unknown component sample subset is unavailable directly, but its empirical embedding belongs to CS.

3. RKHS Distance to Valid Distributions

The C-distance measures how far a candidate reconstructed distribution is from the set of valid distributions, while the CS-distance provides an empirical surrogate. Their convexity and concentration properties support efficient estimation.

  • The C-distance reconstructs φ(G) under a candidate λ and measures its distance to the valid-distribution set C.
  • The empirical CS-distance can be computed efficiently by solving a quadratic program involving the kernel matrix K.
  • d(λ) is zero for λ ∈ [0, λ∗], while bd(λ) is zero for λ ∈ [0, 1].
  • The C-distance and CS-distance are non-decreasing convex functions on [0, ∞).
  • Kernel mean embeddings of the empirical distributions are close to the corresponding population embeddings under the stated bounded-kernel concentration result.
  • Bounds show that bd(λ) is controlled on [1, λ∗] and lower-bounds d(λ) up to an error term, making it a useful surrogate.

4. Mixture Proportion Estimation under a Separability Condition

The paper introduces separability, a function-space analogue of the anchor set condition, under which the C-distance identifies the true mixture proportion. Universal kernels connect anchor sets to separability, enabling consistent estimators based on the empirical CS-distance.

  • Anchor set condition: The anchor set condition requires a compact set contained in supp(H) \ supp(G) with H(A) ≥ γ.This condition makes a region of H’s support unavailable under G.
  • Separability condition: Separability extends the anchor set condition from subsets of X to a class of functions on X.Indicator functions of anchor sets satisfy separability with margin α = γ and tolerance β = 0.
  • Separability condition: Under separability, λ∗ is the departure point from zero of the C-distance function.Theorem 10 establishes this behavior using a witness function and a norm lower bound.
  • Connection to universal kernels: Universal kernels can transfer the anchor set condition to separability with positive margin and controlled tolerance.Theorem 11 derives this connection by approximating a continuous witness function in the RKHS.
  • Estimators: Because d(.) is unavailable, the method uses the empirical CS-distance, which converges toward d(.) as sample size increases.The paper proposes value-thresholding and gradient-thresholding estimators based on this surrogate; the CS-distance is computed through quadratic programming.

5. Convergence of Value and Gradient Thresholding Estimators

Under separability and sufficient samples, both thresholding estimators converge toward the true mixture proportion; with positive tolerance, convergence is to an additive neighborhood whose size depends on β and α.

  • Under the stated kernel, separability, boundedness, and sample-size conditions, Theorem 10 provides convergence bounds for the value thresholding estimator.The bounds hold with high probability under event Eδ and require min(m,n)>(12·λ∗)^2 log(1/δ).
  • Under the same conditions, Theorem 13 derives convergence bounds for the gradient thresholding estimator using convexity-based bounds on ∇bd(λ).The proof translates upper and lower bounds on bd(λ) into bounds on its gradient and then on the estimator.
  • O(m−1/2) convergence holds for both value and gradient thresholding estimators when the separability tolerance is β=0.
  • With β>0, both estimators converge within an additive factor of βλ∗/α; a universal kernel can make β/α arbitrarily small.
  • Without further assumptions on G and H, no specific convergence rate is available for universal kernels because the constants depend on α and β.

6. The Gradient Thresholding Algorithm

The paper selects gradient thresholding as its preferred practical estimator because its step-like gradient is less threshold-sensitive and can be computed efficiently by binary search.

  • The value estimate is much more sensitive to its threshold τ than the gradient estimate is to ν.
  • The gradient estimator is preferred because bd(λ) is hinge-like while ∇bd(λ) is approximately step-like.
  • Because ∇bd(λ) is increasing by convexity, the gradient thresholding estimator can be computed efficiently by binary search.
  • The algorithm estimates slopes numerically around λcurr and computes bd(λ) with the CVXOPT convex programming solver.
  • KM1 sets ν using the theoretical slope scale, whereas KM2 uses a convex combination of the initial and final slopes.For KM2, ν=0.8∗initial slope+0.2∗final slope.

7. Other Methods for Mixture Proportion Estimation

Prior MPE methods use irreducibility, anchor-set, conditional-probability, divergence, or likelihood ideas, but their guarantees and computational properties differ substantially.

  • Irreducibility makes κ∗ identifiable, while the stronger anchor-set condition supports convergence-rate guarantees for an earlier estimator.
  • The earlier VC-class estimator can achieve 1/√min(m,n) convergence under the anchor-set condition but remains intractable on moderately large datasets.
  • Conditional-probability methods depend on estimating a classifier-derived probability, whose error effects are not clearly understood.
  • The EN and Pearson-divergence methods are exact only when the component supports are completely distinct or disjoint, even with infinite data.
  • The Pearson-divergence method avoids an intermediate conditional-probability model and computes the mixture proportion directly.
  • Jain et al.’s likelihood method resembles gradient thresholding by evaluating candidates and selecting the smallest value where a criterion changes substantially.

8. Experiments

Experiments evaluate the proposed algorithms on six UCI binary-classification datasets constructed with multiple mixture–component pairs; KM1 and KM2 generally match or outperform competing methods.

  • The experiments use six standard binary-classification datasets from the UCI machine learning repository.
  • Shuttle, pageblocks, and digits are converted from multiclass to binary datasets by grouping or ignoring classes.
  • Digits and mushroom data are projected onto a 50-dimensional PCA space.
  • The study constructs six mixture–component distribution pairs per dataset using positive-data fractions of 0.25, 0.5, and 0.75, with labels also flipped.
  • KM1 and KM2 perform comparably to or better than other algorithms on every dataset except mushroom.

9. Conclusion

The paper presents an efficient kernel mean embedding method for mixture proportion estimation, proves convergence under certain conditions, and demonstrates benchmark effectiveness.

  • The method addresses mixture proportion estimation in weakly supervised learning settings.
  • The algorithm uses kernel mean embeddings and converges to the true mixture proportion under certain conditions.
  • Experiments on benchmark datasets demonstrate the method’s effectiveness in practice.

Mixture Proportion Estimation via Kernel Embeddings of Distributions

The analysis establishes that the distance functions used by the method are convex and non-decreasing, supporting estimators based on their behavior around the true proportion.

  • Because d(λ) is zero on [0, λ∗], convexity implies its subgradients are non-negative afterward.Thus d(.) is non-decreasing.
  • d(.) and bd(.) are non-decreasing convex functions.
  • Convex combinations of candidate minimizers establish convexity of d(.).The proof combines witnesses at two parameter values and applies the triangle inequality.
  • The same reasoning shows that bd(.) is convex and non-decreasing.

B. Proof of Lemma 5

The proof combines RKHS concentration, separability assumptions, and sample-composition bounds to establish high-probability control for the proposed estimators.

  • Under k(x, x) ≤1, RKHS functions are uniformly bounded and their Rademacher complexity is controlled.The cited bound includes a 1/√n rate.
  • With probability at least 1 −δ, at least n/(2λ∗) mixture samples are drawn from G.The argument uses Bernoulli indicators and Hoeffding’s inequality.
  • Separability with margin α and tolerance β supplies the assumptions used to control the distance functions and estimator thresholds.The proof invokes convexity and empirical-process bounds under the event Eδ.
  • A universal kernel and an anchor set condition imply a separability condition for suitable β.The anchor set is a compact subset of supp(H) \ supp(G) with H(A) ≥γ.
  • The gradient thresholding estimator is motivated by bd(.) being close to a hinge and ∇bd(.) to a step function asymptotically.
Loading 1603.02501v2…