Granted Patent B1

US 11,093,551 · App. 16/129,638 · Granted Aug 17, 2021

Inventors: Vivek Natarajan (Palo Alto, CA); Baiyang Liu (Issaquah, WA); Shubham Gupta (Sunnyvale, CA); Krishna Mittal (Mountain View, CA); Scott Martin (Menlo Park, CA)

Assignee: Facebook, Inc.

G06F16/90332G06F16/90335G06F40/205G06N3/08G10L15/16G10L15/187

Abstract

Claims (49)

1. A method comprising, by one or more computing systems:

receiving, by the one or more computing systems from a client system associated with a first user, a first user input comprising a plurality of n-grams;

generating, in response to receiving the first user input by a compositional model, a tree-structured representation for the first user input based on a parsing by the compositional model, wherein the tree-structured representation comprises one or more non-terminal nodes associated with one or more intents, one or more non-terminal nodes associated with one or more slots, and one or more terminal nodes associated with one or more n-grams of the first user input;

resolving, by the one or more computing systems, the tree-structured representation by applying a depth-first search algorithm, wherein the tree-structured representation comprises one or more non-resolvable non-terminal nodes associated with the one or more slots, wherein each non-resolvable non-terminal node is associated with partial slot information corresponding to an n-gram that has not been resolved to a particular entity identifier, and wherein the partial slot information associated with each non-resolvable non-terminal node is passed to a respective non-terminal parent node, and wherein each non-terminal parent node of a non-resolvable non-terminal node is partially resolved based on the partial slot information, and wherein each non-resolvable non-terminal node is resolved based on the respective partially resolved non-terminal parent node of the non-resolvable non-terminal node;

generating, by the one or more computing systems, a response to the first user input based on the resolved tree-structured representation; and

sending, by the one or more computing systems to the client system of the first user, instructions for presenting the response.

2. The method of claim 1 , wherein resolving each non-resolvable non-terminal node based on the respective partially resolved non-terminal parent node of the non-resolvable non-terminal node comprises:

identifying one or more contexts associated with one or more first n-grams associated with the non-resolvable non-terminal node;

exchanging one or more of the first n-grams associated with the non-resolvable non-terminal node with one or more second n-grams based on the identified one or more contexts; and

resolving the non-resolvable non-terminal node based on the one or more second n-grams associated with the non-resolvable non-terminal node.

3. The method of claim 1 , wherein each slot has a slot type of a plurality of slot types, and wherein resolving a non-terminal node associated with a particular slot of a first slot type comprises changing the first slot type to a second slot type.

4. The method of claim 3 , wherein changing the first slot type to a second slot type is based on an intent associated with a non-terminal parent node of the non-terminal node associated with the particular slot.

5. The method of claim 1 , wherein resolving the tree-structured representation comprises:

querying the entity resolution module for entity information for each slot;

receiving entity identifiers for each resolvable slot;

generating the partial slot information responsive to being unable to resolve a slot.

6. The method of claim 5 , wherein resolving the tree-structured representation comprises, for each intent:

identifying one or more agents associated with the intent;

ranking the one or more agents for the intent;

querying one or more of the agents based on their respective ranks, wherein the query comprises (1) one or more entity identifiers associated with a non-terminal child node of the non-terminal node associated with the intent or (2) the partial slot information associated with the non-terminal child node of the non-terminal node associated with the intent; and

generating resolved information for each non-terminal node.

7. The method of claim 6 , wherein ranking the one or more agents for each intent is based on (1) the one or more semantic-intents, (2) the one or more slots associated with the intent, and (3) one or more contexts associated with the slots.

8. The method of claim 6 , further comprising:

determining, for each resolved information associated with a non-terminal node, whether the resolved information is accessible to the first user based on privacy settings associated with the resolved information.

9. The method of claim 1 , wherein at least one of the non-resolvable non-terminal nodes has two or more entities are associated with it, and wherein the partial slot information associated with the at least one non-resolvable non-terminal node comprises entity identifiers of the two or more entities.

10. The method of claim 9 , further comprising:

sending, by the one or more computing systems to the client system of the first user, instructions for presenting a prompt requesting the user to select one of the two or more entities to be associated with the at least one non-resolvable non-terminal node; and

