# US 12,008,802 B2 · Execution engine for compositional entity resolution for assistant systems

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 12,008,802 B2
- Document ID: US12008802B2
- Status: Granted
- Kind: B2
- Application number: 17/362,676
- Filed: 2021-06-29
- Published: 2021-10-21
- Granted: 2024-06-11
- Earliest claimed: 2018-04-20
- Assignees: Meta Platforms, Inc.
- Applicants: Meta Platforms, Inc.
- Inventors: Vivek Natarajan; Baiyang Liu; Shubham Gupta; Krishna Mittal; Scott Martin
- Web page: https://patentgrep.com/patent/US12008802B2

## CPC

- G06V 10/82: using neural networks
- G06F 3/011: {Arrangements for interaction with the human body, e.g. for user immersion in virtual reality (blind teaching G09B21/00)}
- G06F 3/013: {Eye tracking input arrangements (G06F3/015 takes precedence)}
- G06F 3/017: {Gesture based interaction, e.g. based on a set of recognized hand gestures (interaction based on gestures traced on a digitiser G06F3/04883)}
- G06F 3/167: {Audio in a user interface, e.g. using voice commands for navigating, audio feedback}
- G06F 7/14: Merging, i.e. combining at least two sets of record carriers each arranged in the same ordered sequence to produce a single set having the same ordered sequence
- G06F 9/453: {Help systems}
- G06F 16/176: Support for shared access to files; File sharing support
- G06F 16/2255: {Hash tables}
- G06F 16/2365: {Ensuring data consistency and integrity}
- G06F 16/243: {Natural language query formulation}
- G06F 16/24552: {Database cache management}
- G06F 16/24575: {using context}
- G06F 16/24578: {using ranking}
- G06F 16/248: Presentation of query results
- G06F 16/3323: {using document space presentation or visualization, e.g. category, hierarchy or range presentation and selection}
- G06F 16/3329: Natural language query formulation
- G06F 16/3344: {using natural language analysis}
- G06F 16/338: Presentation of query results
- G06F 16/90332: {Natural language query formulation or dialogue systems}
- G06F 16/90335: {Query processing}
- G06F 16/9038: Presentation of query results
- G06F 16/904: Browsing; Visualisation therefor (for navigating the web G06F16/954; browsing optimisation for the web G06F16/957)
- G06F 16/951: Indexing; Web crawling techniques
- G06F 16/9535: Search customisation based on user profiles and personalisation
- G06F 18/2411: based on the proximity to a decision surface, e.g. support vector machines
- G06F 40/205: Parsing
- G06F 40/295: Named entity recognition
- G06F 40/30: Semantic analysis
- G06F 40/40: Processing or translation of natural language (natural language analysis G06F40/20; semantic analysis G06F40/30)
- G06N 3/006: based on simulated virtual individual or collective life forms, e.g. social simulations or particle swarm optimisation [PSO]
- G06N 3/08: Learning methods
- G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks
- G06N 20/00: Machine learning
- G06Q 50/01
- G06V 10/764: using classification, e.g. of video objects
- G06V 20/10: Terrestrial scenes (scenes under surveillance with static cameras G06V20/52; scenes perceived from the exterior of a vehicle G06V20/56; scenes perceived from the interior of a vehicle G06V20/59)
- G06V 40/28: {Recognition of hand or arm movements, e.g. recognition of deaf sign language (static hand signs G06V40/113)}
- G10L 15/02: Feature extraction for speech recognition; Selection of recognition unit
- G10L 15/063: {Training}
- G10L 15/07: to the speaker
- G10L 15/16: using artificial neural networks
- G10L 15/1815: {Semantic context, e.g. disambiguation of the recognition hypotheses based on word meaning}
- G10L 15/1822: {Parsing for meaning understanding}
- G10L 15/183: using context dependencies, e.g. language models
- G10L 15/187: Phonemic context, e.g. pronunciation rules, phonotactical constraints or phoneme n-grams
- G10L 15/22: Procedures used during a speech recognition process, e.g. man-machine dialogue
- G10L 15/26: Speech to text systems (G10L15/08 takes precedence)
- G10L 17/06: Decision making techniques; Pattern matching strategies
- G10L 17/22: Interactive procedures; Man-machine interfaces
- H04L 12/2816: {Controlling appliance services of a home automation network by calling their functionalities (arrangements in telecontrol or telemetry systems for selectively calling a substation from a main station; in which substation desired apparatus is selected for applying a control signal thereto or for obtaining measured values therefrom H04Q9/00)}
- H04L 41/20: {Network management software packages}
- H04L 41/22: comprising specially adapted graphical user interfaces [GUI]
- H04L 43/0882: Utilisation of link capacity
- H04L 43/0894: Packet rate
- H04L 51/02: using automatic reactions or user delegation, e.g. automatic replies or chatbot-generated messages
- H04L 51/18: Commands or executable codes
- H04L 51/216: Handling conversation history, e.g. grouping of messages in sessions or threads
- H04L 51/52: for supporting social networking services
- H04L 67/306: User profiles
- H04L 67/535: {Tracking the activity of the user (network monitoring arrangements H04L43/00; recording of computer activity G06F11/34)}
- H04L 67/5651: Reducing the amount or size of exchanged application data
- H04L 67/75: Indicating network or usage conditions on the user display
- H04W 12/08: Access security
- G06F 2216/13: Prefetching
- G10L 13/00: Speech synthesis; Text to speech systems
- G10L 13/04: Details of speech synthesis systems, e.g. synthesiser structure or memory management
- G10L 2015/223: {Execution procedure of a spoken command}
- G10L 2015/225: {Feedback of the input speech}
- H04L 51/046: Interoperability with other network applications or services
- H04L 67/10: in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46)
- H04L 67/53: using third party service providers
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G10L: SPEECH ANALYSIS TECHNIQUES OR SPEECH SYNTHESIS; SPEECH RECOGNITION; SPEECH OR VOICE PROCESSING TECHNIQUES; SPEECH OR AUDIO CODING OR DECODING
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)

