Mining transliterations for out-of-vocabulary query terms

• US 8,332,205 B2
• Filed: 01/09/2009
• Issued: 12/11/2012
• Est. Priority Date: 01/09/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Krishnan, Saravanan, Udupa, Uppinakuduru Raghavendra
• Primary Examiner(s): Desir, Pierre-Louis
• Assistant Examiner(s): Sirjani, Fariba
• Application Number:
  US12/350,981
• Publication Number:
  US 20100185670A1
• Time in Patent Office: 1,432 Days
• Field of Search: 704 1- 10, 704/277
• US Class Current: 704/4
• CPC Class Codes: G06F 16/3335 Syntactic pre-processing, e.g. stopword elimination, stemming
• CPC Class Codes: G06F 16/3337 Translation of the query language, e.g. Chinese to English
• CPC Class Codes: G06F 40/129 Handling non-Latin characters, e.g. kana-to-kanji conversion

Abstract

An approach is described for using a query expressed in a source language to retrieve information expressed in a target language. The approach uses a translation dictionary to convert terms in the query from the source language to appropriate terms in the target language. The approach determines viable transliterations for out-of-vocabulary (OOV) query terms by retrieving a body of information based on an in-vocabulary component of the query, and then mining the body of information to identify the viable transliterations for the OOV query terms. The approach then adds the viable transliterations to the translation dictionary. The retrieval, mining, and adding operations can be repeated one or more or times.

Claims

1. A method, implemented using electrical data processing functionality, for retrieving information, comprising:

receiving a query in a source language, the query having one or more query terms;

determining whether each of the query terms is present in a translation dictionary, the translation dictionary mapping terms from the source language to a target language, each query term that is present in the translation dictionary comprising an in-vocabulary term, and each query term that is not present in the translation dictionary comprising an out-of-vocabulary (OOV) term;

translating each in-vocabulary term to a translated term in the target language using the translation dictionary, to provide a set of one or more translated terms;

identifying at least one document that is selected from a collection of documents in the target language based on the set of translated terms, said at least one document including a plurality of candidate words in the target language;

performing mining analysis to attempt to extract a viable transliteration of each OOV term of the query from said at least one document by;

(a) selecting an OOV term in the query for analysis, to provide a selected OOV term;

(b) determining, after said selecting of the OOV term, whether the OOV term is a qualifying OOV term;

(c) selecting a candidate word in said at least one document, to provide a selected candidate word;

(d) determining, after said selecting of the candidate word, whether the selected candidate word is a qualifying candidate word;

(e) determining a transliteration measure between the selected candidate word and the selected OOV term, without first having generated a transliteration for the selected OOV term, said determining of the transliteration measure being performed when the selected candidate word is a qualifying candidate word and the selected OOV term is a qualifying OOV term;

(f) determining whether the selected candidate word is a viable transliteration of the selected OOV term based on the transliteration measure; and

performing operations (a) through (f) for each possible other pairing of an OOV term in the query and a candidate word in said at least one document;

updating the translation dictionary to include each viable transliteration identified by the mining analysis, to provide an updated translation dictionary and an updated set of translated terms for the query; and

repeating said identifying, performing the mining analysis, and updating, at least one time,

said receiving, determining whether each of the query terms is present in a translation dictionary, translating, identifying, performing the mining analysis, updating, and repeating being performed by the electrical data processing functionality.

2. The method of claim 1, wherein the source language and the target language have different respective orthographies.

3. The method of claim 1, wherein the source language and the target language use different respective phonetic alphabets.

4. The method of claim 1, wherein the mining analysis is performed without consideration of whether each selected OOV term is a named entity and without consideration of whether each selected candidate word is a named entity.

5. The method of claim 1, further comprising supplementing the mining analysis by performing machine transliteration.

6. The method of claim 5, wherein the machine transliteration is applied to an OOV term under consideration after determination that the mining analysis has been unsuccessful in generating a viable transliteration for the OOV term under consideration.

7. The method of claim 1, wherein a qualifying OOV term is an OOV term that is determined to be transliteratable.

8. The method of claim 1, wherein a qualifying candidate word is a candidate word that is determined to be transliteratable.

9. The method of claim 1, wherein a qualifying candidate word is a candidate word that has a length that differs from a length of the selected OOV term by no more than a prescribed number of characters.

10. A tangible computer-readable storage medium for storing computer-readable instructions, the computer-readable instructions providing an information retrieval system when executed by one or more processing devices, the computer-readable instructions performing a method comprising:

receiving a query in a source language, the query having one or more query terms;

