Search engine with natural language-based robust parsing for user query and relevance feedback learning

• US 6,766,320 B1
• Filed: 08/24/2000
• Issued: 07/20/2004
• Est. Priority Date: 08/24/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Yang, Qiang, Lee, Kai-Fu, Wang, Hai-Feng
• Primary Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US09/645,806
• Time in Patent Office: 1,426 Days
• Field of Search: 707/3-6, 707/9, 704/9
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24522 Translation of natural language queries to structured queries
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 2216/03 Data mining
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A search engine architecture is designed to handle a full range of user queries, from complex sentence-based queries to simple keyword searches. The search engine architecture includes a natural language parser that parses a user query and extracts syntactic and semantic information. The parser is robust in the sense that it not only returns fully-parsed results (e.g., a parse tree), but is also capable of returning partially-parsed fragments in those cases where more accurate or descriptive information in the user query is unavailable. A question matcher is employed to match the fully-parsed output and the partially-parsed fragments to a set of frequently asked questions (FAQs) stored in a database. The question matcher then correlates the questions with a group of possible answers arranged in standard templates that represent possible solutions to the user query. The search engine architecture also has a keyword searcher to locate other possible answers by searching on any keywords returned from the parser. The answers returned from the question matcher and the keyword searcher are presented to the user for confirmation as to which answer best represents the user'"'"'s intentions when entering the initial search query. The search engine architecture logs the queries, the answers returned to the user, and the user'"'"'s confirmation feedback in a log database. The search engine has a log analyzer to evaluate the log database to glean information that improves performance of the search engine over time by training the parser and the question matcher.

Claims

1. A method comprising:

parsing a search query to produce parsed concepts and keywords;

matching the parsed concepts and keywords to frequently asked questions;

conducting keyword searching on the keywords; and

returning results of the matching and the keyword searching.

2. A method as recited in claim 1, wherein the parsing comprises natural language parsing.

3. A method as recited in claim 1, wherein the matching and the conducting are performed concurrently.

4. A method as recited in claim 1, further comprising identifying answers associated with the frequently asked questions that match the parsed concepts and keywords.

5. A method as recited in claim 1, further comprising presenting the results in a user interface.

6. A method as recited in claim 1, further comprising logging the search query and the results.

7. A method as recited in claim 1, further comprising:

logging the search query in a database, the database containing many search queries; and

ascertaining frequently asked questions based on the search queries logged in the database.

8. A method as recited in claim 1, further comprising:

identifying answers associated with the frequently asked questions that match the parsed concepts and keywords; and

presenting the answers to a user for confirmation as to which answers represent the user'"'"'s intention in the search query.

9. A method as recited in claim 8, further comprising:

logging the search query and the answers confirmed by the user in a log database; and

analyzing the log database to derive weighting factors indicating how relevant the frequently asked questions are to the parsed concepts and keywords.

10. A method as recited in claim 9, further comprising:

logging the search query and the answers confirmed by the user in a log database; and

analyzing the log database to derive weighting factors indicating how relevant the answers are to the frequently asked questions.

11. A method as recited in claim 1, wherein the parsing is performed by a natural language parser, and further comprising:

logging the search query in a database; and

training the natural language parser based on search queries logged in the database.

12. A method as recited in claim 1, further comprising deriving a confidence rating indicating how probable the results pertain to the search query.

13. A method as recited in claim 12, further comprising assigning weighting factors to indicate how relevant the answers are to the questions.

14. A method as recited in claim 12, further comprising presenting the answers to a user for confirmation as to which of the answers represent the user'"'"'s intentions in the query.

15. A method as recited in claim 14, further comprising:

analyzing the query and the answers confirmed by the user; and

modifying the answers that are returned in response to the query based on information gleaned from the analyzing.

16. A method as recited in claim 12, wherein the parsing is performed by a natural language parser and further comprising evaluating the query, the fully-parsed output and the partially-parsed fragment to train the natural language parser.

18. A method as recited in claim 16, further comprising assigning a weighting factor indicative of how likely each answer corresponds to the one or more questions.

19. A method as recited in claim 16, further comprising deriving a confidence rating indicating how probable the possible answers pertain to the query.

17. A method comprising:

receiving a query;

parsing the query to produce at least one parsed concept;

matching the parsed concept to one or more questions;

identifying possible answers as being associated with the one or more questions;

receiving user confirmation of at least one of the possible answers; and

logging the query, the possible answers, and the user confirmation.

20. A method as recited in claim 17, further comprising:

analyzing the query, the possible answers, and the user confirmation; and

modifying the possible answers that are returned in response to the query based on information gleaned from the analyzing.

21. A search engine comprising:

a parser to parse a query using natural language parsing and produce at least one parsed concept;

a question matcher to match said at least one parsed concept or to at least one possible answer; and

a keyword searcher to search for other possible answers based on a keyword.

22. A search engine as recited in claim 21, wherein the parser produces one or more keywords and at least one of (1) a fully-parsed output, and (2) a partially-parsed fragment.

23. A search engine as recited in claim 21, wherein the question matcher comprises:

a database;

multiple tables stored in the database to hold information pertaining to concepts, questions, and answers; and

a matching module configured to correlate, via the tables, the concepts with the questions and the questions with answers.

24. A search engine as recited in claim 23, wherein the tables further hold weighting factors that indicate how relevant the questions are to the concepts, and how relevant the answers are to the questions.

25. A search engine as recited in claim 21, further comprising a user interface to present the possible answers returned from the question matcher and the keyword searcher.

26. A search engine as recited in claim 21, further comprising:

a user interface to present the possible answers returned from the question matcher and the keyword searcher to a user for confirmation regarding which of the answers represent the user'"'"'s intentions in the query;

a query analyzer to evaluate the query, the possible answers, and the answers confirmed by the user.

27. A search engine as recited in claim 21, further comprising a query log to log the query and the possible answers.

28. A search engine as recited in claim 21, further comprising:

a query log to log the query and the possible answers; and

the parser being trained from data in the query log.

29. A search engine comprising:

a user interface to facilitate entry of a natural language query string;

a natural language parser to parse the query string and output at least one of a fully-parsed output, partially-parsed fragment, and one or more individual keywords,

wherein the natural language parser includes;

a segmentation module to segment the query string into individual character strings; and

a natural language parser to parse certain character strings that are parsable and leave the non-parsable character strings unparsed, wherein the natural language parser outputs;

a parse tree; and

a keyword searcher to;

identify keywords in the query; and

output the keywords.

30. A search engine as recited in claim 29, further comprising a question matcher to match the fully-parsed output to a set of frequently asked questions.

31. A search engine as recited in claim 29, further comprising a question matcher to match the partially-parsed fragment to a set of frequently asked questions.

32. A search engine as recited in claim 29, further comprising a keyword searcher to conduct a keyword search using the one or more keywords.

33. A computer-readable medium having computer-executable instructions that, when executed, direct a computer to:

parse a search query using natural language parsing to produce parsed concepts and fragments;

match the parsed concepts and fragments to frequently asked questions;

identify answers associated with the frequently ask questions; and

return results of the matching to a user for confirmation as to which of the answers represent the user'"'"'s intentions in the query.

34. A computer-readable medium as recited in claim 33, further comprising computer-executable instructions that, when executed, direct a computer to:

identify keywords from the search query;

conduct keyword searching on the keywords; and

return results of the keyword matching.