Dialog management using knowledge graph-driven information state in a natural language processing system

1. A computer-implemented method comprising:

determining an operational state of an interaction with a user based on parameter values of a data structure, the operational state reflecting a current status of a request associated with an earlier-made selection made by the user during the interaction, as updated based on the interaction;

identifying a plurality of candidate moves for changing the operational state, the identifying comprising:

determining a domain in which the interaction is occurring;

retrieving a set of candidate moves that correspond to the domain from a knowledge graph, wherein the earlier-made selection corresponds to a first move of the knowledge graph, the first move including a node at a first level of the knowledge graph, and wherein the set of candidate moves includes a plurality of nodes at a second level of the knowledge graph; and

adding the set to the plurality of candidate moves;

encoding input of the user received during the interaction into encoded terms;

determining a second move for changing the operational state based on a match of the encoded terms to the set of candidate moves; and

updating the parameter values of the data structure based on the second move to reflect a current operational state led to by the second move, wherein the set of candidate moves is updated to remove a prior-available candidate move based on the updated parameter values, and wherein the prior-available candidate move has become unavailable based on a de-selection of an earlier-made selection made by the user during the interaction.

2. The computer-implemented method of claim 1 , wherein identifying the plurality of candidate moves comprises:

identifying a non-null parameter value of the parameter values;

determining potential moves for modifying the non-null parameter value; and

adding the potential moves to the plurality of candidate moves.

3. The computer-implemented method of claim 1 , wherein encoding the input of the user received during the interaction into the encoded terms comprises:

parsing the input into terms;

categorizing each of the terms with an entity label;

determining an intent of the terms based on each entity label; and

generating the encoded terms based on the intent.

4. The computer-implemented method of claim 3 , wherein categorizing each of the terms with an entity label comprises:

applying a transformation to the input based on a heuristic; and

determining each entity label for the terms based on the transformation.

5. The computer-implemented method of claim 3 , wherein encoded terms that are categorized as a decision correspond to an addition or subtraction from one or more of the parameter values, wherein encoded terms that are categorized as a form indicate a set of parameters corresponding to the parameter values to be changed as part of the state change, and wherein encoded terms that are categorized as a leaf indicate a parameter value corresponding to the set of parameters that is to be changed.

6. The computer-implemented method of claim 3 , wherein determining the second move for changing the operational state comprises:

determining, for each respective candidate move of the plurality of candidate moves, a respective probability that the respective move matches a given term of the terms;

assigning, for each respective candidate move of the plurality of candidate moves, a respective score based on the respective probability; and

selecting the second move to be a candidate move of the plurality of candidate moves with a highest respective score.

7. The computer-implemented method of claim 6 , wherein the second move comprises a plurality of decisions, each corresponding to a change of a separate parameter value of the plurality of parameter values.

8. The computer-implemented method of claim 1 , further comprising:

outputting a verbal message as part of the interaction based on the current operational state.

9. A non-transitory computer-readable storage medium storing computer program instructions executable by a processor to perform operations comprising:

determining an operational state of an interaction with a user based on parameter values of a data structure, the operational state reflecting a current status of a request associated with an earlier-made selection made by the user during the interaction, as updated based on the interaction;

identifying a plurality of candidate moves for changing the operational state, the identifying comprising:

determining a domain in which the interaction is occurring;

retrieving a set of candidate moves that correspond to the domain from a knowledge graph, wherein the earlier-made selection corresponds to a first move of the knowledge graph, the first move including a node at a first level of the knowledge graph, and wherein the set of candidate moves includes a plurality of nodes at a second level of the knowledge graph; and

adding the set to the plurality of candidate moves;

encoding input of the user received during the interaction into encoded terms;

determining a second move for changing the operational state based on a match of the encoded terms to the set of candidate moves; and

updating the parameter values of the data structure based on the second move to reflect a current operational state led to by the second move, wherein the set of candidate moves is updated to remove a prior-available candidate move based on the updated parameter values, and wherein the prior-available candidate move has become unavailable based on a de-selection of an earlier-made selection made by the user during the interaction.

10. The non-transitory computer-readable storage medium of claim 9 , wherein generating the plurality of candidate moves comprises:

identifying a non-null parameter value of the parameter values;

determining potential moves for modifying the non-null parameter value; and

adding the potential moves to the plurality of candidate moves.

11. The non-transitory computer-readable storage medium of claim 9 , wherein encoding the input of the user received during the interaction into the encoded terms comprises:

parsing the input into terms;

categorizing each of the terms with an entity label;

determining an intent of the terms based on each entity label; and

generating the encoded terms based on the intent.

12. The non-transitory computer-readable storage medium of claim 11 , wherein categorizing each of the terms with an entity label comprises:

applying a transformation to the input based on a heuristic; and

determining each entity label for the terms based on the transformation.

13. The non-transitory computer-readable storage medium of claim 11 , wherein encoded terms that are categorized as a decision command an addition or subtraction from one or more of the parameter values, wherein encoded terms that are categorized as a form indicate a set of parameters corresponding to the parameter values to be changed as part of the state change, and wherein encoded terms that are categorized as a leaf indicate a parameter value corresponding to the set of parameters that is to be changed.

14. The non-transitory computer-readable storage medium of claim 11 , wherein determining the second move for changing the operational state comprises:

determining, for each respective candidate move of the plurality of candidate moves, a respective probability that the respective move matches a given term of the terms;

assigning, for each respective candidate move of the plurality of candidate moves, a respective score based on the respective probability; and

selecting the second move to be a candidate move of the plurality of candidate moves with a highest respective score.

15. The non-transitory computer-readable storage medium of claim 14 , wherein the second move comprises a plurality of decisions, each corresponding to a change of a separate parameter value of the plurality of parameter values.

16. A system comprising:

a processor for executing computer program instructions; and

a non-transitory computer-readable storage medium storing computer program instructions executable by the processor to perform operations comprising:

determining an operational state of an interaction with a user based on parameter values of a data structure, the operational state reflecting a current status of a request associated with an earlier-made selection made by the user during the interaction, as updated based on the interaction;

identifying a plurality of candidate moves for changing the operational state, the identifying comprising:

determining a domain in which the interaction is occurring;

retrieving a set of candidate moves that correspond to the domain from a knowledge graph, wherein the earlier-made selection corresponds to a first move of the knowledge graph, the first move including a node at a first level of the knowledge graph, and wherein the set of candidate moves includes a plurality of nodes at a second level of the knowledge graph; and

adding the set to the plurality of candidate moves;

encoding input of the user received during the interaction into encoded terms;

determining a second move for changing the operational state based on a match of the encoded terms to the set of candidate moves; and

updating the parameter values of the data structure based on the second move to reflect a current operational state led to by the second move, wherein the set of candidate moves is updated to remove a prior-available candidate move based on the updated parameter values, and wherein the prior-available candidate move has become unavailable based on a de-selection of an earlier-made selection made by the user during the interaction.

17. The system of claim 16 , wherein generating the plurality of candidate moves comprises:

identifying a non-null parameter value of the parameter values;

determining potential moves for modifying the non-null parameter value; and

adding the potential moves to the plurality of candidate moves.

18. The system of claim 16 , wherein encoding the input of the user received during the interaction into the encoded terms comprises:

parsing the input into terms;

categorizing each of the terms with an entity label;

determining an intent of the terms based on each entity label; and

generating the encoded terms based on the intent.

19. The system of claim 18 , wherein categorizing each of the terms with an entity label comprises:

applying a transformation to the input based on a heuristic; and

determining each entity label for the terms based on the transformation.

20. The system of claim 18 , wherein encoded terms that are categorized as a decision command an addition or subtraction from one or more of the parameter values, wherein encoded terms that are categorized as a form indicate a set of parameters corresponding to the parameter values to be changed as part of the state change, and wherein encoded terms that are categorized as a leaf indicate a parameter value corresponding to the set of parameters that is to be changed.