determining whether each of the query terms is present in a translation dictionary, the translation dictionary mapping terms from the source language to a target language, each query term that is present in the translation dictionary comprising an in-vocabulary term, and each query term that is not present in the translation dictionary comprising an out-of-vocabulary (OOV) term;

translating each in-vocabulary term to a translated term in the target language using the translation dictionary, to provide a set of one or more translated terms;

identifying at least one document that is selected from a collection of documents in the target language based on the set of translated terms, said at least one document including a plurality of candidate words in the target language;

performing mining analysis to attempt to extract a viable transliteration of each OOV term of the query from said at least one document by;

(a) selecting an OOV term in the query for analysis, to provide a selected OOV term;

(b) determining, after said selecting of the OOV term, whether the OOV term is transliteratable;

(c) selecting a candidate word in said at least one document, to provide a selected candidate word;

(d) determining, after said selecting of the candidate word, whether the selected candidate word is transliteratable, and whether the selected candidate word has a length that differs from a length of the selected OOV term by no more than a prescribed number of characters;

(e) determining a transliteration measure between the selected candidate word and the selected OOV term, without first having generated a transliteration for the selected OOV term, said determining of the transliteration measure being performed when the selected OOV term and the selected candidate word are each transliteratable, and when the length of the selected OOV differs from the length of the selected OOV term by no more than a prescribed number of characters;

(f) determining whether the selected candidate word is a viable transliteration of the selected OOV term based on the transliteration measure; and

performing operations (a) through (f) for each possible other pairing of an OOV term in the query and a candidate word in said at least one document;

updating the translation dictionary to include each viable transliteration identified by the mining analysis, to provide an updated translation dictionary and an updated set of translated terms for the query; and

repeating said identifying, performing the mining analysis, and updating, at least one time.

11. The tangible computer-readable storage medium of claim 10, wherein the mining analysis is performed without consideration of whether each selected OOV term is a named entity and without consideration of whether each selected candidate word is a named entity.

12. An information retrieval system, implemented by electrical data processing functionality, for retrieving information, comprising:

a data store that provides a translation dictionary for correlating terms in a source language to corresponding terms in a target language; and

a transliteration processing module configured to convert queries in the source language to respective counterparts in the target language, the queries encompassing a query that includes an in-vocabulary component and an out-of-vocabulary (OOV) component, the in-vocabulary component comprising at least one in-vocabulary term that is included in the translation dictionary, and the OOV component comprising at least one OOV term that is not included in the translation dictionary, the transliteration processing module comprising;

an in-vocabulary determination module configured to determine, using the translation dictionary, a translated term for each in-vocabulary term of the query, to provide a set of one or more translated terms;

a mining module configured to attempt to identify, within a body of information, a viable transliteration of each OOV term in the query, the body of information being identified based on the set of translated terms provided by the in-vocabulary determination module,

wherein the body of information includes a plurality of candidate words in the target language, and wherein the mining module is configured to analyze each pairing of a selected OOV term in the query and a selected candidate word in the body of information without first having generated a transliteration for the selected OOV term and without consideration of whether the OOV term is a named entity, by attempting to;

determine a transliteration measure between the selected candidate word and the selected OOV term when the selected candidate word is a qualifying candidate word and the selected OOV term is a qualifying OOV term; and

determine whether the selected candidate word is a viable transliteration of the selected OOV term based on the transliteration measure; and

an updating module configured to add each viable transliteration identified by the mining module to the translation dictionary to provide an updated translation dictionary.

13. The information retrieval system of claim 12, further comprising a document retrieval module, the document retrieval module being configured to retrieve the body of information.

14. The information retrieval system of claim 13, wherein the body of information comprises at least one document, and wherein the document retrieval module is configured to select said at least one document from a collection of documents based on the set of translated terms.

15. The information retrieval system of claim 12, wherein the information retrieval system is further configured to identify another body of information associated with the in-vocabulary component of the query, using the updated translation dictionary.

16. The information retrieval system of claim 12, wherein the source language and the target language have different respective orthographies.

17. The information retrieval system of claim 12, wherein the source language and the target language use different respective phonetic alphabets.

18. The information retrieval system of claim 12, wherein the qualifying OOV term is an OOV term that is determined to be transliteratable.

19. The information retrieval system of claim 12, wherein the qualifying candidate word is a candidate word that is determined to be transliteratable, and has a length that differs from a length of the selected OOV term by no more than a prescribed number of characters.

20. The information retrieval system of claim 12, further including a machine transliteration module configured to perform machine transliteration, wherein the information retrieval system is configured to invoke the machine transliteration module for an OOV term under consideration upon determining that the mining module has been unsuccessful in generating a viable transliteration for the OOV term under consideration.