PaperlayerView exact revision on arXiv

Source-linked AI summary

Relative Density-Ratio Estimation for Robust Distribution Comparison

Makoto Yamada, Taiji Suzuki, Takafumi Kanamori, Hirotaka Hachiya, Masashi Sugiyama

arXiv:1106.4729v1stat.MLmath.STstat.ME

TL;DR

Divergence estimation remains challenging because density-ratio functions can fluctuate strongly, motivating a method that avoids unstable ordinary ratios. The paper directly approximates α-relative density-ratios for relative divergence estimation, showing favorable convergence, model-complexity-independent asymptotic variance, and favorable performance across tasks.

  • Problem

    Density-ratio-based divergence estimation is challenging because density-ratio functions often possess high fluctuation.

  • Method

    The paper estimates relative Pearson divergence by directly approximating α-relative density-ratios instead of separately approximating numerator and denominator densities.

  • Results

    The proposed estimator has more favorable non-parametric convergence, asymptotic variance independent of model complexity under correct parametric specification, and favorable experimental comparisons.

  • Takeaways & Limitations

    Relative divergence estimation provides a robust distribution-comparison approach that hardly overfits even with complex models under the stated parametric condition.

  • Takeaways & Limitations

    The variance result assumes a correctly specified parametric model that includes the true relative density-ratio, and further applications remain to be explored.

Abstract

from arXiv · show

Divergence estimators based on direct approximation of density-ratios without going through separate approximation of numerator and denominator densities have been successfully applied to machine learning tasks that involve distribution comparison such as outlier detection, transfer learning, and two-sample homogeneity test. However, since density-ratio functions often possess high fluctuation, divergence estimation is still a challenging task in practice. In this paper, we propose to use relative divergences for distribution comparison, which involves approximation of relative density-ratios. Since relative density-ratios are always smoother than corresponding ordinary density-ratios, our proposed method is favorable in terms of the non-parametric convergence speed. Furthermore, we show that the proposed divergence estimator has asymptotic variance independent of the model complexity under a parametric setup, implying that the proposed estimator hardly overfits even with complex models. Through experiments, we demonstrate the usefulness of the proposed approach.

1. Introduction

The paper addresses the difficulty of divergence estimation when density ratios fluctuate or become unbounded, proposing α-relative divergence estimation as a smoother alternative. It develops theoretical guarantees and reports favorable empirical comparisons across distribution-comparison tasks.

  • Direct density-ratio approximation avoids separately estimating numerator and denominator densities, but divergence estimation remains difficult when ratios fluctuate strongly.
  • KL divergence estimation through density-ratio approximation is computationally expensive because of the nonlinear log term.
  • Pearson divergence offers an analytically computable alternative whose uLSIF-based estimator is obtained by solving a system of linear equations.
  • The proposed α-relative divergence compares p(x) with the α-mixture density αp(x) + (1 − α)p′(x), using direct approximation of its relative density-ratio.
  • For α > 0, the relative density-ratio is bounded above by 1/α, supporting faster non-parametric convergence than the ordinary density-ratio approach.
  • Under a correctly specified parametric model, the estimator’s asymptotic variance is independent of model complexity, and experiments cover outlier detection, homogeneity testing, and transfer learning.

2. Estimation of Relative Pearson Divergence via Least-Squares Relative Density-Ratio Approximation

RuLSIF estimates relative Pearson divergence by directly fitting α-relative density-ratios with a regularized kernel model. The relative formulation smooths ratio functions and improves estimation behavior in illustrative distribution-comparison examples.

  • 2.1 Problem Formulation: The method estimates relative Pearson divergence through least-squares approximation of the α-relative density-ratio.
  • 2.1 Problem Formulation: The α-relative density-ratio uses the α-mixture of p(x) and p′(x), with α-relative Pearson divergence defined from that mixture.
  • 2.1 Problem Formulation: At α = 0, relative Pearson divergence reduces to ordinary Pearson divergence, making the relative version a smoothed extension.
  • 2.2 Direct Approximation of α-Relative Density-Ratios: RuLSIF represents the relative density-ratio with kernel basis functions and determines parameters by minimizing regularized expected squared error.
  • 2.2 Direct Approximation of α-Relative Density-Ratios: The parameter solution is analytic, and the resulting estimator extends uLSIF to α-relative density-ratio estimation.
  • 2.4 Illustrative Examples: As α increases, true relative density-ratio profiles become smoother and bounded in cases where ordinary ratios diverge, generally improving estimation quality.
  • 2.4 Illustrative Examples: When p(x) = p′(x), the true relative density-ratio remains 1 for every α, although estimated ratios still vary with α through matrix H.

3. Theoretical Analysis

