Computational Information Geometry | Frank NIELSEN
Computational Information Geometry
*** To open in February 2010 ***
Visit the blog
The field of computational information geometry (discrete information geometry) is interested in exploring the following domains:
- Generic algorithms: Design meta-algorithms that can handle any arbitrary parameterized distance or loss function.
(The usual class of parameterized distances are Bregman, Csiszar and Burbea-Rao divergences.)
Examples: K-means, expectation maximization (EM), Voronoi diagrams, barycenters, smallest enclosing balls, ball trees, etc.
- Geometry of information.
Examples: Dually flat spaces of exponential/mixture families (VC-dimension of balls remains unchanged to d+1), Riemmanian geometry, Finsler geometry (HARDI datasets), etc.
- Novel applications.
Examples: Statistics, machine learning, computational geometry
Let us give some examples of information manifolds:
- Statistical manifolds (parametric distributions),
- Neural manifolds (Boltzmann machines with fixed topology, i.e., number of nodes),
- ARMA(p,q) time-series manifolds (e-flat=-1-flat)
Strictly speaking, geometrizing information-theoretic problems does not provide a more powerful framework in theory.
This is because synthetical and analytical geometries are equivalent.
Informally, that means that we can do geometry by algebraic equations.
However, geometrizing problems help grab intuition on the problem at hand.
Geometry also yields novel notions to mathematical theories.
For example, let us cite the two curvature notions in statistics: exponential and mixture curvatures emanating from conjugate connections.
So although synthetical geometry provides the same power as analytical geometry, the third-order asymptotic theory of statistics has been obtained so far only from synthetical information geometry.
Dual differential geometries are also useful to tackle information-theoretic problems such as
- Multiterminal problems met in information theory,
- Linear programming problems (e.g., continuous Karmarkar inner method walking along the m-geodesic),
- Clustering (negative entropy and dual Legendre log-normalizer conjugate for soft/hard clustering).
Publications
- Hierarchical Gaussian Mixture Model (2010) International Conference on Acoustics, Speech and Signal Processing (ICASSP) [bib] [pdf][slides]
- Hyperbolic Voronoi diagrams made easy (2010) International Conference on Computational Sciences and Its Applications (ICCSA) [bib] [pdf]
- Boosting $k$-NN for categorization of natural scenes (2010) Computing Research Repository (CoRR) [bib] [pdf]
- Statistical exponential families: A digest with flash cards (2009) Computing Research Repository (CoRR) [bib] [pdf]
- Steering self-learning distance algorithms (2009) Communications of the ACM [bib] [pdf]
- Bregman divergences and surrogates for learning (2009) IEEE Transactions on Pattern Matching and Machine Intelligence [bib] [pdf]
- Approximating smallest enclosing balls with applications to machine learning (2009) International Journal on Computational Geometry and Applications [bib] [pdf]
- Levels of details for Gaussian mixture models (2009) Ninth Asian Conference on Computer Vision (ACCV) [bib] [pdf][poster]
- Opinion on "Open, Closed, or Clopen Access" (2009) [bib]
- Gaussian mixture models via entropic quantization (2009) 2009 European Signal Processing Conference (EUSIPCO) [bib] [pdf]
- Sided and Symmetrized Bregman Centroids (2009) IEEE Transactions on Information Theory [bib] [pdf]
- Accuracy of distance metric learning algorithms (2009) Workshop on Data Mining using Matrices and Tensors (DMMT) [bib] [pdf][slides]
- The dual Voronoi diagrams with respect to representational Bregman divergences (2009) International Symposium on Voronoi Diagrams (ISVD) [bib] [pdf][slides]
- Bregman vantage point trees for efficient nearest neighbor queries (2009) IEEE International Conference on Multimedia and Expo (ICME) [bib] [pdf]
- Searching high-dimensional neighbours: CPU-based tailored data-structures versus GPU-based brute-force method (2009) Computer Vision / Computer Graphics Collaboration Techniques and Applications (MIRAGE) [bib] [pdf][slides]
- Hyperbolic Voronoi diagrams made easy (2009) Computing Research Repository (CoRR) [bib] [pdf]
- Tailored Bregman ball trees for effective nearest neighbors (2009) European Workshop on Computational Geometry (EuroCG) [bib] [pdf][slides]
- A volume shader for quantum voronoi diagrams inside the 3D Bloch ball (2009) ShaderX7: Advanced Rendering Techniques [bib]
- Information geometries and microeconomic theories (2009) Computing Research Repository (CoRR) [bib] [pdf]
- Emerging trends in visual computing (2009) [bib] [pdf]
- Computational information geometry: Pursuing the meaning of distances (2009) Open Systems Science [bib]
- Bregman sided and symmetrized centroids (2008) International Conference on Pattern Recognition (ICPR) [bib] [pdf]
- On the efficient minimization of classification calibrated surrogates (2008) Neural Information Processing Society (NIPS) [bib] [pdf]
- Abstracts of the LIX fall colloquium 2008: Emerging trends in visual computing (2008) Emerging trends in visual computing (ETVC) [bib] [pdf]
- Intrinsic geometries in learning (2008) Emerging trends in visual computing (ETVC) [bib] [pdf]
- Soft Uncoupling of Markov Chains for Permeable Language Distinction: A New Algorithm (2008) Computing Research Repository (CoRR) [bib] [pdf]
- Quantum Voronoi diagrams and Holevo channel capacity for $1$-qubit quantum states (2008) IEEE International Symposium on Information Theory (ISIT) [bib]
- The entropic centers of multivariate normal distributions (2008) European Workshop on Computational Geometry (EuroCG) [bib] [pdf]
- Quantum Voronoi diagrams (2008) European Workshop on Computational Geometry (EuroCG) [bib] [pdf][slides]
- An interactive tour of Voronoi diagrams on the GPU (2008) ShaderX6 [bib]
- A Volume shader for quantum Voronoi diagrams inside the 3D Bloch ball (2008) ShaderX7 [bib]
- On the smallest enclosing information disk (2008) Information Processing Letters [bib] [pdf]
- Les (tr\`es) nombreuses \'epingles algorithmiques de la meule de surrog\'ees (2008) Conference francophone sur l'apprentissage automatique (CAp) [bib]
- On the centroids of symmetrized Bregman divergences (2007) Computing Research Repository (CoRR) [bib] [pdf]
- Bregman Voronoi diagrams: Properties, algorithms and applications (2007) CoRR [bib] [pdf]
- Visualizing Bregman Voronoi diagrams (2007) Symposium on Computational Geometry (SoCG) [bib] [pdf]
- A real generalization of discrete AdaBoost (2007) Artificial Intelligence [bib] [pdf]
- Real boosting a la carte with an application to boosting oblique decision tree (2007) International Joint Conference on Artificial Intelligence (IJCAI) [bib] [pdf]
- On Bregman Voronoi diagrams (2007) Symposium on Discrete Algorithms (SODA) [bib] [pdf][slides]
- On weighting clustering (2006) IEEE Transactions on Pattern Analysis and Machine Intelligence [bib] [pdf]
- On the smallest enclosing information disk (2006) Canadian Conference on Computational Geometry (CCCG) [bib] [pdf]
- A real generalization of discrete AdaBoost (2006) European Conference on Artificial Intelligence (ECAI) [bib]
- Soft uncoupling of Markov chains for permeable language distinction: A new algorithm (2006) European Conference on Artificial Intelligence (ECAI) [bib]
- On approximating the smallest enclosing Bregman balls (2006) Symposium on Computational Geometry (SoCG) [bib] [slides]
- Fitting the smallest enclosing Bregman ball (2005) European Conference on Machine Learning (ECML) [bib] [pdf][slides]
Conferences
Software
- jMEF: A java library for mixtures of exponential families (with a Matlab wrapper)
*** Grand opening -:) , February 2010 ***
Online December 2007.
Last updated, January 2010.
(c) Frank NIELSEN, All rights reserved.