A Stable Multi-Scale Kernel for Topological Machine Learning

Jan Reininghaus; Stefan Huber; Ulrich Bauer; Roland Kwitt

Source-linked AI summary

A Stable Multi-Scale Kernel for Topological Machine Learning

Jan Reininghaus, Stefan Huber, Ulrich Bauer, Roland Kwitt

arXiv:1412.6821v1Dec 21, 2014stat.MLcs.CVcs.LGmath.AT

TL;DR

The paper addresses the lack of a theoretically sound connection between persistence diagrams and Hilbert-space learning methods. It introduces a positive definite multi-scale kernel with 1-Wasserstein stability, and reports consistent empirical improvements over a persistence-landscape-based alternative on shape and texture tasks.

Problem
Persistence diagrams with the Wasserstein distance form only a metric space, so they cannot be directly used by Hilbert-space methods such as SVM or PCA.
Method
The paper defines a multi-scale persistence-diagram kernel through an L2-valued feature map based on scale-space theory.
Results
The kernel is positive definite and 1-Wasserstein stable, with consistent improvements over the landscape-based kernel on shape and texture benchmarks.
Takeaways & Limitations
The method enables topological information to be used in kernel-based machine-learning methods, with tunable scale improving practical behavior.
Takeaways & Limitations
The paper identifies improved understanding of Wasserstein stability beyond existing estimates as needed for a full stability proof extending from persistence diagrams to the underlying data.

Abstract

from arXiv · show

Topological data analysis offers a rich source of valuable information to study vision problems. Yet, so far we lack a theoretically sound connection to popular kernel-based learning techniques, such as kernel SVMs or kernel PCA. In this work, we establish such a connection by designing a multi-scale kernel for persistence diagrams, a stable summary representation of topological features in data. We show that this kernel is positive definite and prove its stability with respect to the 1-Wasserstein distance. Experiments on two benchmark datasets for 3D shape classification/retrieval and texture recognition show considerable performance gains of the proposed method compared to an alternative approach that is based on the recently introduced persistence landscapes.

1. Introduction

Topological data analysis provides information that can complement conventional visual descriptors, but persistence diagrams lack a direct connection to Hilbert-space methods such as SVM and PCA. The paper addresses this gap with a positive definite, stable multi-scale kernel for persistence diagrams.

Topological data analysis can reveal characteristics of visual data that conventional methods often fail to provide.
Persistent homology summarizes multi-scale topological features through birth and death times in persistence diagrams.
Persistence diagrams with the Wasserstein distance form only a metric space, preventing their direct use in Hilbert-space methods such as SVM and PCA.
The paper proposes a positive definite multi-scale kernel with an L2-valued feature map for persistence diagrams.
The kernel’s feature map is Lipschitz continuous with respect to the 1-Wasserstein distance, while its scale parameter controls robustness to noise and can be tuned to the data.

2. Related work

Prior computer-vision work uses topological information either directly in task-specific models or indirectly as descriptors for machine learning. The paper positions its kernel as a theoretically grounded alternative to ad hoc classifier inputs and as closely related to persistence landscapes.

Prior methods either directly use topological information in task-specific segmentation models or feed topological descriptors into machine-learning algorithms.
Persistence information has been used directly for surface-mesh segmentation, restoring ventricular handles, and enforcing topological constraints in segmentation models.
Other approaches use persistence descriptors with discriminant classifiers for cortical-thickness analysis and neurological-disorder classification, but classifier training is typically ad hoc.
Algebraic-geometry features have been proposed to enable persistence-diagram comparisons in machine-learning setups.
Persistence landscapes are conceptually close to the proposed feature map, admit a valid positive definite kernel, and offer a computational alternative to bottleneck or Wasserstein distances.

3. Background

Persistence diagrams encode the appearance and disappearance of topological features across filtrations, while stability relates perturbations of input functions to diagram distances. Kernels provide the Hilbert-space structure needed to apply standard machine-learning methods to these representations.

