Source-linked AI summary
Learning from Distributions via Support Measure Machines
Krikamol Muandet, Kenji Fukumizu, Francesco Dinuzzo, Bernhard Schölkopf
TL;DR
The paper addresses how to perform discriminative learning when training data are better represented as probability distributions than as individual vectors. It embeds distributions in an RKHS, develops SMMs and related kernels, and reports benefits over example-based methods on synthetic and real-world data. The framework also reveals connections to flexible SVMs while retaining a limitation from the loss function.
Problem
The paper studies how to learn from probability distributions instead of large collections of vectorial examples, motivated by uncertainty, missing data, and data volume.
Method
The framework embeds distributions as RKHS mean functions and applies kernel-based regularized learning, including SMMs and flexible nonlinear kernels on distributions.
Results
Experiments on synthetic and real-world data show benefits from learning over pools of distributions, and SMMs often outperform SVM and ASVM baselines as virtual examples increase.
Takeaways & Limitations
The analysis connects distribution-based learning with traditional SVMs, including a flexible SVM that places different kernels on each training example.
Takeaways & Limitations
Even when the embedding preserves distribution information, the loss function can still cause information loss.
Abstract
from arXiv · showhide
This paper presents a kernel-based discriminative learning framework on probability measures. Rather than relying on large collections of vectorial training examples, our framework learns using a collection of probability distributions that have been constructed to meaningfully represent training data. By representing these probability distributions as mean embeddings in the reproducing kernel Hilbert space (RKHS), we are able to apply many standard kernel-based learning techniques in straightforward fashion. To accomplish this, we construct a generalization of the support vector machine (SVM) called a support measure machine (SMM). Our analyses of SMMs provides several insights into their relationship to traditional SVMs. Based on such insights, we propose a flexible SVM (Flex-SVM) that places different kernel functions on each training example. Experimental results on both synthetic and real-world data demonstrate the effectiveness of our proposed framework.
1 Introduction
The paper argues that probability distributions can represent training data more appropriately than individual vectors, especially under uncertainty or massive data volume. It develops kernel-based learning methods for distributions and connects them to SVMs.
- Motivation: Probability distributions can represent training data when individual vector examples are inadequate or less appropriate.The motivation includes uncertain or missing observations and settings where distributions better capture the data structure.
- Motivation: Noisy microarray measurements can be grouped into distributions that approximate gene-expression variability across slides when replication is constrained.Cost and limited mRNA availability can inhibit experimental replication.
- Motivation: In data-rich fields, groups of similar samples can be compressed into a smaller collection of distributions to reduce computational demands.The passage identifies neuroinformatics, climate informatics, and astronomy as examples of high-throughput domains.
- Related work: Earlier work defined positive definite kernels on probability measures, including probability product, Hilbertian, and semi-group kernels.These approaches provide precedents for kernel-based learning directly on distributions.
- Contributions: The paper proves a representer theorem, introduces kernels on distributions, proposes SMMs, and relates them to traditional SVMs and flexible per-example kernels.An SVM on the input space is presented as a special case of the SMM.
2 Regularization on probability distributions
The framework learns from probability distributions by embedding them as mean functions in an RKHS and applying regularized kernel learning. Its representer theorem yields finite combinations of distribution embeddings, while Dirac measures recover the standard SVM formulation.
- Problem setting: Training inputs are probability measures paired with labels, with the paper focusing on binary classification.The label space is Y = {+1, −1}.
- Mean embeddings: Each distribution is represented by a mean embedding in an RKHS, providing a compact representation intended to preserve necessary information and support efficient computation.The embedding is defined using the expectation of kernel features under the distribution.
- Mean embeddings: If the kernel is characteristic, the mean map is injective, so the embedding preserves all information about the distribution.The construction assumes the kernel is bounded for every input.
- Kernels on distributions: Inner products between mean embeddings define a positive definite kernel on distributions through K(P, Q) = ⟨µP, µQ⟩H.The kernel also equals the expected base-kernel value over independent draws from P and Q.
- Representer theorem: Regularized-risk minimizers admit finite linear combinations of distribution mean embeddings, extending the representer theorem to probability distributions.The coefficients determine how distributions contribute through their mean embeddings.
- Relation to standard SVMs: Restricting distributions to Dirac measures reduces the framework to the usual regularization functional and recovers the standard representer theorem.The resulting solution has the form f = Σ_i α_i k(x_i, ·).
- Relation to alternative objectives: The distribution-based objective differs from both training on infinitely many samples and replacing each distribution with its mean, placing the framework between these alternatives.This distinction is stated as a limitation of the formulation’s relationship to sample-based and mean-based objectives.
3 Kernels on probability distributions
The paper constructs kernels on probability distributions from RKHS mean embeddings, enabling nonlinear kernel learning and support measure machines using expected or empirical kernels.
- Kernels on probability distributions: The function class induced by mean embeddings consists of expectations of RKHS functions under probability measures, with universal kernels providing density under the stated compactness assumption.This links approximation on the input space to approximation over distributions.
- Kernels on probability distributions: Nonlinear kernels on distributions reuse standard positive definite kernels applied to mean embeddings, including polynomial constructions based on their inner products.The framework is generic rather than restricted to kernels designed for particular distribution families.
- Kernels on probability distributions: Gaussian RBF kernels are universal on probability distributions when the input space is compact and the mean map is injective.The paper motivates broader universal-kernel theory beyond the established Gaussian RBF case.
- Support measure machines: Support measure machines solve an SVM problem with the expected kernel K(P, Q) = E_x∼P,z∼Q[k(x, z)], with analytic forms available for selected kernels and distributions.The analytic cases are organized in Table 1, while empirical estimates provide an alternative when closed forms are unavailable.
- Support measure machines: A finite sample from a distribution suffices with high probability for the empirical kernel approximation, while probabilistic models can reduce storage when samples are large.Model parameters may occupy less space than storing all data points.
- Support measure machines: SMMs use a linear mean embedding as the first-level representation and a second-level kernel to perform nonlinear learning on distributions.The paper distinguishes the embedding kernel k from the level-2 kernel K.
4 Theoretical analyses
The theoretical analysis bounds when distribution-level risk approximates pointwise risk and characterizes when linear SMMs correspond to SVMs or Flex-SVMs. These results connect distribution-based learning to sample-based kernel methods while identifying assumptions and information loss.
- 4.1 Risk deviation bound: The framework minimizes an expected-loss risk functional whose expectations can be computed exactly for certain distributions and RKHS choices.For universal H, this simplification preserves all distribution information, although the loss function still causes information loss.
- 4.1 Risk deviation bound: Theorem 3 bounds the loss deviation by 2CℓCfσ when f and ℓ are Lipschitz continuous and the distribution has variance σ^2.The deviation is small when the distribution is concentrated around its mean and both functions are well behaved.
- 4.1 Risk deviation bound: When the bound holds for every training distribution, the true risk deviation between R and Rµ is also expected to be small.
- 4.2 Flexible support vector machines: Under suitable density and integrability assumptions, a linear SMM is equivalent to an SVM trained on representative samples with an appropriate kernel.
- 4.2 Flexible support vector machines: Because each density changes the feature map, the resulting kernel permits an SVM to place different kernels at different training points, yielding Flex-SVM.
- 4.2 Flexible support vector machines: For Gaussian distributions differing in location, a linear SMM with a Gaussian RBF embedding kernel is equivalent to a Flex-SVM using a data-dependent larger bandwidth.The location-only assumption is essential and need not hold in every SMM application.
5 Related works
The framework is related to surrogate and expected-kernel approaches for probability measures and to robust SVMs addressing uncertain inputs. Its distinction is supervised learning over distributions with kernels not restricted to empirical forms.
- The linear mean-embedding kernel is connected to Hilbertian metrics, GMMK, and PPK under specific embedding-kernel choices.
- GMMK and PPK estimate probabilistic models or use probability products as surrogate kernels between examples.
- Unlike a cited unsupervised multi-task use of the empirical kernel, this framework treats distributions in a supervised regularized objective and permits broader kernels.
- Expected kernels connect the framework to robust SVMs, where probabilistic uncertainty is incorporated into margin maximization through SOCP.The robust formulation requires a probability-of-correct-classification parameter τi, related to the distribution variance parameter σi.
6 Experimental results
Experiments compare SVM, augmented SVM, and SMM on synthetic, transformed-digit, and natural-scene tasks. SMM generally benefits from learning directly from distributions and can reduce computational cost relative to augmentation.
- SMM is trained directly on distributions, whereas ASVM trains on augmented samples drawn from those distributions.
- SMM implicitly incorporates distributional means and covariances, while mean-based SVM can overemphasize high-density regions and ASVM is sensitive to outliers.
- Both embedding and level-2 kernels affect SMM performance, with embedding kernels generally having greater predictive impact.
- SMM generally outperforms SVM and ASVM as the number of virtual digit examples increases, while also providing a computational-cost benefit over ASVM.
- Natural-scene experiments compare pLSA, standard BoW with SVM, linear SMM, and nonlinear SMM using distribution-based image representations.
7 Conclusions
The paper introduces kernel-based discriminative learning on probability distributions by embedding them in an RKHS. Experiments on synthetic and real-world data report benefits over learning from pools of individual examples.
- The framework embeds probability distributions into an RKHS, enabling kernel-based learning directly on distributions.
- Linear and nonlinear distribution kernels support flexible kernel choices for different problems.
- The analysis relates SMMs to traditional sample-based SVMs and motivates a flexible SVM with different kernels for each training example.
- Synthetic and real-world experiments illustrate benefits from learning with a pool of distributions rather than a pool of examples.
A Proof of Theorem 1
The proof establishes a representer theorem for regularized learning over probability distributions. Any minimizer lies in the finite span of the distributions’ mean embeddings.
- The regularized-risk minimizer can be expressed as a finite linear combination of mean embeddings µ_Pi.
- Decomposing f into a span component and an orthogonal component leaves the expected predictions unchanged for every training distribution.
- Because the loss is independent of the orthogonal component and regularization increases with its norm, the minimizer has no orthogonal component.
B Proof of Theorem 3
The theorem bounds the discrepancy between distribution-based and mean-based evaluations under variance and Lipschitz-continuity assumptions. The proof separately controls two terms before combining the bounds.
- The result assumes a distribution with variance σ^2, a Lipschitz function, and a loss Lipschitz in its second argument.
- The proof begins by introducing a random variable distributed according to P and its mean m_X.
- The two components of the bound are controlled separately and then combined to complete the proof.
C Proof of Lemma 4
Lemma 4 establishes that, under bounded-kernel and density-integrability assumptions, the linear SMM is equivalent to an SVM on the corresponding training sample. The proof uses kernel means and the representer form of minimizers to connect the two optimization problems.
- The proof relies on integrability conditions involving the kernel and density functions to establish the equivalence.
- Under the lemma’s assumptions, each probability measure P_i has density g(x_i, x), and the linear SMM is equivalent to an SVM on {(x_i, y_i)}.
- The proof represents each probability measure g(x_i, x)dx by its kernel mean μ_i.
- For any f ∈ H_k, the kernel mean evaluates through the integral of f against the density g(x_i, x).
- The argument invokes the representer theorem, stating that each minimizer f admits a finite representation.