In the field of optimal transport, two prominent subfields face each other: (i) unregularized optimal transport, ``a-la-Kantorovich'', which leads to extremely sparse plans but with algorithms that scale poorly, and (ii) entropic-regularized optimal transport, ``a-la-Sinkhorn-Cuturi'', which gets near-linear approximation algorithms but leads to maximally un-sparse plans. In this paper, we show that an extension of the latter to tempered exponential measures, a generalization of exponential families with indirect measure normalization, gets to a very convenient middle ground, with both very fast approximation algorithms and sparsity, which is under control up to sparsity patterns. In addition, our formulation fits naturally in the unbalanced optimal transport problem setting.

In supervised learning, understanding an input’s proximity to the training data can help a model decide whether it has sufficient evidence for reaching a reliable prediction. While powerful probabilistic models such as Gaussian Processes naturally have this property, deep neural networks often lack it. In this paper, we introduce Distance Aware Bottleneck (DAB), i.e., a new method for enriching deep neural networks with this property. Building on prior information bottleneck approaches, our method learns a codebook that stores a compressed representation of all inputs seen during training. The distance of a new example from this codebook can serve as an uncertainty estimate for the example. The resulting model is simple to train and provides deterministic uncertainty estimates by a single forward pass. Finally, our method achieves better out-of-distribution (OOD) detection and misclassification prediction than prior methods, including expensive ensemble methods, deep kernel Gaussian Processes, and approaches based on the standard information bottleneck.

Models of hyperbolic geometry have been successfully used in ML for two main tasks: embedding *models* in unsupervised learning (*e.g.* hierarchies) and embedding *data*. To our knowledge, there are no approaches that provide embeddings for supervised models; even when hyperbolic geometry provides convenient properties for expressing popular hypothesis classes, such as decision trees (and ensembles). In this paper, we propose a full-fledged solution to the problem in three independent contributions. The first linking the theory of losses for class probability estimation to hyperbolic embeddings in Poincar\'e disk model. The second resolving an issue for a clean, unambiguous embedding of (ensembles of) decision trees in this model. The third showing how to smoothly tweak the Poincar\'e hyperbolic distance to improve its encoding and visualization properties near the border of the disk, a crucial region for our application, while keeping hyperbolicity. This last step has substantial independent interest as it is grounded in a generalization of Leibniz-Newton's fundamental Theorem of calculus.

Riemannian submanifold optimization with momentum is computationally challenging because, to ensure that the iterates remain on the submanifold, we often need to solve difficult differential equations. Here, we simplify such difficulties for a class of structured symmetric positive-definite matrices with the affine-invariant metric. We do so by proposing a generalized version of the Riemannian normal coordinates that dynamically orthonormalizes the metric and locally converts the problem into an unconstrained problem in the Euclidean space. We use our approach to simplify existing approaches for structured covariances and develop matrix-inverse-free $2^\text{nd}$-order optimizers for deep learning in low precision settings.

We prove that all$f$-divergences between univariate Cauchy distributions are symmetric. Furthermore, those$f$-divergences can be calculated as strictly increasing scalar functions of the chi-square divergence. We report a criterion which allows one to expand$f$-divergences as converging series of power chi divergences, and exemplifies the technique for some$f$-divergences between Cauchy distributions. In contrast with the univariate case, we show that the$f$-divergences between multivariate Cauchy densities are in general asymmetric although symmetric when the Cauchy scale matrices coincide. Then we prove that the square roots of the Kullback-Leibler and Bhattacharyya divergences between univariate Cauchy distributions yield complete metric spaces. Finally, we show that the square root of the Kullback-Leibler divergence between univariate Cauchy distributions can be isometrically embedded into a Hilbert space.

Natural-gradient descent (NGD) on structured parameter spaces (e.g., low-rank covariances) is computationally challenging due to difficult Fisher-matrix computations. We address this issue by using \emph{local-parameter coordinates} to obtain a flexible and efficient NGD method that works well for a wide-variety of structured parameterizations. We show four applications where our method (1) generalizes the exponential natural evolutionary strategy, (2) recovers existing Newton-like algorithms, (3) yields new structured second-order algorithms, and (4) gives new algorithms to learn covariances of Gaussian and Wishart-based distributions. We show results on a range of problems from deep learning, variational inference, and evolution strategies. Our work opens a new direction for scalable structured geometric methods.

Many common machine learning methods involve the geometric annealing path, a sequence of intermediate densities between two distributions of interest constructed using the geometric average. While alternatives such as the moment-averaging path have demonstrated performance gains in some settings, their practical applicability remains limited by exponential family endpoint assumptions and a lack of closed form energy function. In this work, we introduce $q$-paths, a family of paths which is derived from a generalized notion of the mean, includes the geometric and arithmetic mixtures as special cases, and admits a simple closed form involving the deformed logarithm function from nonextensive thermodynamics. Following previous analysis of the geometric path, we interpret our $q$-paths as corresponding to a $q$-exponential family of distributions, and provide a variational representation of intermediate densities as minimizing a mixture of $\alpha$-divergences to the endpoints. We show that small deviations away from the geometric path yield empirical gains for Bayesian inference using Sequential Monte Carlo and generative model evaluation using Annealed Importance Sampling.

We propose a new generic type of artificial neurons called q -neurons. A q -neuron is a stochastic neuron with its activation function relying on Jackson's discrete q -derivative for a stochastic parameter q . We show how to generalize neural network architectures with q -neurons and demonstrate the scalability and ease of implementation of q -neurons into legacy deep learning frameworks. We report experimental results that consistently improve performance over state-of-the-art standard activation functions, both on training and test loss functions.

