Minisymposium

Computational Geometric Learning – Exploring geometric structure in high dimensions

minisymposium on Sunday, June 17, 2012, afternoon, as part of the Computational Geometry Week within the framework of CG:APT during the 28th Symposium on Computational Geometry (SoCG) in June 17-20, 2012 in Chapel Hill.

Scientific summary

Computational Geometric Learning in High Dimension is an area of recent interest at the bridge between Computational Geometry and Learning Theory. It deals with the analysis of shape and data - not necessarily from a geometric source - that lives in some high-dimensional space, but is itself inherently of lower dimension. This minisymposium arises out of an ongoing European project on the subject, and the purpose of the meeting is to disseminate this view and get into contact and cross-fertilization with the other SoCG and CG:APT participants. Participation is possible by registering as part of the Computational Geometry Week, either for a single afternoon, or for the whole week.

Program / speakers

Session 1. Chair: Jean-Daniel Boissonnat
2:20–3:05 Mauro Maggioni, Duke University Geometric estimation of intrinsically low-dimensional probability measures in high dimensions
3:05–3:35 Joachim Giesen, Universität Jena Dimensionality of Learning Problems
3:35-4:05 coffee break
Session 2. Chair: Dan Halperin
4:05-4:50 Pankaj K. Agarwal, Duke University Algorithms for Geometric Similarity
4:50–5:20 Frederic Chazal, INRIA Geometric inference using distance-to-measures functions

Abstracts of Talks

Mauro Maggioni, Duke University (USA): Geometric estimation of intrinsically low-dimensional probability measures in high dimensions

2:20–3:05

Abstract:

We discuss recent work in estimating a probability measure in high dimensions, whose support is (nearly) low-dimensional and has some geometric structure, for example that of a manifold, or a union of hyperplanes. We construct a multiscale geometric tree decomposition of the data and use this decomposition to construct an increasing family of approximation "spaces" in the space or probability measure, parametrized by certain subtrees of the multiscale tree, and perform a multiscale bias-variance tradeoff using this family of approximation spaces. We obtain finite-sample results that guarantee that with high probability the Wasserstein distance between the (random) measure estimated by our algorithm and the true measure is small, depending on the number of samples, a measure of complexity of the models we use (typically this depends only on the intrinsic dimension and not on the ambient dimension!), and a notion of "regularity" of the true measure.

Joachim Giesen, Friedrich-Schiller-University Jena (Germany): Dimensionality of Learning Problems

3:05–3:35

Abstract:

High-dimensional learning seems to be ubiquitous these days. In this talk I will discuss what makes a learning problem high-dimensional before analyzing the dimensionality of support vector machines for binary classification problems.

Pankaj K. Agarwal, Duke University (USA): Algorithms for Geometric Similarity

4:05–4:50

Abstract:

A basic problem in classifying, or searching for similar objects in, a large set of geometric objects is computing similarity between two objects. This has led to extensive work on computing geometric similarity between two objects. This talk discusses some old and some new geometric-similarity algorithms and also touches upon a few open problems in this area.

Frederic Chazal, INRIA Saclay (France): Geometric inference using distance-to-measures functions

4:50–5:20

Abstract:

Data often comes in the form of a point cloud sampled from an unknown compact subset of Euclidean space. The general goal of geometric inference is then to recover geometric and topological features of this subset from the approximating point cloud data. In recent years, it appeared that the study of distance functions allows to address many of these questions successfully. However, one of the main limitations of this framework is that it does not cope well with outliers nor with background noise. In this talk, we will show how to extend the framework of distance functions to overcome this problem. Replacing compact subsets by probability measures, we will introduce a notion of distance-to-measure functions. These functions share many properties with classical distance functions, which makes them suitable for inference purposes. In particular, by considering appropriate level sets of these distance functions, it is possible to associate in a robust way topological and geometric features to a probability measure.

Organizers

  • Joachim Giesen, Universität Jena
  • Christian Lorenz Müller, ETH Zürich
  • Günter Rote, Freie Universität Berlin

 
© 2010 CGL Computational Geometric Learning.