Joint ranking model for multilingual web search

A classifier is built to rank documents of different languages found in a query based at least in part on similarity to other documents and the relevance of those other documents to the query. A joint ranking model, e.g., based upon a Boltzmann machine, is used to represent the content similarity among documents, and to help determine joint relevance probability for a set of documents. The relevant documents of one language are thus leveraged to improve the relevance estimation for documents of different languages. In one aspect, a hidden layer of units (neurons) represents clusters (corresponding to relevant topics) among the retrieved documents, with an output layer representing the relevant documents and their features, and edges representing a relationship between clusters and documents.

BACKGROUND

With more and more different languages becoming used on the Web, both with respect to Web documents and the Internet users, the task of searching for content across multiple languages has become more and more difficult. Multilingual information retrieval (MLIR) for web pages technology works in this area, but is complex due to many language barriers, and in particular translation problems.

For example, given a query in one language, one multilingual search approach attempts to locate documents in another, target language for a query by using machine translation to translate the query into the target language. Another approach performs a document translation, and essentially works in the opposite direction.

However, not only does such machine translation to find relevant documents, generally because of translation issues, but ranking the retrieved pages of different languages is not very good. In general, it is very difficult to estimate cross-lingual relevancy because of the information loss due to the imperfect translation

MLIR ranking is even more difficult because documents in multiple languages have to be compared and merged appropriately. In short, there is lack of suitable ranking algorithms for multilingual web search.

A research field referred to as “learning-to-rank” is directed to learning a unique ranking function for a set of documents; a multilingual version is directed to learning a unique ranking function for documents of different languages. This is done intuitively by representing documents of different languages within a unified feature space, and performing a monolingual ranking task. However, the information loss and misinterpretation due to imperfect queries and document translation makes multilingual search ranking a very difficult problem, and heretofore has not been acceptable in many instances.

SUMMARY

Briefly, various aspects of the subject matter described herein are directed towards a technology by which similarity between a first document of first language and a second document of a second, different language are determined, with the similarity used to rank the relevance of the second document with respect to a query submitted in the first language. In one aspect, the similarity is determined by evaluating multilingual features between documents, e.g., keywords versus translated keywords.

In one aspect, a classifier is trained to use the similarity in ranking relevance, essentially by learning a ranking function to estimate comparable scores of documents of different languages. The classifier may be a Boltzmann machine, constructed with each document and each cluster (a topic-based grouping) corresponding to one unit of the Boltzmann machine, with each document unit corresponding to document features, and with edges between each document unit and each cluster unit representing a correlation between that document's relevancy and that cluster's relevancy. Only a subset of available clusters may be chosen for building the Boltzmann machine, e.g., based on relevance.

In one aspect, the Boltzmann machine may be trained by adjusting weights and thresholds such that a predicted document relevancy distribution approximates a target distribution, and/or by optimizing based upon mean average precision.

DETAILED DESCRIPTION

Various aspects of the technology described herein are generally directed towards a joint ranking model that exploits the similarity in content among a set of documents of different languages, and determines a joint relevance probability for the documents. As will be understood, the relevant documents of one language are leveraged to improve the relevance estimation for documents of different languages. By way of example, if English language document E is very relevant to an English language query QE, and is known from previous offline analysis to be very similar to a Chinese document C, then document C is also likely very relevant to the query QE. The offline analysis may, for example, match features such as translated keywords to determine similarity. A search for multilingual (English and Chinese) documents with query QEranks the Chinese document C generally higher based upon document E's relevance score and document E's similarity to document C. Features may be matched in one or both translation directions, e.g., the English document's keywords may be translated to Chinese and compared against the Chinese document's keywords, and/or the Chinese document's keywords may be translated to English and compared against the English document's keywords, and so forth with other features.

While some of the examples described herein are directed towards an example classifier and example features, it is understood that these are only examples. Other classifiers may be used to leverage the similarities in documents of different languages, and other features may be used. As such, the present invention is not limited to any particular embodiments, aspects, concepts, structures, functionalities or examples described herein. Rather, any of the embodiments, aspects, concepts, structures, functionalities or examples described herein are non-limiting, and the present invention may be used various ways that provide benefits and advantages in computing, searching, ranking and/or document processing in general.

