Permanents, Transport Polytopes and Positive Definite Kernels on Histograms

Marco CuturiIJCAI 2007 · OpenReview

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.

Comparing the optimal permutation (solid) with other possible matchings (dashed) considered by the permanent kernel.

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.

Classification error rates (%) on MNIST subset comparing Gaussian and Permanent kernels across different scales.

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

Abstract

For two integral histograms r = (r1,..., rd) and c = (c1,..., cd) of equal sum N, the Monge-Kantorovich distance dMK(r, c) between r and c parameterized by a d × d distance matrix T is the minimum of all costs 〈 F,T 〉 taken over matrices F of the transportation polytope U(r, c). Recent results suggest that this distance is not negative definite, and hence, through Schoenberg's well-known result, exp(-1/tdMK) may not be a positive definite kernel for all t > 0. Rather than using directly dMK to define a similarity between r and c, we propose in this paper to investigate kernels on r and c based on the whole transportation polytope U(r, c). We prove that when r and c have binary counts, which is equivalent to stating that r and c represent clouds of points of equal size, the permanent of an adequate Gram matrix induced by the distance matrix T is a positive definite kernel under favorable conditions on T. We also show that the volume of the polytope U(r, c), that is the number of integral transportation plans, is a positive definite quantity in r and c through the Robinson-Schensted-Knuth correspondence between transportation matrices and Young Tableaux. We follow by proposing a family of positive definite kernels related to the generating function of the polytope through recent results obtained separately by A. Barvinok on the one hand, and C. Berg and A.J. Duran on the other hand. We finally present preliminary results led on a subset of the MNIST database to compare clouds of points through the permanent kernel.
BibTeX
@inproceedings{cuturi2007permanents,
  author = {Marco Cuturi},
  title = {{Permanents, Transport Polytopes and Positive Definite Kernels on Histograms}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
  url = {https://openreview.net/forum?id=r1ZmTGfu-B},
}
Figure