Cross-lingual query suggestion

• US 8,051,061 B2
• Filed: 02/19/2008
• Issued: 11/01/2011
• Est. Priority Date: 07/20/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Niu, Cheng, Zhou, Ming
• Primary Examiner(s): DANG, THANH HA T
• Application Number:
  US12/033,308
• Publication Number:
  US 20090024613A1
• Time in Patent Office: 1,351 Days
• Field of Search: 707/706, 707/748, 707/749, 707/760, 704/1, 704/8, 704/9
• US Class Current: 707/706
• CPC Class Codes: G06F 16/3337 Translation of the query language, e.g. Chinese to English
• CPC Class Codes: G06F 16/3338 Query expansion

Abstract

Cross-lingual query suggestion (CLQS) aims to suggest relevant queries in a target language for a given query in a source language. The cross-lingual query suggestion is improved by exploiting the query logs in the target language. CLQS provides a method for learning and determining a similarity measure between two queries in different languages. The similarity measure is based on both translation information and monolingual similarity information, and in one embodiment uses both the query log itself and click-through information associated therewith. Monolingual and cross-lingual information such as word translation relations and word co-occurrence statistics may be used to estimate the cross-lingual query similarity with a discriminative model.

Claims

1. A method for query suggestion performed by a processor executing computer-executable instructions stored on a memory device, the method comprising:

for an input query in source language, identifying a query in target language from a query log of a search engine, the query in target language and the input query in source language having a cross-lingual similarity, the identifying the query in target language from the query log comprising;

providing a plurality of candidate queries in target language;

evaluating the plurality of candidate queries in target language at least partly by deducing a monolingual similarity between the input query in source language and a translation of a respective candidate query from target language to source language; and

ranking the plurality of candidate queries in target language using a cross-lingual query similarity score, the cross-lingual query similarity score being based on a plurality of features and a weight of each feature in calculating the cross-lingual query similarity score; and

suggesting the query in target language as a cross-lingual query at least partly based on click-through information of documents selected by users for the query in target language.

2. The method as recited in claim 1, wherein the cross-lingual query similarity score of the input query in source language q_e and the candidate query in target language q_f is computed using an equation sim_CL(q_f,q_e)=w·

φ

(ƒ

(q_f,q_e)), where sim_CL(q_f, q_e) is the cross-lingual query similarity score, ƒ

(q_f, q_e) is a feature vector, φ

is a mapping from an input feature space onto a kernel space, and w is a weight vector in the kernel space.

3. The method as recited in claim 2, wherein the weight vector w is learned by a regression algorithm using a training set of input queries in source language and corresponding queries in target language.

4. The method as recited in claim 2, wherein the weight vector w is learned by a binary or ordinal classification algorithm in which cross-lingual query suggestions are categorized according to discontinuous class labels.

5. The method as recited in claim 2, wherein the weight vector w is learned by fitting a training set based on a principle that cross-lingual similarity of a pair of queries in two different languages fits the monolingual similarity between one query and a translation of the other query of the pair.

6. The method as recited in claim 2, wherein the feature vector f (q_f, q_e) includes at least two of the feature functions selected from bilingual dictionary-based translation score, bidirectional translation score, frequency in Web mining snippets, and monolingual query suggestion-based feature.

7. The method as recited in claim 1, wherein the identifying the query in target language from the query log further comprises:

identifying one or more queries in target language whose cross-lingual query similarity score with the input query meets or exceeds a threshold.

8. The method as recited in claim 7, wherein the threshold is learned using a development data set by fitting a monolingual query suggestion output.

9. The method as recited in claim 1, wherein the providing the plurality of candidate queries in target language comprises:

ranking potential query translations of the input query in source language using term-term cohesion, the potential query translations being constructed from a bilingual dictionary;

selecting a set of top query translations based on ranking result; and

for each top query translation, retrieving from the query log at least one query containing the same keywords as the top query translation.

10. The method as recited in claim 1, wherein the providing the plurality of candidate queries in target language comprises:

ranking queries in the query log using bidirectional translation probability derived from a parallel corpora of the source language and the target language; and

selecting a set of top queries based on ranking result.

11. The method as recited in claim 1, wherein the providing the plurality of candidate queries in target language comprises:

mining candidate queries in the target language on the Web, the each candidate query being a translation of the input query in source language or semantically related to the input query in source language.

