Systems and methods for answering complex questions with mined natural language search results

• US 8,682,647 B1
• Filed: 01/13/2012
• Issued: 03/25/2014
• Est. Priority Date: 01/13/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Lee, John
• Primary Examiner(s): PULLIAS, JESSE SCOTT
• Application Number:
  US13/350,014
• Time in Patent Office: 802 Days
• Field of Search: None
• US Class Current: 704/9
• CPC Class Codes: G06F 16/3329 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking

Abstract

Embodiments relate to systems for, and methods of, answering complex questions with mined natural language search results. The systems and methods generally accept a natural language query, retrieve initial search results for the query, and then thin the retrieved results such that acceptable natural language replies to the query are identified. The natural language results may be further processed for presentation to the requestor.

Claims

1. A computer implemented method of providing a natural language answer to a natural language question, the method comprising:

receiving, over a computer network, a query comprising a grammatical question;

submitting the query to a lookup engine;

receiving initial search results from the lookup engine, the initial search results comprising a plurality of documents;

identifying, in the plurality of documents, a plurality of candidate sentences;

calculating a frequency of a plurality of n-grams appearing in the plurality of candidate sentences, wherein n ranges at least from 1 to 2;

calculating, for each candidate sentence, a measure of commonality between the candidate sentence and the query;

assigning, to each candidate sentence, a score, wherein the score comprises (1) the frequency of a plurality of n-grams appearing in the candidate sentence, and (2) the measure of commonality between the candidate sentence and the query;

sorting the candidate sentences according to score, whereby a rating of candidate sentences is produced; and

sending, over a computer network, a reply to the query, the reply comprising at least a top candidate sentence from the rating of candidate sentences.

2. The method of claim 1, wherein the lookup engine is a web based search engine.

3. The method of claim 1, wherein each score comprises a product of (1) the frequency of a plurality of n-grams appearing in the candidate sentence, and (2) the measure of commonality between the candidate sentence and the query.

4. The method of claim 1, wherein the measure of commonality comprises a count of common words.

5. The method of claim 1, wherein the initial search results comprise a ranking of the plurality of documents according to relevance;

wherein each score further comprises, for each candidate sentence, a rank of the candidate sentence according to the ranking of the plurality of documents.

6. The method of claim 5, wherein the score comprises a product of at least (1) the frequency of a plurality of n-grams appearing in the candidate sentence, (2) the measure of commonality between the candidate sentence and the query, and (3) the rank of the candidate sentence according to the ranking of the plurality of documents.

7. The method of claim 1, wherein the reply comprises candidate sentences whose scores meet a predetermined threshold.

8. The method of claim 1, wherein the reply comprises at least a top three candidate sentences according to the rating of candidate sentences.

9. The method of claim 1, wherein each score comprises the frequency of a plurality of n-grams appearing in the candidate sentence weighted according to n-gram length.

10. The method of claim 1, wherein each score comprises a geometric mean of (1) the frequency of a plurality of n-grams appearing in the candidate sentence, and (2) the measure of commonality between the candidate sentence and the query.

11. A system for providing a natural language answer to a natural language question, the system comprising:

an interface configured to receive, over a computer network, a query comprising a grammatical question;

an interface configured to submit the query to a lookup engine;

an interface configured to receive initial search results from the lookup engine, the initial search results comprising a plurality of documents;

a processor configured to identify, in the plurality of documents, a plurality of candidate sentences;

a processor configured to calculate a frequency of a plurality of n-grams appearing in the plurality of candidate sentences, wherein n ranges at least from 1 to 2;

a processor configured to calculate, for each candidate sentence, a measure of commonality between the candidate sentence and the query;

a processor configured to assign, to each candidate sentence, a score, wherein the score comprises (1) the frequency of a plurality of n-grams appearing in the candidate sentence, and (2) the measure of commonality between the candidate sentence and the query;

a processor configured to sort the candidate sentences according to score, whereby a rating of candidate sentences is produced; and

an interface configured to send, over a computer network, a reply to the query, the reply comprising at least a top candidate sentence from the rating of candidate sentences.

12. The system of claim 11, wherein the lookup engine is a web based search engine.

13. The system of claim 11, wherein each score comprises a product of (1) the frequency of a plurality of n-grams appearing in the candidate sentence, and (2) the measure of commonality between the candidate sentence and the query.

14. The system of claim 11, wherein the measure of commonality comprises a count of common words.

15. The system of claim 11, wherein the initial search results comprise a ranking of the plurality of documents according to relevance;

wherein each score further comprises, for each candidate sentence, a rank of the candidate sentence according to the ranking of the plurality of documents.

16. The system of claim 15, wherein the score comprises a product of at least (1) the frequency of a plurality of n-grams appearing in the candidate sentence, (2) the measure of commonality between the candidate sentence and the query, and (3) the rank of the candidate sentence according to the ranking of the plurality of documents.

