Ultra-High Dimensional Sparse Representations with Binarization for Efficient Text Retrieval (2021)

Abstract: The semantic matching capabilities of neural information retrieval can ameliorate synonymy and polysemy problems of symbolic approaches. However, neural models’ dense representations are more suitable for re-ranking, due to their inefficiency. Sparse representations, either in symbolic or latent form, are more efficient with an inverted index. Taking the merits of the sparse and dense representations, we propose an ultra-high dimensional (UHD) representation scheme equipped with directly controllable sparsity. UHD’s large capacity and minimal noise and interference among the dimensions allow for binarized representations, which are highly efficient for storage and search. Also proposed is a bucketing method, where the embeddings from multiple layers of BERT are selected/merged to represent diverse linguistic aspects. We test our models with MS MARCO and TREC CAR, showing that our models outperforms other sparse models.

## introduction using neural models for representing and processing textual data has become a de-facto standard. recent approaches to information retrieval (ir) and natural language processing (nlp) tasks adopt contextual language models (e.g., bert @xcite ), ameliorating both synonymy and polysemy problems associated with words @xcite @xcite . in these approaches, queries and documents are first encoded into contextual embeddings, either independently @xcite or with interactions @xcite , resulting in low-dimensional dense representations. then the documents are retrieved based on a similarity metric, such as cosine similarity, defined for two vectors. despite the impressive results, the inherent properties of dense representations -low dimensional and dense -can pose a severe efficiency challenge for first-stage or full ranking. since each dimension in a dense embedding is overloaded and entangled (i.e., polysemous) with the limited number of dimensions available, it is susceptible to false matches with large index sizes @xcite . also, all the dimensions must participate in representing words, queries, and documents regardless of the amount of information content as well as in matching @xcite , which is inefficient. as a result, it is meaningless to build an inverted index for the dimensions, without which it is difficult to build an efficient and effective first-stage or full ranker. other drawbacks of the dense embedding approaches to ir include: 1) the retrieval results are hardly interpretable like other neural approaches, making it difficult to improve the design through failure analyses or implement conditional/selective processing @xcite ; and 2) it is not straightforward to adopt the well studied termbased symbolic ir techniques, such as pseudorelevance feedback, for further improvements. our focus is to propose a full-blown neural firststage ranker that alleviates the shortcomings of dense neural ir and yet achieves competitive effectiveness. the main thrust of our method is to utilize ultra-high dimensional (uhd) embeddings foot_0 with high sparsity, possessing superior expressive and discriminating power to the extent that they are binarized. in addition, our proposed approach has the potential to make individual dimensions of the document/query embeddings interpretable @xcite and support mutually non-interfering aggregation of multiple embeddings @xcite . in order to obtain uhd embeddings, we train the w inner-t ake-all (wta) model @xcite on top of bert with a new learning objective for ir. wta model is fundamentally a linear layer that only preserves top-k activation and sets the others to zero. wta is chosen because we can precisely control the outputs' sparsity by explicitly setting the parameter k. in contrast, the method relying on regularization for sparsity (e.g., minimizing l1-norm) @xcite @xcite is neither straightforward nor precise in controlling the degree of sparsity. with the large capacity and robustness against noise and interference, uhd allows for binarized representations so that matching can be further simplified with little degradation in effectiveness. this capability of uhd achieves extreme efficiency in terms of storage and speed, making it possible to build a stand-alone neural ir model for an industry. besides the efficiency goal, we also attempt to represent different aspects of linguistic properties of documents and queries. instead of the common approach of using only the final layer of bert, we make use of multiple layers, each of which emits token representations for different linguistic properties @xcite , by devising a bucketing mechanism. we evaluate our model on ms marco passage retrieval @xcite and trec car @xcite , showing that it outperforms previous sparse models and is competitive with dense models for effectiveness. even though it is a neural model, our uhd-based ir method with binarization is highly efficient, on par with bm25, surpassing all the sparse models. ## related work state-of-the-art neural retrieval models @xcite adopt a crossencoder that shows high effectiveness while known to be impractical for large-scale retrieval @xcite . the cross-encoder requires that a query and documents must be encoded together, limiting models to a re-ranker. dense neural models have been proposed for first-stage retrieval. rep-bert @xcite encodes queries and documents separately and ranks using an inner product. it achieves efficiency by relying heavily on gpus. colbert @xcite positions itself between the cross-encoder and inner product by proposing a late interaction for scoring. despite its promising performance, it remains questionable whether first-stage retrieval is computationally feasible at a large scale @xcite , even with an external library faiss @xcite . sparse models are attractive for first-stage retrieval @xcite @xcite . their retrieval speed comes from the sparsity that enables to leverage an efficient inverted index. on the other hand, they usually lack the ability to use nonsymbolic latent semantics that can be captured by neural models. solar @xcite proposes randomly initialized high-dimensional and ultra-sparse embeddings for book classification but ignores their content, making it unsuitable for ir tasks. snrm @xcite creates a sparse latent representation using a fully connected layer similar to an autoencoder. it is limited with a simple word embedding, lower dimensionality (20k), uncontrollable sparsity. ## experiments we conduct a series of experiments for validity of the proposed retrieval model and the associated methods against recently proposed sparse methods. we also juxtapose our results with those of the most recent dense models although they are not geared toward full ranking, without resorting to additional computational resources. we defer a qualitative analysis that shows uhd's interpretability to appendix a.4 due to the lack of space. while snrm @xcite would be a suitable baseline as a sparse model, we were unable to reproduce the model following the hyperparameter settings presented in the paper. this reproducibility issue is also reported in @xcite and @xcite . implementation details and hyperparameters are available in appendix a.1 for reproducibility. ## conclusion we present uhd-bert, a novel retrieval method empowered by extremely high dimensionality and sparsity that is easily controllable. to fully utilize the capacity of our representation scheme, we propose a bucketing mechanism that incorporates different linguistic aspects extracted from bert and achieves the goal of building a neural retrieval model that ameliorates the synonymy and polysemy problems of symbolic text retrieval methods. with binarization of the learned uhd representations and resulting inverted indices, we attain the desired efficiency that is comparable with bm25 and hence suitable for industrial applications. the benefits of the uhd representations and the resulting retrieval model were demonstrated with two different ir datasets, in comparison with the recent approaches to sparse representation methods. we also show that our method has a significant advantage in efficiency over the state-of-art dense models, with a slightly lower but competitive effectiveness. we plan to investigate how the query-document interactions and symbolic ir techniques can be incorporated for further improvements.