Recurrent neural networks (RNNs) are now widely used on sequence generation tasks due to their ability to learn long-range dependencies and to generate sequences of arbitrary length. However, their left-to-right generation procedure only allows a limited control from a potential user which makes them unsuitable for interactive and creative usages such as interactive music generation. This article introduces a novel architecture called anticipation-RNN which possesses the assets of the RNN-based generative models while allowing to enforce user-defined unary constraints. We demonstrate its efficiency on the task of generating melodies satisfying unary constraints in the style of the soprano parts of the J.S. Bach chorale harmonizations . Sampling using the anticipation-RNN is of the same order of complexity than sampling from the traditional RNN model. This fast and interactive generation of musical sequences opens ways to devise real-time systems that could be used for creative purposes.

We introduce a novel family of distances, called the chord gap divergences, that generalizes the Jensen/Burbea-Rao distances and study its properties. It follows a generalization of the statistical Bhattacharyya distance that is frequently met in applications. We then report an iterative concave-convex procedure for computing centroids, and analyze the performance of the k-means++ clustering with respect to that new dissimi- larity measure by introducing the Taylor-Lagrange remainder form of skew Jensen divergences.

We consider the space of w-mixtures that are finite statistical mixtures sharing the same prescribed component distributions, like Gaussian mixture models sharing the same components. The information geometry induced by the Kullback-Leibler (KL) divergence yields a dually flat space where the KL divergence between two w-mixtures amounts to a Bregman divergence for the negative Shannon entropy generator, called the Shannon information. Furthermore, we prove that the skew Jensen-Shannon statistical divergence between w-mixtures amount to skew Jensen divergences on their parameters and state several divergence inequalities between w-mixtures and their closures.

Optimal transport is a powerful framework for computing distances between probability distributions. We unify the two main approaches to optimal transport, namely Monge-Kantorovitch and Sinkhorn-Cuturi, into what we define as Tsallis regularized optimal transport (TROT). TROT interpolates a rich family of distortions from Wasserstein to Kullback-Leibler, encompassing as well Pearson, Neyman and Hellinger divergences, to name a few. We show that metric properties known for Sinkhorn-Cuturi generalize to TROT, and provide efficient algorithms for finding the optimal transportation plan with formal convergence proofs. We also present the first application of optimal transport to the problem of ecological inference, that is, the reconstruction of joint distributions from their marginals, a problem of large interest in the social sciences. TROT provides a convenient framework for ecological inference by allowing to compute the joint distribution -— that is, the optimal transportation plan itself — when side information is available, which is e.g. typically what census represents in political science. Experiments on data from the 2012 US presidential elections display the potential of TROT in delivering a faithful reconstruction of the joint distribution of ethnic groups and voter preferences.

Hilbert geometry is a metric geometry that extends the hyperbolic Cayley-Klein geometry. In this video, we explain the shape of balls and their properties in a convex polygonal Hilbert geometry. First, we study the combinatorial properties of Hilbert balls, showing that the shapes of Hilbert polygonal balls depend both on the center location and on the complexity of the Hilbert domain but not on their radii. We give an explicit description of the Hilbert ball for any given center and radius. We then study the intersection of two Hilbert balls. In particular, we consider the cases of empty intersection and internal/external tangencies.

Assume that a N-dimensional noisy measurement vector is available via a N × R linear random sensing operation of a R-dimensional Gaussian signal of interest, denoted by s. The problem statement being addressed here is the study of the minimal Bayes' error probability for the detection of s where N → ∞ with N/R → β ∈ (1, ∞). When the exact derivation of this probability is intractable, statistical similarity metrics, nourishing their roots in the information geometry theory, are useful to characterize the exponential rate of the error probability. More precisely, the Chernoff information is asymptotically given by the minimum over s ∈ (0, 1) of the s-divergence. In many applications, it is hard to evaluate the s-divergence. Worse, due to the asymmetry of the s-divergence for the considered detection problem, the Bhattacharyya divergence (s = 1/2), cannot circumvent this problem. As a consequence, the derivation of the optimal value of s requires a costly numerical optimization strategy. In this work, we propose two contributions. The first one is to provide a closed-form expression of the asymptotic normalized s-divergence. The second contribution is to provide an analytic expression for the optimal value of s.

We derive lower- and upper-bounds of α-divergence between univariate mixture models with components in the exponential family. Three pairs of bounds are presented in order with increasing quality and increasing computational cost. They are verified empirically through simulated Gaussian mixture models. The presented methodology generalizes to other divergence families relying on Hellinger-type integrals.

Fisher information and natural gradient provided deep insights and powerful tools to artificial neural networks. However related analysis becomes more and more difficult as the learner’s structure turns large and complex. This paper makes a preliminary step towards a new direction. We extract a local component from a large neural system, and define its relative Fisher information metric that describes accurately this small component, and is invariant to the other parts of the system. This concept is important because the geometry structure is much simplified and it can be easily applied to guide the learning of neural networks. We provide an analysis on a list of commonly used components, and demonstrate how to use this concept to further improve optimization.

This paper introduces DeepBach, a graphical model aimed at modeling polyphonic music and specifically hymn-like pieces. We claim that, after being trained on the chorale harmonizations by Johann Sebastian Bach, our model is capable of generating highly convincing chorales in the style of Bach. DeepBach’s strength comes from the use of pseudo-Gibbs sampling coupled with an adapted representation of musical data. This is in contrast with many automatic music composition approaches which tend to compose music sequentially. Our model is also steerable in the sense that a user can constrain the generation by imposing positional constraints such as notes, rhythms or cadences in the generated score. We also provide a plugin on top of the MuseScore music editor making the interaction with DeepBach easy to use.

We present a series of closed-form upper bounds of the differential entropy of univariate continuous distributions based on the maximum entropy principle. We apply those bounds to Gaussian mixture models, and study their tightness properties.

