University of Birmingham > Talks@bham > Artificial Intelligence and Natural Computation seminars > Cost sensitive learning in high dimensions with approximate nearest neighbours

Cost sensitive learning in high dimensions with approximate nearest neighbours

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

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

Speaker’s homepage:

Host: Dr Ata Kaban


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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on from the University of Cambridge.