Semi-automatic example-based induction of semantic translation rules to support natural language search

• US 8,041,697 B2
• Filed: 08/29/2008
• Issued: 10/18/2011
• Est. Priority Date: 08/31/2007
• Status: Active Grant

• Current Assignee: Zhigu Holdings Limited
• Original Assignee: Microsoft Corporation
• Inventors: Van Den Berg, Martin Henk, Copperman, Hannah, Rayner, Emmanuel, Thione, Giovanni Lorenzo, Crouch, Richard
• Primary Examiner(s): Brown; Sheree N
• Application Number:
  US12/201,066
• Publication Number:
  US 20090138454A1
• Time in Patent Office: 1,145 Days
• Field of Search: 707/705, 704/9
• US Class Current: 707/705
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/3334 Selection or weighting of terms from queries, including natural language queries
• CPC Class Codes: G06F 16/3344 using natural language analysis

Abstract

Technologies are described herein for generating a semantic translation rule to support natural language search. In one method, a first expression and a second expression are received. A first representation is generated based on the first expression, and a second representation is generated based on the second expression. Aligned pairs of a first term in the first representation and a second term in the second representation are determined. For each aligned pair, the first term and the second term are replaced with a variable associated with the aligned pair. Word facts that occur in both the first representation and the second representation are removed from the first representation and the second representation. The remaining word facts in the first representation are replaced with a broader representation of the word facts. The translation rule including the first representation, an operator, and the second semantic representation is generated.

Claims

1. A method for generating a translation rule to support natural language search, comprising:

receiving a first expression and a second expression;

generating a first representation based on the first expression;

generating a second representation based on the second expression;

determining aligned pairs of a first term in the first representation and a second term in the second representation;

replacing, for each aligned pair, the first term in the first representation and the second term in the second representation with a variable associated the aligned pair;

upon replacing the variables that correspond to the aligned pairs with the variable, removing word facts from the first representation and the second representation that occur in both the first representation and the second representation;

upon removing the word facts that correspond to the replaced variables, replacing the remaining word facts in the first representation with a broader representation of the word facts; and

upon replacing the remaining word facts in the first representation with the broader representation, generating the translation rule including the first representation, an operator, and the second semantic representation.

2. The method of claim 1, wherein the first representation and the second representation comprise semantic representations.

3. The method of claim 1, wherein generating a first representation based on the first expression comprises parsing the first expression into the first representation;

and wherein generating the second semantic representation based on the second expression comprises parsing the second expression into the second representation.

4. The method of claim 1, wherein the first representation and the second semantic representation each comprise the word facts and roles.

5. The method of claim 1, wherein determining aligned pairs based on the first representation and the second representation comprises:

matching variables in the first representation with variables in the second representation that correspond to the same word; and

upon matching the variables in the first representation with the variables in the second representation that correspond to the same word, matching the remaining variables in the first representation with the remaining variables in the second representation based on induction.

6. The method of claim 1, wherein replacing the remaining word facts in the first representation with a broader representation of the word facts comprises replacing the remaining word facts in the first representation with a broader representation of the word facts that include at least one of synonyms, hyponyms, hypernyms, aliases, or valences.

7. The method of claim 1, wherein the operator comprises a logical conjunction or a logical disjunction.

8. The method of claim 1, further comprising applying the translation rule during content acquisition to convert a representation of a search result that is stored in an index.

9. The method of claim 1, further comprising applying the translation rule during user search to convert a representation of a search query.

10. The method of claim 1, wherein the first expression and the second expression are semantically different.

14. The method of claim 11, The method of claim 1, wherein replacing the remaining word facts in the first representation with a broader representation of the word facts comprises replacing the remaining word facts in the first representation with a broader representation of the word facts that include at least one of synonyms, hyponyms, hypernyms, aliases, or valences.

11. A method for generating a translation rule to support natural language search, comprising:

receiving a first natural language expression and a second natural language expression, the first expression being semantically different from the second expression;

generating a first representation by parsing the first expression;

generating a second representation by parsing the second expression, the first representation and the second representation each comprising word facts and roles;

determining aligned pairs based on the first semantic representation and the second semantic representation;

replacing, in the first representation and the second representation, variables that correspond to the aligned pairs with a generic variable;

upon replacing the variables that correspond to the aligned pairs with the generic variable, removing the word facts from the first representation and the second semantic representation that that occur in both the first and second representation;

upon removing the word facts that correspond to the replaced variables, replacing the remaining word facts in the first representation with a broader representation of the word facts; and

upon replacing the remaining word facts in the first representation with the broader representation, generating the translation rule including the first representation, an operator, and the second representation.

12. The method of claim 11, wherein the representation is a semantic representation.

13. The method of claim 11, wherein determining aligned pairs based on the first representation and the second representation comprises:

matching variables in the first representation with variables in the second representation that correspond to the same word; and

upon matching the variables in the first representation with the variables in the second representation that correspond to the same word, matching the remaining variables in the first representation with the remaining variables in the second representation based on induction.

15. The method of claim 11, wherein the operator comprises a logical conjunction or a logical disjunction.

16. The method of claim 11, further comprising applying the translation rule during content acquisition to convert a representation of a search result that is stored in an index, the representation matching the first representation.

17. The method of claim 11, further comprising applying the translation rule during user search to convert a representation of a search query, the representation matching the first representation.

18. A computer-readable medium having computer-executable instructions stored thereon which, when executed by a computer, cause the computer to:

receive a first expression and a second expression, the first expression being semantically different from the second expression;

generate a first semantic representation by parsing the first expression;

generate a second semantic representation by parsing the second expression, the first semantic representation and the second semantic representation each comprising word facts and roles, the roles identifying relationships between the word facts;

determine aligned pairs based on the first semantic representation and the second semantic representation;

replace, in the first semantic representation and the second semantic representation, variables that correspond to the aligned pairs with a generic variable by matching variables in the first semantic representation with variables in the second representation that correspond to the same word and by matching the remaining variables in the first semantic representation with the remaining variables in the second semantic representation based on induction;

upon replacing the variables that correspond to the aligned pairs with the generic variable, remove the word facts from the first semantic representation and the second semantic representation that correspond to the replaced variables;

upon removing the word facts that correspond to the replaced variables, replace the remaining word facts in the first semantic representation with a broader representation of the word facts; and

upon replacing the remaining word facts in the first semantic representation with the broader representation, generate a translation rule including the first semantic representation, an operator, and the second semantic representation.

19. The computer-readable storage medium of claim 18, having further computer-executable instructions stored thereon which, when executed by a computer, cause the computer to apply the translation rule during content acquisition to convert a semantic representation of a search result that is stored in a semantic index, the semantic representation matching the first semantic representation.

20. The computer-readable storage medium of claim 18, having further computer-executable instructions stored thereon which, when executed by a computer, cause the computer to apply the translation rule during user search to convert a semantic representation of a search query, the semantic representation matching the first semantic representation.