Source-linked AI summary
Sliced Wasserstein Kernels for Probability Distributions
Soheil Kolouri, Yang Zou, Gustavo K. Rohde
TL;DR
High-dimensional probability distributions require effective discrepancy measures, while many transport distances provide limited options for provably positive definite kernels. The paper introduces Sliced Wasserstein kernels with explicit invertible embeddings and reports benefits over RBF and polynomial kernels across pattern-recognition tasks, while experiments focus on two-dimensional distributions.
Problem
High-dimensional probability distributions need effective discrepancy measures, but many transport-related distances do not satisfy the requirements for standard positive definite RBF kernels.
Method
The paper constructs a family of provably positive definite kernels from the Sliced Wasserstein distance and derives an explicit nonlinear, analytically invertible mapping into kernel space.
Results
The experiments demonstrate benefits over RBF and polynomial kernels across regression, dimensionality reduction, clustering, and classification tasks.
Takeaways & Limitations
Sliced Wasserstein kernels capture more variation with fewer parameters, improve clustering measures, and benefit kernel-SVM classification accuracy.
Takeaways & Limitations
The experiments focus on two-dimensional distributions, leaving higher-dimensional applications for future investigation.
Abstract
from arXiv · showhide
Optimal transport distances, otherwise known as Wasserstein distances, have recently drawn ample attention in computer vision and machine learning as a powerful discrepancy measure for probability distributions. The recent developments on alternative formulations of the optimal transport have allowed for faster solutions to the problem and has revamped its practical applications in machine learning. In this paper, we exploit the widely used kernel methods and provide a family of provably positive definite kernels based on the Sliced Wasserstein distance and demonstrate the benefits of these kernels in a variety of learning tasks. Our work provides a new perspective on the application of optimal transport flavored distances through kernel methods in machine learning tasks.
1. Introduction
Probability distributions are central representations in computer vision, creating a need for effective similarity measures. The paper addresses limitations of existing transport-based kernels by introducing positive definite Sliced Wasserstein kernels and evaluating them across regression tasks.
- Motivation: High-dimensional image representations are often modeled as probability distributions, making suitable distributional similarity measures crucial.Examples include Bag-of-Words, feature matching, texture co-occurrence matrices, and action recognition.
- Motivation: Wasserstein distance measures geometric discrepancy by optimally transporting one probability measure to another under a displacement cost.It has been applied to image retrieval, distribution barycenters, cancer detection, and super-resolution.
- Problem: Many transport-related distances do not meet the flatness requirements needed for standard positive definite RBF kernels, limiting available transport-based kernel constructions.Earlier approaches include kernels based on transport-polytope permanents and certain earth mover’s distances.
- Contribution: The paper introduces a family of provably positive definite Sliced Wasserstein kernels for regression-based pattern recognition tasks.The authors derive theoretical results and an explicit analytically invertible kernel embedding.
- Evaluation: The experiments compare Sliced Wasserstein kernels with commonly used RBF and polynomial kernels across several pattern-recognition settings.The paper is organized around preliminaries, kernel theorems, kernel algorithms, and experimental demonstrations.
2. Background
The background develops Wasserstein distances through transport plans and one-dimensional closed forms, then constructs Sliced Wasserstein distances from projections. It connects positive definite Gaussian kernels to embeddings into inner-product spaces, motivating the paper’s kernel construction.
- Wasserstein distance: The Lp-Wasserstein distance is defined by minimizing transport cost over plans whose marginals equal the two input probability measures.The admissible plan constraints preserve the source and target measures.
- Wasserstein distance: For absolutely continuous measures, Brenier’s theorem provides an equivalent transport-map formulation, while the one-dimensional L2 case has a unique monotonically increasing map and a closed-form solution.The closed form avoids computationally intensive optimization in one dimension.
- Sliced Wasserstein distance: The Sliced Wasserstein distance projects higher-dimensional distributions into one-dimensional representations and aggregates distances between their projected distributions.Its computation therefore uses several one-dimensional optimal transport problems with closed-form solutions.
- Sliced Wasserstein distance: The Sliced Wasserstein distance is symmetric, subadditive, and satisfies coincidence, so it is a true metric.The construction uses projected distributions obtained through the Radon transform, which is described as invertible and linear.
- Positive definite kernels: A Gaussian kernel exp(−γd^2) is positive definite for all γ > 0 exactly when the metric admits an embedding as Euclidean distance in an inner-product space.This criterion motivates proving an explicit feature-space representation for the Sliced Wasserstein kernel.
3. Sliced Wasserstein Kernels
The paper proves that Sliced Wasserstein distances support positive definite Gaussian and polynomial kernels through explicit feature-space embeddings. It first establishes the one-dimensional Wasserstein embedding, then extends the result to sliced distances and polynomial kernels.
- The paper proves that the Sliced Wasserstein Gaussian kernel is positive definite for all γ > 0.The proof uses conditional negative definiteness of the squared Sliced Wasserstein distance.
- One-dimensional Wasserstein kernel: For one-dimensional positive densities, the squared L2-Wasserstein distance is represented as a Euclidean feature-space distance.This representation yields positive definiteness of the corresponding Gaussian kernel.
- One-dimensional Wasserstein kernel: The one-dimensional construction uses a nonlinear map relative to a fixed probability measure, sending densities to linear functionals of their transport maps.The fixed reference density maps to zero, and Wasserstein distance to it equals the norm of the mapped density.
- Sliced Wasserstein Gaussian kernel: The sliced Wasserstein distance admits an inner-product-space embedding, making its squared distance conditionally negative definite and its Gaussian kernel positive definite.Each hyperplane integral produces a one-dimensional density, allowing the one-dimensional result to be integrated over directions.
- Sliced Wasserstein polynomial kernel: Using the sliced Wasserstein feature map, the paper defines positive definite polynomial kernels of the form (⟨φσ(Ii), φσ(Ij)⟩)^d for positive integer d.The construction follows from positive definiteness of the inner-product kernel and Mercer’s kernel properties.
4. The Sliced Wasserstein Kernel-based algorithms
The paper applies Sliced Wasserstein kernels to clustering, dimensionality reduction, and classification by mapping probability distributions into a kernel space. These kernel-space procedures correspond to operations based on the Sliced Wasserstein distance in the original space.
- Sliced Wasserstein k-means: Sliced Wasserstein k-means maps distributions through φσ and performs k-means in the resulting kernel space.Because the feature-space distance equals the Sliced Wasserstein distance, the procedure is equivalent to k-means under that distance in the original space.
- Sliced Wasserstein kernel PCA: Kernel PCA applies standard PCA to the mapped distributions in the kernel or feature space.The paper evaluates principal components using cumulative percent variance to measure captured dataset variation.
- Sliced Wasserstein kernel PCA: Gaussian and polynomial Sliced Wasserstein kernel PCA are equivalent to applying the corresponding kernel PCA methods to φσ(Ii).This establishes the relationship between the distribution-space formulation and standard kernel methods in the feature space.
- Sliced Wasserstein kernel SVM: Kernel SVM finds a maximum-margin hyperplane in feature space, yielding a nonlinear classifier in the original distribution space.The margin is measured according to the Sliced Wasserstein distance, with Gaussian and polynomial Sliced Wasserstein kernels providing the corresponding classifiers.
- Sliced Wasserstein kernel SVM: Multiclass classification is handled by reducing the problem to binary tasks through pairwise coupling or a one-versus-all strategy.The paper cites both approaches for extending the binary SVM formulation to multiclass problems.
5. Experimental Results
The experiments evaluate Sliced Wasserstein kernels on texture and animal-face datasets using dimensionality reduction, classification, and clustering. They compare these kernels with standard representations and commonly used kernels under repeated evaluation procedures.
- Datasets and representations: The experiments use a 25-class UIUC texture dataset and a 21-class LHI animal-face dataset represented by co-occurrence matrices and HOGgles images.The texture dataset has 40 images per class, while the animal-face dataset averages 114 images per class.
- Dimensionality reduction: Figure 3 compares cumulative percentage variation captured by standard PCA and Sliced Wasserstein kernel PCA on both datasets.The kernel-PCA experiment uses a parameter-free linear Sliced Wasserstein kernel so its eigenvalue spectrum does not depend on hyperparameters.
- Classification: The classification study compares linear SVM, RBF kernel SVM, Sliced Wasserstein Gaussian kernel SVM, and Sliced Wasserstein polynomial kernel SVM.Five-fold cross-validation holds out 20% of each class for testing, with hyperparameters selected by grid search.
- Classification: Classification accuracies are reported as means and standard deviations over 100 repeated experiments for both datasets.The repeated evaluation provides the summary statistics shown in Figure 4.
- Clustering: Clustering compares k-means on normalized image-derived representations with kernel k-means on their Sliced Wasserstein feature-space representations.The experiments measure within-cluster sum-of-squares, or inertia, after normalization by the average norms of the compared representations.
6. Discussion
The paper’s Sliced Wasserstein kernels provide a positive-definite feature-space approach that benefits dimensionality reduction, clustering, and classification. The experiments support these benefits while remaining focused on two-dimensional distributions.
- The proposed Sliced Wasserstein kernels are provably positive definite and map probability distributions into an explicit nonlinear, invertible kernel space.
- PCA with the Sliced Wasserstein kernel captures more variation using fewer parameters.
- The experiments evaluated clustering with within-cluster sum-of-squares and V-measure for standard k-means and Sliced Wasserstein kernel k-means.
- Kernel clustering yields higher V-measure and lower inertia, while kernel SVM classification accuracy also benefits from the Sliced Wasserstein kernels.
- The experiments focused on two-dimensional distributions, although the framework can be extended to higher-dimensional probability densities.