Corpus specific natural language query completion assistant

• US 10,102,199 B2
• Filed: 02/24/2017
• Issued: 10/16/2018
• Est. Priority Date: 02/24/2017
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Bailey, Peter Richard, Hawking, David Anthony, Maxwell, David
• Primary Examiner(s): Colucci, Michael
• Application Number:
  US15/442,563
• Publication Number:
  US 20180246878A1
• Time in Patent Office: 599 Days
• Field of Search: 704233, 704 9, 715727, 707769
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/90324 using system suggestions
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking

Abstract

Representative embodiments disclose mechanisms to complete partial natural language questions. Users enter a partial question. The system comprises a plurality of indexes, one index comprising common phrases associated with natural language questions and other indexes comprising short text entries associated with documents, such as document titles. The partial question is used to search one or more of the indexes. The search yields a ranked list of results. The top k entries of the list are selected and one or more language models are created from the top k entries. Each language model comprises n-grams from the top k entries from an index and an associated probability for each n-gram. A question completion generator creates question completion suggestions by matching n-grams with the partial question, removing ungrammatical candidate suggestions, and filtering the remaining suggestions per a filtering criteria. The top N results are returned as suggestions to complete the question.

Claims

1. A method for completing a question comprising:

receiving, from a user, a question prefix representing a portion of a natural language question;

selecting, based on the question prefix, at least one index comprising a short text index or a question term index, the short text index comprising a plurality of text entries, each entry corresponding to an associated document, the question term index comprising a plurality of question entries, each entry corresponding to a partial question phrase;

searching the selected at least one index using the question prefix and retrieving a plurality of retrieved entries;

selecting a subset of the plurality of retrieved entries;

responsive to selecting the subset, creating a language model from the subset, the language model comprising a plurality of n-grams each with an n-gram probability;

creating a plurality of question completion suggestions based on the language model and the question prefix; and

causing presentation of the plurality of question completion suggestions to the user via a user interface.

2. The method of claim 1 wherein the plurality of retrieved entries each have an associated metric.

3. The method of claim 1 wherein each entry in the short text index comprises the title of a document.

4. The method of claim 2 wherein selecting the subset comprises:

ranking retrieved entries by the associated metric; and

selecting as the subset the top k entries in the ranked list.

5. The method of claim 1 wherein creating the plurality of question completion suggestions comprises:

generating a set of candidate completion suggestions based on the question prefix and the language model;

removing from the set of candidate completion suggestions candidate completion suggestions that do not comply with a set of grammar rules to create a subset of candidate completion suggestions; and

filtering the subset of candidate completion suggestions based on a filter criteria; and

ranking the filtered subset.

6. The method of claim 5 wherein the filter criteria selects one candidate completion suggestion associated with an underlying document and removes any other candidate completion suggestions associated with the underlying document.

7. The method of claim 5 wherein the filter criteria selects a candidate completion suggestion based on stored interaction data, the stored interaction data comprising user interactions with prior candidate completion suggestions presented to the user.

8. The method of claim 1 wherein:

the selected at least one index comprises a plurality of short text indexes;

the searching operation searches the plurality of short text indexes and retrieves a plurality of retrieved entries from each of the short text indexes;

the creating operation creates a plurality of language models, each language model created from a subset of entries from a respective short text index, each language model comprising a plurality of n-grams each with an n-gram probability;

question completion suggestions are created based on each language model.

9. The method of claim 2 wherein the associated metric is derived from at least one of:

a number of times a document associated with the entry has been viewed;

a type of match between the question prefix and the entry; and

a number of times a document comes up in search results.

10. A system for completing a question comprising:

a processor and executable instructions accessible on a computer-storage medium that, when executed, cause the processor to perform operations comprising;

receive, from a user, a question prefix representing a portion of a natural language question;

selecting at least one index comprising a short text index or a question term index, the short text index comprising a plurality of text entries, each entry corresponding to an associated document, the question term index comprising a plurality of question entries, each entry corresponding to a partial question phrase;

search the at least one index and retrieve a plurality of retrieved entries;

identify a subset of the plurality of the retrieved entries;

create a language model from the subset, the language model comprising a plurality of n-grams each with an n-gram probability;

create a plurality of question completion suggestions based on the language model and the question prefix;

return plurality of question completion suggestions to the user via a user interface; and

store user interaction with the question completion suggestions.

11. The system of claim 10 wherein the plurality of retrieved entries each have an associated metric.

12. The system of claim 11 wherein identify the subset comprises:

rank the plurality of retrieved entries by the associated metric; and

select as the subset the top k entries in the ranked list.

13. The system of claim 10 wherein each entry in the short text index comprises the title of a document.

14. The system of claim 10 wherein creating the plurality of question completion suggestions comprises:

generate a set of candidate completion suggestions based on the question prefix and the language model;

remove from the set of candidate completion suggestions candidate completion suggestions that do not comply with a set of grammar rules to create a subset of candidate completion suggestions; and

filter the subset of candidate completion suggestions based on a filter criteria; and

rank the filtered subset.

15. The system of claim 14 wherein the filter criteria selects one candidate completion suggestion associated with an underlying document and removes any other candidate completion suggestions associated with the underlying document.

16. The system of claim 14 wherein the filter criteria selects a candidate completion suggestion based on stored interaction data, the stored interaction data comprising user interactions with prior candidate completion suggestions presented to the user.

17. A computer storage medium comprising executable instructions that, when executed by a processor of a machine, cause the machine to perform operations comprising:

receive, from a user, a question prefix representing a portion of a natural language question;

selecting, based on the question prefix, at least one index comprising a short text index or a question term index, the short text index comprising a plurality of text entries, each entry corresponding to an associate document, the question term index comprising a plurality of question entries, each entry corresponding to a partial question phrase;

search the at least one index and retrieve a plurality of retrieved entries, the plurality of retrieved entries comprising the title of a document or the partial question phrase, or both;

select a subset of the plurality of the retrieved entries;

create a language model from the subset, the language model comprising a plurality of n-grams each with an n-gram probability;

create a plurality of question completion suggestions based on the language model and the question prefix; and

return plurality of question completion suggestions to the user via a user interface.

18. The medium of claim 17 wherein the plurality of retrieved entries each have a metric derived from at least one of:

a number of times a document associated with the entry has been viewed;

a type of match between the question prefix and the entry; and

a number of times a document comes up in search results.

19. The medium of claim 17 wherein creating the plurality of question completion suggestions comprises:

generate a set of candidate completion suggestions based on the question prefix and the language model;

remove from the set of candidate completion suggestions candidate completion suggestions that do not comply with a grammar to create a subset of candidate completion suggestions; and

filter the subset of candidate completion suggestions based on a filter criteria; and

rank the filtered subset.

20. The medium of claim 19 wherein

the at least one index comprises a plurality of short text indexes;

the search operation searches the plurality of short text indexes and retrieves a plurality of retrieved entries from each of the short text indexes;

the create operation creates a plurality of language models, each language model created from a subset of entries from a respective short text index, each language model comprising a plurality of n-grams each with an n-gram probability;

question completion suggestions are created based on each language model.