The next PGR seminar is taking place this Friday 28th February at 2PM in JC 1.33a

Below are Titles and Abstracts for Ben and Erdem’s talks – Please do come along if you are able.

Ben Claydon

Title: Mechanisms for Similarity Search

Abstract:

Similarity search encompasses the task of finding those objects in a large collection which are most alike to, in some way, an object presented by the user as a query. The domain of these objects is wide, from images to text to chemical structures. This task becomes yet harder when the database becomes extremely large, and a sublinear query time with respect to the database size becomes a requirement. This talk discusses why the problem becomes so hard when presented with complex data, and how algorithms and data structures can be engineered to serve these queries.

Erdem Kus

Title: Frugal Algorithm Selection

Abstract: When solving decision and optimisation problems, many competing algorithms (model and solver choices) have complementary strengths. Typically, there is no single algorithm that works well for all instances of a problem. Automated algorithm selection has been shown to work very well for choosing a suitable algorithm for a given instance. However, the cost of training can be prohibitively large due to running candidate algorithms on a representative set of training instances. In this work, we explore reducing this cost by choosing a subset of the training instances on which to train. We approach this problem in three ways: using active learning to decide based on prediction uncertainty, augmenting the algorithm predictors with a timeout predictor, and collecting training data using a progressively increasing timeout. We evaluate combinations of these approaches on six datasets from ASLib and present the reduction in labelling cost achieved by each option.