Comparative convexity is a generalization of ordinary convexity based on abstract means instead of arithmetic means. We introduce the generalized skew Jensen divergences and their corresponding Bregman divergences with respect to comparative convexity. To illustrate those novel families of divergences, we consider the convexity induced by quasi-arithmetic means, and report explicit formula for the corresponding Bregman divergences. In particular, we show that those new Bregman divergences are equivalent to conformal ordinary Bregman divergences on monotone embeddings, and further state related results.

This paper presents a new methodology for clustering multivariate time series leveraging optimal transport between copulas. Copulas are used to encode both (i) intra-dependence of a multivariate time series, and (ii) inter-dependence between two time series. Then, optimal copula transport allows us to define two distances between multivariate time series: (i) one for measuring intra-dependence dissimilarity, (ii) another one for measuring inter-dependence dissimilarity based on a new multivariate dependence coefficient which is robust to noise, deterministic, and which can target specified dependencies.

The Kullback-Leibler divergence is a widespread dissimilarity measure between probability density functions, based on the Shannon entropy. Unfortunately, there is no analytic formula available to compute this divergence between mixture models, imposing the use of costly approximation algorithms. In order to reduce the computational burden when a lot of divergence evaluations are needed, we introduce a sub-class of the mixture models where the component parameters are shared between a set of mixtures and the only degree-of-freedom is the vector of weights of each mixture. This sharing allows to design extremely fast versions of existing dissimilarity measures between mixtures. We demonstrate the effectiveness of our approach by evaluating the quality of the ordering produced by our method on a real dataset.

We study the classification with respect to the class of curved Mahalanobis metrics that extend the celebrated flat Mahalanobis distances to constant curvature spaces. We prove that these curved Mahalanobis k-NN classifiers define piecewise linear decision boundaries, and report the performance of learning those metrics within the framework of the Large Margin Nearest Neighbor (LMNN). Finally, we show experimentally that a mixture of curved Mahalanobis metrics define a composite metric distance that improves the classification performance.

Video co-segmentation typically refers to the task to jointly segment common objects existing in a given group of videos. In practice, high-dimensional data such as videos are often conceptually thought of being drawn from a union of subspaces corresponding to multiple categories. Therefore, segmenting data into respective subspaces, known as subspace clustering, has widespread applications in computer vision, including co-segmentation. State-of-the-art methods via subspace clustering seek to solve the problem in two steps: learning an affinity matrix, followed by applying spectral clustering to the affinity matrix. However, it is insufficient to obtain an optimal solution since it does not take into account the interdependence of the affinity matrix and the segmentation. In this paper, we present a new unified video co-segmentation framework inspired by Structured Sparse Subspace Clustering (S3C), which yields more consistent segmentation results. In order to improve the detectability of motion features with missing trajectories, we add an extra signature to motion trajectories. Moreover, we reformulate the S3C algorithm by adding the affine subspace constraint in order to make it more suitable to segment rigid motions lying in affine subspaces of dimension at most 3. Experiments on MOViCS dataset demonstrate the effectiveness of our approaches and robustness with heavy noise.

k-means++ seeding has become a de facto standard for hard clustering algorithms. In this paper, our first contribution is a two-way generalisation of this seeding, k-variates++, that includes the sampling of general densities rather than just a discrete set of Dirac densities anchored at the point locations, *and* a generalisation of the well known Arthur-Vassilvitskii (AV) approximation guarantee, in the form of a *bias+variance* approximation bound of the *global* optimum. This approximation exhibits a reduced dependency on the "noise" component with respect to the optimal potential — actually approaching the statistical lower bound. We show that k-variates++ *reduces* to efficient (biased seeding) clustering algorithms tailored to specific frameworks; these include distributed, streaming and on-line clustering, with *direct* approximation results for these algorithms. Finally, we present a novel application of k-variates++ to differential privacy. For either the specific frameworks considered here, or for the differential privacy setting, there is little to no prior results on the direct application of k-means++ and its approximation bounds — state of the art contenders appear to be significantly more complex and / or display less favorable (approximation) properties. We stress that our algorithms can still be run in cases where there is *no* closed form solution for the population minimizer. We demonstrate the applicability of our analysis via experimental evaluation on several domains and settings, displaying competitive performances vs state of the art.

We prove that the empirical risk of most well-known loss functions factors into a linear term aggregating all labels with a term that is label free, and can further be expressed by sums of the same loss. This holds true even for non-smooth, non-convex losses and in any RKHS. The first term is a (kernel) mean operator — the focal quantity of this work — which we characterize as the sufficient statistic for the labels. The result tightens known generalization bounds and sheds new light on their interpretation. Factorization has a direct application on weakly supervised learning. In particular, we demonstrate that algorithms like SGD and proximal methods can be adapted with minimal effort to handle weak supervision, once the mean operator has been estimated. We apply this idea to learning with asymmetric noisy labels, connecting and extending prior work. Furthermore, we show that most losses enjoy a data-dependent (by the mean operator) form of noise robustness, in contrast with known negative results.

The Kullback-Leibler (KL) divergence between two mixture models is a fundamental primitive in many signal processing tasks. Since the KL divergence of mixtures does not admit a closed-form formula, it is in practice either estimated using costly Monte-Carlo stochastic integration or approximated. We present a fast and generic method that builds algorithmically closed-form lower and upper bounds on the entropy, the cross-entropy and the KL divergence of univariate mixtures. We illustrate the versatile method by reporting on our experiments for approximating the KL divergence between Gaussian mixture models.

Total Bregman divergences are a recent tweak of ordinary Bregman divergences originally motivated by applications that required invariance by rotations. They have displayed superior results compared with ordinary Bregman divergences on several clustering, computer vision, medical imaging, and machine learning tasks. These preliminary results raise two important problems. First, report a complete characterization of the left and right population minimizers for this class of total Bregman divergences. Second, characterize a principled superset of total and ordinary Bregman divergences with good clustering properties, from which one could tailor the choice of a divergence to a particular application. In this paper, we provide and study one such superset with interesting geometric features, that we call conformal divergences, and focus on their left and right population minimizers. Our results are obtained in a recently coined (u, v) -geometric structure that is a generalization of the dually flat affine connections in information geometry. We characterize both analytically and geometrically the population minimizers. We prove that conformal divergences (resp. total Bregman divergences) are essentially exhaustive for their left (resp. right) population minimizers. We further report new results and extend previous results on the robustness to outliers of the left and right population minimizers, and discuss the role of the (u, v) -geometric structure in clustering. Additional results are also given.

