# US 10,482,874 B2 · Hierarchical belief states for digital assistants

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

- Number: US 10,482,874 B2
- Document ID: US10482874B2
- Status: Granted
- Kind: B2
- Application number: 15/678,065
- Filed: 2017-08-15
- Published: 2018-11-15
- Granted: 2019-11-19
- Earliest claimed: 2017-05-15
- Assignees: Apple Inc.
- Applicants: Apple Inc.
- Inventors: Blaise Thomson; Anders Johannsen; Diarmuid Ó Séaghdha; Federico Flego; Luca Simonelli; Stephen J. Young; Thomas David Voice; Thorvaldur Pall Helgason
- Web page: https://patentgrep.com/patent/US10482874B2

## CPC

- 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/22: Procedures used during a speech recognition process, e.g. man-machine dialogue
- G10L 15/16: using artificial neural networks
- G10L 2015/223: {Execution procedure of a spoken command}
- G10L 2015/228: {of application context}
- G10L: SPEECH ANALYSIS TECHNIQUES OR SPEECH SYNTHESIS; SPEECH RECOGNITION; SPEECH OR VOICE PROCESSING TECHNIQUES; SPEECH OR AUDIO CODING OR DECODING

## Abstract

Systems and processes for operating a digital assistant using a hierarchical belief state are disclosed. In an example process, a user utterance of a dialog is received. A belief state for the dialog is determined. The belief state comprises a plurality of dialog slots. Each dialog slot of the plurality of dialog slots includes a respective marginal certainty for a concept or property represented by the respective dialog slot. A first dialog slot of the plurality of dialog slots further includes one or more joint certainties for one or more interpretations arising from the first dialog slot. Based on the marginal certainty of each dialog slot of the plurality of dialog slots and the one or more joint certainties of the first dialog slot, a policy action is selected from a plurality of candidate policy actions that correspond to the belief state. The selected policy action is performed.

## Claims

### Claim 1

An electronic device, comprising:
one or more processors;
a memory; and
one or more programs, wherein the one or more programs are stored in the memory and configured to be executed by the one or more processors, the one or more programs including instructions for:
receiving a user utterance of a dialogue;
parsing one or more text representations of the user utterance to determine a plurality of semantic interpretations for the user utterance, the plurality of semantic interpretations including more than two concepts or properties, wherein the parsing includes determining that a first concept or property and a second concept or property in the more than two concepts or properties have a joint semantic relationship;
determining, based on the plurality of semantic interpretations, a belief state for the dialogue, the belief state comprising a plurality of dialogue slots representing the more than two concepts or properties, wherein each dialogue slot of the plurality of dialogue slots includes a respective marginal certainty for a respective concept or property represented by the respective dialogue slot, and wherein a first dialogue slot of the plurality of dialogue slots further includes a joint certainty for the first concept or property and the second concept or property based on the determined joint semantic relationship;
determining a plurality of candidate policy actions from the determined belief state;
selecting, based on the marginal certainty of each dialogue slot of the plurality of dialogue slots and the joint certainty, a policy action from the plurality of candidate policy actions; and
performing the selected policy action, including outputting results of the policy action for presentation.

### Claim 2 (depends on 1)

The device of claim 1, wherein a subset of the plurality of dialogue slots descends from the first dialogue slot, wherein the subset represents a plurality of interpretations of a portion of the one or more text representations, and wherein two or more dialogue slots in the subset represent a first interpretation of the plurality of interpretations.

### Claim 3 (depends on 2)

The device of claim 2, wherein each dialogue slot of the two or more dialogue slots is not a descendant of another dialogue slot of the two or more dialogue slots.

### Claim 4 (depends on 2)

The device of claim 2, wherein the first interpretation includes a combination of the first concept or property and the second concept or property.

### Claim 5 (depends on 2)

The device of claim 2, wherein the first concept or property is represented by a second dialogue slot of the plurality of dialogue slots, wherein the second concept or property is represented by a third dialogue slot of the plurality of dialogue slots, and wherein the two or more dialogue slots include the second dialogue slot and the third dialogue slot.

### Claim 6 (depends on 2)

The device of claim 2, wherein each interpretation of the plurality of interpretations does not include a concept or property represented by a dialogue slot of the plurality of dialogue slots that is an ancestor of the first dialogue slot.

### Claim 7 (depends on 2)

The device of claim 2, wherein performing the policy action comprises providing a prompt requesting additional information regarding the plurality of interpretations, and wherein the one or more programs further include instructions for:
receiving user input responsive to the prompt; and
updating the belief state, including updating the joint certainty based on the received user input.

### Claim 8 (depends on 1)

The device of claim 1, wherein the first dialogue slot is a descendant of one or more dialogue slots of the plurality of dialogue slots.

### Claim 9 (depends on 1)

The device of claim 1, wherein a fourth dialogue slot of the plurality of dialogue slots defines an operation for obtaining a value for a property.

### Claim 10 (depends on 9)

The device of claim 9, wherein the one or more programs further include instructions for:
prior to performing the selected policy action, performing the operation to obtain the value of the property; and
associating the obtained value of the property to the fourth dialogue slot of the plurality of dialogue slots, wherein the policy action is performed using the obtained value of the property.

### Claim 11 (depends on 1)

The device of claim 1, wherein a fifth dialogue slot of the plurality of dialogue slots includes a probability distribution over a plurality of values for a concept or property represented by the fifth dialogue slot.

### Claim 12 (depends on 11)

The device of claim 11, wherein a first value of the plurality of values includes one or more words of a first text representation of the one or more text representations, and wherein a second value of the plurality of values includes one or more words of a second text representation of the one or more text representations.

### Claim 13 (depends on 1)

The device of claim 1, wherein the plurality of dialogue slots are arranged in a hierarchical structure.

### Claim 14 (depends on 1)

The device of claim 1, wherein the plurality of semantic interpretations are determined using an ontology and the belief state is determined using the ontology, and wherein the ontology includes first and second nodes representing the first concept or property and the second concept or property, respectively.

### Claim 15 (depends on 14)

The device of claim 14, wherein the plurality of dialogue slots have a hierarchical arrangement that is identical to a hierarchical arrangement of a plurality of corresponding nodes of the ontology.

### Claim 16 (depends on 1)

The device of claim 1, wherein the belief state is determined using a previous belief state corresponding to one or more previous user utterances of the dialogue, the one or more previous user utterances received prior to the user utterance.

### Claim 17 (depends on 1)

The device of claim 1, wherein the one or more programs further include instructions for:
receiving a second user utterance of the dialogue;
in response to receiving the second user utterance:
determining, based on the second user utterance and the belief state, an updated belief state for the dialogue, wherein the updated belief state includes one or more dialogue slots representing a first domain of an ontology, and wherein the belief state does not include any dialogue slot representing the first domain;
selecting a second policy action from a second plurality of candidate policy actions that correspond to the updated belief state, wherein the second policy action includes an action represented by the first domain; and
performing the selected second policy action, including outputting results of the second policy action for presentation.

### Claim 18 (depends on 17)

The device of claim 17, wherein the updated belief state includes the plurality of dialogue slots of the belief state.

### Claim 19 (depends on 17)

The device of claim 17, wherein the one or more programs further include instructions for:
receiving a third user utterance of the dialogue;
determining, based on the third user utterance and the updated belief state, a second updated belief state for the dialogue;
selecting a third policy action from a third plurality of candidate policy actions that correspond to the second updated belief state, wherein the policy action and the third policy action each include an action represented by a second domain of the ontology; and
performing the selected third policy action, wherein performing the selected policy action includes setting a parameter of an application of the device to a first value, and wherein performing the selected third policy action includes changing the parameter of the application from the first value to a second value.

### Claim 20 (depends on 1)

The device of claim 1, wherein the first dialogue slot represents a first third concept or property, and wherein the first dialogue slot comprises a data structure containing:
a first marginal certainty for the third concept or property; and
the joint certainty for the first concept or property and the second concept or property.

### Claim 21

A method for operating a digital assistant, the method comprising:
at an electronic device having one or more processors and memory:
receiving a user utterance of a dialogue;
parsing one or more text representations of the user utterance to determine a plurality of semantic interpretations for the user utterance, the plurality of semantic interpretations including more than two concepts or properties, wherein the parsing includes determining that a first concept or property and a second concept or property in the more than two concepts or properties have a joint semantic relationship;
determining, based on the plurality of semantic interpretations, a belief state for the dialogue, the belief state comprising a plurality of dialogue slots representing the more than two concepts or properties, wherein each dialogue slot of the plurality of dialogue slots includes a respective marginal certainty for a respective concept or property represented by the respective dialogue slot, and wherein a first dialogue slot of the plurality of dialogue slots further includes a joint certainty for the first concept or property and the second concept or property based on the determined joint semantic relationship;
determining a plurality of candidate policy actions from the determined belief state;
selecting, based on the marginal certainty of each dialogue slot of the plurality of dialogue slots and the joint certainty, a policy action from the plurality of candidate policy actions; and
performing the selected policy action, including outputting results of the policy action for presentation.

### Claim 22 (depends on 21)

The method of claim 21, wherein a subset of the plurality of dialogue slots descends from the first dialogue slot, wherein the subset represents a plurality of interpretations of a portion of the one or more text representations, and wherein two or more dialogue slots in the subset represent a first interpretation of the plurality of interpretations.

### Claim 23 (depends on 22)

The method of claim 22, wherein each dialogue slot of the two or more dialogue slots is not a descendant of another dialogue slot of the two or more dialogue slots.

### Claim 24 (depends on 22)

The method of claim 22, a wherein the first interpretation includes a combination of the first concept or property and the second concept or property.

### Claim 25 (depends on 22)

The method of claim 22, wherein the first concept or property is represented by a second dialogue slot of the plurality of dialogue slots, wherein the second concept or property is represented by a third dialogue slot of the plurality of dialogue slots, and wherein the two or more dialogue slots include the second dialogue slot and the third dialogue slot.

### Claim 26 (depends on 22)

The method of claim 22, wherein each interpretation of the plurality of interpretations does not include a concept or property represented by a dialogue slot of the plurality of dialogue slots that is an ancestor of the first dialogue slot.

### Claim 27 (depends on 21)

The method of claim 21, wherein the first dialogue slot is a descendant of one or more dialogue slots of the plurality of dialogue slots.

### Claim 28 (depends on 21)

The method of claim 21, wherein performing the policy action comprises providing a prompt requesting additional information regarding the plurality of interpretations, and wherein the method further comprises:
receiving user input responsive to the prompt; and
updating the belief state, including updating the joint certainty based on the received user input.

### Claim 29 (depends on 21)

The method of claim 21, further comprising:
receiving a second user utterance of the dialogue;
in response to receiving the second user utterance:
determining, based on the second user utterance and the belief state, an updated belief state for the dialogue, wherein the updated belief state includes one or more dialogue slots representing a first domain of an ontology, and wherein the belief state does not include any dialogue slot representing the first domain;
selecting a second policy action from a second plurality of candidate policy actions that correspond to the updated belief state, wherein the second policy action includes an action represented by the first domain; and
performing the selected second policy action, including outputting results of the second policy action for presentation.

### Claim 30 (depends on 29)

The method of claim 29, wherein the updated belief state includes the plurality of dialogue slots of the belief state.

### Claim 31

A non-transitory computer-readable storage medium storing one or more programs configured to be executed by one or more processors of an electronic device and memory, the one or more programs including instructions for:
receiving a user utterance of a dialogue;
parsing one or more text representations of the user utterance to determine a plurality of semantic interpretations for the user utterance, the plurality of semantic interpretations including more than two concepts or properties, wherein the parsing includes determining that a first concept or property and a second concept or property in the more than two concepts or properties have a joint semantic relationship;
determining, based on the plurality of semantic interpretations, a belief state for the dialogue, the belief state comprising a plurality of dialogue slots representing the more than two concepts or properties, wherein each dialogue slot of the plurality of dialogue slots includes a respective marginal certainty for a respective concept or property represented by the respective dialogue slot, and wherein a first dialogue slot of the plurality of dialogue slots further includes a joint certainty for the first concept or property and the second concept or property based on the determined joint semantic relationship;
determining a plurality of candidate policy actions from the determined belief state;
selecting, based on the marginal certainty of each dialogue slot of the plurality of dialogue slots and the joint certainty, a policy action from the plurality of candidate policy actions; and
performing the selected policy action, including outputting results of the policy action for presentation.

### Claim 32 (depends on 31)

The computer-readable storage medium of claim 31, wherein the first dialogue slot represents a third concept or property, and wherein the first dialogue slot comprises a data structure containing:
a first marginal certainty for the first concept or property; and
the joint certainty for the first concept or property and the second concept or property.

### Claim 33 (depends on 31)

The computer-readable storage medium of claim 31, wherein a subset of the plurality of dialogue slots descends from the first dialogue slot, wherein the subset represents a plurality of interpretations of a portion of the one or more text representations, and wherein two or more dialogue slots in the subset represent a first interpretation of the plurality of.

### Claim 34 (depends on 33)

The computer-readable storage medium of claim 33, wherein each dialogue slot of the two or more dialogue slots is not a descendant of another dialogue slot of the two or more dialogue slots.

### Claim 35 (depends on 33)

The computer-readable storage medium of claim 33, wherein the first interpretation includes a combination of the first concept or property and the second concept or property.

### Claim 36 (depends on 33)

The computer-readable storage medium of claim 33, wherein the first concept or property is represented by a second dialogue slot of the plurality of dialogue slots, wherein the second concept or property is represented by a third dialogue slot of the plurality of dialogue slots, and wherein the two or more dialogue slots include the second dialogue slot and the third dialogue slot.

### Claim 37 (depends on 33)

The computer-readable storage medium of claim 33, wherein each interpretation of the plurality of interpretations does not include a concept or property represented by a dialogue slot of the plurality of dialogue slots that is an ancestor of the first dialogue slot.

### Claim 38 (depends on 33)

The computer-readable storage medium of claim 33, wherein performing the policy action comprises providing a prompt requesting additional information regarding the plurality of interpretations, and wherein the one or more programs further include instructions for:
receiving user input responsive to the prompt; and
updating the belief state, including updating the joint certainty based on the received user input.

### Claim 39 (depends on 31)

The computer-readable storage medium of claim 31, wherein the first dialogue slot is a descendant of one or more dialogue slots of the plurality of dialogue slots.

### Claim 40 (depends on 31)

The computer-readable storage medium of claim 31, wherein a fourth dialogue slot of the plurality of dialogue slots defines an operation for obtaining a value for a property.

### Claim 41 (depends on 40)

The computer-readable storage medium of claim 40, wherein the one or more programs further include instructions for:
prior to performing the selected policy action, performing the operation to obtain the value of the property; and
associating the obtained value of the property to the fourth dialogue slot of the plurality of dialogue slots, wherein the policy action is performed using the obtained value of the property.

### Claim 42 (depends on 31)

The computer-readable storage medium of claim 31, wherein a fifth dialogue slot of the plurality of dialogue slots includes a probability distribution over a plurality of values for a concept or property represented by the fifth dialogue slot.

### Claim 43 (depends on 42)

The computer-readable storage medium of claim 42, wherein a first value of the plurality of values includes one or more words of a first text representation of the one or more text representations, and wherein a second value of the plurality of values includes one or more words of a second text representation of the one or more text representations.

### Claim 44 (depends on 31)

The computer-readable storage medium of claim 31, wherein the plurality of dialogue slots are arranged in a hierarchical structure.

### Claim 45 (depends on 31)

The computer-readable storage medium of claim 31, wherein the plurality of semantic interpretations are determined using an ontology and the belief state is determined using the ontology, and wherein the ontology includes first and second nodes representing the first concept or property and the second concept or property, respectively.

### Claim 46 (depends on 45)

The computer-readable storage medium of claim 45, wherein the plurality of dialogue slots have a hierarchical arrangement that is identical to a hierarchical arrangement of a plurality of corresponding nodes of the ontology.

### Claim 47 (depends on 31)

The computer-readable storage medium of claim 31, wherein the belief state is determined using a previous belief state corresponding to one or more previous user utterances of the dialogue, the one or more previous user utterances received prior to the user utterance.

### Claim 48 (depends on 31)

The computer-readable storage medium of claim 31, wherein the one or more programs further include instructions for:
receiving a second user utterance of the dialogue;
in response to receiving the second user utterance:
determining, based on the second user utterance and the belief state, an updated belief state for the dialogue, wherein the updated belief state includes one or more dialogue slots representing a first domain of an ontology, and wherein the belief state does not include any dialogue slot representing the first domain;
selecting a second policy action from a second plurality of candidate policy actions that correspond to the updated belief state, wherein the second policy action includes an action represented by the first domain; and
performing the selected second policy action, including outputting results of the second policy action for presentation.

### Claim 49 (depends on 48)

The computer-readable storage medium of claim 48, wherein the updated belief state includes the plurality of dialogue slots of the belief state.

### Claim 50 (depends on 48)

The computer-readable storage medium of claim 48, wherein the one or more programs further include instructions for:
receiving a third user utterance of the dialogue;
determining, based on the third user utterance and the updated belief state, a second updated belief state for the dialogue;
selecting a third policy action from a third plurality of candidate policy actions that correspond to the second updated belief state, wherein the policy action and the third policy action each include an action represented by a second domain of the ontology; and
performing the selected third policy action, wherein performing the selected policy action includes setting a parameter of an application of the device to a first value, and wherein performing the selected third policy action includes changing the parameter of the application from the first value to a second value.