ANC Seminar - Sibylle Hess

Tuesday, 2nd November 2021

Optimization with binary constraints: from k-means to deep learning

Abstract:   In the field of data mining, there is one big open problem: the optimization subject to binary constraints. Binary constraints are ubiquitous in data mining tasks. They make results interpretable and definite. Is this picture showing a cat? Should this movie be recommended to this user? Should the next chess move be this one? Binary results give a definite answer to questions like these. There are a lot of methods which are able to solve binary constrained problems, however, they mostly work under one condition: exclusivity. That is, if a picture shows a cat, then it can not show a dog, if a movie is recommended to one user, then it can't be recommended to the other, and there should only be one next chess move which is the optimal one. Depending on the application, this assumption is is more or less justified. The field of clustering is  an area in which the optimization subject to binary constraints is explicitly studied. In this talk, we will discuss the broad spectrum of tasks where a matrix factorization approximation error in Frobenius norm is minimized subject to binary constraints. We will unveil under which circumstances this optimization task defines the clustering objectives of k-means, spectral clustering and subspace clustering, but we will also make connections to other methods such as deep learning classifiers. Furthermore, I will present my work on a gradient-descent based approach to tackle the general clustering problem of optimizing a smooth loss function subject to binary constraints, dropping the assumption of exclusivity.

Event type: Seminar

Date: Tuesday, 2nd November

Time: 11:00

Location: Online

Speaker(s): Sibylle Hess

Chair/Host: Antonio Vergari