{'fraction_non_alphanumeric': 0.04807736376552546, 'fraction_numerical': 0.016178559970667767, 'mean_word_length': 4.518462316641376, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Deep Robust Multilevel Semantic Cross-Modal Hashing

Hashing based cross-modal retrieval has recently made significant progress. But straightforward embedding data from different modalities into a joint Hamming space will inevitably produce false codes due to the intrinsic modality discrepancy and noises. We present a novel Robust Multilevel Semantic Hashing (RMSH) for more accurate cross-modal retrieval. It seeks to preserve fine-grained similarity among data with rich semantics, while explicitly require distances between dissimilar points to be larger than a specific value for strong robustness. For this, we give an effective bound of this value based on the information coding-theoretic analysis, and the above goals are embodied into a margin-adaptive triplet loss. Furthermore, we introduce pseudo-codes via fusing multiple hash codes to explore seldom-seen semantics, alleviating the sparsity problem of similarity information. Experiments on three benchmarks show the validity of the derived bounds, and our method achieves state-of-the-art performance.


Introduction
Cross-modal retrieval, aiming to search similar instances in one modality with the query from another, has gained increasing attention due to its fundamental role in large-scale multimedia applications. The difficulty of the similarity measurement of data from different modals makes this task very challenging, which is known as the heterogeneity gap [Baltrusaitis et al., 2019]. An essential idea to bridge this gap is mapping different modals into a joint feature space such that they become computationally comparable, and it is widely exploited by previous work [Xu et al., 2019;Zhen et al., 2019;Zhan et al., 2018]. Among them, hashing-based method [Liu et al., 2018;Shi et al., 2019], embedding the data of interest into a low-dimensional Hamming space, has gradually become the mainstream approach due to the low memory usage and high query speed of binary codes.
While recent works have made significant progress, there are several drawbacks still in existing cross-modal hashing methods. First, embedding different modalities data sharing the same semantic into the unified hash codes is hard, since the inherent modality discrepancy and noises will inevitably cause false codes. Nevertheless, most approaches learn to hash straightforwardly with seldom considerations for this problem. They tend to embed data of different semantics into adjacency vertexes in Hamming space, which dramatically increases the collision probability of correct and false hash codes. We illustrate this in Fig. 1 (a), the different semantics (colors) are coded as '001', '011', and '111', the conflict between the codes of data belonging to 'blue' and 'red' semantics happens. Although some work [Jiang and Li, 2017] mentioned this problem and introduced the bit balance [Wang et al., 2018] constraint for maximizing the information provided by each bit, it is too simple and leads to the burden of seeking proper hyper-parameter for effective learning. Second, the query is always complicated in real applications, involving rich semantics, e.g., multi-labels. But numerous work could not run such queries to return satisfying results that are consistent with the humans' cognition on semantic similarity. They focus on preserving simple similarity structures (i.e., similar or dissimilar) rather than more fine-grained ones, and the used similarity information is often very sparse.
We observe that if the representation ability of binary codes with fixed length is adequate, hashing functions should attempt to preserve the complete fine-grained similarity structure for more accurate retrieval. Then, we can explicitly impose the distances between codes, whose similarities are zero, to be larger or equal than a specific value δ to make the learned hash codes more robust. We call δ as robust parameter and the learned codes as robust multilevel semantic codes. As shown in Fig. 1(b), we hash three semantics into a 3-bit Hamming space according to their subtle similarity such that the distance of irrelevant semantics codes is larger or equal than 3, i.e., the 'red' and 'green' semantics, and no conflict happens. Intuitively, the larger δ is, the more robust learned codes are. We could embody this constraint in the objective of hashing learning. However, endowing too large δ is not practical due to the limited coding power of lengthfixed binary codes and the uncertainty of the hashing. The question thus becomes finding appropriate δ. In theory, as the Hamming space and the semantic similarity information are definite, the assumption that all data are well embedded, i.e., no false codes, can be helpful to reduce uncertainty and ease the derivation of the effective range of δ.
Here, we briefly describe our answer to the above question. We would like to encode semantic and similarity information of data to K-bit binary codes. The maximum number of Kbit codes with minimum pairwise Hamming distance δ is certain. According to the coding theory, the log of this number should be larger than the amount of semantic information, and the δ-bits should be able to encode the neighbor similarity information of each point. Based on these facts, we derive the bounds of proper δ and detail the process in Sec. 3.2.
Inspired by the above, we propose a novel Robust Multilevel Semantic Hashing (RMSH), which treats preserving the complete semantic similarity structure of cross-modal data with theoretically guaranteed distance constraint between dissimilar data, as the objective to learn hash functions. For this, a margin-adaptive triplet loss is adopted to control the distance of dissimilar points in Hamming space explicitly, meanwhile embedding similar points with a fine-grained level. To alleviate the sparsity problem of similarity information, we further present fusing multiple hash codes at the semantic level to generate pseudo-codes, exploring the seldom-seen semantics. The main contributions are summarized as follows.
• A novel hashing method, named RMSH, is proposed to learn the multilevel semantic-preserving codes for accurate cross-modal retrieval. Notably, to exploit the finite Hamming space for improving the robustness of learned codes, we require the distance between codes of dissimilar points satisfies larger than a specific value. For more effective hash learning, we further perform a theoretical analysis to investigate the bounds of this value. • To capture the fine-grained semantic similarity structure in coupling with the elaborated distance constraint, we present a margin-adaptive triplet loss. Moreover, a new pseudo-codes network is introduced, tailored to explore more rare and complicated similarity structures. • Extensive experimental results demonstrate the effectiveness of the derived bounds, and the proposed RMSH approach yields the state-of-the-art retrieval performance on three cross-modality datasets.

Related Work
The cross-modal hashing can be grouped into two types, unsupervised and supervised. The former utilizes the cooccurrence information of the multi-modal pair (e.g., imagetext) to maximize their correlation in the common Hamming space. The representative is Collective Matrix Factorization Hashing (CMFH) [Ding et al., 2014], which generates unified hash codes for multiple modalities by performing collec-tive matrix factorization from different views. The supervised ones aim to preserve semantic similarity. Semantic Correlation Maximization (SCM) [Zhang and Li, 2014] uses hash codes to reconstruct semantic similarity matrix. Semantics-Preserving Hashing (SePH) [Lin et al., 2015] minimizes KLdivergence between the hash codes and semantics distributions. Recently, the success of deep learning prompted the development of cross-modal hashing. Cross-Modal Deep Variational Hashing (CMDVH) [Liong et al., 2017] infers fusion binary codes from multi-modal data as the latent variable for model-specific networks to approximate. Self-supervised Adversarial Hashing (SSAH) [Li et al., 2018] incorporates the adversarial learning into cross-modal hashing. Equally-Guided Discriminative Hashing (EGDH) [Shi et al., 2019] jointly considers semantic structure and discriminability to learn hash functions. Despite their effectiveness, most of them ignore the exploitation of limited representative of binary codes for reducing the impact of the modality gap.

The Proposed Approach
In this section, we fist give the problem definition and effective bounds of the defined robust parameter in Sec. 1. Then, the configurations of the proposed RMSH are detailed, including two hashing networks, a pseudo-code network, and the corresponding objective function. An overview of the RMSH is illustrated in Fig. 2.

The Problem Definition
Assume that we are given a multi- denotes the image modality, text modality, and corresponding semantic labels, respectively. x i can be features or raw pixels of images, y i is textual description or tags; label l i ∈ {0, 1} C . The cross-modal similarity S is defined as S ij = |li∩lj | max{|li|,|lj |} . Given training data X, Y and S, our goal is to learn two hash functions: h (x) (x) = b (x) ∈ {−1, 1} K for the image modality and h (y) (y) = b (y) ∈ {−1, 1} K for the text modality such that the similarity relationship S is preserved and distances between dissimilar data are larger or equal than a positive integer δ for robustness, i.e., ∀ x i ∈ X, y j , y k ∈ Y, if S ij ≥ S ik , then the Hamming distance of their binary codes should satisfy Intuitively, a larger δ makes codes more robust, but it cannot be too large due to the finite representation power of K-bit binary codes. In what follows, we investigate how to properly set this parameter to obtain the balance between robustness and compactness.

Bounds of Robust Parameter
In essential, supervised hashing is encoding semantic information H(L L L) and similarity information H(S * ,: S * ,: S * ,: ) of data 1 , where H denotes entropy function. According to the coding theory, we have facts: (1) the number of K-bit codes    1) image/text hashing for converting image/text description into K-bit hash codes; (2) pseudo-codes for imbalanced data; (3) a margin-adaptive triplet loss with derived distance constraint of dissimilar data for preserving fine-grained semantic similarity relationship in the Hamming space and robustness to the modality discrepancy.
satisfying minimum distance δ should be larger than 2 H(L L L) to make sure that different semantics have unique codes; (2) δ bits should be able to encode the neighborhood semantic similarity information H(S * ,: S * ,: S * ,: ) of each sample. For simplicity's sake, let's assume that all data sharing the same semantic are embedded into the same codes. Based on above facts and assumption, we can derive the bounds of δ as follows. 1) Upper bound. We first give some definitions. Definition 1. A(K, δ) denotes the maximum number of K-bit binary codes with pairwise minimum Hamming distance δ.
denotes the set of vectors with distance from the x less than or equal to r and is defined as B K r (x) = {y ∈ Ω|d H (y, x) ≤ r}. By the fact (1), we have 2 H(L L L) ≤ A(K, δ). Then the question becomes estimating A(K, δ). However, an accurate estimation of A(K, δ) is challenging, which is still unsolved. Alternatively, its bounds are well studied [Helgert and Stinaff, 1973]. Towards our goal, we thus introduce a well-known lower-bound of A(K, δ) to derive the upper-bound of the robust parameter. Lemma 1. (Gilbert-Varshamov Bound [Gilbert, 1952]). Given δ, K ∈ N be such that r ≤ K, we have: Since the computation of is hard, we further give the entropy bound on the volume of a Hamming ball. Lemma 2. (Volume of Hamming ball). Given r, K ∈ N and r = pK, p ∈ [0, 1/2], we have: By above Lemmas 1 and 2, we give the main theorem about the upper bound of robust parameter in our problem. Theorem 1. For information H(L L L), if using K-bit binary codes to encode l ∈ L L L such that for ∀ l i = l j , d H (b i , b j ) ≥ δ, δ ≤ K/2, then, δ should satisfy: Proof. By the the fact (1) and Eq. (1) (2), we can obtain the above result.
We  (2) we have δ ≥ max * =1:N {H * }. However, as S is sparse, we could relax this by making the δ be larger than most H * to ensure δ bits can encode the semantic neighbors of each sample with a certain probability. By Chebyshev's Inequality, we have: If P {H * ≤ δ} = p, we have: We estimate H i = − |li| j=1 p(s i = j |li| ) log p(s i = j |li| ), p(s i = j |li| ) = * I(Si, * =j/|li|) * I(|li∩l * |=Si, * ·|li|) , s i ∈ S i,: . Combing Eq. (5) and Eq. (3), we obtain the final bounds of effective robust parameter. The experimental results in Sec. 4.3 demonstrate the effectiveness of derived bounds.

