Computational Information Geometry

Location :
INRIA , Unité de Sophia Antipolis
Project Team Geometrica
BP 93
06902 Sophia Antipolis
FRANCE

Information:
J-D. Boissonnat (04 92 38 77 60, jean-daniel.boissonnat@sophia.inria.fr)
Description:

Information geometry investigates the geometric structure possessed by families of probability distributions [0]. For example, the set of normal distributions can be viewed as a 2-dimensional space with mean and variance as a coordinate system. Such a space is not a metric space. To measure the (dis)similarity between any pair of elements, various divergence measures based on entropy functions have been proposed. The notion of Bregman divergence emerged recently as a general concept that encompasses many of the standard divergences used in information theory, statistics, machine learning, image and signal processing.

The goal of this internship is to design and implement data structures and algorithms for Information Geometry. The work will be a first step towards revisiting the whole core of Computational Geometry in the context of Information Geometry. The proposed work will build upon recent results on minimal enclosing balls [1], Voronoi diagrams [2] and clustering algorithms [3]. Information Geometry usually implies to work in high dimensional spaces. Since the combinatorial complexity of most geometric data structures depends exponentially upon the dimension of the embedding space, complexity issues are critical. Recent concepts like core-sets and witness complexes might appear to be useful. Finally, the tools developped during the internship will be validated on some applications in image processing, structural biology or non linear manifold learning. [0] S. Amari and H. Nagaoka, Methods in Information Geometry, Oxford University Press, 2000.

[1] F. Nielsen and R. Nock, "On Approximating the Smallest Enclosing Bregman Balls" ACM Symposium on Computational Geometry (SoCG), pp. 485-486, 2006.

[2] F. Nielsen, J.-D. Boissonnat and R. Nock, "On Bregman Voronoi Diagrams", ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007.

[3] A. Banerjee, S. Merugu, I.S. Dhillon, and J. Ghosh, Clustering with Bregman divergences, Journal of Machine Learning Research, 6 (2005), pp. 1705--1749

Retour aux autres stages
dernière modification le 13/12/06