SYSTEM AND METHOD FOR SEMI-AUTOMATIC CREATION AND MAINTENANCE OF QUERY EXPANSION RULES

• US 20090292700A1
• Filed: 05/23/2008
• Published: 11/26/2009
• 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, Roulland, Frederic, Kaplan, Aaron N., Willamowski, Jutta K.
• Granted Patent: US 8,103,669 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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:

a candidate detection module, which automatically extracts candidate synonymy pairs from expressions used by users in queries when searching an associated knowledge base;

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.

2. The system of claim 1, wherein the queries are grouped into user sessions, each user session including a first query and a subsequent reformulated query, and wherein the candidate detection module generates each synonymy pair from a first query and a reformulated query of the same user session.

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

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

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

6. The system of claim 5, 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.

7. 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.

8. 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.

9. The system of claim 1, wherein the candidate detection module computes reformulation frequencies for each of a set of the candidate synonymy pairs and optionally performs at least one of:

filtering out candidate synonymy pairs which are below a threshold reformulation frequency; and

ranking candidate synonymy pairs based on their reformulation frequencies.

10. 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.

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

12. 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;

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 queries are grouped into user sessions, each user session including a first query and a subsequent reformulated query, and wherein each synonymy pair comprises a first term extracted from a first query and a second term extracted from a reformulated query of the same user session.

14. 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.

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

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

17. 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.

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

19. The method of claim 17, 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.

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

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

22. 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.

23. A computer program product encoding instructions, which when executed on a computer causes the computer to perform the method of claim 12.

24. A method for query expansion comprising:

providing a log for each of a plurality of prior sessions in which a user searches a knowledge base, each session log comprising a user query and a reformulated user query when searching a knowledge base;

for at least one of the logs, automatically extracting a candidate synonymy pair from the user query and reformulated user query, the candidate synonymy pair comprising a first term extracted from the user query and a second term extracted from the reformulated query;

defining a synonymy rule based on the extracted candidate synonymy pair and optionally a context restriction; and

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