In traditional technology, ranking for multilingual information retrieval (MLIR) ranks documents of different languages solely based on their relevancy to the query, regardless of the original language of the query. Existing research for MLIR ranking is focused on combining relevance scores of different retrieval settings. Although some MLIR ranking schemes involve machine learning, they are still focused on combining relevance scores associated with multiple retrieval settings, but ignore the direct modeling of each feature's contribution to MLIR relevancy. As a result, the resulting ranking algorithms often do not work well for web MLIR, which involves a large number of ranking features.

In contrast, described herein is Web MLIR ranking within a learning-to-rank framework, in which instead of estimating the relevancy of each individual document to the query, a mechanism/process exploits the monolingual and cross-lingual content similarity among documents, and induces a joint relevance probability of all the documents. To this end, as generally represented inFIG. 1, given a set of candidate documents102, multilingual document clustering is performed to identify relevant topics among the documents, as generally represented by the clustering mechanism104and the clustering data106. In addition, multilingual features108, such as keywords, are extracted from the documents by a featurizer mechanism110.

Then, a classifier112(e.g., a Boltzmann machine, trained by a training mechanism114described below) is used to estimate a joint relevance probability based on the documents' individual features108and the correlation between document relevance and topic relevance (as maintained in the clustering data106). Because similar documents usually cover the same topic and share similar relevance ranks, the document relevancy and topic relevancy can be decided collaboratively for improved information retrieval accuracy.

Thus, in addition to the traditional query and document similarity technology, or in place of traditional technology, the technology described herein leverages the similarities among candidate documents102to further enhance their relevance ranking. Based on the observation that similar documents usually share similar relevancy ranks, monolingual relevant documents are leveraged to enhance the relevancy estimation for documents of different languages, thereby helping to overcome the inaccuracies caused by translation errors.

As generally represented inFIG. 2, in one implementation, a Boltzmann machine/stochastic recurrent neural network220is used for the joint relevance estimation (generally due to its successful modeling of correlations among individual decisions to enhance question answering and information extraction). More particularly, a hidden layer of neurons is introduced to represent relevant topics among retrieved documents, with the relevant documents and relevant topics are identified collaboratively. The parameters of the Boltzmann machine may be trained under different configurations, to optimize the accuracy of identifying relevant documents, and/or to directly optimize information retrieval evaluation measures, such as mean average precision (MAP).

In a general framework of learning-to-rank for MLIR, a ranking function is learned to estimate comparable scores to documents of different languages. In a training stage, a set of queries Q={qi} are given; each query qiis associated with a list of retrieved documents di={di,j} together with a list of relevance labels li={li,j}, where li,jis the label associated with di,j, and may take one of the ordinal values in R={r1,r2, . . . ,rk}, r1>r2> . . . >rk. Here > denotes the order relation. Thus, the training data set130(FIG. 1) can be represented as T={qi,di,li}.

To facilitate the learning of the ranking function, a unified feature space={fk(qi,di,j)} is designed, where fk(qi,di,j) is a feature function for each query-document pair. The objective of the training is to learn a ranking function FR:→R that assigns a relevance score for each retrieved document. Then the retrieved documents are ranked by their scores. Specifically, a permutation of integers π(qi,di,FR) is introduced to denote the ranked orders among documents difor query qiusing ranking function FR, and π(qi,di,j,FR) refers to the position of di,jin the ranked list. Then the training process is to search for FRwhich minimizes a loss function representing the disagreement between π(qi,di,FR) and the ranked list given by lifor all the queries.

The ranking function takes different forms when using different learning algorithms. For example, in RankSVM, the ranking function is expressed as:
FR({fk(qi,di,j)})=w·φ({fk(qi,di,j)})   (1)
where φ is the mapping from the input feature space onto the kernel space, and w is the weight vector in the kernel space which will be learned during the training.

In contrast, RankNet uses ranking function of the following form:

The above applies to learning-to-rank in general. To apply learning-to-rank for MLIR, a unified feature space is assigned for documents across different languages. Typical query-document features are exemplified in Table 1, (with further description about constructing the multilingual feature space provided below):

TABLE 1examples of query-document featuresFeature NameDescriptionBM25_FieldBM25 relevance scores between the queryand the document using different fields of thedocument, such as title, body, etc.BM25_Norm_FieldBM25_Field divided by the sum of IDFs ofquery wordsWords_Found_FieldThe % query words found in different fields ofthe documentPerfect_Match_Field# of phrases found in different fields exactlymatching with the queryTFIDF_n_Fieldtf*idf of the first n query terms occurring indifferent fields where n is pre-definedLM_FieldRelevance Score returned by the language-modeling-based retrieval model using differentfields of the document

Edges between instance pairs may be created to represent the dependency among individual instances. However, this results in a quadratic expansion of the edge number in the Boltzmann machine, and is thus unacceptable in the Web search scenario with hundreds of candidate documents involved. As a result, multilingual clustering is first performed to uncover relevant topics, with the direct document link being replaced by the edges between a document and the topics, as generally represented inFIG. 2. Moreover, only the largest clusters are introduced into the Boltzmann machine, whereby the size of the Boltzmann machine is linear in term of the input document number.

Given a query qiand its retrieved documents di={di,j}, multilingual clustering is first performed, and the resulting clusters are represented as ci={ci,j}. More particularly, with multilingual clustering, the retrieved documents are clustered to uncover the relevant topics and create hidden units in Boltzmann machine. Because the documents to be clustered are in different languages, some machine translation mechanisms are employed for document comparison. In one implementation, a known cross-lingual document similarity measure is used for its simple implementation and high efficiency. The measure is a cosine-like function with an extension of TF-IDF (term frequency-inverse document frequency) weights for the cross-lingual case, using a dictionary for keyword translation. The cross-lingual document similarity measure is formalized as follows:

sim⁡(d1,d2)=∑(t1,t2)∈T⁡(d1,d2)⁢tf⁡(t1,d1)⁢idf⁡(t1,t2)⁢tf⁡(t2,d2)⁢idf⁡(t1,t2)N1/2(5)
where N is given as

T(d1,d2) denotes the sets of word pairs where t2is the translation of t1, and t1occurs in document d1, and t2occurs in document; d2·idf(t1,t2) is the extension of IDF for a translation pair (t1,t2) is defined as:

idf⁡(t1,t2)=log⁡(ndf⁡(t⁢⁢1)+df⁡(t⁢⁢2))(7)
where n denotes the total number of documents in two languages. In practice, the similarity of documents of different languages are measured with this function above, and for those of the same language, their similarity is calculated by the classical cosine function.

Using the above document similarity measures, a k-means algorithm is used for document clustering, which requires time complexity O(|C||D|) where |C| is the cluster number and |D| is the document number. The cluster number may be dynamically determined, e.g., with only the four largest clusters introduced into Boltzmann machine (based on the observation that minor clusters usually irrelevant to the query).

In addition to being used for multilingual clustering, Equation (6) is used to compute the Boltzmann machine edge features that represent document-cluster correlations, which are shown in Table 2:

TABLE 2edge features of Boltzmann Machine:Feature NameDescriptionSim_ML_FieldAveraged monolingual similarity between thedocument and the documents in the samelanguage in a cluster using different documentfieldsSim_CL_fieldAveraged cross-lingual similarity (Equation 5)between the document and the documents indifferent languages in a cluster using differentfieldsSim_FieldAveraged similarity between document and thedocuments in a cluster independent of languages

With these features, the Boltzmann machine ofFIG. 2is constructed. Both a document and a cluster correspond to one (neuron) unit of the Boltzmann machine, and the state of the unit takes one of ordinary values R={r1,r2, . . . , rk} representing the relevance of the unit. The cluster units are regarded as the hidden units because their relevance labels are not provided by the training data. The document units are the output units because their relevance labels are the final output for ranking. Although a document belongs to at most one cluster, edges exist between a document unit and every cluster unit, representing the correlation between the document's relevancy and every cluster's relevancy.