We present a novel class of divergences induced by a smooth convex function called total Jensen divergences that are invariant by construction to rotations, a feature inducing a conformal factor on ordinary Jensen divergences. We analyze the relationships between this novel class of total Jensen divergences and the total Bregman divergences. We then define total Jensen centroids, analyze their robustness, and prove that the k-means++ initialization that bypasses explicit centroid computations is good enough in practice to guarantee probabilistically a constant approximation factor to the optimal k-means clustering.

We present in this paper an empirical framework motivated by the practitioner point of view on stability. The goal is to both assess clustering validity and yield market insights by providing through the data perturbations we propose a multi-view of the assets' clustering behaviour. The perturbation framework is illustrated on an extensive credit default swap time series database available online at www.datagrapple.com.

Tailoring nearest neighbors algorithms to boosting is an important problem. Recent papers study an approach, UNN, which provably minimizes particular convex surrogates under weak assumptions. However, numerical issues make it necessary to experimentally tweak parts of the UNN algorithm, at the possible expense of the algorithm's convergence and performance. In this paper, we propose a lightweight Newton-Raphson alternative optimizing proper scoring rules from a very broad set, and establish formal convergence rates under the boosting framework that compete with those known for UNN. To the best of our knowledge, no such boosting-compliant convergence rates were previously known in the popular Gentle Adaboost's lineage. We provide experiments on a dozen domains, including Caltech and SUN computer vision databases, comparing our approach to major families including support vector machines, (Ada)boosting and stochastic gradient descent. They support three major conclusions: (i) GNNB significantly outperforms UNN, in terms of convergence rate and quality of the outputs, (ii) GNNB performs on par with or better than computationally intensive large margin approaches, (iii) on large domains that rule out those latter approaches for computational reasons, GNNB provides a simple and competitive contender to stochastic gradient descent. Experiments include a divide-and-conquer improvement of GNNB exploiting the link with proper scoring rules optimization.

We present an interactive software, HVD, that represents internally the k-order hyperbolic Voronoi diagram of a finite set of sites as an equivalent clipped power diagram. HVD allows users to interactively browse the hyperbolic Voronoi diagrams and renders simultaneously the diagram in the five standard models of hyperbolic geometry: Namely, the Poincaré disk, the Poincaré upper plane, the Klein disk, the Beltrami hemisphere and the Weierstrass hyperboloid.

We report closed-form formula for calculating the Chi square and higher-order Chi distances between statistical distributions belonging to the same exponential family with affine natural space, and instantiate those formula for the Poisson and isotropic Gaussian families. We then describe an analytic formula for the f-divergences based on Taylor expansions and relying on an extended class of Chi-type distances.

We present a generic dynamic programming method to compute the optimal clustering of n scalar elements into k pairwise disjoint intervals. This case includes 1D Euclidean k-means, k-medoids, k-medians, k-centers, etc. We extend the method to incorporate cluster size constraints and show how to choose the appropriate k by model selection. Finally, we illustrate and refine the method on two case studies: Bregman clustering and statistical mixture learning maximizing the complete likelihood.

The Chernoff information was originally introduced for bounding the probability of error of the Bayesian decision rule in binary hypothesis testing. Nowadays, it is often used as a notion of symmetric distance in statistical signal processing or as a way to define a middle distribution in information fusion. Computing the Chernoff information requires to solve an optimization problem that is numerically approximated in practice. We consider the Chernoff distance for distributions belonging to the same exponential family including the Gaussian and multinomial families. By considering the geometry of the underlying statistical manifold, we define exactly the solution of the optimization problem as the unique intersection of a geodesic with a dual hyperplane. Furthermore, we prove analytically that the Chernoff distance amounts to calculate an equivalent but simpler Bregman divergence defined on the distribution parameters. It follows a closed-form formula for the singly-parametric distributions, or an efficient geodesic bisection search for multiparametric distributions. Finally, based on this information-geometric characterization, we propose three novel information-theoretic symmetric distances and middle distributions, from which two of them admit always closed-form expressions.

Due to the success of the bag-of-word modeling paradigm, clustering histograms has become an important ingredient of modern information processing. Clustering histograms can be performed using the celebratedk-means centroid-based algorithm. From the viewpoint of applications, it is usually required to deal with symmetric distances. In this letter, we consider the Jeffreys divergence that symmetrizes the Kullback-Leibler divergence, and investigate the computation of Jeffreys centroids. We first prove that the Jeffreys centroid can be expressed analytically using the LambertWfunction for positive histograms. We then show how to obtain a fast guaranteed approximation when dealing with frequency histograms. Finally, we conclude with some remarks on thek-means histogram clustering.

We present a fast and generic algorithm, k-MLE, for learning statistical mixture models using maximum likelihood estimators. We prove theoretically that k-MLE is dually equivalent to a Bregman k-means for the case of mixtures of exponential families (e.g., Gaussian mixture models). k-MLE is used to initialize appropriately the expectation-maximization algorithm. We also show experimentally that k-MLE outperforms the EM technique with standard initialization by considering modeling color images using high-dimensional Gaussian mixture models.

Gaussian mixture models are a widespread tool for modeling various and complex probability density functions. They can be estimated using Expectation- Maximization or Kernel Density Estimation. Expectation- Maximization leads to compact models but may be expensive to compute whereas Kernel Density Estimation yields to large models which are cheap to build. In this paper we present new methods to get high-quality models that are both compact and fast to compute. This is accomplished with clustering methods and centroids computation. The quality of the resulting mixtures is evaluated in terms of log-likelihood and Kullback-Leibler divergence using examples from a bioinformatics application.

