Patent Publication Number: US-11651037-B2

Title: Efficient cross-modal retrieval via deep binary hashing and quantization

Description:
RELATED APPLICATIONS 
     This application claims the benefit of U.S. Provisional Application No. 62/952,090 filed on Dec. 20, 2019, and titled “Efficient Cross-Modal Retrieval via Deep Binary Hashing and Quantization,” the contents of which are incorporated by reference herein as if fully disclosed herein. 
    
    
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     This invention relates generally to using neural networks for cross-modal data retrieval and, more specifically, to a more efficient cross-modal retrieval system that uses both deep binary hashing and quantization. 
     2. Description of the Background Art 
     With the expansion of multimedia data, approximate nearest neighbor search across different content modalities has gained huge attention. Cross-modal retrieval aims to search for data with similar semantic meaning across different content modalities. An example of cross-modal data retrieval is to match a photo to a text that correctly describes the photo. 
     There are various known methods for cross-modal retrieval. In some methods, dense feature vectors are generated for data items of different modalities, and various search and ranking algorithms, such as cosine similarity search, are then applied to the dense feature vectors to identify semantically similar items across modalities. (See Amit Singhal, Modern information retrieval: A brief overview,  Bulletin of the IEEE Computer Society Technical Committee on Data Engineering , pages 34-43, 2001). Hand-crafted statistics and various deep neural networks are used extract dense features. However, searching and ranking based on dense feature representations suffers from limitations in memory and computational efficiency. 
     To solve the efficiency issue, various coding methods have been proposed for cross-modal retrieval. In these methods, a coded representation of each data item is created from extracted features of the item. Some methods involve generating binary codes for data items given hand-crafted features and calculating the distances between items based on the binary codes. (See Shaishav Kumar and Raghavendra Udupa, Learning hash functions for cross-view similarity search,  IJCAI  pages 1360-1365, 2001. See also Yi Shen and Dit-Yan Yeung, A probabilistic model for multi-modal hash function learning, KDD, pages 940-948, 2012). While these methods are more computationally efficient than searching based on dense feature vectors, they are less accurate due to the limited ability of binary codes to express data. To overcome this limitation, some methods use quantization codes instead of binary codes. (See Yue Cao, Mingsheng Long, Jianmin Wang, and Shichen Liu, Collective deep quantization for efficient cross-modal retrieval,  AAAI , pages 3974-3980, 2017. See also Erkun Yang, Cheng Deng, Chao Li, Wei Liu, Jie Li, and Dacheng Tao, Shared predictive cross-modal deep quantization,  IEEE Transaction on Neural Networks and Learning Systems,  2019). Since quantization codes are continuous values, they are able to better express the underlying data, resulting in more accurate retrieval. However, quantization-based methods suffer with respect to computational efficiency as compared to binary hashing. Therefore, there is demand for a cross-modal retrieval system that is more accurate than known binary-code-based methods and more computationally efficient than known quantization-code-based methods. 
     SUMMARY OF THE DISCLOSURE 
     The present disclosure relates to a new method for cross-modal retrieval via deep binary hashing and quantization. The method is performed by a computer system. In a training phase, the system simultaneously learns neural network models, a binary hash algorithm, and a quantization algorithm that collectively enable the system to generate feature vectors, binary hash codes, and quantization codes across two or more data modalities, where semantic similarity correlations in the underlying data are preserved in these data representations. Specifically, the system applies neural networks to labeled training data of different modalities to generate feature vectors for the training data, and uses a binary hash algorithm and a quantization algorithm to generate the binary hash codes and quantization codes, respectively, for the training data from the feature vectors. The training data comprises pairs of data items labeled as similar or dissimilar, where each pair includes at least two data items of different modalities. A well-defined loss function is used to ensure that the learned features and codes preserve the similarity or dissimilarity correlations between training data items across the modalities. In one embodiment, the loss function comprises four parts: (1) a cross-entropy loss that measures similarities between different modalities based on dense feature vectors; (2) a quantization loss that measures differences between dense feature vectors and quantized features; (3) a binary hashing loss that measures differences between dense features vectors and binarized features; and (4) a balance loss to optimize bit information in binary code. For a number of iterations, the system generates feature vectors, binary hash codes, and quantization codes for the training data, calculates a loss value based on these representations, and then updates the parameters of the neural networks, binary hash algorithm, and quantization algorithm to minimizing the loss value. In this way, the system simultaneously learns the neural network models, binary hash algorithm, and quantization algorithm that will preserve sematic similarity correlations across the data modalities. 
     In a prediction phase, the system retrieves a data item in a database that is semantically similar to a query item of a different modality. The data modalities at issue in the prediction phase are the same as those in the training phase. To identify the database item closest in semantic meaning to the query item, the system first narrows the database search space based on binary hash code distances between each of the database items and the query item. The binary hash codes for the query item and the database items are generated based on the neural networks and binary hash algorithm trained in the training phase. The system then measures the similarity between the query items and the data in the smaller search space using quantization codes generated for the database items in the smaller search space (based on the quantization algorithm trained in the training phase). The system retrieves the closest database item identified using the quantization codes as the closest semantic match to the query item. 
     The advantages of this method are at least twofold:
         (1) Retrieval efficiency: By narrowing down the search space using simple binary codes, the retrieval process is significantly sped up as compared to methods that search based on only dense feature vectors or quantization codes; and   (2) Retrieval quality: The feature learning is constrained with hashing and quantization loss. While quantization learns a limited number of continuous feature representations, binary hashing discretizes the features. The combination of these two coding methods acts as a regularization in feature learning and enables the system to learn good data representations that preserve similarity or dissimilarity across data modalities.       

    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG.  1    is a flowchart that illustrates a method, according to one embodiment, for training a system to perform cross-modal data retrieval using binary hashing and quantization codes. 
         FIGS.  2 A-B  are flowcharts that illustrate a method, according to one embodiment, for cross-modal retrieval using binary hashing and quantization codes. 
         FIG.  3 A  is a diagram that illustrates a pictorial example of the training process. 
         FIG.  3 B  is a diagram that illustrates a pictorial example of the prediction phase. 
         FIG.  4    is a block diagram of an example system for performing cross-modal data retrieval using binary hashing and quantization codes. 
     
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     The present disclosure relates to a system, method, and computer program for cross-modal retrieval via deep binary hashing and quantization. The methods disclosed herein are performed by a computer system (“the system”). 
     The method includes a training phase and a prediction phase. In the training phase, the system simultaneously learns to generate feature vectors, binary codes, and quantization codes for data across two or more modalities that preserves the semantic similarity correlations in the original data. Preserving semantic similarity correlations includes preserving both similarity and dissimilarity relationships (as applicable) between data items. In the prediction phase, the system retrieve a data item in a database that is semantically similar to a query item of a different modality using both binary hashing and quantization. The data modalities involved in the prediction phase are the same as in the training phase. 
     The training and prediction phases each may be performed by different entities (e.g., a computer system at one entity may train the models, and a computer system at another entity may use the trained models to perform cross-modal retrieval). Therefore, the term “system” herein may refer to a system that performs both phases, or, in the training phase description, it may refer to the system that performs only the training phase, and, in the prediction phase description, it may refer to the system that performs only the prediction phase. Regardless, each of these phases is performed by a computer system. Both the training phase and the prediction phase are described in more detail below. 
     1. Training Phase 
     The training method is described with respect to  FIG.  1    and  FIG.  3 A .  FIG.  1    illustrates a method for training a system to perform cross-modal data retrieval using binary hashing and quantization.  FIG.  3 A  is a pictorial example of the training method according to one embodiment. In the depicted example, the two data modalities are images and text, but the method is not limited to these modalities. 
     1.1 Training Data 
     The system obtains a training data set with pairs of data items of different modalities (step  110 ). Specifically, each pair includes a data items of a first modality and a data item of a second modality, wherein the first and second data modalities are different. Examples of data modalities are text, images, video, etc. For example, one item in the pair may be a text item and the other item may be an image or a video. 
     The pairs are associated with a label that indicates whether the pairs are semantically similar. In one embodiment, the pairs are labeled in a binary fashion simply as similar or dissimilar. For example, a pair with the text “dog” and a photo of a dog would be labeled similar (or a numeric representation of similar, such as “1”), and a pair with the text “car” and a photo of the dog would be labeled as “dissimilar” (or a numeric representation of dissimilar, such as “0”). In other embodiments, a more gradual scale is used to indicate the degree of similarity. For example, there may a scale from 0-5, where 0 indicates most dissimilar and 5 indicates most similar. In such case, a pair with the text “donut” and a photo of a donut may be labeled with a “5”, while a pair with the text “food” and a photo of donut may be labeled “3”, and a pair with the text “cat” and a photo of a donut may be labeled as “0”. 
     1.2 Generating Feature Vectors 
     Neural networks are used to generate feature vector representations of the training data items. Specifically, the system applies a first neural network to data items of the first modality in the training data set to generate a feature vector for each of these items (step  120 ). Likewise, the system applies a second neural network to data items of the second modality in the training data set to generate a feature vector for each of these items (step  130 )). For example, in  FIG.  3 A , neural network  320  generates a feature vector f i  for each input training image  310 , and neural network  340  generates a feature vector f j  for each input training text item  330 . In certain embodiments, a convolutional neural network is applied to image or video data items, and a long short-term neural network (LSTM) or multilayer perceptron is applied to text data. In certain embodiments, the feature vectors are dense feature vectors. 
     1.3 Generating Binary Hash Codes and Quantization Codes 
     As described in more detail below, the system generates a binary hash code and a quantization code for each of the training data items from the feature vector for the item (step  140 ). 
     1.3.1 Binary Hashing Given feature vector x∈R n  for a data item, the system computes a binary hashing code h x =H(x)∈R n , where HO is a function that maps continuous value to {+1,−1}. For example, in  FIG.  3 A , binary hash code h i  is generated based on image feature vector f i , and binary hash code h j  is generated based on text feature vector f j . 
     1.3.2 Quantization 
     Given feature vector x∈R n  for a data item, the system computes a quantization code Cb x ≈x, where C∈R n×k  is the dictionary book for quantization, and b x  is the index indicator or quantization code that indicates a column in the dictionary book. In certain embodiments, the system assumes that the input can belong to only one of the dictionaries (i.e., ∥b x ∥ 0 =1). In  FIG.  3 A , quantization code b i  is generated based on image feature vector f i , and quantization code b j  is generated based on text feature vector f j . 
     1.4 Simultaneously Optimizing Feature Vectors, Binary Hash Codes, and Quantization 
     As described below, the system iteratively generates features vectors, binary hash codes, and quantization codes for the training data (step  120 - 140 ), calculates a loss value based on these representations (step  150 ), and adjusts the parameters of the neural networks, binary hash algorithm, and quantization algorithm to minimize the loss value (step  160 ). The system uses a loss function that measures the extent to which the learned features and the binary hash and quantization codes preserve the semantic similarity correlations between training data items across modalities (e.g., the hash codes and quantization codes for two semantically similar data items are trained to be similar). 
     In one embodiment, the loss function comprises four parts: (1) a cross-entropy loss that measures similarities between different modalities based on dense feature vectors; (2) a quantization loss that measures differences between dense feature vectors and quantized features; (3) a binary hashing loss that measures differences between dense features vectors and binarized features; and (4) a balance loss to optimize bit information in binary code. This type of loss function enables the system to simultaneously optimize the feature vectors, binary hash codes, and quantization codes. 
     The equations below provide an example of how a loss function with the four parts (i.e., four sub-functions) described above may be defined. For the equations below, we define a training pair as having data items i, j that come from different modalities. The data items have dense representations features f i , f i , and the pair has the similarity label s ij , where s ij =1 means items i, j are similar, and s ij =0 means items i, j are dissimiliar. Examples of each of the four sub-functions are set forth below: 
     Similarity loss: To measure the similarity between different modalities, the Maximum a Posteriori (MAP) estimation may be used. The logarithm MAP is
 