Using sd={sdi,j} and sc={sci,j′} to represent the states of the document and cluster units, the energy of the Boltzmann machine is defined as:

E⁡(sd,sc,qi)=-12⁢∑l,j,j′⁢wk⁢gl⁡(di,j,ci,j′)⁢sdi,j⁢sci,j′-∑i,k⁢si,j⁢θk⁢fk⁡(qi,di,j)(3)
where fk(qi,di,j) is one of the query-document features exemplified in Table 1, gl(di,j,ci,j′) is a document-cluster feature shown in Table 2 (the edge feature estimation involves the cross-lingual document similarity described herein section), and θkand wlare the corresponding weights. The probability of the global state configuration follows Boltzmann distribution which takes the following form:

To summarize the Boltzmann Machine for MLIR Ranking ofFIG. 2, the first layer contains output units corresponding to documents, and the second layer contains hidden units corresponding to clusters. Edges exist between every document and cluster units, corresponding to the dependency between document relevancy and cluster (topic) relevancy. Each document unit s associated with features fk(qi,di,j) exemplified in Table 1, and each edge is associated with features gl(di,j,ci,j′) shown in Table 2.

To use the trained Boltzmann Machine as a classifier, given the training data T={qi, di, li}, the training of Boltzmann machine adjusts the weights and thresholds in Equation (3) in such a way that the predicted document relevancy distribution {p(sd,qi)=Σscp(sd, sc, qi)} approximates the target distribution {p*(sd,qi)} as closely as possible, where