17. The system of claim 11, wherein the reply comprises candidate sentences whose scores meet a predetermined threshold.

18. The system of claim 11, wherein the reply comprises at least a top three candidate sentences according to the rating of candidate sentences.

19. The system of claim 11, wherein each score comprises the frequency of a plurality of n-grams appearing in the candidate sentence weighted according to n-gram length.

20. The system of claim 11, wherein each score comprises a geometric mean of (1) the frequency of a plurality of n-grams appearing in the candidate sentence, and (2) the measure of commonality between the candidate sentence and the query.

21. A computer implemented method of providing a natural language answer to a natural language question, the method comprising:

receiving, over a computer network, a query comprising a grammatical question;

submitting the query to a lookup engine;

receiving initial search results from the lookup engine, the initial search results comprising a plurality of documents, wherein the initial search results comprise a ranking of the plurality of documents according to relevance;

identifying, in the plurality of documents, a plurality of candidate sentences;

calculating a frequency of a plurality of n-grams appearing in the plurality of candidate sentences, wherein n ranges at least from 1 to 2;

assigning, to each candidate sentence, a score, wherein the score comprises (1) the frequency of a plurality of n-grams appearing in the candidate sentence, and (2) a rank of the candidate sentence according to the ranking of the plurality of documents;

sorting the candidate sentences according to score, whereby a rating of candidate sentences is produced; and

sending, over a computer network, a reply to the query, the reply comprising at least a top candidate sentence from the rating of candidate sentences.

22. The method of claim 21, wherein the lookup engine is a web based search engine.

23. The method of claim 21, wherein each score comprises a product of (1) the frequency of a plurality of n-grams appearing in the candidate sentence, and (2) the rank of the candidate sentence according to the ranking of the plurality of documents.

24. The method of claim 21, wherein each score further comprises, for each candidate sentence, a measure of commonality between the candidate sentence and the query.

25. The method of claim 24, wherein the score comprises a product of at least (1) the frequency of a plurality of n-grams appearing in the candidate sentence, (2) the measure of commonality between the candidate sentence and the query, and (3) the rank of the candidate sentence according to the ranking of the plurality of documents.

26. The method of claim 25, wherein the measure of commonality comprises a count of common words.

27. The method of claim 21, wherein the reply comprises candidate sentences whose scores meet a predetermined threshold.

28. The method of claim 21, wherein the reply comprises at least a top three candidate sentences according to the rating of candidate sentences.

29. The method of claim 21, wherein each score comprises the frequency of a plurality of n-grams appearing in the candidate sentence weighted according to n-gram length.

30. The method of claim 21, wherein each score, comprises a geometric mean of (1) the frequency of a plurality of n-grams appearing in the candidate sentence, and (2) the rank of the candidate sentence according to the ranking of the plurality of documents.

31. A system for providing a natural language answer to a natural language question, the system comprising:

an interface configured to receive, over a computer network, a query comprising a grammatical question;

an interface configured to submit the query to a lookup engine;

an interface configured to receive initial search results from the lookup engine, the initial search results comprising a plurality of documents, wherein the initial search results comprise a ranking of the plurality of documents according to relevance;

a processor configured to identify, in the plurality of documents, a plurality of candidate sentences;

a processor configured to calculate a frequency of a plurality of n-grams appearing in the plurality of candidate sentences, wherein n ranges at least from 1 to 2;

a processor configured to assign, to each candidate sentence, a score, wherein the score comprises (1) the frequency of a plurality of n-grams appearing in the candidate sentence, and (2) a rank of the candidate sentence according to the ranking of the plurality of documents;

a processor configured to sort the candidate sentences according to score, whereby a rating of candidate sentences is produced; and

an interface configured to send, over a computer network, a reply to the query, the reply comprising at least a top candidate sentence from the rating of candidate sentences.

32. The system of claim 31, wherein the lookup engine is a web based search engine.

33. The system of claim 31, wherein each score comprises a product of (1) the frequency of a plurality of n-grams appearing in the candidate sentence, and (2) the rank of the candidate sentence according to the ranking of the plurality of documents.

34. The system of claim 31, wherein each score further comprises, for each candidate sentence, a measure of commonality between the candidate sentence and the query.

35. The system of claim 34, wherein the score comprises a product of at least (1) the frequency of a plurality of n-grams appearing in the candidate, sentence, (2) the measure of commonality between the candidate sentence and the query, and (3) the rank of the candidate sentence according to the ranking of the plurality of documents.

36. The system of claim 35, wherein the measure of commonality comprises a count of common words.

37. The system of claim 31, wherein the reply comprises candidate sentences whose scores meet a predetermined threshold.

38. The system of claim 31, wherein the reply comprises at least a top three candidate sentences according to the rating of candidate sentences.