In this paper, we consider the family of total Bregman divergences (tBDs) as an efficient and robust "distance" measure to quantify the dissimilarity between shapes. We use the tBD-based ℓ₁-norm center as the representative of a set of shapes, and call it the t-center. First, we briefly present and analyze the properties of the tBDs and t-centers following our previous work in. Then, we prove that for any tBD, there exists a distribution which belongs to the lifted exponential family (lEF) of statistical distributions. Further, we show that finding the maximum a posteriori (MAP) estimate of the parameters of the lifted exponential family distribution is equivalent to minimizing the tBD to find the t-centers. This leads to a new clustering technique, namely, the total Bregman soft clustering algorithm. We evaluate the tBD, t-center, and the soft clustering algorithm on shape retrieval applications. Our shape retrieval framework is composed of three steps: 1) extraction of the shape boundary points, 2) affine alignment of the shapes and use of a Gaussian mixture model (GMM) to represent the aligned boundaries, and 3) comparison of the GMMs using tBD to find the best matches given a query shape. To further speed up the shape retrieval algorithm, we perform hierarchical clustering of the shapes using our total Bregman soft clustering algorithm. This enables us to compare the query with a small subset of shapes which are chosen to be the cluster t-centers. We evaluate our method on various public domain 2D and 3D databases, and demonstrate comparable or better results than state-of-the-art retrieval techniques.

The scope of the well-known k-means algorithm has been broadly extended with some recent results: first, the k means++ initialization method gives some approximation guarantees; second, the Bregman k-means algorithm generalizes the classical algorithm to the large family of Bregman divergences. The Bregman seeding framework combines approximation guarantees with Bregman divergences. We present here an extension of the k-means algorithm using the family of α-divergences. With the framework for representational Bregman divergences, we show that an α-divergence based k-means algorithm can be designed. We present preliminary experiments for clustering and image segmentation applications. Since α-divergences are the natural divergences for constant curvature spaces, these experiments are expected to give information on the structure of the data.

We study the centroid with respect to the class of information-theoretic Burbea-Rao divergences that generalize the celebrated Jensen-Shannon divergence by measuring the non-negative Jensen difference induced by a strictly convex and differentiable function. Although those Burbea-Rao divergences are symmetric by construction, they are not metric since they fail to satisfy the triangle inequality. We first explain how a particular symmetrization of Bregman divergences called Jensen-Bregman distances yields exactly those Burbea-Rao divergences. We then proceed by defining skew Burbea-Rao divergences, and show that skew Burbea-Rao divergences amount in limit cases to compute Bregman divergences. We then prove that Burbea-Rao centroids can be arbitrarily finely approximated by a generic iterative concave-convex optimization algorithm with guaranteed convergence property. In the second part of the paper, we consider the Bhattacharyya distance that is commonly used to measure overlapping degree of probability distributions. We show that Bhattacharyya distances on members of the same statistical exponential family amount to calculate a Burbea-Rao divergence in disguise. Thus we get an efficient algorithm for computing the Bhattacharyya centroid of a set of parametric distributions belonging to the same exponential families, improving over former specialized methods found in the literature that were limited to univariate or “diagonal” multivariate Gaussians. To illustrate the performance of our Bhattacharyya/Burbea-Rao centroid algorithm, we present experimental performance results fork-means and hierarchical clustering methods of Gaussian mixture models.

Divergence measures provide a means to measure the pairwise dissimilarity between "objects," e.g., vectors and probability density functions (pdfs). Kullback-Leibler (KL) divergence and the square loss (SL) function are two examples of commonly used dissimilarity measures which along with others belong to the family of Bregman divergences (BD). In this paper, we present a novel divergence dubbed the Total Bregman divergence (TBD), which is intrinsically robust to outliers, a very desirable property in many applications. Further, we derive the TBD center, called the t-center (using the l(1)-norm), for a population of positive definite matrices in closed form and show that it is invariant to transformation from the special linear group. This t-center, which is also robust to outliers, is then used in tensor interpolation as well as in an active contour based piecewise constant segmentation of a diffusion tensor magnetic resonance image (DT-MRI). Additionally, we derive the piecewise smooth active contour model for segmentation of DT-MRI using the TBD and present several comparative results on real data.

Shape database search is ubiquitous in the world of bio-metric systems, CAD systems etc. Shape data in these domains is experiencing an explosive growth and usually requires search of whole shape databases to retrieve the best matches with accuracy and efficiency for a variety of tasks. In this paper, we present a novel divergence measure between any two given points in Rnor two distribution functions. This divergence measures the orthogonal distance between the tangent to the convex function (used in the definition of the divergence) at one of its input arguments and its second argument. This is in contrast to the ordinate distance taken in the usual definition of the Bregman class of divergences. We use this orthogonal distance to redefine the Bregman class of divergences and develop a new theory for estimating the center of a set of vectors as well as probability distribution functions. The new class of divergences are dubbed the total Bregman divergence (TBD). We present the l\-norm based TBD center that is dubbed the t-center which is then used as a cluster center of a class of shapes The t-center is weighted mean and this weight is small for noise and outliers. We present a shape retrieval scheme using TBD and the t-center for representing the classes of shapes from the MPEG-7 database and compare the results with other state-of-the-art methods in literature.

