Machine learning and statistical inference have become foundational in most applications of computer science, e.g., computational biology, speech recognition, computer vision, natural language translation, electronic commerce, database integretiy, and information retrieval. But the mathematical foundations of machine learning and statistical inference remain largely unresolved. Most glaringly, the generalization properties of simple least squares regression (Tychonoff regression) remain poorly understood --- existing bounds do not work well for the common case of a Gaussian kernel. The generalization theory of simple support vector machines (SVMs) and SVMs with latent variables or structured labels are even less well understood. The choice of regularization (L2, L1, or L0) is perhaps the least well understood. This talk will focus on open mathematical problems but will also discuss the philosophical foundations of generalizing from finite data.

Preferences occur in many everyday tasks. Whether we look for a house, a car, a computer, a digital camera, or a vacation package, we usually state our own preferences and we expect to find the item of our dreams. It is therefore natural that modelling and solving sets of preferences is a central issue in AI, if we want to understand human intelligence and use computing devices to replicate some of functions of the human brain.

This talk will discuss different kinds of preferences, it will describe and compare some of the AI formalisms to model preferences, and it will hint at existing preference solvers. Uncertainty will also be considered, in the form of a possibly incomplete set of preferences, because of privacy issues or missing data. We will also discuss multi-agent settings where possibly incomplete preferences need to be aggregated, and will present results related to both normative and computational properties of such systems.

While the results on single-agent preference solving are mostly related to AI sub-areas such as constraint programming and knowledge representation, those on multi-agent preference aggregation are multi-disciplinary, since preference aggregation and its properties have been extensively studied also in in decision theory, economy, and political sciences.

A ubiquitous property of intelligent systems is their ability to separate the essential from the irrelevant. A precise mathematical formulation of this fundamental ability remains elusive, since it is conceptualized in different ways in different scientific fields. In classical pattern recognition, this idea is rendered as finding "good features", or data representations that can separate "signal from the noise". In parametric statistics, the notion of relevant information in a sample is captured in Fischer's definition of "minimal sufficient statistics", which in its original form was in fact restricted to parametric families in exponential forms. In machine learning, this same aim is captured in algorithms that produce useful hypotheses from samples, and are tested by their ability to generalize beyond the given data.

In this talk I will argue that all these views can be unified by one information theoretic tradeoff between compression and prediction, known as "The Information Bottleneck method". This surprisingly simple principle, found in entirely different contexts in information theory, naturally generalizes the classical notion of minimal sufficient statistics into a continuum of efficient predictive representations, which can be effectively calculated. I will present some new rigorous properties of the information bottleneck method, and more specifically will discuss recently obtained generalization and distribution independent finite sample bounds.