# Top Position Sensitive Ordinal Relation Preserving Bitwise Weight for Image Retrieval
## 2 Method  
### Top-Position-Sensitive Ordinal-Relation-Preserving Restriction  
We define \(X\)\(\in\)\(R^{d\times N}\) as a training dataset, which includes \(N\) samples, and \(x_{i}\)\(\in\)\(R^{d\times 1}\) is the \(i\)-th data point. Our aim is to simultaneously learn a set of hash functions and bitwise weight functions. Thus, we can map \(x_{i}\) into \(r\)-bit binary code \(b_{i}=\{h_{1}(x_{i}),\,\cdots,\,h_{r}(x_{i})\}\) and generate its bitwise weights [\(w_{1}(x_{i})\), \(\cdots\), \(w_{r}(x_{i})\)]. Here, \(h_{c}(x_{i})=sgn(u_{c}Tx_{i}+b)\) represents the \(c\)-th hash function, and \(sgn(\cdot)\) is the sign function. If \(u_{c}\leftarrow[u_{c}\ b]\) and \(x_{i}\leftarrow[x_{i}\ 1]\), we can rewrite the \(c\)-th hash function as \(h_{c}(x_{i})=\text{sgn}\ (u_{c}Tx_{i})\). Similarly, we define the \(c\)-th bit weight function as \(w_{c}(x_{i})=v_{c}Tx_{i}\), and it is sensitive to query sample \(x_{i}\). In this paper, we achieve an ANN search task in two steps [20; 21; 22; 23]. First, we retrieve nearest neighbors by Hamming distances as in most commonly used hash algorithms [1; 9; 11; 12]. Then, for data points that share the same Hamming distance to a query sample, the weighted Hamming distance \(d_{wh}(\cdot)\) is utilized to resort their ranking orders, as shown in Equation (1):  
\[d_{wh}(x_{i},x_{j})=\sum_{c=1}^{r}w_{c}(x_{i})\cdot\Big{(}b_{c}(x_{i})\otimes b _{c}(x_{j})\Big{)}. \tag{1}\]  
Therefore, to guarantee the performance of an ANN search task, the data points' ordinal relation should be well preserved in both a Hamming space and a weighted Hamming space. Generally, existing ordinal-relation-preserving restrictions treat each data point at different ranking positions  
Figure 1: Flow chart of the proposed top-position-sensitive ordinal-relation-preserving bitwise weight (TORBW) method. A tensor ordinal graph is constructed to approximate a similarity relationship of any two data pairs, and we establish a top-position-sensitive ordinal-relation-preserving restriction to improve the performance. We adopt an iterative optimization mechanism to simultaneously learn binary codes and bitwise weights. During the retrieval of approximate nearest neighbors, we utilize weighted hamming distances to resort a chaos ranking list in a Hamming space. equally [1, 13]. In contrast, evaluation standards of ANN search tasks, such as mean average precision (\(mAP\)), pay more attention to samples at the top position [25]. To achieve the above requirement, we define a top-position-sensitive ordinal-relation-preserving restriction as in Equation (2), which can effectively optimize the precision at the top position:  
\[L(x_{i},x_{j})=\log(1+R_{E}(x_{i},x_{j})+R_{H}(x_{i},x_{j})), \tag{2}\]  
where \(R_{E}\) and \(R_{H}\) represent the position of \(x_{j}\) at the ranking lists of \(x_{i}\)'s nearest neighbors in different spaces. For the loss function defined in Equation (2), its first-order derivation is larger than zero, and the second-order derivation is smaller than zero. Obviously, \(L(x_{i},x_{j})\) is a monotonic nondecreasing function, and its growth ration drastically decreases as the ranking order increases. Therefore, the loss function \(L(x_{i},x_{j})\) can penalize more of the samples without preserving its original ranking orders at the top position than those at the bottom. As defined in Equation (3), \(R_{E}(x_{i},x_{j})\) represents the ranking order of \(x_{j}\) to \(x_{i}\) in a Euclidean space:  
\[R_{E}(x_{i},x_{j})=\sum_{k=1}^{n}I(d(x_{i},x_{k})<d(x_{i},x_{j})), \tag{3}\]  
where \(d(\cdot,\cdot)\) represents the Euclidean distance. As shown in Equation (4), \(R_{H}(x_{i},x_{j})\) calculates the number of dissimilar samples with closer positions than \(x_{j}\) in a Hamming space:  
\[R_{H}(x_{i},x_{j})=\sum_{l=1}^{n}I(d_{wh}(x_{i},x_{l})<d_{wh}(x_{i},x_{j})), \tag{4}\]  
where \(d_{wh}(\cdot,\cdot)\) returns the weighted Hamming distance and \(R_{H}\) is computed on the basis of \(R_{E}\). The first question is how to compute the ranking list \(R_{E}\).