Monthly Archives: June 2010

On sunday is the 2010 Int. Symp. on Voronoi Diagrams (ISVD). We shall present: Jensen-Bregman Voronoi diagrams and centroidal tessellations

Here are the slides of the talk.
The Jensen-Bregman divergence is a distortion measure defined by the Jensen difference provided by a strictly convex function. Jensen-Bregman divergences extend the well-known Jensen-Shannon divergence by allowing to choose an arbitrary convex function generator instead of the standard Shannon entropy. This class of Jensen-Bregman divergences notably includes the squared Euclidean distance. Although Jensen-Bregman divergences are symmetric distances by construction, they are not metrics as they violate the triangle inequality. We study the geometric properties and combinatorial complexities of both the Voronoi diagrams and the centroidal Voronoi diagrams induced by such as class of information-theoretic divergences. We show that those Jensen- Bregman divergences appear naturally into two contexts: (1) when symmetrizing Bregman divergences, and (2) when computing the Bhattacharyya distances of statistical distributions. The Bhattacharyya distance measures the amount of overlap of distributions, and is popularly used to provide both lower and upper bounds in machine learning: the Bayes? misclassification error. Since the Bhattacharyya distance of popular distributions in statistics called the exponential families (including familiar Gaussian, Poisson, multinomial, Beta/Gamma families, etc.) can be computed equivalently as Jensen-Bregman divergences, the Jensen-Bregman Voronoi diagrams allow one also to study statistical Voronoi diagrams induced by an entropic function. Keywords-Jensen?s inequality, Jensen difference, Bregman divergences, Jensen-Shannon divergence, Bhattacharyya distance, Burbea-Rao divergence, Hellinger-Kakutani-Matusita divergences, f-divergence, -divergence, exponential families, information geometry.

The following work has been presented at CVPR 2010. It considers orthogonal projection onto a tangent plane instead of vertical projection when defining a distance using a convex generator.

Shape database search is ubiquitous in the world of biometric 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 Rn or 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 [4]. 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 L1-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..

Simplification and hierarchical representations of mixtures of exponential families just got out at Signal Processing
Abstract

A mixture model in statistics is a powerful framework commonly used to estimate the probability measure function of a random variable. Most algorithms handling mixture models were originally specifically designed for processing mixtures of Gaussians. However, other distributions such as Poisson, multinomial, Gamma/Beta have gained interest in signal processing in the past decades. These common distributions are unified in the framework of exponential families in statistics. In this paper, we present three generic clustering algorithms working on arbitrary mixtures of exponential families: the Bregman soft clustering, the Bregman hard clustering, and the Bregman hierarchical clustering. These algorithms allow one to estimate a mixture model from observations, to simplify such a mixture model, and to automatically learn the ?optimal? number of components in a simplified mixture model according to a resolution parameter. In addition, we present jMEF, an open source JavaTM library allowing users to create, process and manage mixtures of exponential families. In particular, jMEF includes the three aforementioned Bregman clustering algorithms.

Keywords: Mixtures models; Kullback?Leibler divergence; Bregman divergence; Exponential family; Mixtures of exponential families; Clustering algorithms