Computational Information Geometry Wonderland

To get a random Gaussian N(mu,Sigma), sample the mu uniformly from [0,1] (or N(0,1)) and sample the symmetric positive definite matrix from a Wishart distribution: Sample each entry of a matrix A from a Normal distribution N(0,1), and set SIGMA=lambda AA^T where lambda is a uniform random number that controls the size of the covariance matrice.

November 18th-20th, 2008, Paris.

Registration is now open (and free)

ETVC08

http://www.lix.polytechnique.fr/Labo/Frank.Nielsen/ETVC08/

Last February, I was strikingly introduced with the truly pioneer work of visionary artist Albert ROBIDA (http://www.robida.info/). In short, Robida painted over 60.000 drawings and illustrated well over 200 books in his artist life. Albert Robida envisionned not only many IT products well ahead of his time, but he was also already awared and convinced of ecology problems. To give a remarkable example of Robida's visionary talent, let us point out that Robida imagined and painted a deviced called the phonoscope in 1883. The phonoscope is simply the precursor of the 21st century home theater (see imghttp://www.robida.info/images/visionnaire/journal_telephonoscopique.jpg). It is related to Edison's telephonoscope , also disclosed in an invention report in 1879 (imghttp://www.flickr.com/photos/seriykotik/208841133/). Perhaps, more strikingly, Robida envisionned the e-learning application with a remote teacher giving a lecture for a student at home: imghttp://www.robida.info/images/visionnaire/cours.jpg However, for most of the people, the most striking drawing we saw was the ancestor of the Mp3 Walkman at imghttp://www.robida.info/images/visionnaire/phono-operagraphe.jpg In this illustation, you can observe a shepherd (a walk man) listening to music in mountains. In other words, the music devices we carry everyday was already imagined two centuries ago. If such a device was already imagined, was about recording music? Very recent work carried out in March 2008 by American audio historians recovered the first recorded sound by little-known
parisian Edouard-Leon Scott de Martinville on April 9, 1860: Au Clair de la Lune, a French folk song (an ex. Scott's 1857 drawing of a phonautographic recording session was discloded in his patent paperwork registered at the french intellectual property office (INPI). More details of the ingenious process that consists in printing the sound on a sheet of paper is explained at linkhttp://www.firstsounds.org/ Note that the device could not play sounds back. (Edison used a sheet of tinfoil to record in 1927 ?Mary had a little lamb", see http://history.sandiego.edu/gen/recording/mary.html)

To conclude, let us mention that Albert Robida also wrote and illustrated the book "The Electric Life" where he depicts life in the 20th century and warns mankind of the potential danger of using non-controlled technology. How timely! We're all now fully aware and have imminently to face this issue.

Frank Nielsen.

A few links:.

A short biography:.

http://en.wikipedia.org/wiki/Albert_Robida

Robida's "Twentieth Century" book:.

http://www.amazon.com/Twentieth-Century-Classics-Science-Fiction/dp/0819566802/ref=sr_1_1?ie=UTF8&s=books&qid=1208178705&sr=1-1

History of the first recorded sound:.
http://www.firstsounds.org/

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.

Since most pdfs can be equivalently expressed as a Gaussian mixture model, it is tempting to simplify them. The measure taken between two GMMs (one with many components, and the other with a reduced number) is the Kullback-Leibler relative entropy (=cross entropy-entropy). The problem is to decide whether we should minimize KL(GMMsource||GMM simplified) or the converse KL(GMM simplified||GMMsource) or the symmetrized KL (Jensen-Shannon, in green). Here are a few experiments carried out when simplidying a GMM to a single normal:


I let you guess whether the blue/red is the left/right or the converse... -:)

Kullback-Leibler ball for unnormalized positive distributions.

Using s/w volume rendering,we can easily visualize Voronoi structures in 3D. The picture below is a screen capture of an interactive s/w using GPU shaders. We can similarly visualize the quantum voronoi diagrams inside the Bloch ball...
VorL2.bmp

Bregman balls in 3D

... Robida ? 19?????? 20???????????????????????????? 60,000??????? 200??????????????????????????????????????????????? (http://www.robida.info/)????????????? IT ????????????????????????????????????????????????

Robida ????????????????????????1883????????? ? "phonoscope" ????????????? "phonoscope" ?????????????????????????????????? 1879?? Edison ? "telephonoscope" ?????????????????????????????????????????????????????????????????Robida ??? "e-?????" ???????????? ?????????????????????????????????????? ... WALKMAN ??????????????????? (a walk man) ?????????????????????????????????????????????????????????????????????????? ... ?????????????????????????????????????????????????? ????????????????????? (2008?3?) ??????????????? Edouard-Leon Scott de Martinville ? 1860 ?4?9???????????? Au Clair de la Lune ?????????? ??????????Scott ???? 1857?????? phonautographic ????????????????????? (INPI) ?????????????????????????????????????????????????????? ?????????? ?????????????????(??????????????) ??????????????????? (???? Edison ?1927????????????????????????????)

??? Albert Robida ????????? "The Electric Life" ??????????????? 20???????????????????????????????????????????????????? ...

Frank NIELSEN, excerpts 2008.

November 18th-20th, 2008.

Registration is now open (and free)

ETVC08

http://www.lix.polytechnique.fr/Labo/Frank.Nielsen/ETVC08/

Nicely written and well sound!

The paper:

Error Analysis of a Numerical Calculation about One-qubit Quantum Channel Capacity (ISVD'07)

investigates the numerical error in computing the Holevo channel capacity using the furthest Voronoi diagram wrt. to the von Neuman quantum divergence. They show that the error is in O(1/eps) for sampling in the latitude-longitude 1/eps points.

This algorithm allows us to study, e.g., the additivity conjecture of quantum channels.

It is a nice aspect of quantum information geometry derived from traditional computational geometry. Interestingly, the Legendre transformation for 1-qubit represented on the Bloch sphere is explicited too.

Good news from the CNRS after the Nobel prize of Albert Fert, it has been evaluated at number 6 worldwide.

Read the ranking

Seminars in January at INRIA SA, and forthcoming events

Dually Flat Manifolds and Global Information Geometry,, Nihat Ay and Wilderich Tuschmann, Preprint 24, MPI Math Leipzig, 2002. Appeared also in Open Systems & Information Dynamics, Volume 9 , Issue 2 (2002) t

Pages: 195 - 200
Year of Publication: 2002 ISSN:1230-1612

The authors rise and solve the following question:
Does any Riemannian manifold (M,g) admits a dually flat structure on M (ie, a pair of dually torsion-free connections) ?
The answer is no (eg., compact Riemannian manifolds with finite fundamental group, independent of the metric: this is a purely topological argument). Then the authors go one on finding the conditions for such an existence by considering pair of connections with at least one of them complete, meaning that the geodesics are defined on the whole real line. In probabilistic information geometry, it is the case for the exponentia connection nabla^(e) but the mixture connection nabla^(m) is not complete creating a full range of optimization problems involving Bregman projections. Finally, applications to quantum information geometry is reported. This is a well-written paper that focuses on global topological property of dual flatness, a must-read that I recommend.

One of the blog readers (are there many?) introduced me to his paper on shape analysis in information geometry.
Shape analysis using the Fisher-Rao Riemannian metric: unifying shape representation and deformation

The short paper (always good) gives an executive view of how to use the Fisher-Rao metric to compute shape geodesics using mixture models (like GMMs).

They apply their method on 2D corpuse callosum shapes.

This is one important problem for building and comparing a shape repository with a shape atlas.

The geodesic is used to drive the deformation on the ambiant Euclidean space.

Thank you for letting me know of this work.

A colleague of mine introduced me to particle filters. This is an interesting approach that however relies on Monte-Carlo simulations.

An ICIP paper.

I attended one talk on "noise is signal". The basic idea is to use the prior that noise should be symmetric so that the observed noise in images that has been deformed by the camera response function should be analyzed to recover the curve. This seems to work fine. Also, Matsushita-san introduced a "metric" (a similarity measure) with some insights of noise. The talk was instructive.

Another talk was about Clifford algebra (and geometric algebra interpretation). Here the basic primitive is not point but sphere and the vectors are splitted into 3 categories for inner products of basis equal to 1, -1, or 0. This seems to be a full generalization of the many anterior algebras. I am curious to hear about differential extensions of it. Tomorrow is the application day. Looking forward to hearing part II!

I am programming kmeans for multivariate normals with respect to the relative entropy distance . Here is a snapshot for the left (blue) and right (red) entropic centroid of 2 bivariate normals

Tomorrow, I'll attend the COE workshop on math aspects of image processing and computer vision. I'm looking forward to hearing the talks.

I invite you to read this paper:

Empirical development of an exponential probabilistic model for text retrieval: using textual analysis to build a better model

The authors concentrate on determining what is a good model for explaining a text corpus. They show that the multinomial model falls short, as it is widely known, and go on learning the 1-order exponential family that better represent corpora for naive Bayesian retrieval.

Overall, although we cannot explain all data sets, and risk over-fitting, it is crucial to design better generative models. One big success these years was the LDA (Latent Dirichlet Allocation) scheme. But, this has to be learnt and not hardcoded anymore. There is plenty room for this line of research...

Today is rainy saturday in Tokyo and I have soon to take the train to Saitama. So here is a short post: I like very much to think of abstraction as the main creativity engine in scientific activities.

I found by browsing the www the following paper:
THE RIEMANNIAN MANIFOLD OF ALL RIEMANNIAN METRICS (1991)
I am amazed about the possibilities of studying things once they have an avatar point lying on an avatar world (ie: the differential manifold)

Today is a short post on a NIPS'98 paper:

Batch and on-line parameter estimation of Gaussian mixtures based on the joint entropy

The authors compute the relative entropy (KL divergence) among two Gaussian mixture models (GMMs) and derive a simple update rule (in sec 5). They call their method joint entropy (JE) update and claim that it requires half the steps of the EM.

The important remark is to notice that the relative entropy between two GMMs is non-convex. So they proceed by studying an upper-bound called the joint entropy distance

Unfortunately the term normalized mutual information is a bit confusing since there exists several definitions of it. They all share the same insights of producing a value in [0,1] such that a greater value means a better ``score''.

Mutual-information-based registration of medical images: a survey (2003)

The definition given is just the sum of the marginal entropies over the joint-entropy

It is moreover related to the entropy correlation coefficient as follows:

In the ICDE'06 paper:

MIC Framework: An Information-Theoretic Approach to Quantitative Association Rule Mining

The authors present an efficient system for finding out quantitative association rules (QARs) by wise combinatorial enumeration in graph with edges built if and only if the corresponding vertices have a good normalized mutual information.

The normalized mutual information is defined as:

This reflects the percentage of reduction in uncertainty about x due to the knowledge of y. It is in interval [0,1].

The paper makes mention of an article of Sergey Brin, that is well cited (over 150+) on citeseer. This paper defines a notion of interestingness of an association rule.

The question remains open to find out the geometry and axiomatic approach of defining good rules in data mining...

I've read the following paper:

Empirical evaluation of dissimilarity measures for color and texture

The paper compares 9 kinds of divergences for several applications of computer vision such as classification supervised/unsupervised segmentation, and, image annotation and retrieval. I am not going to cite verbatim their concluding remarks, but for short (1) EMD is performing very good for partial matches, and (2) there is no winner for all tasks, which confort my point of view: divergences should be tailored and learnt from data-sets on the fly.
Also adaptive binning in histogram seems to be a key for improved performance.

Today, I would like to introduce the NIPS 2006 paper:

Differential Entropic Clustering of Multivariate Gaussians.

The paper shows how to clustering a set of multivariate normals with respect to the Kullback-Leibler divergence. The key ingredient that makes it a non-trivial application of the former clustering with Bregman divergence paper (JMLR'05) is to show how to compute the centroid of a set of multivariate normals by decomposing the Bregman divergence into a convex sum of two Bregman divergences: a Mahalanobis distance on the means followed by a Burg matrix divergence on the variance-covariance matrix.

The authors also report on experimental results by using the normalized mutual information.

I write twice this post. When I pushed on the submit button, all my message was erased. This is a big frustration to start a day with such an accident -:)!

Ok, the Earth Mover Distance (EMD) distance introduced in 1997 by Stanford CS group, is in fact known to statisticians under the name of Mallows distance:

It coincides exactly for normalized histograms but not for unormalized distributions. I recommend reading ICCCV'01's paper for a nice description of these similitudes:
The Earth Mover's distance is the Mallows distance: some insights from statistics

Ok, I push the "preview" button and cross fingers for not encountering the same problem twice -:)

Prof. Vemuri recently sent me his paper:

Efficient Shape Indexing Using an Information Theoretic Representation

Spellman and Vemuri presented a left-side KL minimax center for probability density functions belonging to the exponential families (using log-partition statistical physics notations).

They prove that the minimizer is unique and defines the e-radius

Finally, they show that the center allows more efficiency for nearest neighbor queries. There is definitively "something" information geometry to be done on barycenters and centroids, like Bruno Pelletier first initiated in his 2005 paper.

The previous post was about computing the centroid of normals with respect to the symmetrized Kullback-Leibler divergence. Today, I would like to present the same problem for a different measure: The Bhattacharyya distortion measure. Given two normals in d dim, their distance is expressed by:

The authors of

http://www.citeulike.org/user/ciga/article/1823637 An optimal Bhattacharyya centroid algorithm for Gaussian clusteringwith applications in automatic speech recognition

present an iterative algorithm. This is the same flavor as for the SKL case.