Network Architecture
We build image and text hashing as two deep neural networks via adding two fully-connected layers with tanh function on the top feature layer of commonly-used specific-modality deep models, e.g., CNN model ResNet for image modality, BOW or sentence2vector for text modality. These two layers as the hash functions transform the feature x i , y i into binarylike codes z , we propose pseudocodes networks to manipulate the binary-like codes at the semantic level for generating codes of rare semantics, which are mixed with original codes to explore complicated similarity structure. We defined two types of code operation, i.e., union and intersection, as two fully-connected networks: where [·, ·] denotes the concatenation operation. W u , W t ∈ R K×2K are weights to be learnt. z 1⊕2 = f u (z 1 , z 2 ) with label l u = l 1 ⊕ l 2 = l 1 ∪ l 2 . z 1⊗2 = f t (z 1 , z 2 ) with label l t = l 1 ⊗ l 2 , defined as l 1 ∩ l 2 .

Objective Function
To preserve multilevel semantic similarity and fully exploit the space between dissimilar points in Hamming space, we formulate the goal in Sec 3.1 as follows: We couple these two goals in the scheme of margin-adaptive triplets, that is: , is adaptive to the discrepancy of similarity and δ controls the distance of dissimilar points. Given a triplet of multi-modal data x {1,2,3} , y {1,2,3} and their labels l {1,2,3} , we can obtain five hash codes for each modality, i.e., b {1,2,3} , and . We partition them into the intra-modality triplets b {1,2,3} , b {1,2,4} , b {1,2,5} , and the inter- {1,2} }, each of which reflects some aspect of the similarity structure and corresponds to a separate loss term in the final loss.
The final triplet loss for one modality is defined as: where λ 1 , λ 2 control the weight of intra-modal and intermodal similarity loss, respectively. Besides, we adopt weighted cross-entropy loss to ensure that each individual hashing codes consistent with its own semantics, especially for the pseudo-codes from fusion, and the loss is defined as follows: wherel is the predicted value of RMSH, and w p is the weight of positive samples. Finally, the overall objective for N training triplets where λ 3 balances the classification loss of pseudo-codes, θ x , θ y are parameters of image and text hashing, respectively.

