PaperlayerView exact revision on arXiv

Source-linked AI summary

A Kernelized Stein Discrepancy for Goodness-of-fit Tests and Model Evaluation

Qiang Liu, Jason D. Lee, Michael I. Jordan

arXiv:1602.03253v2stat.ML

TL;DR

The paper addresses goodness-of-fit testing when likelihoods and normalization constants are computationally intractable. It combines Stein’s identity with RKHS theory to construct a tractable discrepancy based on q’s score function, estimate it with U-statistics, and obtain consistent tests. The method is presented as a convenient tool for evaluating complex probability models, with empirical comparisons showing KSD-U competitive with classical tests in the reported setting.

  • Problem

    Goodness-of-fit testing is difficult for complex probabilistic models whose likelihoods or CDFs are intractable and whose approximations may not provide calibrated statistical significance.

  • Method

    The paper constructs a computationally tractable Stein discrepancy by restricting the optimization to an RKHS ball, using only q’s score function and estimating the result with U-statistics.

  • Results

    The KSD-based goodness-of-fit test is consistent against any fixed q ≠ p, while KSD-U performs comparably with or better than the classical tests and MMD-MC(1000) in the reported experiment.

  • Takeaways & Limitations

    The discrepancy provides a practical tool for goodness-of-fit testing of complex models, including models with computationally intractable normalization constants.

  • Takeaways & Limitations

    Unlike KSD, Fisher divergence lacks a computationally convenient U-statistic representation and depends on the unknown p score, making estimation substantially more difficult.

Abstract

from arXiv · show

We derive a new discrepancy statistic for measuring differences between two probability distributions based on combining Stein's identity with the reproducing kernel Hilbert space theory. We apply our result to test how well a probabilistic model fits a set of observations, and derive a new class of powerful goodness-of-fit tests that are widely applicable for complex and high dimensional distributions, even for those with computationally intractable normalization constants. Both theoretical and empirical properties of our methods are studied thoroughly.

1. Introduction

The paper introduces a likelihood-free goodness-of-fit approach for complex models by combining Stein’s identity with RKHSs, yielding a tractable discrepancy based only on q’s score function. Its U-statistic estimation supports statistically calibrated tests, including when normalization constants are intractable.

  • 1. Introduction: Likelihood-based goodness-of-fit evaluation becomes infeasible for many complex models because likelihoods or CDFs can be computationally intractable and difficult to approximate accurately.The paper notes that likelihood calculation or approximation is often #P-complete for graphical models, while MCMC and variational approximations may have large, hard-to-estimate errors.
  • 1. Introduction: The method defines a discrepancy for testing whether observations from p match a specified distribution q, using Stein’s identity and RKHS theory.The discrepancy is constructed by restricting the Stein discrepancy’s function class to an RKHS ball associated with a smooth positive definite kernel.
  • 1. Introduction: The discrepancy depends on q only through its score function, which does not depend on q’s intractable normalization constant.For q(x)=f(x)/Z, the score equals ∇x log f(x), so evaluating it avoids computing Z.
  • 1. Introduction: The approach provides a computationally tractable alternative to the usual variational Stein discrepancy, whose optimization is often intractable.Earlier tractable work imposed smoothness constraints at finitely many points; the proposed approach instead uses an RKHS ball.
  • 1. Introduction: An i.i.d. sample from p enables efficient empirical estimation of the discrepancy through a U-statistic.The resulting statistic has a distribution characterized by U-statistic theory, supporting a hypothesis test based on H0: Ep[uq(x,x′)] = 0 versus H1: Ep[uq(x,x′)] > 0.

2. Backgrounds

The background develops RKHS and Stein-operator machinery for relating score-function differences to expectations under p. These identities provide the analytical foundation for constructing the paper’s discrepancy.

  • 2.1. Kernels and Reproducing Kernel Hilbert Spaces: Positive definite kernels define RKHSs whose elements are kernel-induced function combinations equipped with an inner product and norm.The kernel satisfies a reproducing property, and every positive definite kernel determines a unique RKHS.
  • 2.1. Kernels and Reproducing Kernel Hilbert Spaces: The paper extends the scalar RKHS construction to Hd, the Hilbert space of d-dimensional vector-valued functions.Each component belongs to the scalar RKHS, with the vector space equipped with a corresponding inner product.
  • 2.2. Stein’s Identity and Operator: The Stein score function is defined for a smooth density, and the Stein operator acts linearly on functions in the density’s Stein class.For vector-valued functions, the operator produces a matrix-valued function through a score-weighted function term plus its derivative.
  • 2.2. Stein’s Identity and Operator: Stein’s identity states that the expectation of the Stein operator under the target density is zero under suitable smoothness and boundary conditions.The required boundary condition can be verified using integration by parts or the divergence theorem.
  • 2.2. Stein’s Identity and Operator: The expectation of q’s Stein operator under p equals a score-function difference weighted by the test function.For vector-valued functions, taking the trace of the resulting matrix gives a scalar quantity used in discrepancy construction.