39. The system of claim 31, wherein each score comprises the frequency of a plurality of n-grams appearing in the candidate sentence weighted according to n-gram length.

40. The system of claim 31, wherein each score comprises a geometric mean of (1) the frequency of a plurality of n-grams appearing in the candidate sentence, and (2) the rank of the candidate sentence according to the ranking of the plurality of documents.

41. A computer implemented method of providing a natural language answer to a natural language question, the method comprising:

receiving, over a computer network, a query comprising a grammatical question;

submitting the query to a lookup engine;

receiving initial search results from the lookup engine, the initial search results comprising a plurality of documents, wherein the initial search results comprise a ranking of the plurality of documents according to relevance;

identifying, in the plurality of documents, a plurality of candidate sentences;

calculating, for each candidate sentence, a measure of commonality between the candidate sentence and the query;

assigning, to each candidate sentence, a score, wherein the score comprises (1) a rank of the candidate sentence according to the ranking of the plurality of documents, and (2) the measure of commonality between the candidate sentence and the query;

sorting the candidate sentences according to score, whereby a rating of candidate sentences is produced; and

sending, over a computer network, a reply to the query, the reply comprising at least a top candidate sentence from the rating of candidate sentences.

42. The method of claim 41, wherein the lookup engine is a web based search engine.

43. The method of claim 41, wherein each score comprises a product of (1) the rank of the candidate sentence according to the ranking of the plurality of documents, and (2) the measure of commonality between the candidate sentence and the query.

44. The method of claim 41, wherein the measure of commonality comprises a count of common words.

45. The method of claim 41, further comprising calculating a frequency of a plurality of n-grams appearing in the plurality of candidate sentences, wherein n ranges at least from 1 to 2.

46. The method of claim 45, wherein the score comprises a product of at least (1) the frequency of a plurality of n-grams appearing in the candidate sentence, (2) the measure of commonality between the candidate sentence and the query, and (3) the rank of the candidate sentence according to the ranking of the plurality of documents.

47. The method of claim 41, wherein each score comprises a geometric mean of (1) the rank of the candidate sentence according to the ranking of the plurality of documents, and (2) the measure of commonality between the candidate sentence and the query.

48. The method of claim 45, wherein each score comprises the frequency of a plurality of n-grams appearing in the candidate sentence weighted according to n-gram length.

49. The method of claim 41, wherein the reply comprises candidate sentences whose scores meet a predetermined threshold.

50. The method of claim 41, wherein the reply comprises at least a top three candidate sentences according to the rating of candidate sentences.

51. A system for providing a natural language answer to a natural language question, the system comprising:

an interface configured to receive, over a computer network, a query comprising a grammatical question;

an interface configured to submit the query to a lookup engine;

an interface configured to receive initial search results from the lookup engine, the initial search results comprising a plurality of documents, wherein the initial search results comprise a ranking of the plurality of documents according to relevance;

a processor configured to identify, in the plurality of documents, a plurality of candidate sentences;

a processor configured to calculate, for each candidate sentence, a measure of commonality between the candidate sentence and the query;

a processor configured to assign, to each candidate sentence, a score, wherein the score comprises (1) a rank of the candidate sentence according to the ranking of the plurality of documents, and (2) the measure of commonality between the candidate sentence and the query;

a processor configured to sort the candidate sentences according to score, whereby a rating of candidate sentences is produced; and

an interface configured to send, over a computer network, a reply to the query, the reply comprising at least a top candidate sentence from the rating of candidate sentences.

52. The system of claim 51, wherein the lookup engine is a web based search engine.

53. The system of claim 51, wherein each score comprises a product of (1) the rank of the candidate sentence according to the ranking of the plurality of documents, and (2) the measure of commonality between the candidate sentence and the query.

54. The system of claim 51, wherein the measure of commonality comprises a count of common words.

55. The system of claim 51, further comprising a processor configured to calculate a frequency of a plurality of n-grams appearing in the plurality of candidate sentences, wherein n ranges at least from 1 to 2.

56. The system of claim 55, wherein the score comprises a product of at least (1) the frequency of a plurality of n-grams appearing in the candidate sentence, (2) the measure of commonality between the candidate sentence and the query, and (3) the rank of the candidate sentence according to the ranking of the plurality of documents.

57. The system of claim 55, wherein each score comprises the frequency of a plurality of n-grams appearing in the candidate sentence weighted according to n-gram length.

58. The system of claim 51, wherein each score comprises a geometric mean of (1) the rank of the candidate sentence according to the ranking of the plurality of documents, and (2) the measure of commonality between the candidate sentence and the query.

59. The system of claim 51, wherein the reply comprises candidate sentences whose scores meet a predetermined threshold.

60. The system of claim 51, wherein the reply comprises at least a top three candidate sentences according to the rating of candidate sentences.