Theoretical analysis shows that relative PE divergence estimators gain convergence and variance advantages from smoother relative density-ratios, while model complexity can still affect finite-sample accuracy and the alternative estimator’s variance.

  • 3.1 Theoretical Analysis: The proposed estimators are analyzed through non-parametric convergence rates and parametric estimation variance under technical assumptions.The analysis uses function-space complexity γ and regularization conditions on λ_n.
  • 3.1 Non-parametric Analysis: The c PE_α estimator has a leading convergence term of order n̄^-1/2, whereas f PE_α has order λ_n^1/2 n̄^-1/2 and is slightly slower depending on γ.When p = p′ or α is close to 1, the leading term for c PE_α can vanish, yielding a faster rate.
  • 3.1.3 Numerical Illustration: For finite samples, f PE_α can be more accurate when α is small because its regularization-dependent error coefficient may be smaller.The experiments report that c PE_α tends to perform better for large α, while f PE_α is slightly favorable for small α and small sample sizes.
  • 3.2 Parametric Analysis: Under a correctly specified parametric model, c PE_α’s asymptotic variance depends on the true relative density-ratio rather than model complexity, so it hardly overfits.By contrast, f PE_α’s variance is affected by the model space, and experiments show larger models tend to increase its standard deviation.
  • 3.2.2 Interpretation: The parametric variance advantage is specific to relative PE divergence estimation: approximation error cancels in the divergence estimate but not in relative density-ratio estimation.The proposed estimator is generally more favorable as α increases because the variance bound decreases with ||r_α||∞.

4. Experiments

Experiments evaluate relative divergence estimation in homogeneity testing, outlier detection, and transductive transfer learning. Middle α values generally provide stable performance, while adaptive selection helps address instability at extreme α values.

  • Two-sample homogeneity test: Middle α balances distinguishability and approximability when ordinary density-ratios diverge, while α = 0.95 can over-smooth the ratio.This pattern is reported for datasets where the null hypothesis is false.
  • Two-sample homogeneity test: Plain and reciprocal LSTT can be excellent at extreme α values, but their performance is unstable across true distributions.Middle α tends to perform reasonably well across all artificial datasets.
  • Two-sample homogeneity test: Adaptive LSTT reduces instability when α is small or large, but offers little improvement over plain and reciprocal LSTT at middle α.For equal distributions, plain and reciprocal LSTT accept the null hypothesis at approximately 95%, whereas adaptive LSTT is slightly lower on the toy dataset.
  • Two-sample homogeneity test: When one distribution has wider support, assigning it to P′ and using large α appears effective; otherwise, middle α in the adaptive setup is reasonable.This is presented as an empirical choice based on prior knowledge of the distributions.
  • Two-sample homogeneity test: LSTT with α = 0.5 compares favorably with α = 0 and 1, and is useful for two-sample homogeneity testing.For correct null hypotheses, LSTT with α = 0.5 and MMD have comparable type-I error; the same α setting compares favorably when distributions differ.
  • Outlier detection: RuLSIF with small α tends to work well in low dimensions, whereas large α tends to work better as dimensionality increases.AUC values overall decrease as input dimensionality increases, making outlier detection more challenging.
  • Transductive transfer learning: Relative importance weights are proposed because their estimation for 0 < α < 1 does not depend on estimating the ordinary ratio at α = 1.This is intended to address unreliable exponentially flattened weights when ordinary ratio estimation is poor.
  • Transductive transfer learning: RIW-LS with α = 0.5 tends to outperform EIW-LS and has much smaller test-error standard deviation in the reported transfer-learning experiment.In another realization, both methods fit the true function well and produce almost the same functions.

5. Conclusion

The paper concludes that relative Pearson divergence estimation provides robust distribution comparison with favorable theory and practical results. It demonstrates usefulness in homogeneity testing, outlier detection, and covariate-shift transfer learning.

  • Conclusion: The proposed estimator directly approximates relative density-ratios and estimates relative Pearson divergence efficiently.The method avoids separate density estimation and is described as computationally efficient.
  • Conclusion: Its non-parametric convergence rate is more favorable than that of the existing plain Pearson divergence estimator.The paper attributes this theoretical advantage to relative divergence estimation.
  • Conclusion: Under a correctly specified parametric setup, asymptotic variance is independent of model complexity, so the estimator hardly overfits even with complex models.This statement is restricted to the correctly specified parametric setup.
  • Conclusion: Experiments demonstrate practical usefulness in two-sample homogeneity testing, inlier-based outlier detection, and transductive transfer learning under covariate shift.The paper identifies these as the evaluated application areas.
  • Conclusion: The authors identify exploring applications beyond the three evaluated tasks as a promising direction.Examples named include multi-task learning, independence testing, dimensionality reduction, matching, clustering, conditional density estimation, and classification.

