Program

Lecture(r)s

Below you find short abstracts of the lectures. Clicking on the photos gets you to the respective lecturers' homepage.

Nicolò Cesa-Bianchi Università degli Studi di Milano		Learning, Prediction and Games Unlike standard statistical approaches to forecasting, prediction of individual sequences does not impose any probabilistic assumption on the data-generating mechanism. Yet, prediction algorithms can be constructed that work well for all possible sequences, in the sense that their performance is always nearly as good as the best forecasting strategy in a given reference class. In this course we will first introduce a general model for sequential prediction and define some basic deterministic and randomized prediction strategies for various loss functions. We will then analyze their application to problems of prediction with partial feedback and to repeated game playing, including multiarmed bandit problems, calibration, and minimization of internal regret. The lectures will be based on the monography: Prediction, learning, and games Nicolň Cesa-Bianchi and Gábor Lugosi Cambridge University Press, 2006
Gábor Lugosi Pompeu Fabra University
Hans Ulrich Simon Ruhr-Universität Bochum		Stability of Clustering The goal of cluster analysis is to partition observed data into groups (called "clusters") so that the pairwise dissimilarities between data assigned to the same cluster tend to be smaller than those in different clusters. Although clustering is one of the most widely used techniques for exploratory data analysis in various fields, the building of a solid theoretical foundation is still in progress. Among the methods in cluster analysis that currently attracts considerable attention from both sides, theoreticians and applied researchers, we find the "stability approach". The intuitive idea behind "stability" is as follows: if we repeatedly sample data points and apply a clustering algorithm, then a "good" algorithm should produce clusterings that do not vary much from one sample to another. In the tutorial, we present some new results that aim at a "theory of stability" by providing a rigorous mathematical analysis within a clean formal framework. In the first lecture, we derive necessary and sufficient conditions for stable behavior of a clustering algorithm. In the second lecture, we apply the general results to so-called risk-minimizing algorithms whose risk function is induced by a "dissimilarity measure". These clustering algorithms represent a rich family with the popular "k-means" algorithm as a special case. The topic of the tutorial is "brand-new" so that we cannot provide pointers to textbooks dealing with stability of clustering. In order to get a general idea of cluster analysis, we recommend to follow (one or more of) the following suggestions: Apply GOOGLE to the keyword "Clustering" and see what you get. Have a look in Chapter 6 of the classical book "Pattern Classification and Scene Analysis" by Duda and Hart. Have a look in Chapter 14.3 of the book "The Elements of Statistical Learning" by Hastie, Tibshirani, and Friedman. Later (but before the tutorial), we will provide further material about clustering stability that will be fairly self-contained (including up-to-date pointers to the relevant literature and talk slides.) abstract.pdf Slides wow available for downloading: Slides Part I, Slides Part II, Solutions to exercises: Exercise 4, Exercise 5, Exercise 6, Exercise p.05, Exercise p.26, Exercise p.27,
Afra Zomorodian Dartmouth College		Topological Data Analysis We often seek to understand the structure of a set of data points. Generally, we assume that the points are sampled from some underlying space in which we are interested. One approach to data analysis is clustering, where we assume that the underlying space had multiple components. As such, clustering attempts to recover the way in which the original space was connected -- its connectivity. Topological data analysis -- the topic of my two lectures -- extends this analysis by examining other attributes of connectivity, such as the existence of tunnels or enclosed spaces. In the first lecture, we will cover some basic concepts from topology including important invariants that characterize a space. We will also look at structures that we may use to compute these invariants from point sets. In the second lecture, we will discuss persistent homology, a theory for analyzing point sets at multiple scales. We will also look at some recent applications of persistent homology. In both lectures as well as the exercises, I hope to include discussion of current software for topological analysis. The lectures will be partly based on the book: Topology for Computing Afra Zomrodian Cambridge University Press, 2005 The material in the book is based on my dissertation which can be found here. There are also useful notes from the most recent incarnation of a course on computational topology. Slides wow available for downloading: Slides Part I, Slides Part II,

Organization