Computational Information Geometry Wonderland

Extending the usual Bregman divergence:

\begin{align} B_F(p:q) &= & F(p) - F(q) - (p-q)^T \nabla F(q) \\ B_F(p:q) &= & F(p) - F(q) - \lim_{t\to 0^+} \frac{F(q+t(p-q)) - F(q)}{t}, \end{align} \begin{align} B_F(p:q) &= & \lim_{t\to 0^+} \frac{1}{t} ((1-t)F(p) - (1-t)F(q) - F(q+t(p-q)) + F(q) ), \\ B_F(p:q) &= & \lim_{t\to 0^+} \frac{1}{t} ((1-t)F(p) +t F(q) - F(q+t(p-q)) ), \end{align}

That is, we get a limit case of a skew Jensen divergence (also known as a Burbea-Rao divergence). See here.
The limit definition can be extended for $F$ an operator-valued smooth functional from a Banach convex space $C$ to a Hilbert space $\mathcal{H}$: $F: C \rightarrow B(\mathcal{H})$. Petz studied those Bregman operator divergences for density matrices. See Petz's paper.

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..

Olivier attended the VISAPP conference where he presented results on

Reranking with Contextual dissimilarity measures from representational Bregman k-means

Here is the abstract followed by a short report of the conference.

We present a novel reranking framework for Content Based Image Retrieval (CBIR) systems based on con-textual dissimilarity measures. Our work revisit and extend the method of Perronnin et al. (Perronnin et al., 2009) which introduces a way to build contexts used in turn to design contextual dissimilarity measures for reranking. Instead of using truncated rank lists from a CBIR engine as contexts, we rather use a clustering algorithm to group similar images from the rank list. We introduce the representational Bregman divergences and further generalize the Bregman k-means clustering by considering an embedding representation. These representation functions allows one to interpret ?-divergences/projections as Bregman divergences/projections on ?-representations. Finally, we validate our approach by presenting some experimental results on ranking performances on the INRIA Holidays database.

VISAPP 2010 -- International Conference on Computer Vision Theory and Applications

VISAPP is part of VISIGRAPP - The International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications. The purpose of this joint conference is to bring together researchers and practitioners on the areas of computer vision, imaging, computer graphics and information visualization, interested in both theoretical advances and applications in these fields. Computer Vision, Imaging, Computer Graphics and Information Visualization are well known areas which are becoming more and more interrelated with important interdisciplinary work, often as a result of an iterative combined process of image analysis and synthesis with models created in one of the fields being used to improve models created in another.

The VISIGRAPP component conferences are specialized in the following topics: GRAPP is structured along four main tracks, covering different aspects related to Computer Graphics, from Modelling to Rendering, including Animation and Interactive Environments, IMAGAPP covers theory, applications and technologies related to image display, colour coding, medical imaging, remote sensing, business document processing, digital fabrication, printing and electronic devices, VISAPP has also four main tracks, namely: Image Formation and Processing, Image Analysis, Image Understanding and Motion, Tracking and Stereo Vision and IVAPP structured along several topics related to Information Visualization.

The 2010 edition of VISIGRAPP was hold in Angers (France) from May 17th to May 21th. There were 4 invited speakers: Pascal Fua, from the École Polytechnique Fédérale de Lausanne (Switzerland), spoke about different ways of modeling deformable surfaces from monocular video sequences; Ali Mohammad-Djafari, from CNRS and Supéléc (France) spoke about methods for solving inverse problems, mainly regularization and bayesian estimation approaches, with applications in imaging and computer vision. The talk by Gabriela Csurka, from Xerox Research (France), was about Fisher kernel representation, describing Bag-Of-Features representation, Fisher vector and some applications. The last keynote speaker, Brian Barsky from University of California Berkeley, described recent research for modeling the human vision process, mainly for simulating eye diseases and consequences of surgery cures.