log  p ( f   i   ,f   i   |s   ij )∝ log  p ( s   ij   |f   i   ,f   i ) p ( f   i ) p ( f   i )  (1)
 
     In equation 1, the conditional likelihood for similarity label s ij  is: 
     
       
         
           
             
               
                 
                   
                     p 
                     ⁡ 
                     ( 
                     
                       
                         
                           s 
                           ij 
                         
                         | 
                         
                           f 
                           i 
                         
                       
                       , 
                       
                         f 
                         j 
                       
                     
                     ) 
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               σ 
                               ⁡ 
                               ( 
                               
                                 
                                   
                                     f 
                                     i 
                                   
                                 
                                 , 
                                 
                                   
                                     f 
                                     j 
                                   
                                 
                               
                               ) 
                             
                           
                           
                             
                               
                                 s 
                                 ij 
                               
                               = 
                               1 
                             
                           
                         
                         
                           
                             
                               1 
                               - 
                               
                                 σ 
                                 ⁡ 
                                 ( 
                                 
                                   
                                     
                                       f 
                                       i 
                                     
                                   
                                   , 
                                   
                                     
                                       f 
                                       j 
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                           
                             
                               
                                 s 
                                 ij 
                               
                               = 
                               0 
                             
                           
                         
                       
                       = 
                       
                         
                           
                             σ 
                             ⁡ 
                             ( 
                             
                               
                                 
                                   f 
                                   i 
                                 
                               
                               , 
                               
                                 
                                   f 
                                   j 
                                 
                               
                             
                             ) 
                           
                           
                             s 
                             ij 
                           
                         
                         ⁢ 
                         
                           
                             ( 
                             
                               1 
                               - 
                               
                                 σ 
                                 ⁡ 
                                 ( 
                                 
                                   
                                     
                                       f 
                                       i 
                                     
                                   
                                   , 
                                   
                                     
                                       f 
                                       j 
                                     
                                   
                                 
                                 ) 
                               
                             
                             ) 
                           
                           
                             1 
                             - 
                             
                               s 
                               ij 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
     Where 
               σ   ⁡   (   x   )     =     1   /     (     1   +     e     -   x         )             
is the sigmoid function, and  x,y  is the inner product operation. Assuming the prior for f i  and f i  is known, the cross entropy loss term, denoted L sim , may be expressed as:
 
     
       
         
           
             
               
                 
                   
                     L 
                     sim 
                   
                   = 
                   
                     
                       ∑ 
                       ij 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       ( 
                       
                         
                           log 
                           ⁡ 
                           
                             ( 
                             
                               1 
                               + 
                               
                                 e 
                                 
                                   〈 
                                   
                                     
                                       f 
                                       i 
                                     
                                     , 
                                     
                                       f 
                                       j 
                                     
                                   
                                   〉 
                                 
                               
                             
                             ) 
                           
                         
                         - 
                         
                           
                             s 
                             
                               i 
                               , 
                               j 
                             
                           
                           ⁢ 
                           
                             〈 
                             
                               
                                 f 
                                 i 
                               
                               , 
                               
                                 f 
                                 j 
                               
                             
                             〉 
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
     Hash Loss: A hash loss function minimizes binary code error. Given the binary code h∈{+1,−1}, where n is the binary code length, the hash loss, denoted L h , may be expressed as:
 
 L   h =Σ ij (∥ f   i   −h   i ∥ F   2   +∥f   j   −h   j ∥ F   2 )  (4)
 
     Balance Loss: A balance loss function optimizes the bit information in binary code (so that bit information is used maximally). The balance loss, denoted L b , may be expressed as follows:
 
 L   b =Σ ij   ∥f   i 1∥ F   2   +∥f   j 1∥ F   2 )
 
     Where 1 is a vector of 1s. It balances the number of +1 and −1 in each training sample, 
     Quantization Loss: To minimize quantization error, the system uses multiple dictionary books and sums over their results: 
               f   ≈       ∑     l   =   1     m         C   l     ⁢     b   l           ,         
where each dictionary book C l ∈   n=k  binary indicator b l ∈{0,1} k , and ∥b l ∥ 0 =1. The quantization loss, denoted L q , may be expressed as follows:
 
     
       
         
           
             
               L 
               q 
             
             = 
             
               
                 ∑ 
                 
                   i 
                   , 
                   j 
                 
               
               
                 ( 
                 
                   
                     
                        
                       
                         
                           f 
                           i 
                         
                         - 
                         
                           
                             ∑ 
                             
                               l 
                               = 
                               1 
                             
                             m 
                           
                           
                             
                               C 
                               l 
                             
                             ⁢ 
                             
                               b 
                               i 
                               l 
                             
                           
                         
                       
                        
                     
                     F 
                     2 
                   
                   + 
                   
                     
                        
                       
                         
                           f 
                           j 
                         
                         - 
                         
                           
                             ∑ 
                             
                               l 
                               = 
                               1 
                             
                             m 
                           
                           
                             
                               C 
                               l 
                             
                             ⁢ 
                             
                               b 
                               j 
                               l 
                             
                           
                         
                       
                        
                     
                     F 
                     2 
                   
                 
                 ) 
               
             
           
         
       
     
     Combining these four loss sub-functions, results in the following loss function L:
 
 L=l   sim   L   sim   +l   h   L   h   +l   b   L   b   +l   q   L   q  
 
     Where l sim , l h , l h , l q  are hyperparameters to balance between the different loss sub-functions. 
     After calculating a loss value, the system adjusts the parameters of the neural network, the binary hash algorithm, and the quantization algorithm to reduce the loss value. In other words, the system adjusts the parameters of the neural network, the binary hashing code h, the dictionary book C, and the quantization code b to reduce the loss value. Steps  120 - 160  are repeated for a number of iterations to reduce (and preferably minimize) the binary hash code distances and quantization code distances between data items in a pair labeled as similar (or most similar in a gradual scale) (step  170 ). In each successive iteration, new feature vectors, binary hash codes, and quantization codes are generated based on the adjustments made to the neural networks, binary hash algorithm, and quantization algorithm in the proceeding iteration. Steps  120 - 160  may be repeated for a fixed number of iterations or until convergence is achieved. 
     2. Prediction Phase 
       FIGS.  2 A- 2 B  illustrate a method for cross-modal retrieval of a database item having similar semantic meaning to a query item of a different modality using binary hashing and quantization. In the prediction phase, the system uses the neural networks, binary hash algorithm, and quantization algorithm trained in the training phase. The data modalities in the prediction phase are the same as the data modalities in the training phase. For purposes of this description, the database items are of the first modality (same as first modality in the training phase) and the query item is of the second modality (same as the second modality in the training phase). 
     2.1 Generating Binary Hash Codes and Quantization Codes for Database Items of a First Modality 
     The system accesses a database with a plurality of database items of the first modality (step  210 ). The system applies the first neural network to the database items to generate a feature vector for each of the database items (step  220 ). The system generates a binary hash code and a quantization code for each of the database items using the feature vectors for the database items, the binary hash algorithm, and the quantization algorithm (step  230 ). The first neural network and the binary hash and quantization algorithms used in these steps were trained in the training phase. 
     As stated above, in certain embodiments, systems at different entities may perform the training and prediction phases. The steps of creating binary hash codes and quantization codes for the database item may be performed by the same system that performs the training, and the system that performs the prediction phase may simply access a database that already has binary hash codes and quantization codes associated with the database items. 
     2.2 Receiving a Query Item of a Second Modality 
     The system performing the prediction phase receives a query item of the second modality and applies the second neural network to the query item to generate a feature vector for the query item (steps  240 ,  250 ). The system then generates a binary hash code for the query item based on the feature vector and the binary hash algorithm (step  260 ). In certain embodiments, the system also will generate a quantization code for the query item, depending on whether quantization distance or asynchronous quantization distance (AQD) is used to measure similarities between items based on quantization codes (discussed below). 
     2.3 Narrowing the Search Field Using Binary Hash Codes 
     The system calculates a distance (i.e., a similarity measure) between the query item and each of the database items based on the binary hash codes of the query item and the database items (step  260 ). In one embodiment, the similarity measure is a Hamming distance: dist(h x , h y )=sum(h x XORh y ), where h x  and h y  are the binary hash codes for query item x and database item y. The larger the value of the Hamming distance, the more semantically dissimilar items x and y are. The system then narrows the database search space by selecting a subset of database items for further processing. Specifically, the system selects a number of semantically closest database items to the query item based on the distances calculated in step  270  (step  275 ). 
     2.4 Identifying the Database Item with the Closest Semantic Similarity Based on Quantization Codes 
     The system then computes a quantization distance between the query item and each of the database items in the narrower search space (i.e., each of the database items in the selected subset (step  280 )). The quantization distances are calculated using the quantization codes associated with each of the subset of database items and either the feature vector for the query item or a quantization code for the query item. If the feature vector of the query item is used in this step, then Asymmetric Quantizer Distance(AQD) may be used to measure similarities: AQD(x, y)=f x   T (Cb y ), 
     where: 
     x is the query item and y is the database item; 
     f x  is the feature vector for x; 
     T is transpose operation; 
     where C ∈ is the dictionary book for quantization; and 
     and b y  is the index indicator that indicates a column in the dictionary book 
     As the AQD calculation involves computing the inner product between feature vector x and the quantization code y, the larger the AQD value, the closer the quantization distance between x and y is, and the more similar x and y are. 
     If a quantization code is used for the query item in this step, the quantization distance (QD) may be used to measure similarities: QD(x, y)=(Cb x ) T (Cb y ). The larger the QD value, the smaller the quantization distance between two items, and the more similar the items are. 
     The system retrieves the database item with the closest quantization distance to the query item, as this is considered the database item with the closest semantic meaning the query item (step  290 ). 
     2.5 Pictorial Example of Prediction Phase 
       FIG.  3 B  depicts a pictorial example of the prediction process according to one embodiment. In this example, the system finds a matching text description from a database  365  for image query item  350 . Neural network  360  generates a feature vector f for the image query item  350 . Binary hash code h is then computed based on the feature vector. The process then proceeds as follows: 
     (1) The system computes the Hamming distance between the image query item and each of the text database items using binary hash codes for the image query items and each of the database items (binary hash codes  370  are associated with text database  365 ). 
     (2) The system narrows the search space by selecting a subset of database items  375  with closest Hamming distance to the image query item  360 . 
     (3) The system computes the AQD value between the image query item and each of the subset of text items using feature vector f for the query item and the quantization codes  380  for the text database items in the subset. 
     (4) The system retrieves the text database item with the closest quantization distance to the image query item based on the AQD values. The larger the AQD value for the query item and a database item, the closer the quantization distance between the items, and closer the items are semantically. 
     3. Example System 
       FIG.  4    illustrates an example software architecture for a system for performing cross-modal retrieval in accordance with the methods described herein. Other software architectures may be used, and the methods described herein are not limited to the illustrated architecture. The system  400  includes a data representation module  430  that includes neural networks  450 , binary hashing module  460 , and quantization module  470 . As described above, these modules respectively generate feature vectors, binary hash codes, and quantization codes for database items  410  and query item  420 . These modules are trained by training module  490  using training data  405  in accordance with the training method discussed above. There is one neural network module  450  for each type of data modality handled by the system. 
     Query module  480  identifies and retrieves the item in database  410  that is semantically closest to query item  420  in accordance with the prediction process described above. In this example, query module  480  includes Hamming distance module  484  and AQD module  488 , which respectfully calculate Hamming distances and asynchronous quantization distances between the query item and database items. Database interface  415  enables the system to interface with database  410 . 
     5. General 
     The methods described with respect to  FIGS.  1 - 4    are embodied in software and performed by a computer system (comprising one or more computing devices) executing the software. A person skilled in the art would understand that a computer system has one or more physical memory units, disks, or other physical, computer-readable storage media for storing software instructions, as well as one or more processors for executing the software instructions. A person skilled in the art would also understand that a computer system may be stand-alone or connected to a computer network as a server. In certain embodiments, a computer system controlled by one entity may perform the training process and a computer system controlled by another entity may perform the prediction process. 
     As will be understood by those familiar with the art, the invention may be embodied in other specific forms without departing from the spirit or essential characteristics thereof. Accordingly, the above disclosure is intended to be illustrative, but not limiting, of the scope of the invention, which is set forth in the following claims.