## Abstract

In one embodiment, a method includes receiving, from a client system of a user, a user input comprising a plurality of n-grams, parsing the user input to identify one or more overall intents, hidden intents, and slots associated with the one or more n-grams, wherein at least one of the hidden intents is non-resolvable for being associated with partial slot information corresponding to an n-gram that has not been resolved to a particular entity identifier, wherein the partial slot information is associated with two more entity identifiers of two or more entities, respectively, sending, to the client system, instructions for prompting the user to select one of the entities to be associated with the non-resolvable hidden intent, resolving the non-resolvable hidden intent based on the entity identifier of the entity selected by the user, and generating a response to the user input based on the resolved hidden intent.

## Claims

### Claim 1

A method comprising, by one or more computing systems:
receiving, from a client system of a user, a user input comprising a plurality of n-grams;
parsing the user input to identify one or more overall intents, one or more hidden intents, and one or more slots associated with the one or more n-grams, wherein at least one of the hidden intents is non-resolvable for being associated with partial slot information corresponding to a first n-gram that has not been resolved to a particular entity identifier, wherein the partial slot information is associated with two or more entity identifiers of two or more entities, respectively, wherein each hidden intent is associated with one of the one or more overall intents, and wherein the one or more hidden intents must be resolved prior to resolving the overall intent;
sending, to the client system, instructions for prompting the user to select one of the two or more entities to be associated with the at least one non-resolvable hidden intent and to associate the first n-gram to the entity identifier of the entity selected by the user;
resolving the at least one non-resolvable hidden intent based on the entity identifier of the entity selected by the user;
resolving the one or more overall intents based on the resolved at least one non-resolvable hidden intent that is resolved from the entity identifier of the entity selected by the user; and
generating a response to the user input based on the resolved hidden intent and the resolved one or more overall intents.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
receiving, from the client system of the user, an indication of the entity selected by the user.

### Claim 3 (depends on 2)

The method of claim 2, further comprising:
executing, responsive to receiving the indication, one or more tasks associated with fulfilling the user input.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
sending, to the client system of the user, instructions for presenting the response.

### Claim 5 (depends on 1)

The method of claim 1, wherein parsing the user input comprises:
generating, by a compositional model in response to receiving the user input, a tree-structured representation for the user input, wherein the tree-structured representation comprises one or more non-terminal nodes associated with the one or more overall intents and the one or more hidden intents, one or more non-terminal nodes associated with the one or more slots, and one or more terminal nodes associated with the one or more n-grams of the user input; and 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 corresponds to one of the non-resolvable hidden intents and is associated with the partial slot information corresponding to the 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.

### Claim 6 (depends on 5)

