Hashing hyperplane queries to near points with applications to large-scale active learning

IEEE Transactions on Pattern Analysis and Machine Intelligence
Sudheendra VijayanarasimhanKristen Grauman

Abstract

We consider the problem of retrieving the database points nearest to a given hyperplane query without exhaustively scanning the entire database. For this problem, we propose two hashing-based solutions. Our first approach maps the data to 2-bit binary keys that are locality sensitive for the angle between the hyperplane normal and a database point. Our second approach embeds the data into a vector space where the euclidean norm reflects the desired distance between the original points and hyperplane query. Both use hashing to retrieve near points in sublinear time. Our first method's preprocessing stage is more efficient, while the second has stronger accuracy guarantees. We apply both to pool-based active learning: Taking the current hyperplane classifier as a query, our algorithm identifies those points (approximately) satisfying the well-known minimal distance-to-hyperplane selection criterion. We empirically demonstrate our methods' tradeoffs and show that they make it practical to perform active selection with millions of unlabeled points.

References

Mar 26, 2003·Journal of Chemical Information and Computer Sciences·Manfred K WarmuthChristian Lemmen
Sep 13, 2008·IEEE Transactions on Pattern Analysis and Machine Intelligence·Antonio TorralbaWilliam T Freeman
Jun 2, 2010·IEEE Transactions on Pattern Analysis and Machine Intelligence·Ronen BasriLihi Zelnik-Manor

❮ Previous
Next ❯

Related Concepts

Related Feeds

Bioinformatics in Biomedicine

Bioinformatics in biomedicine incorporates computer science, biology, chemistry, medicine, mathematics and statistics. Discover the latest research on bioinformatics in biomedicine here.

Related Papers

IEEE Transactions on Pattern Analysis and Machine Intelligence
David GorisseFrederic Precioso
IEEE Transactions on Pattern Analysis and Machine Intelligence
Pabitra MitraSankar K Pal
IEEE Transactions on Pattern Analysis and Machine Intelligence
Mani Malek EsmaeiliMehrdad Fatourechi
IEEE Transactions on Pattern Analysis and Machine Intelligence
Bogdan MateiMartial Hebert
© 2021 Meta ULC. All rights reserved