Context-aware human-to-computer dialog

• US 10,268,680 B2
• Filed: 03/01/2017
• Issued: 04/23/2019
• Est. Priority Date: 12/30/2016
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Takiel, Piotr
• Primary Examiner(s): Godbold, Douglas
• Assistant Examiner(s): Villena, Mark
• Application Number:
  US15/446,908
• Publication Number:
  US 20180189267A1
• Time in Patent Office: 783 Days
• CPC Class Codes: G06F 16/3329 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G06F 40/35 Discourse or dialogue representation
• CPC Class Codes: G10L 15/19 Grammatical context, e.g. disambiguation of the recognition hypotheses based on word sequence rules
• CPC Class Codes: G10L 15/22 Procedures used during a speech recognition process, e.g. man-machine dialogue

Abstract

Methods, apparatus, and computer readable media are described related to utilizing a context of an ongoing human-to-computer dialog to enhance the ability of an automated assistant to interpret and respond when a user abruptly transitions between different domains (subjects). In various implementations, natural language input may be received from a user during an ongoing human-to-computer dialog with an automated assistant. Grammar(s) may be selected to parse the natural language input. The selecting may be based on topic(s) stored as part of a contextual data structure associated with the ongoing human-to-computer dialog. The natural language input may be parsed based on the selected grammar(s) to generate parse(s). Based on the parse(s), a natural language response may be generated and output to the user using an output device. Any topic(s) raised by the parse(s) or the natural language response may be identified and added to the contextual data structure.

Claims

1. A computer-implemented method, comprising:

receiving natural language input from a user as part of an ongoing human-to-computer dialog between the user and an automated assistant operated by one or more processors, wherein one or more topics raised previously during the ongoing human-to-computer dialog are stored in memory as part of a contextual data structure associated with the ongoing human-to-computer dialog;

selecting, from a plurality of grammars associated with a plurality of respective topics, one or more grammars to parse the natural language input, wherein the selecting is based on one or more respective measures of relevance of the previously-raised one or more topics to the ongoing human-to-computer dialog, wherein the measure of relevance associated with each given topic of the one or more topics is determined based at least in part on a count of turns of the ongoing human-to-computer dialog since the given topic was last raised, wherein the count of turns since the given topic was last raised is inversely related to relevance of the given topic to the ongoing human-to-computer dialog;

parsing the natural language input based on the selected one or more grammars to generate one or more parses;

generating, based on one or more of the parses, a natural language response;

outputting the natural language response to the user using one or more output devices;

identifying one or more topics raised by one or more of the parses or the natural language response; and

adding the identified one or more topics to the contextual data structure.

2. The computer-implemented method of claim 1, wherein the measure of relevance associated with each given topic of the one or more topics is determined based at least in part on a measure of relatedness between the given topic and one or more other topics of the one or more topics in the contextual data structure.

3. The computer-implemented method of claim 1, wherein the contextual data structure comprises an undirected graph comprising a plurality of nodes and a plurality of edges connecting the plurality of nodes.

4. The computer-implemented method of claim 3, wherein each node of the undirected graph represents a given topic of the one or more topics stored as part of the contextual data structure, and a count of turns of the ongoing human-to-computer dialog since the given topic was last raised.

5. The computer-implemented method of claim 4, wherein each edge connecting two nodes represents a measure of relatedness between two topics represented by the two nodes, respectively.

6. The computer-implemented method of claim 1, further comprising generating a dialog tree with one or more nodes that represent one or more interactive voice processes that have been invoked during the ongoing human-to-computer dialog.

7. The computer-implemented method of claim 6, wherein one or more of the nodes is associated with one or more topics.

8. The computer-implemented method of claim 7, wherein the selecting comprises selecting the one or more grammars from one or more grammars associated with the one or more topics.

9. A system comprising one or more processors and memory operably coupled with the one or more processors, wherein the memory stores instructions that, in response to execution of the instructions by one or more processors, cause the one or more processors to:

receive natural language input from a user as part of an ongoing human-to-computer dialog between the user and an automated assistant operated by one or more processors, wherein one or more topics raised previously during the ongoing human-to-computer dialog are stored in memory as part of a contextual data structure associated with the ongoing human-to-computer dialog;

select, from a plurality of grammars associated with a plurality of respective topics, one or more grammars to parse the natural language input, wherein the selecting is based on one or more respective measures of relevance of the previously-raised one or more topics to the ongoing human-to-computer dialog, wherein the measure of relevance associated with each given topic of the one or more topics is determined based at least in part on a count of turns of the ongoing human-to-computer dialog since the given topic was last raised, wherein the count of turns since the given topic was last raised is inversely related to relevance of the given topic to the ongoing human-to-computer dialog;

parse the natural language input based on the selected one or more grammars to generate one or more parses;

generate, based on one or more of the parses, a natural language response;

output the natural language response to the user using one or more output devices;

identify one or more topics raised by one or more of the parses or the natural language response; and

add the identified one or more topics to the contextual data structure.

10. The system of claim 9, wherein the measure of relevance associated with each given topic of the one or more topics is determined based at least in part on a measure of relatedness between the given topic and one or more other topics of the one or more topics in the contextual data structure.

11. The system of claim 9, wherein the contextual data structure comprises an undirected graph comprising a plurality of nodes and a plurality of edges connecting the plurality of nodes.

12. The system of claim 11, wherein each node of the undirected graph represents a given topic of the one or more topics stored as part of the contextual data structure, and a count of turns of the ongoing human-to-computer dialog since the given topic was last raised.

13. The system of claim 12, wherein each edge connecting two nodes represents a measure of relatedness between two topics represented by the two nodes, respectively.

14. At least one non-transitory computer-readable medium comprising instructions that, in response to execution of the instructions by one or more processors, cause the one or more processors to perform the following operations:

receiving natural language input from a user as part of an ongoing human-to-computer dialog between the user and an automated assistant operated by one or more processors, wherein one or more topics raised previously during the ongoing human-to-computer dialog are stored in memory as part of a contextual data structure associated with the ongoing human-to-computer dialog;

selecting, from a plurality of grammars associated with a plurality of respective topics, one or more grammars to parse the natural language input, wherein the selecting is based on one or more respective measures of relevance of the previously-raised one or more topics to the ongoing human-to-computer dialog, wherein the measure of relevance associated with each given topic of the one or more topics is determined based at least in part on a count of turns of the ongoing human-to-computer dialog since the given topic was last raised, wherein the count of turns since the given topic was last raised is inversely related to relevance of the given topic to the ongoing human-to-computer dialog;

parsing the natural language input based on the selected one or more grammars to generate one or more parses;

generating, based on one or more of the parses, a natural language response;

outputting the natural language response to the user using one or more output devices;

identifying one or more topics raised by one or more of the parses or the natural language response; and

adding the identified one or more topics to the contextual data structure.