Cost sensitive learning in high dimensions with approximate nearest neighbours

Add to your list(s) Download to your calendar using vCal

• Henry W J Reeve, School of Computer Science, University of Manchester
• Monday 06 February 2017, 11:00-12:00
• Computer Science, The Sloman Lounge (UG).

If you have a question about this talk, please contact Lars Kunze.

Speaker’s homepage: http://www.cs.man.ac.uk/~reeveh/

Host: Dr Ata Kaban

Abstract:

We shall explore a nearest neighbour approach to multi-class cost-sensitive learning in high dimensional feature spaces. The behaviour of the classical k-nearest neighbour algorithm has been explored extensively, culminating in the result of Chaudhuri and Dasgupta which shows that the algorithm attains minimax optimal learning rates in the binary classification setting. However, in high dimensional feature spaces exact nearest neighbour computations are prohibitively expensive. Instead approximate nearest neighbours must be used. Kaban gave a bound on the generalisation error of the approximate nearest neighbour algorithm obtained by applying a 1-nearest neighbour classifier to randomly projected data. The bound highlights the way in which random projections enable the classifier to efficiently utilise low-dimensional structure within a high dimensional feature space. We consider approximate nearest neighbour algorithms in the context of the more general problem of multi-class, cost-sensitive learning. We suppose that the data is concentrated on a low-dimensional manifold within a high-dimensional ambient feature space and show that the cost-sensitive approximate nearest neighbour algorithm is capable of exploiting this low dimensional structure to attain minimax optimal learning rates.

This talk is part of the Artificial Intelligence and Natural Computation seminars series.

This talk is included in these lists:

• Artificial Intelligence and Natural Computation seminars
• Computer Science Departmental Series
• Computer Science Distinguished Seminars
• Computer Science, The Sloman Lounge (UG)
• computer sience

Note that ex-directory lists are not shown.