Interpretable Distribution Features with Maximum Testing Power

Wittawat Jitkrittum; Zoltan Szabo; Kacper Chwialkowski; Arthur Gretton

Source-linked AI summary

Interpretable Distribution Features with Maximum Testing Power

Wittawat Jitkrittum, Zoltan Szabo, Kacper Chwialkowski, Arthur Gretton

arXiv:1605.06796v2May 22, 2016stat.MLcs.LG

TL;DR

The paper addresses how to find interpretable features that distinguish high-dimensional probability distributions from samples. It proposes spatial- and frequency-domain semimetrics whose features maximize a lower bound on test power, and reports linear-time performance comparable to quadratic-time MMD while yielding human-interpretable differences.

Problem
Existing distribution-comparison tools do not directly identify interpretable features that maximize test power, especially for high-dimensional or locally differing distributions.
Method
The paper learns spatial or frequency locations and kernel parameters by maximizing a lower bound on the power of ME and SCF two-sample tests.
Results
Linear-time ME and SCF tests outperform previous linear-time tests and achieve performance comparable to or exceeding quadratic-time MMD on high-dimensional benchmarks.
Takeaways & Limitations
The learned features provide a parsimonious, human-interpretable indication of how and where two distributions differ.
Takeaways & Limitations
The theoretical guarantees require bounded kernel classes and test-location collections with a finite supremum of the inverse-covariance norm.

Abstract

from arXiv · show

Two semimetrics on probability distributions are proposed, given as the sum of differences of expectations of analytic functions evaluated at spatial or frequency locations (i.e, features). The features are chosen so as to maximize the distinguishability of the distributions, by optimizing a lower bound on test power for a statistical test using these features. The result is a parsimonious and interpretable indication of how and where two distributions differ locally. An empirical estimate of the test power criterion converges with increasing sample size, ensuring the quality of the returned features. In real-world benchmarks on high-dimensional text and image data, linear-time tests using the proposed semimetrics achieve comparable performance to the state-of-the-art quadratic-time maximum mean discrepancy test, while returning human-interpretable features that explain the test results.

1 Introduction

The paper seeks interpretable features that distinguish high-dimensional probability distributions from samples, beyond differences captured by their means. It optimizes feature locations for test power, producing linear-time tests with interpretable results and performance comparable to quadratic-time MMD.

1 Introduction: The paper identifies distribution features that maximize distinguishability between high-dimensional distributions observed through i.i.d. samples.The distributions may differ in non-trivial ways, including differences not reducible to their means.
1 Introduction: The MMD witness function shows where probability mass differs but does not directly identify features that maximize test power.This limitation is especially important in high dimensions and for local differences in characteristic functions.
1 Introduction: The proposed ME and SCF tests optimize a lower bound on test power to select spatial or frequency-domain features.ME uses optimized spatial locations, while SCF uses frequency locations and smooth characteristic functions.
1 Introduction: The empirical test-power criterion converges, supporting fewer features and parsimonious interpretations of how distributions differ.The paper proves uniform asymptotic convergence over Gaussian kernel classes.
1 Introduction: Linear-time tests using the proposed features outperform previous linear-time tests and compare to or exceed quadratic-time MMD on high-dimensional text and image data.The learned features provide human-interpretable explanations of the test results.

2 ME and SCF tests

ME and SCF are linear-time two-sample tests based on differences between analytic distribution representations at selected locations. ME uses spatial test locations, whereas SCF evaluates smoothed characteristic functions at frequency locations, with regularization stabilizing the statistic.

2 ME and SCF tests: The two-sample test evaluates whether distributions P and Q differ using statistics computed from independent samples and a null threshold.The null hypothesis is H0: P = Q, and H0 is rejected when the statistic exceeds the critical value.
2 ME and SCF tests: ME computes a normalized squared distance between empirical mean embeddings at J spatial test locations.Its statistic is asymptotically chi-squared with J degrees of freedom under H0.
2 ME and SCF tests: The normalized ME statistic is a semimetric with a computationally tractable chi-squared null distribution.The unnormalized counterpart is a metric for any set of test locations, while both variants behave similarly for two-sample testing.
2 ME and SCF tests: SCF measures a normalized L2 distance between smoothed characteristic functions evaluated at J frequency-domain locations.Its asymptotic null distribution is chi-squared with 2J degrees of freedom.
2 ME and SCF tests: Adding γ_nI regularizes the covariance inverse for stability while preserving the chi-squared null limit when γ_n → 0.The modified statistic remains asymptotically χ2(J′) under H0.

3 Lower bound on test power, consistency of empirical power statistic

The paper learns test locations and kernel parameters by maximizing a lower bound on test power, then establishes consistency of the empirical optimization criterion. Disjoint training and testing data preserve the null distribution while enabling more powerful, interpretable tests.

