| [home] - [up] |
Abstract: In this talk, we give a survey on statistical learning with special emphasis on large-margin classifiers (like Vapnik's Support Vector Machine). We first explain the principles of statistical learning along with some some central notions like empirical or structural risk minimization. Then, we move on to the problem of controlling the generalization error. Here, combinatorial notions like the Vapnik-Chervonenkis Dimension of the hypothesis class and geometrical notions like the margin achieved by a separating hyper-plane come into play. Next, we explain how kernel-based large-margin classifiers avoid the so-called curse of dimensionality. Finally, we discuss some theoretical limits of these learning machines: it turns out that there exist learning problems that, in principle, enjoy small generalization error bounds, but loose this property when they are loaded into linear learning machines that are based on large margin classification. The talk closes with the presentation of some open problems.
Colloquium - 16:00
Abstract: In 1983 Thomassen proved that if the girth of a graph G is large and its minimum degree is at least 3, then G contains large complete minors. Here the girth of a graph G is the length of its shortest cycle. So if a graph G has large girth then it looks locally like a tree. Thus Thomassen's observation is the surprising fact that if the minimum degree of such a "locally sparse" graph is at least 3, i.e. if its large girth is not merely obtained by subdividing edges, then it must contain a large dense substructure, namely a large complete minor.
Together with Deryk Osthus I proved more precise asymptotic bounds on the girth required to force a complete graph of given order as minor. The proofs rely on the probabilistic method. Our results imply Hadwiger's conjecture (which states that every graph of chromatic number at least r contains a Kr minor) for all graphs whose chromatic number is sufficiently large and which do not contain a cycle of length four. In my talk, I will sketch the proof for some special cases.