Motion estimation is known to be a non-convex optimization problem. This non-convexity comes from several ambiguities in motion estimation such as the aperture problem, or fast motion relative to the magnitude of the image gradient. In this paper, we propose a fast random search algorithm to estimate motion. Randomized algorithms are very popular in computer science and optimization for non-convex problems. However, to the best of our knowledge none has been used so far for motion estimation, due to complexity constraints. In this paper, we propose two fast algorithms to perform random search on image pixels. One produces a dense optical flow by matching patches. The other one takes advantage of a quad tree or segmentation tree structure of the image to estimate motion in regions of increasing size. Quantitative and visual results show that the motion obtained seems to be a very advantageous compromise between speed and quality of estimated motion.

Earth Mover Distance (EMD) is a popular distance to compute distances between Probability Density Functions (PDFs). It has been successfully applied in a wide selection of problems of image processing. This success comes from two reasons, a physical one, since it computes a physical cost to transport an element of mass between two images or two histograms, and a statistical one, since it is a cross-bin metric (as opposed to a bin-wise metric). In computer vision, these features are useful since small variation of illuminance can shift the histogram. However, histograms are not a sufficient statistic to discriminate images since they ignore all geometric correlations. In addition, transport also called flow of an histogram loose the information of geometric flow to warp one image on to an other. This paper proposes a new construction of EMD between images. This construction approximates the EMD between two images, by computing a pixel-wise transport at the complexity cost of computing an EMD between 1-D Histograms and preserves the geometrical and topological structure of the image. This construction simply relies on a segmentation of the image (also called superpixelization of the image). Results on matching on images shows the stability of the method even when the superpixelizations are highly inconsistent across images.

The k-nearest neighbor (kNN) search problem is widely used in domains and applications such as classification, statistics, and biology. In this paper, we propose two fast GPU-based implementations of the brute-force kNN search algorithm using the CUDA and CUBLAS APIs. We show that our CUDA and CUBLAS implementations are up to, respectively, 64X and 189X faster on synthetic data than the highly optimized ANN C++ library, and up to, respectively, 25X and 62X faster on high-dimensional SIFT matching.

Statistical modeling of images plays a crucial role in modern image processing tasks like segmentation, object detection and restoration. Although Gaussian distributions are conveniently handled mathematically, the role of many other types of distributions has been revealed and emphasized by natural image statistics. In this paper, we consider a versatile class of distributions called exponential families that encompasses many well-known distributions, such as Gaussian, Poisson, multinomial, Gamma/Beta and Dirichlet distributions, just to name a few. For those families, we derive mathematical expressions for their Shannon entropy and cross-entropy, give a geometric interpretation, and show that they admit closed-form formula up to some entropic normalizing constant depending on the carrier measure but independent of the member of the family. This allows one to design algorithms that can compare exactly entropies and cross-entropies of exponential family distributions although some of them have strictus sensus no known closed forms (eg., Poisson). We discuss about maximum entropy and touch upon the entropy of mixtures of exponential families for which we provide a relative entropy upper bound.

Bhattacharrya distance (BD) is a widely used distance in statistics to compare probability density functions (PDFs). It has shown strong statistical properties (in terms of Bayes error) and it relates to Fisher information. It has also practical advantages, since it strongly relates on measuring the overlap of the supports of the PDFs. Unfortunately, even with common parametric models on PDFs, few closed-form formulas are known. Moreover, the BD centroid estimation was limited to univariate gaussian PDFs in the literature and no convergence guarantees were provided. In this paper, we propose a closed-form formula for BD on a general class of parametric distributions named exponential families. We show that the BD is a Burbea-Rao divergence for the log normalizer of the exponential family. We propose an efficient iterative scheme to compute a BD centroid on exponential families. Finally, these results allow us to define a Bhattacharrya hierarchical clustering algorithms (BHC). It can be viewed as a generalization of k-means on BD. Results on image segmentation shows the stability of the method.

In this paper we redefine and generalize the classic k-nearest neighbors (k-NN) voting rule in a Bayesian maximum-a-posteriori (MAP) framework. Therefore, annotated examples are used for estimating pointwise class probabilities in the feature space, thus giving rise to a new instance-based classification rule. Namely, we propose to "boost" the classic k-NN rule by inducing a strong classifier from a combination of sparse training data, called "prototypes". In order to learn these prototypes, our MapBoost algorithm globally minimizes a multiclass exponential risk defined over the training data, which depends on the class probabilities estimated at sample points themselves. We tested our method for image categorization on three benchmark databases. Experimental results show that MapBoost significantly outperforms classic k-NN (up to 8%). Interestingly, due to the supervised selection of sparse prototypes and the multiclass classification framework, the accuracy improvement is obtained with a considerable computational cost reduction.

Nearest neighbor (NN) retrieval is a crucial tool of many computer vision tasks. Since the brute-force naive search is too time consuming for most applications, several tailored data structures have been proposed to improve the efficiency of NN search. Among these, vantage point tree (vp-tree) was introduced for information retrieval in metric spaces. Vptrees have recently shown very good performances for image patch retrieval with respect to the L2metric. In this paper we generalize the seminal vp-tree construction and search algorithms to the broader class of Bregman divergences. These distorsion measures are preferred in many cases, as they also handle entropic distances (e.g., Kullback-Leibler divergence) besides quadratic distances. We also extend vp-tree to deal with symmetrized Bregman divergences, which are commonplace in applications of content-based multimedia retrieval. We evaluated performances of our Bvp-tree for exact and approximate NN search on two image feature datasets. Our results show good performances of Bvp-tree, specially for symmetrized Bregman NN queries.

Bartlett et al. (2006) recently proved that a ground condition for surrogates, classification calibration, ties up their consistent minimization to that of the classification risk, and left as an important problem the algorithmic questions about their minimization. In this paper, we address this problem for a wide set which lies at the intersection of classification calibrated surrogates and those of Murata et al. (2004). This set coincides with those satisfying three common assumptions about surrogates. Equivalent expressions for the members-sometimes well known-follow for convex and concave surrogates, frequently used in the induction of linear separators and decision trees. Most notably, they share remarkable algorithmic features: for each of these two types of classifiers, we give a minimization algorithm provably converging to the minimum of any such surrogate. While seemingly different, we show that these algorithms are offshoots of the same "master" algorithm. This provides a new and broad unified account of different popular algorithms, including additive regression with the squared loss, the logistic loss, and the top-down induction performed in CART, C4.5. Moreover, we show that the induction enjoys the most popular boosting features, regardless of the surrogate. Experiments are provided on 40 readily available domains.