3 Lower bound on test power, consistency of empirical power statistic: The method optimizes test locations and kernel parameters by maximizing a lower bound on ME test power.The same power-maximization principle applies to SCF, and the criterion is linked to the population quantity μ^TΣ^-1μ.
3 Lower bound on test power, consistency of empirical power statistic: The learned locations increase the probability of rejecting H0 under H1 and serve as discriminative features that explain distribution differences.The optimized parameters do not change the asymptotic null distribution or rejection threshold when tuning and testing use disjoint data.
3 Lower bound on test power, consistency of empirical power statistic: The empirical regularized statistic converges uniformly to its population counterpart over bounded kernel classes and suitable test-location collections.The guarantee includes isotropic and full Gaussian kernel classes under the stated assumptions.
3 Lower bound on test power, consistency of empirical power statistic: The proofs control empirical mean and covariance errors uniformly using empirical-process, Rademacher-complexity, entropy, and VC-subgraph bounds.These bounds establish convergence of the empirical power objective over the parameter class.
3 Lower bound on test power, consistency of empirical power statistic: The consistency and power results require a finite supremum of the inverse-covariance norm over the allowed kernels and test locations.Compact bandwidth constraints and separated, norm-bounded locations provide one construction ensuring this condition for non-degenerate P and Q.

4 Experiments

The experiments evaluate optimized test locations and Gaussian-kernel parameters using repeated two-sample testing, with linear-time computation and empirical type-I-error and power estimates.

4 Experiments: The experiments repeat each problem for 500 trials and estimate type-I error or test power from rejection frequencies at α = 0.01.Toy samples are regenerated per trial, while real-problem samples are randomly partitioned into training and test sets.
4 Experiments: The optimized parameters comprise one Gaussian width and J test locations, forming a Jd + 1-dimensional vector optimized by gradient ascent.For ME, locations are initialized from fitted multivariate normal distributions; for SCF, standard-normal initialization is sufficient.
4 Experiments: Both testing and optimization are linear in the sample size n.The stated testing cost is O(J3 + J2n + dJn), while each optimization iteration costs O(J3 + dJ2n).

1. Informative features: simple demonstration

Toy experiments show that optimized spatial or frequency test locations identify informative regions and improve power, especially for subtle or high-dimensional distribution differences.

Informative features: simple demonstration: In the GMD contour experiment, maximizing the criterion places test locations in regions where P and Q have less-overlapping probability mass.When one location is fixed in a key region, the other is best placed in the other key region; repeated locations in one neighborhood do not increase discriminability.
Informative features: simple demonstration: The criterion’s non-convexity reflects multiple informative ways to detect distribution differences rather than a drawback.A convex objective would not capture this multimodality.
Test power vs. sample size n: The four toy problems include Same Gaussian, Gaussian mean difference, Gaussian variance difference, and Blobs, with H0 holding only in SG.Blobs encodes differences at a smaller length scale than its global structure, making it challenging.
Test power vs. sample size n: ME-full consistently outperforms quadratic-time MMD across GVD sample sizes, while SCF-full substantially outperforms MMD when differences are localized in frequency.On the subtle Blobs problem, optimized locations substantially improve power over random spatial locations, and SCF variants outperform ME variants.
Test power vs. dimension d: ME-full reaches test power 1.0 throughout the GMD dimension experiment, whereas ME-grid power drops monotonically as dimension increases.This comparison is reported with fixed test sample size 10000 and J = 5; quadratic-time MMD is computationally infeasible in these large-dimensional experiments.
Test power vs. dimension d: Across dimensions, tests except the T-test maintain type-I error roughly at α = 0.01, while high-dimensional covariance estimation makes the T-test incorrect.MMD-lin also degrades quickly as dimension increases.

4. Distinguishing articles from two categories

The study distinguishes NIPS papers from different research categories using TF-IDF representations and learned discriminative features. ME-full achieved the strongest linear-time performance while identifying interpretable terms.

The NIPS collection contains 5903 papers from 1988–2015, represented as TF-IDF bag-of-words features after linguistic filtering.The preprocessing retained nouns, removed stop words, applied stemming, and filtered terms by document frequency.
ME-full had the highest test power among linear-time tests across all NIPS category tasks, reaching 1.0 for Bayes-Neuro.Its performance was close to or better than quadratic-time MMD-quad.
B.1 Discriminative terms identified by ME test: The Bayes-Neuro task yielded interpretable top terms including spike, markov, cortex, dropout, recurr, iii, and gibb.Markov and gibb are discriminative terms associated with Bayesian inference.
B.1 Discriminative terms identified by ME test: Replacing important-word rankings with least-important rankings produced nondiscriminative terms such as circumfer, bra, dominiqu, rhino, mitra, kid, and impostor.This comparison supports the informativeness of the learned feature rankings.

5. Distinguishing positive and negative emotions

The facial-expression experiment tests whether learned features distinguish positive from negative emotions in high-dimensional face images. ME-full and SCF-full maintained high power with correct type-I errors, while learned locations emphasized facial regions associated with smiling.