p*(sd|qi)={1,if⁢⁢sd=Ii;0,otherwise.⁢⁢K-L
divergence is used to measure the probability distribution difference:

To minimize K using gradient descent, the following weight updating rules are obtained:
Δw1=εΣi,j,j′gl(sdi,j,sci,j′)(sdi,jsci,jclampped−sdi,jsci,jfree)   (9)
Δθk=εΣi,jfk(sdi,j)(sdi,jclampped−sdi,jfree)   (10)
where ε is a parameter called learning rate, andclamppedandfreedenote the expectation values obtained from the “clamped” and “free-running” stages of the training, respectively. In the clamped stage, the state values of the output units (that is, the document relevance label) are to be equal to the labels in the training data; in the free-running stage, all the possible state configurations are considered for the expectation estimation.

The training procedures start with a set of initial weight values which may be generated randomly. The weights are updated iteratively based on Equation (9) and (10) until the model converges to a local minimum of K. Usually, such a training procedure is repeated several times with different initial weights to attempt more optimal performance.

It is noted that the exact estimation of the expectation valueclamppedandfreeis time consuming because it requires enumerating all the possible state configurations, which is exponential with the number of units. Considering that a query may result in hundreds of retrieved documents, such computation is intractable. As a result, Gibbs sampling is used to approximately estimate the expectation values involved in Equation (9) and (10).

After the Boltzmann machine training, given a new query qiand the corresponding retrieved documents di, the relevance probability distribution of a retrieved document may be estimated as follows:
p(sdi,j,qi)=Σsd\sdi,j,scp(sd, sc, qi)   (11)
then l′i,j=argmaxsdi,jp(sdi,j,qi) is the relevance label predicted by the Boltzmann machine, and is used for the search results ranking. In addition, the value of p(l′i,j,qi) is used to break any tie during the ranking.

FIG. 1shows the classifier112being used with online multilingual searches in block diagram form. As a query140arrives at a search engine142, the search engine provides its results to the classifier112. The classifier ranks the results according to its training, and the search engine142outputs ranked results144. The ranking of the classifier may be combined with other ranking mechanisms.

The exact estimation of p(sdi,j,qi) requires exponential time complexity because a complete global state enumeration is needed. To improve the computation efficiency, one implementation uses mean-field approximation, e.g., for Boltzmann machine inference, including its foundation based on Variational Principle.

In mean field approximation, the state distribution of each unit only relies on the states of its neighboring units, which are all fixed to average state values. So based on the Boltzmann machine inFIG. 2, there is:

Here Equation (12) compute the relevance probability distribution of a document given the average relevance labels of the clusters. Similarly, Equation (13) computes the relevance probability distribution of a cluster given the average relevance labels of the documents. Equation (14) and (15) estimate the average relevance labels given the probability distributions computed by Equation (12) and (13).

Equations (12)-(15) are referred to as mean-field equations, and are solved using the following iterative procedure for a fix-point solution:(i) Assume an average state value for every unit;(ii) For each unit, estimate its state value probability distribution using Equation (12) and (13) given the average state values of its neighbors;(iii) Update the average state values for every unit using Equation (14) and (15);(iv) Go to Step (ii) until the average state values converge.

With respect to Boltzmann Machine Training by mean average precision optimization, as described above, a Boltzmann machine is trained to optimize the relevance label predictions. However, relevance label prediction is just loosely related to MLIR accuracy because the exact relevance labels are not necessary to derive the correct ranking orders. One ranking model trained by direct optimizing information retrieval evaluation measures reports the highest information retrieval ranking accuracy. In one implementation, the Boltzmann machine may be trained in a similar way, that is, by optimizing the mean average precision of MLIR.

Given a query qi, the retrieved documents di, the exact relevance labels li, and a ranking function FR, the predicted ranking order is π(qi,di,FR). Then average precision for qiis defined as:

AvgPi=∑j=1n⁡(qi)⁢Pi⁡(j)·yi,j∑j=1n⁡(qi)⁢yi,j(16)
where yi,jis assigned with 1 or 0 depending on di,j′(π(qi, di, j′,FR)=j) is relevant or not, and Pi(j) is defined as the precision at the rank position of j:

Pi⁡(j)=∑j′<j⁢yi,j′j(17)
Mean average precision is an average of AvgPiover all the queries.

Instead of simply maximizing mean average precision, the following objective function is selected to maximize:
MAP−CΣl|wl|2−CΣk′|θk′|2(18)

Here ΣEl|wl|2+Σk′|θk′|2is a L-2 regularization term representing the complexity of the model. So Equation (18) is a trade-off between the accuracy of the model and the model's complexity. Similar with SVM learning algorithm, a parameter C is introduced to control the trade-off.

Because the mean average precision is not a continuous function with the weights of the Boltzmann machine, Powell's Direction Set Method, which does not involve derivation computations, is used for the optimization. To achieve more optimal performance, Powell's Direction Set Method is repeatedly called many times with different initial values of the machine's weights. One particular set of the initial values is the weights learned when Boltzmann machine is trained by optimizing classification accuracy as described herein.

Note that the optimization procedure iteratively computes the mean average precision given many different weight values of the Boltzmann machine. The mean-field approximation described herein is used for the involved model inference.

FIG. 3summarizes the various operations, including clustering the documents based on topic (step302) and featurizing the documents based upon the multilingual feature space (step304), this includes any appropriate machine translation. Step306selects only a subset of the clusters, as described above, e.g., the most relevant four.

Step308represents building the Boltzmann machine, with documents each represented as a document (output) unit having associated document features, and each cluster represented as a cluster (hidden) unit, related to the document units by edge features. At step310the Boltzmann machine is trained (e.g., adjusted and/or optimized) as described above. Step312represents the use of the Boltzmann machine in ranking documents of different languages.

Exemplary Operating Environment

With reference toFIG. 4, an exemplary system for implementing various aspects of the invention may include a general purpose computing device in the form of a computer410. Components of the computer410may include, but are not limited to, a processing unit420, a system memory430, and a system bus421that couples various system components including the system memory to the processing unit420. The system bus421may be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures. By way of example, and not limitation, such architectures include Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video Electronics Standards Association (VESA) local bus, and Peripheral Component Interconnect (PCI) bus also known as Mezzanine bus.

The system memory430includes computer storage media in the form of volatile and/or nonvolatile memory such as read only memory (ROM)431and random access memory (RAM)432. A basic input/output system433(BIOS), containing the basic routines that help to transfer information between elements within computer410, such as during start-up, is typically stored in ROM431. RAM432typically contains data and/or program modules that are immediately accessible to and/or presently being operated on by processing unit420. By way of example, and not limitation,FIG. 4illustrates operating system434, application programs435, other program modules436and program data437.

The computer410may also include other removable/non-removable, volatile/nonvolatile computer storage media. By way of example only,FIG. 4illustrates a hard disk drive441that reads from or writes to non-removable, nonvolatile magnetic media, a magnetic disk drive451that reads from or writes to a removable, nonvolatile magnetic disk452, and an optical disk drive455that reads from or writes to a removable, nonvolatile optical disk456such as a CD ROM or other optical media. Other removable/non-removable, volatile/nonvolatile computer storage media that can be used in the exemplary operating environment include, but are not limited to, magnetic tape cassettes, flash memory cards, digital versatile disks, digital video tape, solid state RAM, solid state ROM, and the like. The hard disk drive441is typically connected to the system bus421through a non-removable memory interface such as interface440, and magnetic disk drive451and optical disk drive455are typically connected to the system bus421by a removable memory interface, such as interface450.

The drives and their associated computer storage media, described above and illustrated inFIG. 4, provide storage of computer-readable instructions, data structures, program modules and other data for the computer410. InFIG. 4, for example, hard disk drive441is illustrated as storing operating system444, application programs445, other program modules446and program data447. Note that these components can either be the same as or different from operating system434, application programs435, other program modules436, and program data437. Operating system444, application programs445, other program modules446, and program data447are given different numbers herein to illustrate that, at a minimum, they are different copies. A user may enter commands and information into the computer410through input devices such as a tablet, or electronic digitizer,464, a microphone463, a keyboard462and pointing device461, commonly referred to as mouse, trackball or touch pad. Other input devices not shown inFIG. 4may include a joystick, game pad, satellite dish, scanner, or the like. These and other input devices are often connected to the processing unit420through a user input interface460that is coupled to the system bus, but may be connected by other interface and bus structures, such as a parallel port, game port or a universal serial bus (USB). A monitor491or other type of display device is also connected to the system bus421via an interface, such as a video interface490. The monitor491may also be integrated with a touch-screen panel or the like. Note that the monitor and/or touch screen panel can be physically coupled to a housing in which the computing device410is incorporated, such as in a tablet-type personal computer. In addition, computers such as the computing device410may also include other peripheral output devices such as speakers495and printer496, which may be connected through an output peripheral interface494or the like.

The computer410may operate in a networked environment using logical connections to one or more remote computers, such as a remote computer480. The remote computer480may be a personal computer, a server, a router, a network PC, a peer device or other common network node, and typically includes many or all of the elements described above relative to the computer410, although only a memory storage device481has been illustrated inFIG. 4. The logical connections depicted inFIG. 4include one or more local area networks (LAN)471and one or more wide area networks (WAN)473, but may also include other networks. Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets and the Internet.

When used in a LAN networking environment, the computer410is connected to the LAN471through a network interface or adapter470. When used in a WAN networking environment, the computer410typically includes a modem472or other means for establishing communications over the WAN473, such as the Internet. The modem472, which may be internal or external, may be connected to the system bus421via the user input interface460or other appropriate mechanism. A wireless networking component474such as comprising an interface and antenna may be coupled through a suitable device such as an access point or peer computer to a WAN or LAN. In a networked environment, program modules depicted relative to the computer410, or portions thereof, may be stored in the remote memory storage device. By way of example, and not limitation,FIG. 4illustrates remote application programs485as residing on memory device481. It may be appreciated that the network connections shown are exemplary and other means of establishing a communications link between the computers may be used.

An auxiliary subsystem499(e.g., for auxiliary display of content) may be connected via the user interface460to allow data such as program content, system status and event notifications to be provided to the user, even if the main portions of the computer system are in a low power state. The auxiliary subsystem499may be connected to the modem472and/or network interface470to allow communication between these systems while the main processing unit420is in a low power state.

CONCLUSION