Lectures

Similarity Search / Intro to Content Optimization

Similarity search is a task to organize a database of objects in a way that given a new object one can efficiently find its most similar object in the database.

In the first half we will study two prominent families of algorithms for similarity search: locality-sensitive hashing and combinatorial framework. In the second part I will give an introduction to new research area of content optimization. Content optimization is a family of tasks for selecting content items (headlines, ad units, modules, menu items) maximizing a certain objective function. In particular, we will study explore/exploit algorithm that is used to pick best stories for Yahoo! frontpage.

Computational pattern analysis

We will present the concept of pattern-analysis, its importance for modern society and modern scientific research, and the key technologies behind it. We will discuss its promises, particularly as an enabler for science-automation and for business, and its risks, particularly with respect to privacy. We will also discuss a unified theoretical framework for describing all pattern analysis tasks in a single way. Applications to web mining will be used as a running example.

Evolutionary computing

This three lecture course focuses on evolutionary algorithms and related biologically inspired techniques for solving optimisation problems. Such algorithms are easy to implement, applicable in a wide range of problem domains, and often provide excellent solutions to real-world problem instances.

The first part gives a brief overview of the research field evolutionary computation. We will then outline the main components of a classical evolutionary algorithm, including genetic operators, problem representations and selection mechanisms. Subsequently, we will consider some theoretical aspects of such algorithms that allow us to predict when they are efficient and not.

In the second part, we will describe how evolutionary algorithms can be adapted to solve optimisation problems with multiple, conflicting objectives. Some important multi-objective evolutionary algorithms will be presented and contrasted with classical techniques.

The third part gives an introduction to a class of biologically inspired techniques called ant colony optimisation. We will discuss the main components of these algorithms, how they can be configured to solve various combinatorial optimisation problems, and finally some of their theoretical properties.

Private data analysis

We will focus on the recent notion of Differential Privacy [Dwork, McSherry, Nissim, Smith, TCC 2006]. Differential Privacy stipulates that an analysis over information collected from a group of individuals should be almost indifferent to the specific value any individual contributor. More formally, the probability of every output changes by at most a small constant factor as a result of an individual change.

We will explore issues related to privacy in data analysis. In particular, we will review lower bounds on privacy, techniques for constructing differentially private analyses, and applications to areas such as data mining and learning.

The talks will be self-contained, assuming undergraduate knowledge in algorithms, probability theory, and linear algebra.