Learning Hash Functions Using Column Generation

Xi Li, Guosheng Lin, Chunhua Shen, Anton Hengel, Anthony Dick
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(1):142-150, 2013.

Abstract

Fast nearest neighbor searching is becoming an increasingly important tool in solving many large-scale problems. Recently a number of approaches to learning data-dependent hash functions have been developed. In this work, we propose a column generation based method for learning data-dependent hash functions on the basis of proximity comparison information. Given a set of triplets that encode the pairwise proximity comparison information, our method learns hash functions that preserve the relative comparison relationships in the data as well as possible within the large-margin learning framework. The learning procedure is implemented using column generation and hence is named CGHash. At each iteration of the column generation procedure, the best hash function is selected. Unlike most other hashing methods, our method generalizes to new data points naturally; and has a training objective which is convex, thus ensuring that the global optimum can be identified. Experiments demonstrate that the proposed method learns compact binary codes and that its retrieval performance compares favorably with state-of-the-art methods when tested on a few benchmark datasets.

Cite this Paper

BibTeX
@InProceedings{pmlr-v28-li13a, title = {Learning Hash Functions Using Column Generation}, author = {Li, Xi and Lin, Guosheng and Shen, Chunhua and Hengel, Anton and Dick, Anthony}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {142--150}, year = {2013}, editor = {Dasgupta, Sanjoy and McAllester, David}, volume = {28}, number = {1}, series = {Proceedings of Machine Learning Research}, address = {Atlanta, Georgia, USA}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v28/li13a.pdf}, url = {https://proceedings.mlr.press/v28/li13a.html}, abstract = {Fast nearest neighbor searching is becoming an increasingly important tool in solving many large-scale problems. Recently a number of approaches to learning data-dependent hash functions have been developed. In this work, we propose a column generation based method for learning data-dependent hash functions on the basis of proximity comparison information. Given a set of triplets that encode the pairwise proximity comparison information, our method learns hash functions that preserve the relative comparison relationships in the data as well as possible within the large-margin learning framework. The learning procedure is implemented using column generation and hence is named CGHash. At each iteration of the column generation procedure, the best hash function is selected. Unlike most other hashing methods, our method generalizes to new data points naturally; and has a training objective which is convex, thus ensuring that the global optimum can be identified. Experiments demonstrate that the proposed method learns compact binary codes and that its retrieval performance compares favorably with state-of-the-art methods when tested on a few benchmark datasets.} }
Endnote
%0 Conference Paper %T Learning Hash Functions Using Column Generation %A Xi Li %A Guosheng Lin %A Chunhua Shen %A Anton Hengel %A Anthony Dick %B Proceedings of the 30th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Sanjoy Dasgupta %E David McAllester %F pmlr-v28-li13a %I PMLR %P 142--150 %U https://proceedings.mlr.press/v28/li13a.html %V 28 %N 1 %X Fast nearest neighbor searching is becoming an increasingly important tool in solving many large-scale problems. Recently a number of approaches to learning data-dependent hash functions have been developed. In this work, we propose a column generation based method for learning data-dependent hash functions on the basis of proximity comparison information. Given a set of triplets that encode the pairwise proximity comparison information, our method learns hash functions that preserve the relative comparison relationships in the data as well as possible within the large-margin learning framework. The learning procedure is implemented using column generation and hence is named CGHash. At each iteration of the column generation procedure, the best hash function is selected. Unlike most other hashing methods, our method generalizes to new data points naturally; and has a training objective which is convex, thus ensuring that the global optimum can be identified. Experiments demonstrate that the proposed method learns compact binary codes and that its retrieval performance compares favorably with state-of-the-art methods when tested on a few benchmark datasets.
RIS
TY - CPAPER TI - Learning Hash Functions Using Column Generation AU - Xi Li AU - Guosheng Lin AU - Chunhua Shen AU - Anton Hengel AU - Anthony Dick BT - Proceedings of the 30th International Conference on Machine Learning DA - 2013/02/13 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-li13a PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 1 SP - 142 EP - 150 L1 - http://proceedings.mlr.press/v28/li13a.pdf UR - https://proceedings.mlr.press/v28/li13a.html AB - Fast nearest neighbor searching is becoming an increasingly important tool in solving many large-scale problems. Recently a number of approaches to learning data-dependent hash functions have been developed. In this work, we propose a column generation based method for learning data-dependent hash functions on the basis of proximity comparison information. Given a set of triplets that encode the pairwise proximity comparison information, our method learns hash functions that preserve the relative comparison relationships in the data as well as possible within the large-margin learning framework. The learning procedure is implemented using column generation and hence is named CGHash. At each iteration of the column generation procedure, the best hash function is selected. Unlike most other hashing methods, our method generalizes to new data points naturally; and has a training objective which is convex, thus ensuring that the global optimum can be identified. Experiments demonstrate that the proposed method learns compact binary codes and that its retrieval performance compares favorably with state-of-the-art methods when tested on a few benchmark datasets. ER -
APA
Li, X., Lin, G., Shen, C., Hengel, A. & Dick, A.. (2013). Learning Hash Functions Using Column Generation. Proceedings of the 30th International Conference on Machine Learning, in Proceedings of Machine Learning Research 28(1):142-150 Available from https://proceedings.mlr.press/v28/li13a.html.

Related Material