Optimization
Since the Eq. (10) is a discrete optimization problem, we relax b as z by introducing quantization error ||z − b|| 2 2 , and substitute Hamming distance with Euclidean distance, i.e. d H (b 1 , b 2 ) = ||b 1 − b 2 || 2 2 . The Eq. (10) is hence rewritten as follows: ). λ 4 controls the weight of quantization error. In the training phase, for better performance. We adopt alternating optimization to learn θ x , θ y , and b.
1) Learn θ x and θ y with b fixed. When b are fixed, the optimization for θ x and θ y is performed using stochastic gradient descent based on Adaptive Moment Estimation (Adam).
2) Learn b with θ x and θ y fixed. When θ x and θ y are fixed, we can obtain the closed-form solution of bi.e., b i = sgn(z

Datasets
Microsoft COCO contains 82,783 training and 40,504 testing images. Each image is associated with five sentences (only the first sentence is used in our experiments), belonging to 80 most frequent categories. We use all training set for training and sample 4,956 pairs from the testing set as queries.
MIRFLICKR25K [Huiskes and Lew, 2008] contains 25,000 image-text pairs. Each point associates with some of 24 labels. We remove pairs without textual tags or labels and subsequently get 18,006 pairs as the training set and 2,000 pairs as the testing set. The 1386-dimensional bag-of-words vector gives the text description. NUS-WIDE [Chua et al., July 8 10 2009] contains 260,648 web images, belonging to 81 concepts. After pruning the data without any label or tag information, only the top 10 most frequent labels and the corresponding 186,577 text-image pairs are kept. 80,000 pairs and 2,000 pairs are sampled as the training and testing sets, respectively. The 1000-dimensional bag-of-words vector gives the text description. We sampled 5,000 pairs of the training set for training.

Evaluation protocol and Baselines
Evaluation protocol. We perform cross-modal retrieval with two tasks. (1) Image vs. Text (I vs. T): retrieve relevant data in the text training set using an image query. (2) Text vs. Image (T vs. I): retrieve relevant data in the image training set using a text query. We adopt the commonly-used Normalized Discounted Cumulative Gain (NDCG) [Järvelin and Kekäläinen, 2000] as the performance metric.  Baselines. We compare our RMSH with five cross-modal hashing methods CMFH [Ding et al., 2014], SCM [Zhang and Li, 2014], SePH [Lin et al., 2015], SSAH [Li et al., 2018]. For a fair comparison, all non-deep methods take the deep off-the-shelf features as inputs, and all deep models are implemented carefully with the same CNN sub-structures for image data and the same multiple fully-connect layers for textual data. The parameters of all baselines are set according to the original papers or experimental validations. Implementation details. Our RMSH method is implemented with Tensorflow. We use ResNet [He et al., 2016] pre-trained on ImageNet as the CNN model in image hashing. For MS COCO dataset, the 4800-dimensional Skip-thought vector [Kiros et al., 2015] gives the sentence description. The structure of two hashing layers are 1024 → K-bit length.

Experimental Results
Comparisons with state-of-the-arts. Table 1 reports the NDCG@500 results. From Table 1, we observe that the RMSH method substantially outperforms other compared methods on all used datasets. Specifically, compared to the best deep method SSAH, the RMSH obtains the relative increase of 2.1%∼7.8%, 0.8%∼5.1%, and 0.1%∼10% for different bits on MIRFLICKR25K, NUS-WIDE, and MS COCO datasets, respectively. Because the SSAH is learning to preserve the binary cross-modal similarity structures, its hashing codes cannot capture the fine-grained ranking information, thus achieve inferior NDCG scores. In contrast, the RMSH learns the more complicated similarity with more robustness to the modality discrepancy.
To visualize the quality of learned codes by RMSH, we use t-SNE tools to embed the 128 bits testing binary-like features of NUS-WIDE datasets into 2-dimension spaces and visualize their distribution in Fig. 3. As can be seen, both image and text features provide a better separation between different categories. Also, the features belonging to the same class from different modalities appear to be compact. These results indicate the RMSH well preserves the semantic similarity of both intra-modal and inter-modal.
Impact of robust parameter δ. To validate the correctness of the derived bounds of robust parameter δ in Sec. 3.2, we separately tune δ in {K/40, K/20, K/8, 3K/20, K/4, K/3, K/2, 2K/3 } with other parameters fixing and report the retrieval performance in Fig. 4, where K=128. We also maker the bounds of δ derived by Eq. (3) and (5). We see that the RMSH method performs better at the range of bounds on all datasets. This result experimentally proves the correctness of the bounds for robust cross-modal hash learning.
Besides, Fig. 5 shows the distribution of the Hamming distance of learned codes by RMSH. We observe that 1) too small δ makes the dissimilar points be more nearly, which cause the difficulties of keeping multilevel similarity structure of the similar points; 2) too large δ prefer to scatter dissimilar points in the whole Hamming space, which is cline to cause false coding since the number of different codes that satisfy the distance constraint is limited.
Ablation Study. To analyze the effectiveness of different loss terms and the pseudo-codes codes in the proposed RMSH method, we separately remove: L cl , L tr and pseudocodes with others remained to evaluate their influence on the final performance. These three models are called RMSH-NC, RMSH-NT, and RMSH-NP. Fig.6 shows the result. We see that separately removing them will damage the retrieval performance to varying degrees. Notably, 1) the performance gap between RMSH and RMSH-NT is enlarged with bits increasing on MIRFLICKR25K, which confirms the importance of robust parameter for exploiting Hamming space. 2) Because the similarity information on MS COCO (80 con- cepts) is more sparse, the improvement introduced by the strategy of the pseudo-codes is more significant.

Conclusion
We have presented a novel robust multilevel semantic hashing for cross-modal retrieval. The approach preserves the multilevel semantic similarity of data and explicitly ensures the distance between different codes is larger than a specific value for robustness to the modality discrepancy. Mainly, we give an effective range of this value from the information coding theory analysis and characterize the above goal as a marginadaptive triplet loss. We further introduce a pseudo-codes network for the imbalanced semantics. Our approach yields the state-of-the-art empirical results on three benchmarks.