# Boundary-Aware Hashing for Hamming Space Retrieval
## 3 Boundary-Aware Hashing
### Boundary-Aware Penalization  
In many previous methods [7; 23], the specific hashing model was instantiated by the Bayesian learning framework with any valid probability function. **Sigmoid function. ** As shown in Figure 3, we can observe that it is more difficult for similar points to be concentrated within the Hamming ball with radius 2. The dissimilar points are also hard to push out of the ball. The above problems may affect the Hamming space retrieval. **Cauchy distribution. ** As shown in Figure 3, for dissimilar pairs with Hamming distance less than 2, its loss approaches infinite. This makes a limited benefit on the pruning effectiveness. Furthermore, it is possible to prune out similar pairs, resulting in the decrease in recall. Following DCH [7], we use \(\mathbf{\gamma}=\mathbf{5}\) to display loss for similar/dissimilar pairs. **Max-margin \(\mathbf{t}\)-distribution. ** MMHH [9] focuses on the data distribution outside the Hamming ball and overlooks the distribution of dissimilar pairs inside the ball, making it difficult to distribute the dissimilar ones inside to the ball outside, as shown in Figure 3.  
A critical challenge for supervised hashing is that there are much fewer similar pairs than dissimilar pairs. Most previous methods reduce the imbalanced data by up-weighting similar pairs. However, this operation may severely affect the effectiveness of retrieval. With the increase in training iterations, there will be a large number of similar points accumulated in the Hamming ball and dissimilar pairs will become fewer. This will lead to a biased model for Hamming space retrieval. Obviously, this operation is not conducive to handling different sampling points inside and outside the Hamming ball. One natural way to alleviate this problem is to adjust the penalization degree of different sample points by boundary information. Motivated by contrastive loss [14], which can effectively handle pairwise data relationships, we have designed a boundary-aware penalization based on the boundary information as  
\[L=\sum_{s_{ij}\in S}\big{(}s_{ij}c_{ij}\log\big{(}1+d\big{(}b_{i},b_{j}\big{)} \big{)}+\big{(}1-s_{ij}\big{)}m\exp\big{(}H-d\big{(}b_{i},b_{j}\big{)}\big{)} \big{)}, \tag{1}\]  
where \(H=2\) is the Hamming ball radius pre-specified for the most search scenes in Hamming space retrieval, and \(m=\frac{1}{1+H}\) is a parameter to make the gradient of similar and dissimilar pairs equal on the given Hamming radius. \(d\big{(}b_{i},b_{j}\big{)}\) is the Hamming distance between a pair of hash codes \(\big{(}b_{i},b_{j}\big{)}\). \(c_{ij}\) is the cosine similarity of the labels \(y_{i}\) and \(y_{j}\) corresponding to the two images \(x_{i}\) and \(x_{j}\), i.e., \(c_{ij}=\cos\big{(}y_{i},y_{j}\big{)}\). It can effectively measure  
Figure 3: Loss function. The \(X\)-axis denotes Hamming Distance at 16 bits, and the \(Y\)-axis denotes the mapping loss at 16 bits of Hamming Distance. the degree of similarity between two multi-labels, enabling the model to effectively learn the correlation between images. The boundary-aware penalization is devised with logarithmic and exponential functions. Exponential functions with boundary information encourage large penalizing of the dissimilar pairs within the Hamming ball and small penalizing outside the ball, which discriminatively penalizes the dissimilar data inside/outside the Hamming ball. Moreover, the logarithmic function encourages similar pairs to be closer at small distances. Specifically, when the Hamming distances are 16 and 64, the similar gradient is 0.0588 and 0.0154, while the dissimilar gradient is \(2.8\times 10^{-7}\) and \(4.0\times 10^{-28}\), and the ratio of the two is approximately \(2.1\times 10^{5}\) and \(3.9\times 10^{25}\) times. This indicates that the pull is much greater than the push at the large Hamming distance and demonstrates that they play an exponential role. Therefore, similar samples can be pulled into the Hamming ball using the logarithmic function. At the small Hamming distance, the push is much greater than the pull.