resolving the at least one non-resolvable non-terminal node based on the entity identifier of the entity selected by the first user.

11. The method of claim 9 , further comprising selecting one of the two or more entities to be associated with the at least one non-resolvable non-terminal node based on a comparison of social signals between the first user and each of the two or more entities; and

resolving the at least one non-resolvable non-terminal node based on the entity identifier of the selected entity.

12. The method of claim 1 , wherein the one or more intents comprise one or more hidden intents associated with one or more non-terminal nodes and an overall intent associated with a non-terminal parent node of the one or more non-terminal nodes, and wherein the one or more hidden intents are resolved prior to resolving the overall intent.

13. The method of claim 1 , further comprising:

identifying a domain associated with the first user input; and

selecting the compositional model from a plurality of compositional models based on the identified domain, wherein the plurality of compositional models correspond to a plurality of domains, respectively.

14. The method of claim 1 , wherein the compositional model is trained based on a plurality of training samples associated with one or more domains.

15. The method of claim 1 , further comprising performing an action in response to resolving the tree-structured representation.

16. The method of claim 15 , wherein the action comprises sending, to the client system of the first user, instructions to execute one or more tasks associated with fulfilling the first user input.

17. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:

receive, by the one or more computing systems from a client system associated with a first user, a first user input comprising a plurality of n-grams;

generate, in response to receiving the first user input by a compositional model, a tree-structured representation for the first user input based on a parsing by the compositional model, wherein the tree-structured representation comprises one or more non-terminal nodes associated with one or more intents, one or more non-terminal nodes associated with one or more slots, and one or more terminal nodes associated with one or more n-grams of the first user input;

resolve, by the one or more computing systems, the tree-structured representation by applying a depth-first search algorithm, wherein the tree-structured representation comprises one or more non-resolvable non-terminal nodes associated with the one or more slots, wherein each non-resolvable non-terminal node is associated with partial slot information corresponding to an n-gram that has not been resolved to a particular entity identifier, and wherein the partial slot information associated with each non-resolvable non-terminal node is passed to a respective non-terminal parent node, and wherein each non-terminal parent node of a non-resolvable non-terminal node is partially resolved based on the partial slot information, and wherein each non-resolvable non-terminal node is resolved based on the respective partially resolved non-terminal parent node of the non-resolvable non-terminal node;

generate, by the one or more computing systems, a response to the first user input based on the resolved tree-structured representation; and

send, by the one or more computing systems to the client system of the first user, instructions for presenting the response.

18. A system comprising: one or more processors; and a non-transitory memory coupled to the processors comprising instructions executable by the processors, the processors operable when executing the instructions to:

receive, by the one or more computing systems from a client system associated with a first user, a first user input comprising a plurality of n-grams;

generate, in response to receiving the first user input by a compositional model, a tree-structured representation for the first user input based on a parsing by the compositional model, wherein the tree-structured representation comprises one or more non-terminal nodes associated with one or more intents, one or more non-terminal nodes associated with one or more slots, and one or more terminal nodes associated with one or more n-grams of the first user input;

resolve, by the one or more computing systems, the tree-structured representation by applying a depth-first search algorithm, wherein the tree-structured representation comprises one or more non-resolvable non-terminal nodes associated with the one or more slots, wherein each non-resolvable non-terminal node is associated with partial slot information corresponding to an n-gram that has not been resolved to a particular entity identifier, and wherein the partial slot information associated with each non-resolvable non-terminal node is passed to a respective non-terminal parent node, and wherein each non-terminal parent node of a non-resolvable non-terminal node is partially resolved based on the partial slot information, and wherein each non-resolvable non-terminal node is resolved based on the respective partially resolved non-terminal parent node of the non-resolvable non-terminal node;

generate, by the one or more computing systems, a response to the first user input based on the resolved tree-structured representation; and

send, by the one or more computing systems to the client system of the first user, instructions for presenting the response.

Assignments (2)

Cited By (13)

US 12,249,014 US 12,353,897 US 12,406,142 US 12,443,797 US 12,495,098 US 12,499,350 US 12,561,032 US 12,567,404 US 12,573,391 US 12,592,017 US 12,603,085 US 12,625,557 US 12,670,671