Incremental Cover Trees for Dynamic Diversification

15.04.2019, 12:00  –  Golm, Haus 9, Raum 0.13
Forschungsseminar Wahrscheinlichkeitstheorie

Hannah Marienwald (TU Berlin)

Dynamic diversification – finding a set of data points with maximum pairwise distance from a time-dependent sample pool – is an important, but NP-hard problem in many different applications. Therefore, various approximation algorithms exist. The incremental cover tree (ICT) with high computational efficiency and flexibility has been applied to this task and has shown good performance.  Specifically, it was empirically observed that ICT typically provides a set with its diversity only marginally (≈ 20%) worse than the state-of-the-art method for static diversification.

This talk will introduce you to the diversification maximization problem and how it can be solved using an incremental cover tree. We will compare its empirical performance with the results of the state-of-the-art approach. Furthermore, I will provide a theoretical bound on the worst possible performance of the ICT approach which I proved to be the tightest possible approximation factor.

If time allows, I will also demonstrate a new use of dynamic diversification for generative image samplers.