The method of claim 5, wherein each non-resolvable non-terminal node corresponding to a non-resolvable hidden intent is resolved based on the respective partially resolved non-terminal parent node of the non-resolvable non-terminal node and the entity identifier of the entity selected by the user.

### Claim 7 (depends on 5)

The method of claim 5, wherein the response is generated further based on the resolved tree-structured representation.

### Claim 8 (depends on 5)

The method of claim 5, 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 second n-grams associated with the non-resolvable non-terminal node;
exchanging one or more of the second n-grams associated with the non-resolvable non-terminal node with one or more third n-grams based on the identified one or more contexts; and
resolving the non-resolvable non-terminal node based on the one or more third n-grams associated with the non-resolvable non-terminal node.

### Claim 9 (depends on 5)

The method of claim 5, 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.

### Claim 10 (depends on 9)

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

### Claim 11 (depends on 1)

The method of claim 1, further comprising:
querying an entity resolution module for entity information for each slot;
receiving entity identifiers for each resolvable slot; and
generating the partial slot information responsive to being unable to resolve a slot.

### Claim 12 (depends on 11)

The method of claim 11, further comprising, for each non-resolvable hidden intent:
identifying one or more agents associated with the non-resolvable hidden intent;
ranking the one or more agents for the non-resolvable hidden 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 each resolvable slot, (2) the partial slot information associated with the non-resolvable hidden intent, and (3) the entity identifier of the entity selected by the user; and
generating resolved information for the non-resolvable hidden intent.

### Claim 13 (depends on 12)

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

### Claim 14 (depends on 12)

The method of claim 12, further comprising:
determining, for each resolved information associated with each non-resolvable hidden intent, whether the resolved information is accessible to the user based on privacy settings associated with the resolved information,
wherein the response is generated further based on determining that the resolved information is accessible.

### Claim 15 (depends on 1)

The method of claim 1, further comprising:
identifying the two or more entities associated with the partial slot information based on a comparison of social signals between the user and each of the two or more entities.

### Claim 16 (depends on 1)

The method of claim 1, further comprising:
identifying a domain associated with the user input; and
selecting a compositional model for parsing the user input from a plurality of compositional models based on the identified domain, wherein the plurality of compositional models correspond to a plurality of domains, respectively.

### Claim 17

One or more computer-readable non-transitory storage media embodying software that is operable when executed to:
receive, from a client system of a user, a user input comprising a plurality of n-grams;
parse the user input to identify one or more overall intents, one or more hidden intents, and one or more slots associated with the one or more n-grams, wherein at least one of the hidden intents is non-resolvable for being associated with partial slot information corresponding to a first n-gram that has not been resolved to a particular entity identifier, wherein the partial slot information is associated with two or more entity identifiers of two or more entities, respectively, wherein each hidden intent is associated with one of the one or more overall intents, and wherein the one or more hidden intents must be resolved prior to resolving the overall intent;
send, to the client system, instructions for prompting the user to select one of the two or more entities to be associated with the at least one non-resolvable hidden intent and to associate the first n-gram to the entity identifier of the entity selected by the user;
resolve the at least one non-resolvable hidden intent based on the entity identifier of the entity selected by the user;
resolve the one or more overall intents based on the resolved at least one non-resolvable hidden intent that is resolved from the entity identifier of the entity selected by the user; and
generate a response to the user input based on the resolved hidden intent and the resolved one or more overall intents.

### Claim 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, from a client system of a user, a user input comprising a plurality of n-grams;
parse the user input to identify one or more overall intents, one or more hidden intents, and one or more slots associated with the one or more n-grams, wherein at least one of the hidden intents is non-resolvable for being associated with partial slot information corresponding to a first n-gram that has not been resolved to a particular entity identifier, wherein the partial slot information is associated with two or more entity identifiers of two or more entities, respectively, wherein each hidden intent is associated with one of the one or more overall intents, and wherein the one or more hidden intents must be resolved prior to resolving the overall intent;
send, to the client system, instructions for prompting the user to select one of the two or more entities to be associated with the at least one non-resolvable hidden intent and to associate the first n-gram to the entity identifier of the entity selected by the user;
resolve the at least one non-resolvable hidden intent based on the entity identifier of the entity selected by the user;
resolve the one or more overall intents based on the resolved at least one non-resolvable hidden intent that is resolved from the entity identifier of the entity selected by the user; and
generate a response to the user input based on the resolved hidden intent and the resolved one or more overall intents.