In this paper, we generalize the notions of centroids (and barycenters) to the broad class of information-theoretic distortion measures called Bregman divergences. Bregman divergences form a rich and versatile family of distances that unifies quadratic Euclidean distances with various well-known statistical entropic measures. Since besides the squared Euclidean distance, Bregman divergences are asymmetric, we consider the left-sided and right-sided centroids and the symmetrized centroids as minimizers of average Bregman distortions. We prove that all three centroids are unique and give closed-form solutions for the sided centroids that are generalized means. Furthermore, we design a provably fast and efficient arbitrary close approximation algorithm for the symmetrized centroid based on its exact geometric characterization. The geometric approximation algorithm requires only to walk on a geodesic linking the two left/right-sided centroids. We report on our implementation for computing entropic centers of image histogram clusters and entropic centers of multivariate normal distributions that are useful operations for processing multimedia information and retrieval. These experiments illustrate that our generic methods compare favorably with former limited ad hoc methods.

We generalize the notions of centroids and barycenters to the broad class of information-theoretic distortion measures called Bregman divergences. Because Bregman divergences are typically asymmetric, we consider both the left-sided and right-sided centroids and the symmetrized centroids, and prove that all three are unique. We give closed-form solutions for the sided centroids that are generalized means, and design a provably fast and efficient approximation algorithm for the symmetrized centroid based on its exact geometric characterization that requires solely to walk on the geodesic linking the two sided centroids.

Bartlett et al (2006) recently proved that a ground condition for convex surrogates, classification calibration, ties up the minimization of the surrogates and classification risks, and left as important open problems the algorithmic questions about the minimization of these surrogates. Our paper gives an answer for a wide subset of these surrogates that we call “balanced surrogates”, a set with popular members (logistic loss, squared loss), that contains all surrogates meeting three important requirements about classification. We propose an algorithm that fits linear separators to the minimization of any such surrogate, with guaranteed convergence bounds under a so-called “Weak Learning Assumption”, a generalization of the one that grounds celebrated boosting algorithms. Experiments on more than 50 readily available domains of 10 flavors of the algorithm display the performances of new surrogates.

In this paper, we first introduce a smooth parametric family of Bregman-Csiszar quantum entropies including the von Neumann and Burg quantum entropies. We then describe the dualistic nature of Voronoi diagrams for 1-qubit quantum states inside the 3D Bloch ball representation. We show that these diagrams can be computed as Bregman Voronoi diagrams for the corresponding Bregman generator acting on Hermitian density matrices. This implies that these dual diagrams can be derived from power diagrams of balls in the Laguerre geometry, and allows one to prove by equivalence that the von Neumann quantum Voronoi diagram on the degenerated Bloch sphere of pure quantum states coincides with the ordinary Euclidean Voronoi diagram, bypassing the fact that the quantum divergence is not defined there. We then show how to compute the Holevo channel capacity of 1-qubit quantum states, and provide a practical approximation algorithm based on Bregman core-sets. Finally, we define the quantum sided centroids that yield practical upper bounds on the Holevo capacity in linear time.

Bartlett et al (2006) recently proved that a ground condition for convex surrogates, classification calibration, ties up the minimization of the surrogates and classification risks, and left as an important problem the algorithmic questions about the minimization of these surrogates. In this paper, we propose an algorithm which provably minimizes any classification calibrated surrogate strictly convex and differentiable --- a set whose losses span the exponential, logistic and squared losses ---, with boosting-type guaranteed convergence rates under a weak learning assumption. A particular subclass of these surrogates, that we call balanced convex surrogates, has a key rationale that ties it to maximum likelihood estimation, zero-sum games and the set of losses that satisfy some of the most common requirements for losses in supervised learning. We report experiments on more than 50 readily available domains of 11 flavors of the algorithm, that shed light on new surrogates, and the potential of data dependent strategies to tune surrogates.

Voronoi diagrams are fundamental geometric structures that partition the space into elementary regions of influence defining discrete proximity graphs and dually well-shaped Delaunay triangulations [Aurenhammer & Klein, 2000]. In this video, we explain and illustrate a recent generalization of Voronoi diagrams [Nielsen et al., 2007] to a wide class of distortion measures called Bregman divergences [Banerjee et al., 2005].

We present a generalization of Bǎdoiu and Clarkson's algorithm [3] for computing a (1+ε)-approximation of the smallest enclosing ball of a point set equipped with a Bregman divergence as a distortion measure.

In this paper, we present a recommendation system for automatically recentering and cropping digital still pictures that exhibit capturing artefacts. Autoframing images not only yields better visual pictures but more importantly allows us to remove undesirable artefacts such as lens obstructions by fingers, cellphone straps, or back heads. We report on our real-time prototype system that is targeted to consumer digital still cameras

Recent papers and patents in iterative unsupervised learning have emphasized a new trend in clustering. It basically consists of penalizing solutions via weights on the instance points, somehow making clustering move toward the hardest points to cluster. The motivations come principally from an analogy with powerful supervised classification methods known as boosting algorithms. However, interest in this analogy has so far been mainly borne out from experimental studies only. This paper is, to the best of our knowledge, the first attempt at its formalization. More precisely, we handle clustering as a constrained minimization of a Bregman divergence. Weight modifications rely on the local variations of the expected complete log-likelihoods. Theoretical results show benefits resembling those of boosting algorithms and bring modified (weighted) versions of clustering algorithms such as k-means, fuzzy c-means, Expectation Maximization (EM), and k-harmonic means. Experiments are provided for all these algorithms, with a readily available code. They display the advantages that subtle data reweighting may bring to clustering.