Appendix A. Technical Details of Non-Parametric Convergence Analysis

This appendix introduces the technical details of the paper’s non-parametric convergence analysis.

  • Appendix A: The appendix provides technical details for the non-parametric convergence analysis described in Section 3.1.It serves as the technical expansion of that earlier analysis.
  • Appendix A: The analysis concerns the non-parametric convergence behavior of the proposed estimator.The passage identifies the analysis as non-parametric and convergence-focused.
  • Appendix A: The appendix supplements the main text rather than introducing a separate experimental evaluation.Its stated purpose is to give technical details of the earlier analysis.

A.1 Results

The appendix formalizes the estimator and assumptions used to analyze non-parametric convergence. It uses function-class complexity, regularization, and theorem-based bounds to characterize estimator behavior.

  • Setup: The analysis defines linear operators and estimates Pearson divergence through the density ratio between p and αp + (1 − α)q.The estimator targets the relative Pearson divergence by direct density-ratio estimation.
  • Estimator: The density-ratio estimator uses a non-negative regularization functional and a model class G.The regularized model is parameterized through the function-class setup described in the appendix.
  • Estimator: An RKHS with a bounded kernel is given as a useful example of the model class, with its norm used as the regularization functional.The Gaussian kernel satisfies the bounded-kernel condition with C = 1.
  • Assumptions: The convergence analysis assumes the true density-ratio function belongs to G and is bounded above.The bound is written as g∗(x) ≤ M0 for all x ∈ DX.
  • Complexity control: Bracketing entropy measures function-class complexity by counting ε-brackets needed to cover the class.Larger γ corresponds to a more complex function class because more brackets are needed.
  • Results: The appendix states a theorem and auxiliary lemma establishing the convergence analysis under the stated assumptions and regularization conditions.The theorem uses n̄ = min(n, n′), M0 = ∥g∗∥∞, and asymptotic-order notation Op.

A.2 Proof of Lemma 3

The proof bounds the L2(S)-error between the estimated and target functions by controlling empirical-process terms, bracketing entropies, and regularity quantities.

  • Bracketing entropies for squared function classes are controlled by constructing brackets from δ-brackets for GM.
  • The proof sets f := bg − g∗ and reduces bounding ∥bg − g∗∥L2(S) to bounding the left-hand side of a derived inequality.
  • Jensen’s inequality, Young’s inequality, and auxiliary bounds are combined to control the L2(S)-norm and complete the lemma’s proof.
  • The resulting rate bound is expressed using Op(max{1, R(g∗)}).
  • The argument uses empirical-process bounds and the central limit theorem to show that relevant terms are Op(λ¯n).

Appendix B. Technical Details of Parametric Variance Analysis

This appendix provides the technical details underlying the parametric variance analysis introduced in Section 3.2.

  • The appendix develops the technical details of the parametric variance analysis described in Section 3.2.

B.1 Results

The results establish asymptotic variance expressions and bounds for relative Pearson-divergence estimators under correctly specified parametric models.

  • Under a correctly specified model and mild assumptions, the estimator bg is consistent and the estimated parameter bθ is asymptotically normal.
  • The paper defines c PEα as one possible estimator of the α-relative Pearson divergence PEα, while noting alternative estimators such as f PEα.
  • Theorem 4 introduces sup-norms for the ordinary density ratio r and α-relative density ratio rα before deriving an upper bound for V[c PEα].
  • Theorem 5 defines the variance V[f PEα] and specifies the gradient vector ∇g evaluated at the target parameter θ∗.
  • Under regularity conditions, the variance of f PEα is given asymptotically by the theorem’s variance expression.

B.2 Proof of Theorem 4

The proof derives the asymptotic variance of c PEα through parameter expansions, operator identities, and monotonicity properties of relative density-ratio terms.

  • The proof starts from an asymptotic expansion of c PEα based on the parameter error δθ = bθ − θ∗.
  • Linear operators G and G′ are introduced for samples from p and p′, respectively, and used to derive the asymptotic variance.
  • The proof establishes that the relevant functions involving rα are non-negative and increasing with respect to the ordinary ratio r.
  • These monotonicity relations yield upper bounds for the variances appearing in Eq.(27).
  • The final inequality completes the proof of Theorem 4.

B.3 Proof of Theorem 5

The proof derives the estimator's defining optimality condition, expands the resulting equation and f_PEα around the relevant parameter, and concludes with the stated result.

  • The estimator bθ is defined as the optimal solution of an optimization problem.
  • The extremal condition for the optimization problem yields an equation used in the subsequent analysis.
  • Writing δθ = bθ − θ∗, the proof expands this equation around θ = θ∗.
  • The proof separately computes an asymptotic expansion of f_PEα.
  • The expansions yield the claimed result and complete the proof.
Loading 1106.4729v1…