A persistence diagram records points (b, d) for k-dimensional holes born at b and filled at d during a filtration.
Essential features represented by points (b, ∞) are excluded, and the paper assumes all persistence diagrams are finite.
Sublevel sets f^-1(−∞, t] form a filtration, producing a persistence diagram from a function defined on a domain.
For images, sublevel sets contain pixels whose grayscale values are at most a threshold, while mesh functions and point clouds provide other filtration constructions.
The Wasserstein family generalizes bottleneck distance, with the limit p →∞ yielding the bottleneck distance.
Earlier stability bounds provide only Hölder continuity and a constant Wasserstein bound for p = 1, rather than Lipschitz continuity.
A kernel represents data through inner products in a Hilbert space, and its induced pseudometric equals the feature-map distance.
Kernel stability means the induced pseudometric is bounded by a constant times the underlying metric, equivalently requiring a Lipschitz feature map.

4. The persistence scale-space kernel

The persistence scale-space kernel embeds persistence diagrams into L2 through heat diffusion of Dirac-delta representations, yielding a positive definite kernel that remains stable under the 1-Wasserstein distance.

Persistence diagrams are embedded into a Hilbert space by representing each diagram as a sum of Dirac delta distributions.The paper uses this representation as the starting point for constructing the feature map.
The method diffuses the Dirac-delta initial condition through a heat equation with a Dirichlet boundary on the diagonal, producing an L2(Ω) function at scale σ.This construction addresses the lack of robustness to perturbations in the direct induced metric.
The feature map is defined by evaluating the diffusion solution at t=σ, and its inner product defines the persistence scale-space kernel kσ.The map is injective, so distinct persistence diagrams receive distinct feature representations.
The kernel can be evaluated in O(|F|·|G|) time for persistence diagrams F and G.The explicit evaluation formula is obtained from the closed-form diffusion solution.
Theorem 2 establishes that kσ is 1-Wasserstein stable through Lipschitz continuity of the feature map.The stability proof uses augmented diagrams, an optimal matching, Minkowski’s inequality, and an exponential inequality.
Increasing σ decreases the stability bound, allowing the scale parameter to counteract noise and potentially improve machine-learning performance when tuned to the data.The paper also proves that no non-trivial additive kernel is stable with respect to dW,p for any 1 < p ≤∞.

5. Evaluation

The evaluation compares the proposed multi-scale kernel with the persistence landscape kernel across theoretical thought experiments, shape classification and retrieval, and texture recognition. Across the shape tasks, scale tuning improves consistency and performance, while texture results favor kσ over kL but not conventional response-histogram SVMs.

Evaluation design: The evaluation contrasts persistence landscapes with the proposed kernel through conceptual stability experiments and benchmarks on shapes and textures.The experiments target shape classification/retrieval and texture recognition, using persistence-diagram features with SVM classifiers.
Comparison to persistence landscapes: High-persistence weighting makes dkL unbounded in the first thought experiment, whereas dkσ and Wasserstein distances approach constants as persistence increases.The diagrams maintain the same Euclidean point separation while moving away from the diagonal.
Comparison to persistence landscapes: In the second thought experiment, dkσ, dB, and dW,p distinguish classes differing only in low-persistence points, while dkL is dominated by high-persistence variation.The proposed distance therefore avoids the high-persistence emphasis attributed to the landscape kernel in this setup.
Shape classification: On synthetic and real SHREC 2014 data, kσ consistently improves classification over kL, with gains reaching 30% for some HKS time parameters.The scale σ can compensate for unfavorable input smoothness, whereas kL relies more heavily on suitable HKS preprocessing.
Shape retrieval: For SHREC retrieval, dkσ has stable performance around the optimal HKS time, while dkL can drop from 91% to 53.3% and 76.7% on synthetic data and from 70% to 45.2% and 43.5% on real data.Despite occasional settings where dkL matches or exceeds dkσ, dkσ ranks among the top five entries on both SHREC subsets.

6. Conclusion

The proposed kernel performs well theoretically and empirically for shape classification and texture recognition using an SVM, while its tunable scale parameter benefits practice. Future work targets computational bottlenecks and stronger stability understanding.

The proposed kernel exhibits good theoretical and empirical behavior for shape classification and texture recognition using an SVM.
Future work should address computational bottlenecks to enable application in large-scale scenarios.Approximation could leverage additivity and stability while reducing distinct points in the kernel summation.
Improved understanding of persistence-diagram stability beyond previous Wasserstein-distance estimates could extend kernel stability to the underlying data.
The method enables topological information to be used in kernel-based machine-learning methods.

A. Indefiniteness of dW,p

Wasserstein-distance constructions do not generally provide valid positive-definite kernels for persistence diagrams, preventing their direct use in kernel-based learning. The appendix uses definiteness criteria, eigenvalue arguments, and counterexamples to establish this obstacle while noting that formal general assessment remains open.

Neither −dW,p nor exp(−ξdW,p(·,·)) is conditionally positive definite for the examined choices of p.Consequently, these constructions cannot be employed in kernel-based learning techniques.
Conditional definiteness restricts the quadratic-form condition to coefficient vectors whose entries sum to zero.
A kernel is positive definite when it is representable as an inner product in a Hilbert-space feature space.This representation enables kernel-based algorithms operating through implicit dot products.
Positive definiteness is characterized by nonnegative Gram-matrix eigenvalues, while a conditionally negative definite matrix has at most one positive eigenvalue.
The relation between conditional negative definiteness and positive definiteness states that exp(−ξk) is positive definite for every ξ>0 exactly when k is conditionally negative definite.
Simple counterexamples produce Gram matrices with at least two positive and two negative eigenvalues, ruling out the relevant definiteness properties.The examples cover various p values, including p=∞, while a formal general assessment remains open.

B. Plots of the feature map Φσ

The feature map is constructed by solving a heat-diffusion partial differential equation from signed Dirac deltas associated with persistence-diagram points. Restricting the solution to the domain yields an L2-valued map whose scale controls the suppression of low-persistence features and contributes to stability.

For each persistence-diagram point, the construction uses a positive and negative Dirac delta after extending the domain from Ω to R2.
Convolving the signed Dirac-delta sum with a Gaussian kernel produces the solution of the extended heat-diffusion equation.
Restricting the extended solution to Ω×R≥0 gives the solution of the original PDE and yields the feature map Φσ:D→L2(Ω).
Figure 6 depicts the signed Dirac-delta construction on the extended domain and its Gaussian convolution.
Increasing σ makes the influence of a low-persistence point near the diagonal essentially vanish.The effect is attributed to the Dirichlet boundary condition and contributes to stability of the persistence scale-space kernel.
Figure 7 illustrates Φσ(D) as an L2(Ω) function across growing scales σ.

C. Closed-form solution for kσ

The persistence scale-space kernel is defined from feature maps of two persistence diagrams, using their pointwise product and integration. Extending the domain and exploiting symmetry allows the relevant integrals to be evaluated in closed form.

The persistence scale-space kernel kσ(F,G) is defined for two persistence diagrams F and G.
After extending the domain to R2, the feature-map symmetry makes the pointwise products for F and G equal across the extended domain.
The kernel integrals are evaluated using a coordinate transform, rotation, and Fubini’s theorem.The transformation moves x−q to x, and the rotation places p−q on the positive x1-axis.
The calculation yields a closed-form expression for the kernel kσ.

D. Additional retrieval results on SHREC 2014

Additional SHREC 2014 retrieval results are reported for synthetic and real data. The section covers T1, T2, EM, and DCG performance.

T1 retrieval performance is reported for synthetic and real SHREC 2014 data.The table presents synthetic results on the left and real results on the right.
T2 retrieval performance is reported for synthetic and real SHREC 2014 data.The table presents synthetic results on the left and real results on the right.
EM retrieval performance is reported for synthetic and real SHREC 2014 data.The table presents synthetic results on the left and real results on the right.
DCG retrieval performance is reported for synthetic and real SHREC 2014 data.The table presents synthetic results on the left and real results on the right.