3. Kernelized Stein Discrepancy

The paper introduces kernelized Stein discrepancy (KSD), an RKHS-based, computationally tractable discrepancy that can be evaluated using only the model score. Under stated assumptions, KSD is nonnegative and vanishes exactly when the two distributions match.

  • Kernelized Stein Discrepancy: KSD is introduced by combining Stein’s method with reproducing kernel Hilbert space theory.The construction uses a smooth positive definite kernel and an RKHS unit ball.
  • Kernelized Stein Discrepancy: The KSD definition uses a kernel and the score difference δq,p(x) = sq(x) − sp(x) evaluated on independent draws from p.The score difference is δq,p(x) = sq(x) − sp(x).
  • Kernelized Stein Discrepancy: For integrally strictly positive definite kernels and finite ||gp,q||2^2, S(p, q) ≥ 0 and S(p, q) = 0 if and only if p = q.Here gp,q(x) = p(x)(sq(x) − sp(x)).
  • Kernelized Stein Discrepancy: The framework assumes smooth densities and Stein-class kernels; its finite-norm condition may fail for heavy-tailed p, including a Cauchy p with Gaussian q.The RBF kernel is in the Stein class for smooth densities supported on R^d.
  • Kernelized Stein Discrepancy: Applying Stein’s identity yields a representation requiring only sq, avoiding the need to know sp or the normalization constant of q.This representation enables empirical evaluation from samples drawn from p and the model score.
  • Kernelized Stein Discrepancy: The RKHS formulation interprets S(p, q) as the maximum of Ex∼p[Aqf(x)] over the unit ball of the associated RKHS.The Stein operator acts on RKHS functions, and the spectral form applies it across the kernel eigenfunctions.

4. Goodness-of-fit Testing Based on KSD

The KSD goodness-of-fit test estimates a score-based discrepancy with U-statistics and uses null calibration to test p = q. Its U-statistic test is consistent, while bootstrap calibration achieves asymptotically correct significance levels; a linear alternative reduces computation at a power cost.

  • Empirical estimation: KSD is estimated with U-statistics from observations and the model score, with the U-statistic providing an unbiased minimum-variance estimator.The corresponding V-statistic is biased but nonnegative; the paper focuses on the U-statistic for unbiasedness.
  • Asymptotic theory: Under p = q, the U-statistic is degenerate, whereas under p ≠ q it is asymptotically normal under the stated moment and kernel conditions.The null behavior involves a weighted Gaussian limit determined by eigenvalues of the kernel under p.
  • Test consistency: nŜu remains finite under the null and grows at a √n-rate under fixed alternatives, yielding a test with limiting power one for every fixed q ≠ p.The rejection rule compares nŜu with the 1 − α null quantile.
  • Bootstrap calibration: The null limit distribution and its α-quantile generally lack analytic forms, so the paper uses a bootstrap procedure whose critical-value estimator is asymptotically consistent.The bootstrap test attains the correct significance level asymptotically, while the usual bootstrap may fail for degenerate U-statistics.
  • Computational trade-offs: The bootstrap test costs O(mn^2), whereas a linear estimator gives O(n) time complexity but is less statistically powerful and performs worse in experiments.Block-wise averaging provides intermediate computation-efficiency trade-offs.

5. Related Methods

