Abstract
For two integral histograms $r$ and $c$ of equal sum $N$, the Monge-Kantorovich distance $d_{MK}(r, c)$ is the minimum cost taken over matrices in the transportation polytope $U(r, c)$. Recent results suggest this distance is not negative definite, meaning $\exp(-1/t d_{MK})$ may not be a positive definite (PD) kernel. Rather than using $d_{MK}$ directly, we investigate kernels based on the entire transportation polytope. We prove that for binary counts (point clouds), the permanent of an induced Gram matrix is a PD kernel. We also show that the volume of $U(r, c)$ is a PD quantity through the Robinson-Schensted-Knuth correspondence. Finally, we propose a family of PD kernels related to the polytope's generating function and present results on the MNIST database comparing point clouds via the permanent kernel.
Introduction
In machine learning, data is frequently represented as histograms, such as word counts or color distributions. Comparing these distributions often relies on the Monge-Kantorovich distance (Earth Mover’s Distance), which finds the minimum cost to transform one distribution into another. However, for a distance to be used effectively in kernel-based methods like Support Vector Machines (SVMs), it must be "negative definite" to ensure the resulting kernel is Positive Definite. Because the Earth Mover’s Distance fails this property in many cases, it can lead to unstable optimization.
Methods: Beyond the Optimal Path
Instead of searching for the single optimal transport plan, this research proposes looking at the whole set of possible transport plans—the transportation polytope $U(r, c)$. By summing over all possible ways to transform one distribution into another, we can derive kernels that are mathematically guaranteed to be Positive Definite.
The Permanent Kernel
For point clouds where every bin has a count of 1, we define a kernel based on the permanent of a Gram matrix. Unlike a determinant, which considers the signature of permutations, a permanent sums them all. This effectively aggregates the costs of all possible matchings between two sets of points, rather than just the shortest path.
Volume and Generating Functions
For general histograms, the paper demonstrates that the volume of the transportation polytope (the total number of integral transportation plans) is a valid PD kernel. This is proven using the Robinson-Schensted-Knuth (RSK) correspondence. This approach is further generalized into a family of kernels based on the generating function of the polytope, weighting different transport plans to consider both geometry and combinatorial structure.
Experimental Results
The proposed permanent kernel was evaluated on a subset of the MNIST database. Images were preprocessed by randomly sampling 20 distinct black pixels to represent each digit as a 2D point cloud. The permanent kernel was compared against a standard smoothed Gaussian kernel in a 10-class classification task.
As shown in the table, the Permanent Kernel consistently outperformed the Gaussian baseline. For instance, at $\sigma = 0.2$, the Permanent Kernel achieved a 31.3% error rate, compared to 33.45% for the Gaussian kernel. The results suggest that considering "all paths" provides a more robust and discriminative similarity measure than traditional methods.
Discussion and Future Work
The primary challenge for these kernels is computational complexity. Computing the permanent of an $n \times n$ matrix is #P-complete, making it expensive as the number of points grows. While feasible for small clouds ($n=20$), larger datasets will require approximation methods like Sequential Monte Carlo (SMC) sampling. Future work will focus on these approximations to bring the mathematical benefits of transport polytope kernels to larger, real-world applications.
Summary updated