Cross-lingual search re-ranking

• US 7,917,488 B2
• Filed: 03/03/2008
• Issued: 03/29/2011
• Est. Priority Date: 03/03/2008
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Niu, Cheng, Zhou, Ming
• Primary Examiner(s): Wu; Yicun
• Assistant Examiner(s): Mamillapalli; Pavan
• Application Number:
  US12/041,629
• Publication Number:
  US 20090222437A1
• Time in Patent Office: 1,121 Days
• Field of Search: 707/707, 707/760, 704/8, 704/277
• US Class Current: 707/706
• 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. One or more computer readable media having stored thereupon a plurality of instructions that, when executed by a processor, cause the processor to perform the following actions:

retrieving a first set of documents in a first language and a second set of documents in a second language via a cross-lingual search query that is based on a search query written in the first language;

for each document of the first set and the second set of documents, computing a value of a unified ranking function that is a function of the search query and a corresponding document, the unified ranking function comprising a term descriptive of a cross-lingual query generative probability between the search query and the corresponding document, the cross-lingual query generative probability being a summation calculated based on a term descriptive of a probability of translating the search query from the first language to the second language and a term descriptive of a monolingual query generative probability of the search query being in the second language given an observation of a document in the second language; 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 one or more computer readable media of claim 1, 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:

3. The one or more computer readable media of claim 2, 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.

4. The one or more computer readable media of claim 2, wherein the monolingual query generative probability is estimated using a framework of discriminate regression.

5. The one or more computer readable media of claim 1, wherein the cross-lingual query generative probability between the search query (q_c) and a document (d_e) based on query translation is expressed in terms comprising:

6. The one or more computer readable media of claim 5, wherein the weight parameter μ

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

7. The one or more computer readable media of claim 5, 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.

8. The one or more computer readable media of claim 1, wherein the cross-lingual query generative probability between the search query (q_c) and a document (d_e) based on document translation is expressed in terms comprising:

9. The one or more computer readable media of as recited in claim 8, wherein the weight parameter h_ij is determined using a learning model having a training corpus.

10. The one or more computer readable media of claim 8, wherein the feature function h_k(d_c,d_e) is selected from IBM translation model score and phrase translation model score.

11. The one or more computer readable media of claim 1, wherein the unified ranking function is expressed in terms comprising:

12. The one or more computer readable media of claim 11, wherein weight parameters λ

_i, μ

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

13. The one or more computer readable media of claim 11, 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.

14. The one or more computer readable media of claim 1, wherein the first language is Chinese and the second language is English.

15. 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 that is a function of the search query and the document, the unified ranking function comprising a cross-lingual generative probability that is a summation calculated by multiplication of a term descriptive of a probability of translating the search query of the first language to the second language with a term descriptive of a monolingual query generative probability of the search query being in the second language given an observation of a document that is in the second language from the second set of documents; and

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

16. The method of claim 15, wherein the unified ranking function is expressed as:

17. The method of claim 16, wherein weight parameters λ

_i, μ

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

18. 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 a first set and a second set of documents, computing a value of a unified ranking function that is a function of a search query and a corresponding document, the unified ranking function comprising a cross-lingual generative probability that is a summation calculated based on a first term descriptive of a probability of translating an observed document from the second set of documents that is in the second language to a first language and a second term descriptive of a monolingual query generative probability of the search query being in the first language given the observed document that is in the second language from the second set of documents; and

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

19. The one or more computer readable media of claim 18, wherein the unified ranking function is expressed in terms comprising:

20. The one or more computer readable media of claim 18, 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: