BACKGROUND

Users are increasingly able to interact with computers using natural language, e.g., in what will be referred to herein as “human-to-computer dialogs.” For example, many mobile computing devices such as smart phones, tablets, smart watches, standalone smart speakers, and so forth, include software programs referred to as “automated assistants” (a.k.a. “interactive assistant modules,” “mobile assistants,” etc.). Automated assistants may be configured to parse and interpret natural language input (e.g., spoken first then converted to text, or received initially as text) and provide responsive output, such as answers to questions, task initiation, etc. Existing automated assistants often have difficulty switching between domains of conversation. For example, if a user and an automated assistant have been exchanging dialog about a subject in one topic or domain (e.g., playing a game), and then the user abruptly steers the conversation towards another topic in an unrelated domain (e.g., weather), the automated assistant may not be entirely responsive and/or may require additional dialog to properly respond. One possible reason is that automated assistants tend to be created and/or maintained by a relatively small number of entities (e.g., a single developer). It may be difficult for such a small number of entities to anticipate how users may transition between innumerable possible conversational domains/topics and design robust dialogs, grammars, etc., for each such domain/topic.

SUMMARY

Techniques are described herein for utilizing a context of an ongoing human-to-computer dialog to enhance the ability of an automated assistant (or more generally, an interactive voice response “IVR” component) to interpret and respond when a user abruptly transitions the human-to-computer dialog between different domains. In various implementations, a so-called “contextual data structure” may be used to persist various “topics” that are relevant to an ongoing human-to-computer dialog. These topics may be used, for instance, to select one or more grammars that are used to parse the user's natural language input.

Based on parses produced by the selected grammars, and in some cases further based on a dynamic dialog tree that represents the ongoing human-to-computer dialog, a response (e.g., natural language response, initiation of a task, etc.) may be generated and provided by the automated assistant. Meanwhile, any new topics added to the ongoing dialog by the user and/or by the automated assistant may be added to the contextual data structure. Topics that have not been mentioned or alluded to in some time may be dropped. In this way, if a user provides natural language input that is not immediately pertinent but was pertinent to some previous topic of the ongoing dialog, the automated assistant may be able to seamlessly pivot back to the previous topic.

In some implementations, techniques described herein may be implemented on a system that includes a parser subsystem and a response subsystem. The parser subsystem may be responsible for interpreting natural language input and providing an interpretation (e.g., a “parse” and/or a topic) to the response subsystem. The response subsystem may be responsible for receiving the interpretations and responding appropriately, be it by generating and outputting a natural language response or by taking some other responsive action (e.g., launching a particular app).

In some implementations, the parser subsystem may be configured to select one or more grammars to parse received natural language input based on one or more topics stored in the aforementioned contextual data structure associated with the ongoing human-to-computer dialog. For example, in some implementations, each of a plurality of grammars (e.g., a library of grammars which may potentially be very large) may be stored in association with one or more applicable topics. A grammar may be selected/applied if one or more of its associated topics is currently pertinent (and/or pertinent enough) to the human-to-computer dialog, and may not be applied otherwise. Thus, when a user provides natural language input, only those grammars that are associated with currently-pertinent topics are selected and applied. This technique is occasionally referred to herein as “contextual filtering.” Contextual filtering provides a technical advantage of avoiding grammars that do not make sense in the context of the conversation, and hence might result in nonsensical output. In some cases this may reduce the number of grammars that are applied to each natural language input received from a human (as opposed to applying all grammars of a potentially enormous library to each natural language input). Reducing the number of grammars applied reduces utilization of computing resources such as processor cycles, memory, and/or network bandwidth. This may be particularly beneficial for human-to-computer dialogs because minimizing latency of an automated assistant (i.e. making sure the automated assistant responds to user input as quickly as possible) may be of paramount importance to users. If a human-to-computer dialog has just been initiated, and hence no topics are yet pertinent, the parser subsystem may process received natural language input using conventional techniques. The parser subsystem may then begin to populate the contextual data structure based on topics raised by a human or by an automated assistant during the human-to-computer dialog.

Interacting with both the parser subsystem and the response subsystem is the aforementioned contextual data structure. The contextual data structure may take various forms of data structures stored in memory, and may be used to persist topics that are, or have recently been, relevant to an ongoing human-to-computer dialog. When a topic is raised, either by the user or by the automated assistant, the topic may be added to the contextual data structure, e.g., by the response subsystem. If a topic is raised that is already persisted in the contextual data structure, the topic may be “touched,” e.g., it may be brought to the forefront of the conversation once again.

To this end, in various implementations, each topic persisted in the contextual data structure may be associated with a measure of relevance of the topic to the ongoing human-to-computer dialog. For example, in some implementations, a measure of relevance associated with each topic may be determined based at least in part on a count of turns of the ongoing human-to-computer dialog since the topic was last raised. The more turns since the topic was raised (e.g., added or touched), the lower the measure of relevance for that topic. Suppose a user began a human-to-computer dialog with a question about the weather (causing the topic “weather” to be added), but the dialog then covered a wide range of topics unrelated to weather. The more turns into the dialog since the topic of weather was raised, the more the relevance score associated with the topic weather is diminished. In some implementations, if a topic's measure of relevance diminishes below a threshold, that topic may be dropped from the contextual data structure altogether. Dropping “stale” topics from the contextual data structure may offer various technical advantages. The more grammars that are selected (i.e. contextually filtered as described above) and applied by the parser subsystem to each natural language input received from the user, the more computing resources are consumed. By dropping stale topics, the number of grammars applied by the parser subsystem to each natural language input may be reduced, thereby reducing computing resource consumption. Additionally, by focusing the parser subsystem on grammars associated with topics pertinent to a current human-to-computer dialog, it is less likely that off-topic or otherwise nonsensical parses will be produced (which may lead the automated assistant to provide similarly-nonsensical output). Thus, the number of human-to-computer dialog turns (and hence, user-provided natural language inputs) required to achieve a user's particular goal may be reduced, which may benefit users with limited physical or situational abilities to provide multiple inputs.

Measures of relevance may be based on other factors as well. For example, in some implementations, a measure of relevance associated with each topic may be determined based at least in part on a measure of relatedness (e.g., semantic) between the topic and one or more other topics in the contextual data structure. If a first topic has not been raised in a while, but a semantically-related second topic is raised later, the first topic's measure of relevance may be raised.

In some implementations, the contextual data structure may take the form of an undirected graph comprising a plurality of nodes and a plurality of edges connecting the plurality of nodes. Each node of the undirected graph may represent a given topic of the one or more topics stored as part of the contextual data structure. In some implementations, each node may also store a count of turns of the ongoing human-to-computer dialog since the given topic was last raised. In some implementations, each edge connecting two nodes may represent a measure of relatedness (e.g., semantic, etc.) between two topics represented by the two nodes, respectively. Of course, other data structures are contemplated herein.

In some implementations, each grammar may be associated both with a topic and a threshold relevance score for that topic. If the topic is persisted in the contextual data structure but its relevance score does not satisfy the threshold, the grammar may not be selected. This enables fine-tuning of when grammars will be applied and when they won't.

In various implementations, the response subsystem may receive interpretations (or “parses”) from the grammars that are selected and applied by the parser subsystem. In some implementations, the parser subsystem may also provide the response subsystem with topics, e.g., as part of the parses/interpretations and/or separately. In some implementations, these topics may be already persisted in the contextual data structure and that have been touched by virtue of their associated grammars having been applied. In various implementations, the response subsystem may employ a dialog tree to steer the ongoing human-to-computer dialog between seemingly unrelated topics. In essence, the response subsystem receives one or more parses (or interpretations) and topics from the parser subsystem, and steers the conversation along the dialog tree based on the parses and topics.

For example, in some implementations, each node in the dialog tree represents a natural language process. A root node of the dialog tree may be configured to handle any natural language input (either by initiating a process or by requesting disambiguation from the user) and to initiate one or more child nodes corresponding to processes that are initiated in response to natural language input from the user. The child processes may themselves add additional child processes to handle various aspects of their own internal dialog. This may simplify code maintenance and reuse, as each process may be a modular process that is configured to implement techniques described herein.

Whenever the response subsystem generates a response (e.g., a natural language response, a responsive action or task, etc.) for the user, the response subsystem may add any related topics to the contextual data structure. In some implementations, each node of the dialog tree may be associated with one or more topics (which may, for instance, be selected by a developer of the process underlying the node). As noted above, each grammar also may be associated with one or more topics. Consequently, by adding these topics to the contextual data structure, the response subsystem in effect adds the number of grammars that may be applicable by the parser subsystem at any point in time. Thus, if a user converses about one topic, changes course, then returns to the original topic (or to a semantically-related topic), grammars associated with that original topic may still be applicable because their associated topics are still persisted in the contextual data structure. But as noted above, if the human-to-computer dialog strays from a given topic for long enough, in some implementations, the topic may be dropped from the contextual data structure, e.g., to prevent the parser subsystem from applying an excessive number of grammars to each natural language input, which as noted above can become computationally expensive.

As an example, suppose a user initiates a human-to-computer dialog with the phrase, “Let's play a game.” The response subsystem may start the dialog tree at the root node. The parser subsystem may parse/interpret the user's natural language input and provide the response subsystem with the parse/interpretation and any raised topics (e.g., game). Based on the received parse and topic(s), the response subsystem may provide dialog such as, “OK, what game do you want to play?”, and to initiate a gaming child process beneath the root node. The response subsystem may also add topics such as “game” and “game selection” (which may be determined by the parser subsystem based on the received input and/or by the response subsystem based on topics associated with the gaming child process) to the contextual data structure. The gaming child process may be associated (e.g., by its developer) with one or more topics, each which may be associated with one or more topics related to games, such as “game,” “game selection.” One grammar that may be associated with such topics may be, for instance, a list_available_games grammar. Another grammar associated with such topics may be, for instance, “number_of_players” grammar. Suppose the user now utters, “What games do you have?” The parser subsystem may select the list_available_games grammar because its topic(s) (game, game selection) are currently in the contextual data structure with relatively high measures of relevance (because they were just recently raised). The list_available_games grammar may parse the user's statement and provide its interpretation (e.g., the command, “LIST GAMES”) to the response subsystem. Consequently, the automated assistant (e.g., by way of the response subsystem) may list available games, such as “I have Sports Trivia and Historical Trivia.” The response subsystem may also add topics such as “trivia,” “sports” and “history” to the contextual data structure, and may add, to the dialog tree, child process nodes corresponding to the Sports Trivia and Historical Trivia games.

Now, suppose the user abruptly changes the subject, such as by uttering, “What's the weather forecast today?” There may not currently be any topics stored in the contextual data structure that are related to the topic “weather.” In some implementations, the parser subsystem may identify (e.g., contextually filter from a large repository of grammars) one or more grammars that are associated with each topic raised by this utterance, such as “weather.” The parser subsystem may provide the response subsystem with one or more parses produced by the one or more identified grammars, as well as the corresponding topic(s). The response subsystem may attempt to associate (e.g., match) existing dialog tree nodes with the parses/topic(s) returned by the parser subsystem. In some cases, a parse/topic provided by the parser subsystem may be associable (e.g., match) a dialog tree node if (i) a topic associated with the dialog tree node matches the topic of the parse/topic, and (ii) the dialog tree node is capable of handling the parse of the parse/topic. If one or both conditions are not satisfied, control may pass back to the root node of the dialog tree. That is likely the case in this example because the topic “weather” is likely not going to match any of the aforementioned topics that have already been added to the dialog tree. Accordingly, the response subsystem may load a child process node associated with the topic “weather,” and may provide a response such as “Cloudy with a 30% chance of rain.” The response subsystem may also add the topic “weather” to the contextual data structure, and in some cases may reduce the measures of relevance associated with topics unrelated to weather that are already contained in the contextual data structure, such as “game,” “game selection,” “trivia,” “sports,” and “history.”