The KDEF experiment compared happy, neutral, and surprised faces against afraid, angry, and disgusted faces using 1632-dimensional grayscale images.The dataset contains 5040 aligned images from 70 actors; sad faces were excluded to balance sample sizes.
ME-full and SCF-full achieved high test power while maintaining correct type-I errors on facial-expression tests.The evaluation used 500 repetitions, Gaussian kernels, and J = 1.
Average learned ME-full locations emphasized the nose, upper lip, and nasolabial folds, capturing differences between positive and negative emotions.Figure 4g shows the average across trials of the learned test locations.

Supplementary Material

The supplementary algorithm splits data, optimizes test parameters on training data, and evaluates the resulting statistic on held-out data against a chi-squared threshold.

Algorithm 1 takes two samples, a significance level α, and a number of test locations J as inputs.
The procedure splits the data into equal-sized disjoint training and test sets before optimizing parameters on the training set.The optimized parameters are denoted θ and the training criterion is estimated using Dtr.
The test threshold is the (1 − α)-quantile of χ2(J′), and the test statistic is computed on the held-out test set.

B Experiments on NIPS text collection

The supplementary NIPS experiments document text preprocessing, category construction, discriminative-term analysis, and runtime behavior. The proposed tests remain computationally practical at large sample sizes and dimensions.

B Experiments on NIPS text collection: Papers were assigned to disjoint Bayesian, deep-learning, learning-theory, or neuroscience categories using title keywords, with overlapping matches excluded.
B.1 Discriminative terms identified by ME test: The top discriminative terms varied by category pair, including collabor for Bayes-Bayes, infer for Bayes-Deep, and spike for Bayes-Neuro.The reported lists contain ten terms for each category pair.
C Runtimes: The runtime experiments compare test-power scaling with sample size and dimension, with additional runtime tables for NIPS and facial-expression data.
C Runtimes: ME-full and SCF-full completed accurate tests in under 10 minutes at test sample size 10000 and dimension d = 1500, while each optimized test took under one second.Parameter optimization adds slight overhead but remains linear in n.
C Runtimes: MMD-quad has the largest runtime for large n because its complexity is quadratic in the sample size.At test sample size 10000, MMD-quad is computationally infeasible in the reported dimension experiment.

D Proof of theorem 2

The proof establishes concentration and uniform convergence for empirical quantities over kernel-induced function classes, yielding consistency of the ME test statistic estimate.

D Proof of theorem 2: The proof combines bounds for the three empirical-process terms with a union bound to obtain the stated high-probability consistency result.The final step applies the separate bounds simultaneously for j = 1, 2, 3.
D Proof of theorem 2: The argument bounds deviations of empirical means, product measures, covariance terms, and regularized matrix expressions using covering-number and concentration inequalities.Dudley entropy bounds, symmetrization, McDiarmid’s inequality, and Hoeffding’s inequality control the relevant terms.
D Proof of theorem 2: Uniform boundedness, separability, measurability, and VC-subgraph assumptions make the kernel-induced classes suitable for empirical-process bounds.The proof verifies these properties for F1, F2, and F3 before applying concentration results.

E Example kernel families

The paper verifies that Gaussian kernel families induce uniformly bounded, separable Carathéodory, VC-subgraph function classes with explicit dimension-dependent VC-index bounds.

E Example kernel families: Isotropic Gaussian kernels yield VC indices V C(F1) ≤ d + 4, V C(F2) ≤ d + 4, and V C(F3) ≤ 2d + 4.The bounds follow by composing VC classes with the monotone map φ(z) = e^-z.
E Example kernel families: For both Gaussian families, F1, F2, and F3 are uniformly bounded separable Carathéodory families with ∥f∥L∞(M) ≤ 1.Uniform boundedness follows from the Gaussian kernel bound |k(x, y)| ≤ 1, while continuity supplies the Carathéodory property.
E Example kernel families: Full Gaussian kernels yield VC indices V C(F1) ≤ d(d + 1) 2 + d + 2, V C(F2) ≤ d(d + 1) + 2, and V C(F3) ≤ d(d + 1) + 2d + 3.These bounds use finite-dimensional spans of linear and quadratic coordinate functions.

F Proof of proposition 1

The proposition proves a lower bound on ME test power by relating it to a population signal-to-covariance quantity and controlling its empirical approximation with concentration inequalities.

F Proof of proposition 1: The ME test’s population quantity λn = nµ⊤Σ^-1µ governs the power bound, and the bound L(λn) increases with λn for large n.The empirical counterpart is λ̂n = nz⊤n(Sn + γnI)^-1zn.
F Proof of proposition 1: The proof decomposes the deviation into three terms involving empirical covariance, empirical feature means, and regularization, then bounds each separately.The bounds use Hoeffding’s inequality and norm inequalities for the relevant matrices and vectors.
F Proof of proposition 1: A union bound combines the separate concentration inequalities to establish the proposition’s high-probability lower-power guarantee.The argument applies the bounds with t = α/3 to the three components.