BACKGROUND

The invention relates in general to the field of computer-implemented methods for assessing distances between pairs of documents, such as methods known as Word Mover's Distance and Relaxed Word Mover's Distance.

Modern computational systems are known, which are capable of ingesting, storing and searching across a prodigious amount of textual information. Efficient search through textual information should ideally allow both high-quality results and speed of execution. Today, high-quality search results can be achieved thanks to a new class of text representations based on neural networks, such as the popular word2vec representation [1]. The algorithm word2vec capitalizes on neural networks to map words onto an appropriate vector space. In this embedding space, words that are semantically synonymous will be close to each other. To capture the similarity between sentences, Kusner et al., proposed the Word Mover's Distance (WMD) [2], which represents a promising method for evaluating the similarity between text documents, in terms of quality of search results obtained. WMD is an adaptation of the Earth Mover's Distance (EMD) [3], initially proposed to measure similarity between images. Like EMD, WMD constructs a histogram representation of the documents and estimates the cost of transforming one histogram into the other. However, the computational complexity of both approaches scales cubically with the size of the histograms, making their application prohibitive on Big Data.

To mitigate the large complexity of WMD, Kusner et al., proposed using a faster, lower-bound approximation to WMD, called the Relaxed Word Mover's Distance, or RWMD [2]. They showed that the accuracy achieved by RWMD is very close to that of WMD. According to the original paper, the time complexity of the RWMD method grows quadratically with the size of the histograms, which represents a significant improvement with respect to the WMD method. However, quadratic complexity still limits the applicability of RWMD to relatively small datasets. Such a complexity still prevents computing pairwise similarities across millions of documents, which would have extensive applications in clustering, classification, and querying of documents.

SUMMARY

According to a first aspect, the present invention is embodied as a computer-implemented method for assessing distances between pairs of documents. This method first comprises accessing: two sets X2and X1of histograms of words, where each of the histograms pertains to a respective document; and a vocabulary V of words. Each of the two sets Xk, k=1, 2, is representable as a sparse matrix, each row of which corresponds to a histogram Xk[l]∈ Xk, l ∈ {1, . . . , Nk}. In addition, each histogram Xk[l] is representable as a sparse vector, whose dimension is determined by a dimension of the vocabulary V.

The present methods essentially comprise two phases, which aim at computing distances between pairs of histograms (X1[i], X2[j]), ∀ i ∈ {1, . . . , N1} ∧∀ j ∈ {1, . . . , N2}. The first phase include computations performed for each histogram X2[j] ∈ X2and for each word in the vocabulary V. There, a distance between said each word in V and a closest entry in said each histogram X2[j] is computed, so as to obtain a dense, floating-point vector)), whose dimension is determined by the dimension of the vocabulary V.

The second phase includes computing, again for said each histogram X2[j] ∈ X2, a sparse-matrix, dense-vector multiplication between a matrix-representation of the set X1of histograms and the vector y (as computed during the first phase for said each histogram X2[j] ∈ X2). The multiplication is performed as a matrix-vector product, in order to obtain distances between all histograms X1[i], i ∈ {1, . . . , N1} of the set X1and said each histogram X2[j]. ATM. Performing the two-phase process for each histogram X2[j] allow distances between all pairs of histograms to be obtained, based on which distances between documents can subsequently be assessed.

This approach makes it possible to markedly reduce the time complexity and storage requirements, compared to methods such as WMD and RWMD, while essentially retaining the quality of search results obtained. This, in practice, makes it possible for high-quality search results such as provided by the WMD and RWMD methods applicable to massive datasets.

In embodiments, the vector y is computed based on: a dense matrix W that stores vector representations of words in the vocabulary V, and a dense matrix T2[j] that stores vector representations of words in X2[j]. For example, the vector y is preferably computed as min(W ∘ T2[j]T), where ∘ is a modified matrix multiplication operation, wherein distances are computed between word vectors of W and T2[j]T. Row-wise minimums of W ∘ T2[j]Tare then computed to obtain min(W ∘ T2[j]T). This way, minimal distances between the words in the vocabulary V and the words in X2[j] can be obtained, which are stored in the vector y, in view of the subsequent sparse-matrix, dense-vector multiplication.

The above embodiments makes it possible to compute the costs of moving histograms X1[i], i ∈ {1 . . . N1} to histograms X2[j], j ∈ {1 . . . N2}. Now, a tighter lower bound can be achieved by further computing the costs of moving histograms X2[j], j ∈ {1 . . . N2} to X1[i], i ∈ {1 . . . N1}. That is, the above two-phase process can be repeated, wherein X1and X2are swapped and the new round of computations are now run for each X1[i].

According to another aspect, the invention is embodied as a computerized method for managing sets of documents. This additional method assumes that, given a set X1of histograms of words, where each of the histograms pertains to a respective document, the set X1corresponds to a first set of documents as currently stored in a pool of documents. Now, a new set (i.e., a second set) of documents may be received. There, a corresponding set X2of histograms of words is created, wherein each histogram pertains to a respective document of the new set of documents received. Finally, distances between pairs of documents of the two sets can be assessed, according to embodiments of the method described above.

The new set of documents is preferably stored in the pool of documents after having assessed distances between pairs of documents of the two sets.

According to a final aspect, the invention can be embodied as a computer program product for assessing distances between pairs of documents. The computer program product comprises a computer readable storage medium having program instructions embodied therewith. The program instructions are executable by one or more processors, to cause the latter to implement steps according to the present methods.

Computerized methods and computer program products embodying the present invention will now be described, by way of non-limiting examples, and in reference to the accompanying drawings.

