Lavrenko, Victor

Osborne, Miles

Moran, Sean James

Engineering and Physical Sciences Research Council (EPSRC)

2017-02-20T11:43:02Z

2017-02-20T11:43:02Z

2016-06-27

This thesis is concerned with improving the effectiveness of nearest neighbour search. Nearest neighbour search is the problem of finding the most similar data-points to a query in a database, and is a fundamental operation that has found wide applicability in many fields. In this thesis the focus is placed on hashing-based approximate nearest neighbour search methods that generate similar binary hashcodes for similar data-points. These hashcodes can be used as the indices into the buckets of hashtables for fast search. This work explores how the quality of search can be improved by learning task specific binary hashcodes. The generation of a binary hashcode comprises two main steps carried out sequentially: projection of the image feature vector onto the normal vectors of a set of hyperplanes partitioning the input feature space followed by a quantisation operation that uses a single threshold to binarise the resulting projections to obtain the hashcodes. The degree to which these operations preserve the relative distances between the datapoints in the input feature space has a direct influence on the effectiveness of using the resulting hashcodes for nearest neighbour search. In this thesis I argue that the retrieval effectiveness of existing hashing-based nearest neighbour search methods can be increased by learning the thresholds and hyperplanes based on the distribution of the input data. The first contribution is a model for learning multiple quantisation thresholds. I demonstrate that the best threshold positioning is projection specific and introduce a novel clustering algorithm for threshold optimisation. The second contribution extends this algorithm by learning the optimal allocation of quantisation thresholds per hyperplane. In doing so I argue that some hyperplanes are naturally more effective than others at capturing the distribution of the data and should therefore attract a greater allocation of quantisation thresholds. The third contribution focuses on the complementary problem of learning the hashing hyperplanes. I introduce a multi-step iterative model that, in the first step, regularises the hashcodes over a data-point adjacency graph, which encourages similar data-points to be assigned similar hashcodes. In the second step, binary classifiers are learnt to separate opposing bits with maximum margin. This algorithm is extended to learn hyperplanes that can generate similar hashcodes for similar data-points in two different feature spaces (e.g. text and images). Individually the performance of these algorithms is often superior to competitive baselines. I unify my contributions by demonstrating that learning hyperplanes and thresholds as part of the same model can yield an additive increase in retrieval effectiveness.

http://hdl.handle.net/1842/20390

en

The University of Edinburgh

Moran, S. (2016). Learning to Project and Binarise for Hashing Based Approximate Nearest Neighbour Search. In ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR). Pisa, Italy.

Moran, S. and Lavrenko, V. (2014). Sparse Kernel Learning for Image Annotation. In Proceedings of International Conference on Multimedia Retrieval, ICMR ’14, pages 113:113–113:120, New York, NY, USA. ACM.

Moran, S. and Lavrenko, V. (2015). Graph Regularised Hashing. In Advances in Information Retrieval - 37th European Conference on IR Research, ECIR 2015, Vienna, Austria, March 29 - April 2, 2015. Proceedings, pages 135–146.

Moran, S. and Lavrenko, V. (2015). Regularised Cross-Modal Hashing. In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR ’15, pages 907–910. ACM.

Moran, S., Lavrenko, V., and Osborne, M. (2013). Neighbourhood Preserving Quantisation for LSH. In Proceedings of the 36th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR ’13, pages 1009–1012, New York, NY, USA. ACM.

Moran, S., Lavrenko, V., and Osborne, M. (2013). Variable Bit Quantisation for LSH. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, ACL 2013, 4-9 August 2013, Sofia, Bulgaria, Volume 2: Short Papers, pages 753–758.

Osborne, M., Moran, S., McCreadie, R., von L¨unen, A., Sykora, M. D., Cano, A. E., Ireson, N., Macdonald, C., Ounis, I., He, Y., Jackson, T., Ciravegna, F., and O’Brien, A. (2014). Real-Time Detection, Tracking, and Monitoring of Automatically Discovered Events in Social Media. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, ACL 2014, June 22-27, 2014, Baltimore, MD, USA, System Demonstrations, pages 37–42.

Ulz, M. H. and Moran, S. J. (2013). Optimal kernel shape and bandwidth for atomistic support of continuum stress. Modelling and Simulation in Materials Science and Engineering, 21(8):085017.

Locality Sensitive Hashing

LSH

image retrieval

Learning to hash for large scale image retrieval

Thesis or Dissertation

Doctoral

PhD Doctor of Philosophy