Suppose the user now utters, “Sports Trivia.” Even though the user most recently changed the subject of the human-to-computer dialog to “weather,” the topics of “game,” “game selection,” “trivia,” “sports,” and “history” are all still stored in the contextual data structure, albeit with slightly reduced measures of relevance. Accordingly, the parser subsystem may still select (e.g., contextually filter from a larger repository of grammars) one or more grammars associated with these topics to parse the user's utterance. The parser subsystem may then apply the selected grammars to the input, and may provide the resulting parses and associated topics to the response subsystem. The response subsystem may then pass control to the Sports Trivia child process node that was added to the dialog tree previously.

Techniques described herein may give rise to a variety of additional technical advantages beyond those already mentioned. For example, the techniques described herein enable smooth changing of conversation subjects without requiring individual developers (e.g., of individual IVR processes) to expend considerable resources handling such subject changing. Additionally or alternatively, because grammars are only applicable when particular topics are relevant (and in some cases, must have measures of relevance that satisfy various thresholds), the use of techniques described herein also limit the number of generated parses/interpretations to only those which make sense in the current dialog context. This may save computation resources such as memory, processor cycles, network bandwidth, etc.

In some implementations, techniques described herein facilitate modular design of IVR dialogs to be implemented by automated assistants. Such modular design (including the hierarchal structure of dialog trees described herein) may be easier to maintain, and may allow also for easy code reuse. An additional technical advantage of some implementations is that the dialog trees described herein allow all business logic to be easily developed in a single programming language (such as C++). Consequently, the development time decreases compared to solutions involving several programming languages.

In some implementations, a method performed by one or more processors is provided that includes: 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; selecting one or more grammars to parse the natural language input, wherein the selecting is based on one or more topics stored in memory as part of a contextual data structure associated with 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.

These and other implementations of technology disclosed herein may optionally include one or more of the following features.

In various implementations, the one or more grammars may be selected from a plurality of grammars, and wherein each of the plurality of grammars is stored in association with one or more applicable topics. In various implementations, each topic stored in the memory as part of the contextual data structure may be associated with a measure of relevance of the topic to the ongoing human-to-computer dialog. In various implementations, a measure of relevance associated with each topic may be determined based at least in part on a count of turns of the ongoing human-to-computer dialog since the topic was last raised.

In various implementations, a measure of relevance associated with each topic may be determined based at least in part on a measure of relatedness between the topic and one or more other topics in the contextual data structure.

In various implementations, the contextual data structure may include an undirected graph comprising a plurality of nodes and a plurality of edges connecting the plurality of nodes. In various implementations, each node of the undirected graph may represent 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. In various implementations, each edge connecting two nodes may represent a measure of relatedness between two topics represented by the two nodes, respectively.

In various implementations, the method may further include 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. In various implementations, one or more of the nodes may be associated with one or more topics. In various implementations, the selecting may include selecting the one or more grammars from one or more grammars associated with the one or more topics.

In addition, some implementations include one or more processors of one or more computing devices, where the one or more processors are operable to execute instructions stored in associated memory, and where the instructions are configured to cause performance of any of the aforementioned methods. Some implementations also include one or more non-transitory computer readable storage media storing computer instructions executable by one or more processors to perform any of the aforementioned methods.

It should be appreciated that all combinations of the foregoing concepts and additional concepts described in greater detail herein are contemplated as being part of the subject matter disclosed herein. For example, all combinations of claimed subject matter appearing at the end of this disclosure are contemplated as being part of the subject matter disclosed herein.

