To Project More or to Quantize More: Minimizing
Reconstruction Bias for Learning Compact Binary Codes
Zhe Wang
1,2
, Ling-Yu Duan
1
, Junsong Yuan
2
, Tiejun Huang
1
, Wen Gao
1
1
Institute of Digital Media, Peking University, Beijing, China
2
Rapid-Rich Object Search (ROSE) Lab, Nanyang Technological University, Singapore.
{zhew,lingyu,tjhuang,wgao}@pku.edu.cn, {jsyuan}@ntu.edu.sg
Abstract
We present a novel approach called Minimal Re-
construction Bias Hashing (MRH) to learn sim-
ilarity preserving binary codes that jointly opti-
mize both projection and quantization stages. Our
work tackles an important problem of how to ele-
gantly connect optimizing projection with optimiz-
ing quantization, and to maximize the complemen-
tary effects of two stages. Distinct from previous
works, MRH can adaptively adjust the projection
dimensionality to balance the information loss be-
tween projection and quantization. It is formulated
as a problem of minimizing reconstruction bias of
compressed signals. Extensive experiment results
have shown the proposed MRH significantly out-
performs a variety of state-of-the-art methods over
several widely used benchmarks.
1 Introduction
Approximate nearest neighbour (ANN) search
[
Gionis et al.,
1999a
]
plays an important role in machine learning, com-
puter vision and information retrieval. Using similarity pre-
serving binary codes to represent original data points is
of particular interest for ANN search
[
Weiss et al., 2008;
Norouzi and Fleet, 2011
]
. The binary codes can bring about
low memory cost as well as fast similarity distance computing
speed. This is particular useful when dealing with large scale
database
[
Torralba et al., 2008; Gong and Lazebnik, 2011;
Weiss et al., 2008; Duan et al., 2016
]
.
A common binary coding approach, often called Hash-
ing, is to develop similarity preserving hashing functions for
mapping data points into a Hamming space. As it is NP-
hard to directly learn the optimal binary codes
[
Weiss et
al., 2008
]
, hashing methods typically work on a two-stage
strategy: projection and quantization
[
Kong and L, 2012;
Kong et al., 2012
]
. Specifically, given a data point x 2 R
d
,
they first project x into a low dimensional vector
y =[f
1
(x), f
2
(x),...,f
k
(x)] 2 R
k
,
where real-valued functions {f
i
(·)}
k
i=1
are called projection
functions. Then they utilize Single Bit Quantization (SBQ)
to quantize each projection element f
i
(x) into a single bit by
thresholding
[
Kong and L, 2012; Wang et al., 2016
]
.
Lots of research efforts have been devoted to the first stage,
with an aim to learn powerful projections to maintain the sim-
ilarity structure of the original data points. Local Sensitive
Hashing (LSH)
[
Andoni and Indyk, 2006
]
adopts a random
projection which is independent of training data. Similarly,
Shift Invariant Kernel Hashing (SIKH)
[
Raginsky and Lazeb-
nik, 2009
]
chooses random projection and applies shifted co-
sine function to generate binary codes. Both LSH and SIKH
are data independent and flexible since they do not rely on
any training data. However, long codes are often required to
achieve satisfactory performance
[
Gong and Lazebnik, 2011;
Raginsky and Lazebnik, 2009
]
.
To build up more effective projection, many promising
data dependent methods have been proposed. Through learn-
ing the projection functions over training data, data depen-
dent methods usually outperform data independent methods
at relatively shorter codes
[
Liu et al., 2010
]
. Representa-
tive methods include Spectral Hashing
[
Weiss et al., 2008
]
,
Binary Reconstructive Embedding Hashing
[
Kulis and Dar-
rell, 2009
]
, Semi-Supervised Hashing
[
Wang et al., 2010
]
,
Anchor Graph Hashing
[
Liu et al., 2010
]
, Iterative Quan-
tization
[
Gong and Lazebnik, 2011
]
, Minimal Loss Hash-
ing
[
Norouzi and Fleet, 2011
]
, Kernal Supervised Hash-
ing
[
Liu et al., 2012
]
, Isotropic Hashing
[
Kong and Li, 2012
]
,
K-means Hashing
[
He et al., 2013
]
, Inductive Hashing on
Manifolds
[
Shen et al., 2013
]
, Harmonious Hashing
[
Xu et
al., 2013
]
, Discrete Graph Hashing
[
Liu et al., 2014
]
, Sparse
Projection Hashing
[
Xia et al., 2015
]
, etc.
Moreover, recent works have reported the impact of quan-
tization on Hashing performance. Single Bit Quantization
(SBQ) in most hashing methods incurs lots of quantization er-
rors, which would seriously degrade the performance
[
Kong
and L, 2012; Kong et al., 2012
]
. Thus, promising Multi-
ple Bits Quantization (MBQ) methods have been proposed.
Double Bits Quantization
[
Kong and L, 2012
]
divides each
projection dimension into three regions and uses double bits
code to represent each element region. Manhattan Quan-
tization
[
Kong et al., 2012
]
proposes natural binary code
(NBC) and adopts Manhattan distance to compute the dis-
tance between NBC codes. Hamming Compatible Quanti-
zation
[
Wang et al., 2015
]
aims to minimize the distance
error function to preserve the capability of similarity met-
ric between Euclidean space and Hamming space. Over-
all, MBQ methods do facilitate the reduction of information
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI-16)