Hash Learning with Conditional Random Field and Rank Preserving Boosting

Transforming data into binary codes for Approximate Nearest Neighbor
(ANN) search has caught lots of attention in recent years. Two major advantages
of binary codes are dramatically reducing the search time and storage.
To make the codes more discriminative and more compact, it is crucial
to leverage the (partial) pair-wise label1/similarity information if provided.
However, binary code learning is an integer programming problem, which
is NP-hard. So, one promising branch of solutions is to relax the problem
into real value domain as an eigen-problem. Nevertheless, the relaxation
will introduce additional errors which will bias the learning results due to
the quadratic objective function. Hence, we treat the hash generation process
in a novel aspect, i.e., (binary) labeling problem with prior knowledge. That
is, we propose a binary code enhancement method to suppress the bias effect
resulting from eigen-based solutions, and model the problem into Conditional
Random Field (CRF). Moreover, we also adopt the boosting scheme to preserve
the distance (rank) in Hamming space. Our experimental results show
that our framework has significant improvement compared to the prior works.