There were a lot of parallel sessions (2 or 3 only for VISAPP) which led to difficult choices between interesting talks. I will just a say a few words about some talks from the session I attended: Nuria Ortigosa presented the paper "Disparity maps for free path detection" describing an algorithm to detect obstacles and free path using stereo images. Sang Min presented the paper "Object retrieval based on user-drawn sketches", describing a similarity measure between sketches based on tensorial fields. Duan-Yu Chen, presenting the paper "Real-time gender recognition for uncontrolled environment of real-life images" spoke about a way to combine different approaches in order to get a robust algorithm. Laura Papaelo presented TOPMESH, a powerful library to build models of non-manifolds objects. Codruta Orniana-Ancuti, presenting "Robust grayscale conversion for vision-substitution systems", described a method to convert color images to grayscale images suitable for an auditory-vision system. Roland Moerzinger presented the paper "Improving person detection in videos by automatic scene adaptation" which introduces a way to improve person detection quality in the case of a static camera and a single planar ground. Zhaolin Su, for the paper "Real-time enhancement of image and video saliency using semantic depth of field", presented a way to change the depth of field of an image using saliency information. The talk of Svenja Kahn, "Time-of-flight based scene reconstruction with a mesh processing tool for model based camera tracking", described a way to build 3D models using a time-of-flight camera without the need of a prior knowledge of the model, for application in augmented reality.

Even if the goal to allow meetings between people from different fields is very interesting, it was really difficult to attend sessions from other fields without missing interesting talks in one's own field.

In my paper at ISVD 2009 on

The dual Voronoi diagrams with respect to representational Bregman divergences

slides

I show that by using a representational function, we can obtain alpha-divergences as a representational Bregman divergences. Therefore, it is easy to extend algorithms tailored to Bregman divergences to alpha divergences.

Here is a code snippet in Java: RepresentationalAlphaBregman.java

Running it, you get something like

Shows that alpha divergences can be obtained from representational Bregman divergences
alpha-div=0.9008838766115398    equals Bregman rep. div=0.9008838766115399
alpha-div=0.14730849849416264   equals Bregman rep. div=0.14730849849416267
alpha-div=0.05455969651963932   equals Bregman rep. div=0.054559696519639225
alpha-div=1.2439567444853374    equals Bregman rep. div=1.2439567444853372
alpha-div=0.15345391125768915   equals Bregman rep. div=0.15345391125768917
alpha-div=0.12118392973570616   equals Bregman rep. div=0.12118392973570632
alpha-div=1.038494366079179 equals Bregman rep. div=1.0384943660791794
alpha-div=0.08541142546071197   equals Bregman rep. div=0.08541142546071195
alpha-div=0.06842729068201092   equals Bregman rep. div=0.06842729068201084
alpha-div=0.6941500904965174    equals Bregman rep. div=0.6941500904965173

In the ISVD 2009 paper, we give closed-form solutions for centroids of representational Bregman divergences, including alpha-means et beta-means.

Frank.

Well most of us are familiar with Bregman divergences allows one to extend many familiar algorithms such as the celebrated k-means clustering algorithm. Bregman divergences are known to be the canonical divergences of dually flat spaces. Euclidean geometry is simply self-dually flat (induced by the Legendre self-dual paraboloid function).

However if we consider separable divergence defined by means of a monotonous function called the representation funcrton acting on coordinate systems and a convex function, then we can define generalized canonical divergences as explained in Jun Zhang's seminal paper:
Zhang, J. 2004. Divergence function, duality, and convex analysis. Neural Comput. 16, 1 (Jan. 2004), 159-195. DOI= http://dx.doi.org/10.1162/08997660460734047

<

p> Now Eguchi and Copas' beta divergences (KL for beta=0) also induce a dually flat structure both on the manifold of positive arrays (and also the submanifold of probability vectors).
S. Eguchi and J. Copas (2002): A class of logistic-type discriminant functions, Biometrika, 89, 1-22. (

So let us keep in mind that dually flat spaces is a notion that encompasses Bregman divergences... A philosophical egg and chicken question of the link between geometry vs distances.

More than a year ago, I printed 3D Bregman balls using a lithography process. I took may hours to print these shapes...

Generalized Kullback-Leibler (positive measures):

Itakura-Saito (Burg entropy):

Logistic loss:

To create the STL files, you need to discretize the surface of theses balls by walking on their geodesics passing through the centers. A bisection search does this to stop a more or less the radius.

Bregman balls in 3D

Recently, I came across the following paper that is nicely written and truly enjoyable reading:

Matrix Exponentiated Gradient Updates for On-line Learning and Bregman Projection
J. Mach. Learn. Res., Vol. 6 (2005), pp. 995-1018.

http://www.citeulike.org/user/ciga/article/1640081

The paper makes use of Bregman divergences for matrices (von Neumann and LogDet divergences), recall their basic properties, and show a general updating rule in machine learning, generalizing the analysis of AdaBoost and online learning.

I highly recommend this paper, specially Sec. 5 that displays experimental results of the method.