There exist supervised hashing methods that can handle such semantic similarity but they are prone to overfitting when labeled data is small or noisy.Moreover, these methods are usually very slow to train.
Hashing methods can be divided into two main categories:unsupervised methods and supervised methods.
1. Unsupervised methods use just the unlabeled data X to generate binary codes for the given points.
Locality Sensitive Hashing (LSH), Spectral Hashing (SH).
2. Supervised hashing methods use with labeled data.
A Boosting Similarity Sensitive Coding (BoostSSC), Restricted Boltzmann Machines (RBMs)
In this paper propose a Semi-Supervised Hashing (SSH) technique that can leverage semantic similarity using labeled data while remaining robust to overfitting.
A supervised term tries to minimize the empirical error on the labeled data while an unsupervised term provides effective regularization by maximizing desirable properties
Semi-Supervised Hashing
Fraction of pairs are associated with two categories of label information, M and C.
M is denoted as a neighbor-pair in which xi and xj are either neighbors in a metric space or share common class labels.
C is called a nonneighbor-pair if two samples are far away in metric space or have different class labels.
Formulation
We want to learn a W that gives the same bits for (xi, xj) belong M and different bits for (xi, xj) belong C.
Define the following objective function measuring the empirical accuracy on the labeled data for a
family of hash functions H:
Defining a matrix S incorporating the pairwise labeled information from Xl as
as:
Relaxing Objective Function
Relax the balancing constraint Sigma hk(xi) = 0 by first showing that this constraint is equivalent to maximizing the variance for the kth bit
Relaxing Orthogonality Constraints
It is well known that for most real-world datasets, most of the variance is contained in top few projections. The orthogonality constraints force one to progressively pick those directions that have very low variance, substantially reducing the quality of lower bits.
Hence, instead of imposing hard orthogonality constraints, authors convert them into a penalty term added to the objective function.
Semi-supervised paradigm is to learn efficient hash codes which can handle semantic similarity/dissimilarity among the data points.
The proposed method leads to a very simple eign-decomposition based solution which is extremely efficient.
沒有留言:
張貼留言