The paper relates KSD to Fisher divergence and MMD while emphasizing that KSD retains tractable estimation for goodness-of-fit testing when likelihoods, scores, or exact model samples pose difficulties.

  • Connection with Fisher divergence: KSD can be viewed as a kernelized version of Fisher divergence, with Fisher divergence arising as a limiting or special-kernel case.The paper also establishes inequalities connecting the two discrepancies.
  • Connection with Fisher divergence: Fisher divergence has stronger convergence properties in the cited comparison, but its convenient KSD-style U-statistic representation is unavailable because the corresponding identity kernel is not differentiable.Estimating Fisher divergence therefore requires handling terms involving the unknown data-distribution score.
  • Connection with MMD: Turning goodness-of-fit testing into a two-sample test may require exact samples from q, but MCMC can be expensive, fail to converge, or introduce correlations.This motivates score-based testing when exact model sampling is impractical.
  • Connection with MMD: MMD uses samples from both p and q and can be estimated with U- or V-statistics, whereas KSD uses p-samples and the score function of q for goodness-of-fit testing.KSD can be interpreted as a special MMD with the Stein kernel uq.

6. Experiments

The experiments evaluate KSD-based and competing goodness-of-fit tests on a 1D Gaussian mixture and a Gaussian-Bernoulli RBM, including settings with intractable likelihoods. KSD-U is competitive with classical tests in the toy setting and follows the oracle likelihood-ratio test on the RBM, while alternatives expose computational and sampling trade-offs.

  • 1D Gaussian mixture: Figure 1 varies perturbation magnitude, sample size, and ROC behavior while reporting error rates whose type I components remain below 0.05.The simulations perturb the Gaussian mixture's means, variances, or mixture weights and average results over 1000 trials.
  • 1D Gaussian mixture: On the 1D Gaussian mixture, KSD-U performs comparably with or better than χ2, Kolmogorov-Smirnov, Cramer-von Mises, and MMD-MC(1000).The oracle LR performs best, while KSD-Linear performs worst but remains a computationally efficient alternative for more complex models.
  • Gaussian-Bernoulli RBM: On the Gaussian-Bernoulli RBM, KSD-U follows the oracle LR, while MMD-MCMC breaks down because its MCMC sample is not representative of q.MMD-MC(100) performs worse than KSD-U, whereas MMD-MC(1000) is almost as good.
  • Gaussian-Bernoulli RBM: For RBM discrepancy curves, exact likelihood ratios discriminate best, MMD-MCMC fails to distinguish null and alternative cases, and AIS is worse than KSD-U and MMD-MC(1000).Figure 2 also examines how MMD-MC performance changes with the size of the exact sample from q.

7. Conclusion and Future Directions

The paper proposes a computationally tractable discrepancy measure and derives goodness-of-fit tests for complex probability models. It identifies composite testing and comparative theoretical discrimination power as future directions.

  • The paper proposes a computationally tractable discrepancy measure between complex probability models and derives a novel class of goodness-of-fit tests.
  • Future work includes extending the method to composite goodness-of-fit tests for classes of distributions.
  • Future work also includes analyzing KSD's theoretical discrimination power against classical goodness-of-fit tests, MMD with infinite exact Monte Carlo samples, and Gorham and Mackey's method.

A. Proofs

The proofs establish the kernelized Stein discrepancy's algebraic and statistical properties through Stein-class arguments, reproducing-kernel identities, and U-statistic asymptotics. They connect the discrepancy to score-function differences and characterize when variational equalities hold.

  • Theorem proofs: The proofs use Stein-class closure for kernels and their derivatives to justify applying Stein's identity to the kernelized operators.The argument establishes that v(·, x′) and related kernel derivatives remain in the Stein class.
  • Theorem proofs: The reproducing property converts the kernelized discrepancy into an RKHS representation involving the score difference sq − sp.The resulting variational form expresses the RKHS norm through maximization over functions in the vector-valued RKHS.
  • Asymptotic theory: The U-statistic analysis shows a finite null limit for nŜu(p, q) and √n divergence under any fixed alternative q ≠ p, motivating the goodness-of-fit test.The appendix proof checks the relevant U-statistic asymptotics and uses Stein's identity in the null case.
  • Theorem proofs: The proofs establish positive definiteness of the kernelized Stein kernel and derive bounds using Cauchy-Schwarz and RKHS norm relations.These steps support the discrepancy's nonnegativity and its comparison with the variational Stein formulation.
  • Assumptions: The variational equality holds when sq − sp belongs to the appropriate vector-valued Stein class, which must be imposed explicitly beyond L2(p).L2(p) includes discontinuous and nonsmooth functions, so Stein-class membership is an additional requirement.
Loading 1602.03253v2…