Computational Information Geometry

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

Information:
JD. Boissonnat (04 92 38 77 60, jeandaniel.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 2dimensional 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 coresets 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. 485486, 2006.
[2] F. Nielsen, J.D. Boissonnat and R. Nock, "On Bregman Voronoi
Diagrams", ACMSIAM 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. 17051749
Retour aux autres stages
dernière modification le 13/12/06