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

• US 20040243568A1
• Filed: 03/22/2004
• Published: 12/02/2004
• Est. Priority Date: 08/24/2000
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Wang, Hai-Feng, Yang, Qiang, Lee, Kai-Fu
• Application Number:
  US10/806,789
• Publication Number:
  US 20040243568A1
• Time in Patent Office: Days
• US Class Current: 707/3
• 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. Canceled

2. Canceled

3. Canceled

4. Canceled

5. Canceled

6. Canceled

7. Canceled

8. Canceled

9. Canceled

10. Canceled

11. Canceled

12. Canceled

13. Canceled

14. Canceled

15. Canceled

16. Canceled

17. Canceled

18. Canceled

19. Canceled

20. Canceled

21. Canceled

22. Canceled

23. Canceled

24. Canceled

25. Canceled

26. Canceled

27. Canceled

28. Canceled

29. Canceled

30. Canceled

31. Canceled

32. Canceled

33. Canceled

34. Canceled

35. Canceled

36. Canceled

37. A method comprising:

receiving a query;

mapping the query to from a query space to a question space to identify associated frequently asked questions;

mapping the questions from the question space to a template space to identify associated templates;

mapping the templates from the template space to an answer space to identify associated answers; and

returning the answers in response to the query.

38. A method as recited in claim 37, wherein the mapping from the query space to the question space comprises:

parsing the query to identify at least one associated concept; and

correlating the concept to one or more frequently asked questions.

39. A method as recited in claim 37, wherein the mapping from the question space to the template space comprises cross-indexing from a first table containing question identifications to a second table containing templates identifications.

40. A method as recited in claim 39, wherein the mapping from the template space to the answer space comprises cross-indexing from the second table to a third table containing answer identifications.

41. A method as recited in claim 37, further comprising:

presenting the answers to a user for confirmation as to which of the answers represent the user'"'"'s intentions in the query;

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.

42. Canceled

43. Canceled

44. Canceled

45. Canceled

46. Canceled

47. Canceled

48. Canceled

49. Canceled

50. Canceled

51. Canceled

52. Canceled

53. Canceled

54. Canceled

55. Canceled

56. Canceled

57. Canceled

58. Canceled

59. Canceled

60. Canceled

61. Canceled

62. Canceled

63. Canceled

64. Canceled

65. Canceled

66. Canceled

67. Canceled

68. Canceled

69. Canceled

70. Canceled

71. Canceled

72. A method of parsing a search query, comprising:

segmenting the search query into individual character strings;

producing a parse tree from at least one parsable character string of the search query; and

generating at least one keyword based at least one non-parsable character string of the search query.

73. The method of claim 72, further comprising:

conducting keyword searching using the at least once keyword.

74. The method of claim 72, wherein the parse tree represents a collection of concepts related to the search query.

75. The method of claim 74, further comprising matching the parsed concepts to a list of frequently asked questions.

76. The method of claim 75, further comprising:

identifying at least one answer associated with the list of frequently asked questions that match the parsed concepts and keywords; and

presenting the at least one answer to a user in a user interface that permits a user to select a desired answer from the one or more answers.

77. The method of claim 76, further comprising:

logging the search query and at least one answer selected by the user in a log database; and

analyzing the log database to derive at least one weighting factor indicating how relevant the frequently asked questions are to the parsed concepts and keywords.

78. A parser for a search engine, comprising:

a segmentation module that segments a search query into one or more individual character strings;

a natural language parser module that produces a parse tree from one or more parsable character strings of the search query; and

a keyword searcher to identify one or more keywords in the search query and to output the keywords.

79. The parser of claim 78, wherein the parse tree represents a collection of concepts related to the search query.

80. The parser of claim 78, further comprising a search module that matches the parsed concepts to a list of frequently asked questions.

81. The parser of claim 80, wherein the search module:

identifies at least one answer associated with the list of frequently asked questions that match the parsed concepts and keywords; and

presents the at least one answer to a user in a user interface that permits a user to select a desired answer from the one or more answers.

82. The parser of claim 81, wherein the search module:

logs the search query and at least one answer selected by the user in a log database; and

analyzes the log database to derive at least one weighting factor indicating how relevant the frequently asked questions are to the parsed concepts and keywords.