We present a novel interactive system and its user interface for removing objects in digital pictures. Our system consists of two components: (i) (partially supervised/automatic) image segmentation, and (ii) (guided) texture synthesis.

In this paper, we explore the problem of deleting objects in still pictures. We present an interactive system based on an intuitive user-friendly interface for removing undesirable objects in digital pictures. To erase an object in an image, a user indicates which object is to be removed by simply pinpointing it with the mouse cursor. As the mouse cursor rolls over the image, the current implicit selected object's border is highlighted, providing a visual feedback. In case where the computer-segmented area does not match the users' perception of the object, users can further provide a few inside/outside object cues by clicking on a small number of object or nonobject pixels. A small number of such cues is generally enough to reach a correct matching, even for complex textured images. Afterwards, the user removes the object by clicking the left mouse button, and a hole-filling technique is initiated to generate a seamless background portion. Our image manipulation system consists of two components: (i) fully automatic or partially user-steered image segmentation based on an improved fast statistical region-growing segmentation, and (ii) texture synthesis or image inpainting of irregular shaped hole regions. Experiments on a variety of photographs display the ability of the system to handle complex scenes with highly textured objects.

It is difficult to obtain a specific region within unsegmented volume data (region of interest, ROI). The user must first segment the volume, a task which itself involves significant user intervention, and then chooses a desired target within the 3D space. This paper proposes a simple and intuitive user interface for the task: the user traces the contour of the target region using a 2D free form stroke on the screen, and the system instantly returns a plausible 3D region inside the stroke by applying a segmentation algorithm. The main contribution is that the system infers the depth information of the ROI automatically by analyzing the data, whereas existing systems require the user to provide the depth information explicitly. Our system first computes the 3D location of the user-specified 2D stroke based on the assumption that the user traced the silhouette of the ROI, that is, the curve where the gradient is perpendicular to the viewing direction. The system then places constraint points around the 3D stroke to guide the following segmentation. Foreground constraints are placed inside the stroke and background constraints are placed outside the stroke. We currently use the statistical region-merging algorithm of Nock et al. [Nock and Nielsen 2004a] to perform the segmentation. We tested our system with real-world examples to verify the effectiveness of our approach.

Recent works in unsupervised learning have emphasized the need to understand a new trend in algorithmic design, which is to influence the clustering via weights on the instance points. In this paper, we handle clustering as a constrained minimization of a Bregman divergence. Theoretical results show benefits resembling those of boosting algorithms, and bring new modified weighted versions of clustering algorithms such as k-means, expectation-maximization (EM) and k-harmonic means. Experiments display the quality of the results obtained, and corroborate the advantages that subtle data reweightings may bring to clustering.

This paper explores a statistical basis for a process often described in computer vision: image segmentation by region merging following a particular order in the choice of regions. We exhibit a particular blend of algorithmics and statistics whose segmentation error is, as we show, limited from both the qualitative and quantitative standpoints. This approach can be efficiently approximated in linear time/space, leading to a fast segmentation algorithm tailored to processing images described using most common numerical pixel attribute spaces. The conceptual simplicity of the approach makes it simple to modify and cope with hard noise corruption, handle occlusion, authorize the control of the segmentation scale, and process unconventional data such as spherical images. Experiments on gray-level and color images, obtained with a short readily available C-code, display the quality of the segmentations obtained.

This paper presents an interactive system for designing and browsing volumetric illustrations. Volumetric illustrations are 3D models with internal textures that the user can browse by cutting the models at desired locations. To assign internal textures to a surface mesh, the designer cuts the mesh and provides simple guiding information to specify the correspondence between the cross-section and a reference 2D image. The guiding information is stored with the geometry and used during the synthesis of cross-sectional textures. The key idea is to synthesize a plausible cross-sectional image using a 2D texture-synthesis technique, instead of sampling from a complete 3D RGB volumetric representation directly. This simplifies the design interface and reduces the amount of data, making it possible for non-experts to rapidly design and use volumetric illustrations. We believe that our system can enrich human communications in various domains, such as medicine, biology, and geology.

This work explores a statistical basis for a process often described in computer vision: image segmentation by region merging following a particular order in the choice of regions. We exhibit a particular blend of algorithmics and statistics whose error is, as we formally show, close to the best possible. This approach can be approximated in a very fast segmentation algorithm for processing images described using most common numerical feature spaces. Simple modifications of the algorithm allow us to cope with occlusions and/or hard noise levels. Experiments on grey-level and color images, obtained with a short C-code, display the quality of the segmentations obtained.

In this paper, we present a method for acquiring, spatially filtering and viewing annotated videos captured with a full field of view multihead camera moving along a path. We describe our tailored egomotion recovery algorithm used for calculating the trajectory path of the panoramic head. We then focus on sampling the plenoptic path efficiently according to geometric visibility events. Appropriate samplings allow us to filter and compress the panoramic images avoiding some redundancies in the image database. We present several applications and results of plenoptic paths either obtained from indoor shootings or perfectly rendered by computer graphics scripts.

A set of objects is k-pierceable if there exists a set of k points such that each object is pierced by (contains) at least one of these points.Finding the smallest integer k such that a set is k-pierceable is NP-complete.In this paper, we present efficient algorithms for findinga piercing set (i.e., a set ofkpoints asabove) for several classes of convex objects and small values of k.In some of the cases, our algorithms imply known as well as new Helly-type theorems, thus adding to previous results of Danzer and Griinbaum who studied the case of axisparallel boxes.The problems studied here are related to the collection of optimization problems in which one seeks the smallest scaling factor of a centrally symmetric convex object K, so that a set of points can be covered by k congruent homothets of K. h = h(C, P)associated with a class of objects C and a property P is