System and method for semi-automatic creation and maintenance of query expansion rules

• US 8,103,669 B2
• Filed: 05/23/2008
• Issued: 01/24/2012
• Est. Priority Date: 05/23/2008
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Castellani, Stefania, Kaplan, Aaron N., Roulland, Frederic, Willamowski, Jutta K.
• Primary Examiner(s): LU, KUEN S
• Application Number:
  US12/126,115
• Publication Number:
  US 20090292700A1
• Time in Patent Office: 1,341 Days
• Field of Search: 707/758, 707/802, 707/736
• US Class Current: 707/736
• CPC Class Codes: G06N 5/025 Extracting rules from data

Abstract

A system and method enable semi-automated generation of query expansion rules for searching a knowledge base. Candidate synonymy pairs are automatically extracted from queries made by users when searching a knowledge base. Synonymy rules are defined, based on the extracted candidate synonymy pairs, and may be context dependent. Query expansion rules based on the defined synonymy rules can then be exported to a storage medium for use in expansion of new user queries when searching the knowledge base.

Claims

1. A semi-automated system for generating query expansion rules comprising:

memory which stores;

a candidate detection module, which automatically extracts candidate synonymy pairs from expressions used by users in queries when searching an associated knowledge base, the user queries being grouped into user sessions based on session information, each user session including a first user query input by a user and a subsequent reformulated user query input by the same user, the candidate detection module generating each synonymy pair from a term of a first user query input by a user and a term of a reformulated user query input by the same user in the same user session;

an interactive definition module for defining synonymy rules based on the extracted candidate synonymy pairs; and

a synonymy rule export module which exports query expansion rules based on the defined synonymy rules to a storage medium for use in expansion of user queries when searching the knowledge base; and

a computer processor which executes the modules.

2. The system of claim 1, wherein the candidate detection module automatically generates a synonymy pair comprising a first term and a second term, the first term being present in the first query input by the user and absent from the reformulated query input by the user and the second term being present in the reformulated query and absent from the first query.

3. The system of claim 2, wherein the interactive definition module is configured for filtering out synonymy pairs generated automatically by the candidate detection module where the second term is absent from the knowledge base.

4. The system of claim 2, wherein some of the synonymy rules each include a synonymy pair and a context restriction for the synonymy pair.

5. The system of claim 4, wherein the interactive definition module is configured for generating a candidate context for generating the context restriction, the candidate context for the restriction being based on at least one of:

a query term which is present in at least one query with the first term;

a knowledge base term which is present in the knowledge base in association with the second term.

6. The system of claim 1, further comprising a user interface whereby the interactive definition module interacts with an editor for definition of the synonymy rules.

7. The system of claim 1, further comprising an evaluation module which applies the synonymy rules to a set of prior user sessions to assist an editor in evaluating the synonymy rules in terms of their impact on search results.

8. The system of claim 1, wherein the candidate detection module computes reformulation frequencies for each of a set of the candidate synonymy pairs and filters out candidate synonymy pairs which are below a threshold reformulation frequency, the reformulation frequency being the frequency with which a query containing a term T1 is followed in the same session by another query that is identical except that term T1 is replaced by a term T2 and optionally ranks candidate synonymy pairs based on their reformulation frequencies.

9. In combination, a search engine system and the system of claim 1, the search engine system comprising a search engine which generates logs of user sessions with the knowledge base and the storage medium which stores the query expansion rules exported by the export module.

10. A method for generating query expansion rules comprising generating at least one query expansion rule with the system of claim 1.

11. The system of claim 1, wherein the interactive definition module provides for interactive contextualizing of the synonymy rules.

12. A method for generating query expansion rules comprising:

with a computer comprising memory and a computer processor;

automatically extracting candidate synonymy pairs from expressions used by users in queries when searching a knowledge base, the user queries being grouped into user sessions based on session information, each user session including a first user query input by a user and a subsequent reformulated user query input by the same user,

wherein the extracting includes generating each candidate synonymy pair from a term of a first user query input by a user and a term of a reformulated user query input by the same user in the same user session;

providing for interactive definition of synonymy rules based on the extracted candidate synonymy pairs and for contextualizing the synonymy rules; and

exporting query expansion rules based on the defined synonymy rules to a storage medium for use in expansion of user queries when searching the knowledge base.

13. The method of claim 12, wherein the first term is present in the first query and absent from the reformulated query and the second term is present in the reformulated query and absent from the first query.

14. The method of claim 12, further comprising filtering out synonymy pairs where the second term is absent from the knowledge base.

15. The method of claim 12, further comprising filtering out candidate synonymy pairs for which a reformulation frequency is below a threshold.

16. The method of claim 12, wherein the defining of the synonymy rules includes generating, for at least one of the extracted candidate synonymy pairs, a context restriction, the synonymy rule comprising the candidate pair and the context restriction.

17. The method of claim 16, wherein the context restriction is generated interactively by an editor.

18. The method of claim 16, further comprising automatically generating a candidate context for generating the context restriction, the candidate context being based on at least one of:

a common term which is present in both the first query and second query; and

a knowledge base term which is present in the knowledge base in association with the second term.

19. The method of claim 16, further comprising presenting candidate contexts and candidate pairs to an editor for definition of the synonymy rules.

20. The method of claim 12, further comprising evaluating the synonymy rules in terms of their impact on search results.

21. The method of claim 12, further comprising, after a synonymy rule has been defined:

automatically inferring an additional candidate synonymy rule based on at least one of;

symmetry of the defined synonymy rule, and

transitivity of the defined synonymy rule with another synonymy rule; and

presenting the additional candidate synonymy rule to an editor for evaluation.

22. The method of claim 12, further comprising:

applying a query expansion rule based on the defined synonymy rule to a new user query when searching the knowledge base.

23. A computer program product comprising a non-transitory recording medium encoding instructions, which when executed on a computer causes the computer to perform a method for generating query expansion rules comprising:

automatically extracting candidate synonymy pairs from expressions used by users in queries when searching a knowledge base, the user queries being grouped into user sessions based on session information, each user session including a first user query input by a user and a subsequent reformulated user query input by the same user, the extracting including generating each candidate synonymy pair from a term of a first user query input by a user and a term of a reformulated user query input by the same user in the same user session;

providing for interactive definition of synonymy rules based on the extracted candidate synonymy pairs and for contextualizing the synonymy rules; and

exporting query expansion rules based on the defined synonymy rules to a storage medium for use in expansion of user queries when searching the knowledge base.