CROSS-LINGUAL SEARCH RE-RANKING

• US 20090222437A1
• Filed: 03/03/2008
• Published: 09/03/2009
• Est. Priority Date: 03/03/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Niu, Cheng, Zhou, Ming
• Granted Patent: US 7,917,488 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Cross-lingual search re-ranking is performed during a cross-lingual search in which a search query of a first language is used to retrieve two sets of documents, a first set in the first language, and a second set in a second language. The two sets of documents are each first ranked by the search engine separately. Cross-lingual search re-ranking then aims to provide a uniform re-ranking of both sets of documents combined. Cross-lingual search re-ranking uses a unified ranking function to compute the ranking order of each document of the first set and the second set of documents. The unified ranking function is constructed using generative probabilities based on multiple features, and can be learned by optimizing weight parameters using a training corpus. Ranking SVM algorithms may be used for the optimization.

Claims

1. A method for re-ranking results of a cross-lingual search, wherein the cross-lingual search is performed using a search query of a first language to retrieve a first set of documents in the first language and a second set of documents in a second language, the method comprising:

for each document of the first set and the second set of documents, computing a value of a unified ranking function which is a function of the search query and the document; and

ranking the first set of documents and the second set of documents together based on the values of the unified ranking function.

2. The method as recited in claim 1, wherein when the document is one of the first set of documents in the first language, the ranking function comprises a term descriptive of a monolingual query generative probability between the search query and the document.

3. The method as recited in claim 2, wherein the term descriptive of the monolingual query generative probability between the search query (q_c) and the document (d_c) is expressed in terms comprising:

$\underset{i}{\sum <br><br>}<br><br>{\mathrm{\lambda <br><br>}}_i<br><br>f_i<br><br>\left(q_c,d_c\right),$

where f_i(q_c,d_c) is a monolingual relevancy feature function used for estimating relevancy between the search query q_c and the document d_c, and λ

_i is corresponding weight parameter.

4. The method as recited in claim 3, wherein the monolingual relevancy feature function ƒ

_i(q_c,d_c) is selected from a group of feature functions including snippet-based BM25 score, snippet-based language model score, snippet-based tf-idf score, title-based BM25 score, title-based language model score, and title-based tf-idf score.

5. The method as recited in claim 1, wherein when the document is one of the second set of documents in the second language, the ranking function comprises a term descriptive of a cross-lingual query generative probability between the search query and the document based on query translation.

6. The method as recited in claim 5, wherein the cross-lingual query generative probability between the search query (q_c) and the document (d_e) based on query translation is expressed in terms comprising:

$\underset{i,j}{\sum <br><br>}<br><br>{\mathrm{\mu <br><br>}}_{\mathrm{ij}}<br><br>f_i<br><br>\left(q_e,d_e\right)<br><br>g_j<br><br>\left(q_c,q_e\right),$

where q_e is a translation of the search query q_c in the second language, f_i(q_e,d_e) is a monolingual relevancy feature function used for estimating relevancy between q_e as a search query in the second language and the document d_e, g_j(q_c,q_e) is a feature function associated with query translation between the search query q_c and the translation search query q_e, and μ

_ij is corresponding weight parameter.

7. The method as recited in claim 6, wherein the weight parameter μ

_ij is determined using a learning model having a training corpus.

8. The method as recited in claim 6, wherein the feature function g_j(q_c,q_e) is selected from a group of feature functions including bilingual dictionary-based score based on term-term cohesion, bidirectional translation score based on parallel corpora, frequency in Web mining snippets, and monolingual query suggestion-based feature.

9. The method as recited in claim 1, wherein when the document is one of the second set of documents in the second language, the ranking function comprises a term descriptive of a cross-lingual query generative probability between the search query and the document based on document translation.

10. The method as recited in claim 9, wherein the cross-lingual query generative probability between the search query (q_c) and the document (d_e) based on document translation is expressed in terms comprising:

$\underset{i,k}{\sum <br><br>}<br><br>{\mathrm{\pi <br><br>}}_{\mathrm{ik}}<br><br>f_i<br><br>\left(q_c,d_c\right)<br><br>h_k<br><br>\left(d_c,d_e\right)$

where d_c is a translation of the document d_e in the first language, f_i(q_c, d_c) is a monolingual relevancy feature function used for estimating relevancy between the search query q_c and the translation document d_c, h_k(d_c,d_e) is a feature function associated with document translation between the translation document d_c and the document d_e, and h_ij is corresponding weight parameter.

11. The method as recited in claim 10, wherein the weight parameter h_ij is determined using a learning model having a training corpus.

12. The method as recited in claim 10, wherein the feature function h_k(d_c,d_e) is selected from IBM translation model score and phrase translation model score.

13. The method as recited in claim 1, wherein the unified ranking function is expressed in terms comprising:

$\begin{array}{cc}\begin{array}{c}\mathrm{\psi <br><br>}<br><br>\left(q_c,d\right)=\\ \{\begin{array}{cc}\underset{i}{\sum <br><br>}<br><br>{\mathrm{\lambda <br><br>}}_i<br><br>f_i<br><br>\left(q_c,d_c\right)& \mathrm{if}<br><br><br><br>d<br><br><br><br>\mathrm{is}<br><br><br><br>d_c\\ \underset{i,j}{\sum <br><br>}<br><br>{\mathrm{\mu <br><br>}}_{\mathrm{ij}}<br><br>f_i<br><br>\left(q_e,d_e\right)<br><br>g_j<br><br>\left(q_c,q_e\right)+{\sum <br><br>}_{i,k}<br><br>{\mathrm{\pi <br><br>}}_{\mathrm{ik}}<br><br>f_i<br><br>\left(q_c,d_c\right)<br><br>h_k<br><br>\left(d_c,d_e\right)& \mathrm{if}<br><br><br><br>d<br><br><br><br>\mathrm{is}<br><br><br><br>d_e\end{array},\end{array}& \end{array}$

where ranking function ψ

(q_c,d) is a function of the search query q_c and document d of the first set and the second set of documents;

document d_e is one of the second set of documents in the second language;

f_i(q_c, d_c) is a monolingual relevancy feature function used for estimating relevancy between the search query q_c and the document d_c;

λ

_i is corresponding weight;

q_e is a translation of the search query q_c in the second language;

f_i(q_e,d_e) is a monolingual relevancy feature function used for estimating relevancy between q_e as a search query in the second language and the document d_e;

g_j(q_c,q_e) is a feature function associated with query translation between the search query q_c and the translation search query q_e;

μ

_ij is corresponding weight parameter;

d_c is a translation of the document d_e in the first language;

f_i(q_c,d_c) is a monolingual relevancy feature function used for estimating relevancy between the search query q_c and the translation document d_c;

h_k(d_c,d_e) is a feature function associated with document translation between the translation document d_c and the document d_e; and

h_ij is corresponding weight parameter.

14. The method as recited in claim 13, wherein weight parameters λ

_i, μ

_ij, and h_ij are determined by optimizing search ranks using a ranking SVM algorithm applied to a training corpus.

15. The method as recited in claim 13, wherein weight parameters λ

_i, μ

_ij, and h_ij are determined by a learning algorithm applied to a training corpus, the training corpus including a training query, a set of training candidate documents in both the first language and a second language, and a relevance rank with respect to the training query assigned to each training candidate'"'"'s document.

16. The method as recited in claim 1, wherein the first language is Chinese and the second language is English.

17. A cross-lingual search ranking method, comprising:

receiving a search query of a first language;

retrieving a first set of documents in the first language based on the search query;

retrieving a second set of documents in a second language based on the search query;

for each document of the first set and the second set of documents, computing a value of a unified ranking function which is a function of the search query and the document; and

ranking the first set of documents and the second set of documents together based on the values of the unified ranking function.

18. The method as recited in claim 17, wherein the unified ranking function is expressed as:

$\begin{array}{cc}\begin{array}{c}\mathrm{\psi <br><br>}<br><br>\left(q_c,d\right)=\\ \{\begin{array}{cc}\underset{i}{\sum <br><br>}<br><br>{\mathrm{\lambda <br><br>}}_i<br><br>f_i<br><br>\left(q_c,d_c\right)& \mathrm{if}<br><br><br><br>d<br><br><br><br>\mathrm{is}<br><br><br><br>d_c\\ \underset{i,j}{\sum <br><br>}<br><br>{\mathrm{\mu <br><br>}}_{\mathrm{ij}}<br><br>f_i<br><br>\left(q_e,d_e\right)<br><br>g_j<br><br>\left(q_c,q_e\right)+{\sum <br><br>}_{i,k}<br><br>{\mathrm{\pi <br><br>}}_{\mathrm{ik}}<br><br>f_i<br><br>\left(q_c,d_c\right)<br><br>h_k<br><br>\left(d_c,d_e\right)& \mathrm{if}<br><br><br><br>d<br><br><br><br>\mathrm{is}<br><br><br><br>d_e\end{array},\end{array}& \end{array}$

where ranking function ψ

(q_c,d) is a function of the search query q_c and the document d of the first set and the second set of documents;

document d_e is of the second set of documents in the second language;

f_i(q_c,d_c) is a monolingual relevancy feature function used for estimating relevancy between the search query q_c and the document d_c;

λ

_i is corresponding weight parameter;

q_e is a translation of the search query q_c in the second language;

f_i(q_e,d_e) is a monolingual relevancy feature function used for estimating relevancy between q_e as a search query in the second language and the document d_e;

g_j(q_c,q_e) is a feature function associated with query translation between the search query q_c and the translation search query q_e;

μ

_ij is corresponding weight parameter;

d_c is a translation of the document d_e in the first language;

f_i(q_c,d_c) is a monolingual relevancy feature function used for estimating relevancy between the search query q_c and the translation document d_c;

h_k(d_c,d_e) is a feature function associated with document translation between the translation document d_c and the document d_e; and

h_ij is corresponding weight parameter.

19. The method as recited in claim 18, wherein weight parameters λ

_i, μ

_ij and h_ij are determined by optimizing search ranks using a ranking SVM algorithm over a training corpus.

20. One or more computer readable media having stored thereupon a plurality of instructions that, when executed by a processor, causes the processor to perform the following actions:

for each document of the first set and the second set of documents, computing a value of a unified ranking function which is a function of the search query and the document; and

ranking the first set of documents and the second set of documents together based on the values of the unified ranking function.