12. The method as recited in claim 11, further comprising:

ranking the candidate queries using a co-occurrence double-check measure;

selecting a set of top candidate queries based on ranking result.

13. The method as recited in claim 1, wherein providing the plurality of candidate queries in target language comprises:

providing a set of initial candidate queries in target language; and

expanding the set of initial candidate queries in target language by identifying additional candidate queries having a high monolingual similarity with each initial candidate query in target language.

14. A method for query suggestion performed by a processor executing computer-executable instructions stored on a memory device, the method comprising:

receiving an input query in source language;

providing a plurality of candidate queries in target language, at least part of the plurality of candidate queries in target language being selected from a query log of a search engine;

evaluating the plurality of candidate queries in target language at least partly by deducing a monolingual similarity between the input query in source language and a translation of a respective candidate query from target language to source language;

ranking the plurality of candidate queries in target language using a cross-lingual query similarity score, the cross-lingual query similarity score being based on a plurality of features and a weight of each feature in calculating the cross-lingual query similarity score; and

from top ranking candidate queries in target language, suggesting a query in target language as a cross-lingual query at least partly based on click-through information of documents selected by users for the plurality of candidate queries in target language.

15. The method as recited in claim 14, wherein the providing the plurality of candidate queries in target language comprises:

ranking potential query translations of the input query in source language using term-term cohesion, the potential query translations being constructed from a bilingual dictionary;

selecting a set of top query translations based on ranking result; and

for each top query translation, retrieving from the query log at least one query containing the same keywords as the top query translation.

16. The method as recited in claim 14, wherein the providing the plurality of candidate queries in target language comprises:

ranking queries in the query log using a bidirectional translation probability derived from a parallel corpora of the source language and the target language; and

selecting a set of top queries based on ranking result.

17. The method as recited in claim 14, further comprising:

mining additional candidate queries in the target language on the Web, each additional candidate query being a translation of the input query in source language or semantically related to the input query in source language.

18. The method as recited in claim 14, further comprising:

expanding the plurality of candidate queries in target language by identifying additional candidate queries having a high monolingual similarity with each initial candidate query in target language.

19. A method for query suggestion performed by a processor executing computer-executable instructions stored on a memory device, the method comprising:

for an input query in source language, identifying a query in target language from a query log of a search engine, the query in target language and the input query in source language having a cross-lingual similarity, the identifying the query in target language from the query log comprising;

providing a plurality of candidate queries in target language; and

ranking the plurality of candidate queries in target language using a cross-lingual query similarity score, the cross-lingual query similarity score of the input query in source language q_e and the candidate query in target language q_f being computed using an equation sim_CL(q_f,q_e)=w·

φ

(ƒ

(q_f,q_e)), sim_CL(q_f, q_e) being the cross-lingual query similarity score, f (q_f, q_e) being a feature vector, the feature vector f (q_f, q_e) including at least two of the feature functions selected from bilingual dictionary-based translation score, bidirectional translation score, frequency in Web mining snippets, and monolingual query suggestion-based feature, φ

being a mapping from an input feature space onto a kernel space, and w being a weight vector in the kernel space; and

suggesting the query in target language as a cross-lingual query.

20. A method for query suggestion performed by a processor executing computer-executable instructions stored on a memory device, the method comprising:

for an input query in source language, identifying a query in target language from a query log of a search engine, the query in target language and the input query in source language having a cross-lingual similarity, the identifying the query in target language from the query log comprising;

providing a plurality of candidate queries in target language;

evaluating the plurality of candidate queries in target language at least partly by deducing a monolingual similarity between the input query in source language and a translation of a respective candidate query from target language to source language; and

ranking the plurality of candidate queries in target language using a cross-lingual query similarity score, the cross-lingual query similarity score of the input query in source language q_e and the candidate query in target language q_f being computed using an equation sim_CL(q_f,q_e)=w·

φ

(ƒ

(q_f,q_e)), sim_CL(q_f, q_e) being the cross-lingual query similarity score, ƒ

(q_f, q_e) being a feature vector, φ

being a mapping from an input feature space onto a kernel space, and w being a weight vector in the kernel space; and

suggesting the query in target language as a cross-lingual query at least partly based on click-through information of documents selected by users for the query in target language.