Search

We propose a novel class of deep stochastic predictors for classifying metric data on graphs within the PAC‐Bayes risk certification paradigm. Classifiers are realized as linearly parametrized deep assignment flows with random initial conditions. Building on the recent PAC‐Bayes literature and data‐dependent priors, this approach enables (i) to use risk bounds as training objectives for learning posterior distributions on the hypothesis space and (ii) to compute tight out‐of‐sample risk certificates of randomized classifiers more efficiently than related work. Comparison with empirical test set errors illustrates the performance and practicality of this self‐certifying classification method. [ABSTRACT FROM AUTHOR]

Assignment flows are smooth dynamical systems for data labeling on graphs. Although they exhibit structural similarities with the well‐studied class of replicator dynamics, it is nontrivial to apply existing tools to their analysis. We propose an embedding of the underlying assignment manifold into the interior of a single probability simplex. Under this embedding, a large class of assignment flows are pushed to much higher‐dimensional replicator dynamics. We demonstrate the applicability of this result by transferring a spectral decomposition of replicator dynamics to assignment flows. [ABSTRACT FROM AUTHOR]

This paper extends the recently introduced assignment flow approach for supervised image labeling to unsupervised scenarios where no labels are given. The resulting self‐assignment flow takes a pairwise data affinity matrix as input data and maximizes the correlation with a low‐rank matrix that is parametrized by the variables of the assignment flow, which entails an assignment of the data to themselves through the formation of latent labels (feature prototypes). A single user parameter, the neighborhood size for the geometric regularization of assignments, drives the entire process. By smooth geodesic interpolation between different normalizations of self‐assignment matrices on the positive definite matrix manifold, a one‐parameter family of self‐assignment flows is defined. Accordingly, our approach can be characterized from different viewpoints, e.g. as performing spatially regularized, rank‐constrained discrete optimal transport, or as computing spatially regularized normalized spectral cuts. Regarding combinatorial optimization, our approach successfully determines completely positive factorizations of self‐assignments in large‐scale scenarios, subject to spatial regularization. Various experiments including the unsupervised learning of patch dictionaries using a locally invariant distance function, illustrate the properties of the approach. [ABSTRACT FROM AUTHOR]

The image labeling problem can be described as assigning to each pixel a single element from a finite set of predefined labels. Recently, a smooth geometric approach for inferring such label assignments was proposed by following the Riemannian gradient flow of a given objective function on the so‐called assignment manifold. Due to the specific Riemannian structure, this results in a coupled replicator dynamic incorporating local spatial geometric averages of lifted data‐dependent distances. However, in this framework an approximation of the flow is necessary in order to arrive at explicit formulas. We discuss preliminary results of an alternative model where lifting and averaging is decoupled in the objective function so as to stay closer to established approaches and at the same time preserve the ingredients of the original approach. As a consequence the resulting flow is explicitly given, without the need for any approximation, while still exploiting the underlying Riemannian structure. [ABSTRACT FROM AUTHOR]

We introduce the linear assignment flow as an approximation of the full nonlinear assignment flow, which is a method for contextual data labeling on arbitrary graphs. The linear assignment flow is a dynamical system evolving on the tangent space of a statistical manifold. It is numerically determined using exponential integrators and Krylov subspace approximation, for which we provide error estimates. The approximation property of the linear assignment flow is illustrated by a numerical experiment. This work is supplemented by two papers on variational modeling and unsupervised labeling [1]. [ABSTRACT FROM AUTHOR]

We introduce a smooth coupled system of Riemannian flows for simultaneously learning a dictionary of manifold‐valued prototypes and assigning these prototypes to the image data in a spatially coherent way. In particular, we detail a numerical update scheme for the evolution of prototypes on the Riemannian manifold of symmetric positive definite matrices. The scheme is applied to covariance descriptors are extracted from image data in order to demonstrate our approach. [ABSTRACT FROM AUTHOR]