Selecting a response in a multi-turn interaction between a user and a conversational bot

• US 10,818,293 B1
• Filed: 07/14/2020
• Issued: 10/27/2020
• Est. Priority Date: 07/14/2020
• Status: Active Grant

• Current Assignee: Drift.com, Inc.
• Original Assignee: Drift.com, Inc.
• Inventors: Orkin, Jeffrey D., Ward, Christopher M.
• Primary Examiner(s): Godbold, Douglas
• Application Number:
  US16/928,892
• Time in Patent Office: 105 Days
• CPC Class Codes: G06F 16/338 Presentation of query results
• CPC Class Codes: G06F 16/9017 using directory or table look-up use of a directory or look-up table in file systems G06F16/13
• CPC Class Codes: G06F 16/90332 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 16/9038 Presentation of query results
• CPC Class Codes: G06F 40/35 Discourse or dialogue representation
• CPC Class Codes: G06F 9/542 Event management; Broadcasting; Multicasting; Notifications
• CPC Class Codes: G10L 15/063 Training
• CPC Class Codes: G10L 15/22 Procedures used during a speech recognition process, e.g. man-machine dialogue
• CPC Class Codes: G10L 15/32 Multiple recognisers used in sequence or in parallel; Score combination systems therefor, e.g. voting systems
• CPC Class Codes: G10L 2015/0631 Creating reference templates; Clustering

Abstract

A method to select a response in a multi-turn conversation between a user and a conversational bot. The conversation is composed of a set of events, wherein an event is a linear sequence of observations that are user speech or physical actions. Queries are processed against a set of conversations that are organized as a set of inter-related data tables, with events and observations stored in distinct tables. As the multi-turn conversation proceeds, a data model comprising an observation history, together with a hierarchy of events determined to represent the conversation up to at least one turn, is persisted. When a new input (speech or physical action) is received, it is classified using a statistical model to generate a result. The result is then mapped to an observation in the data model. Using the mapped observation, a look-up is performed into the data tables to retrieve a possible response.

Claims

1. A method to provide query understanding to select a response in a multi-turn conversation between a user and a conversational bot, the conversation composed of a set of events, wherein an event is composed of a linear sequence of observations that represent an expression of the event, comprising:

organizing a corpus of annotated conversation transcripts into a relational database comprising a set of inter-related tables, the tables including at least a table of events, and a table of observations;

in response to initiation of the multi-turn conversation, instantiating a data model;

as the multi-turn conversation proceeds, persisting in the data model a conversation history between the user and the bot, the data model comprising an observation history, together with a set of events that have been determined to represent the conversation up to at least one turn;

in response to receipt of a new input by the user that is one of;

a speech act, and a physical act, determining a response to the new input;

processing the new input to generate a result, and mapping the result to an observation in the data model;

using the mapped observation as a key, performing a first look-up into the set of inter-related tables to retrieve a set of candidate interpretations given the conversation up to the at least one turn, wherein a candidate interpretation is one that either extends an event or starts a new event;

when a given one of the set of candidate interpretations is determined to extend an event in the set of events, appending the mapped observation to the event to create an extended event;

when an extended event cannot be created but a given one of the set of candidate interpretations is determined to start a new event that has the mapped observation as its initial observation, adding the new event to the set of events;

when no candidate interpretation extends an event or logically starts a new event by an exact match to an existing event in the annotated historical transcripts, creating an aliased event by identifying one other event whose event expression is an approximate match to an existing event in the annotated historical transcripts;

when a given one of the set of candidate interpretations is determined to extend the one other event, appending the mapped observation to the one other event to create an extension of the aliased event;

when the extension cannot be created for the aliased event, creating a new aliased event having the mapped observation as its initial observation, the new aliased event being associated with a sequence of events that has not been seen in the annotated historical transcripts; and

using one of;

the extended event, the new event, the aliased event as extended, and the new aliased event, as a key, performing a second look-up into the set of inter-related tables to retrieve the response.

2. The method as described in claim 1 further including updating the set of events in the data model to include one of:

the extended event, the new event, the aliased event as extended, and the new aliased event.

3. The method as described in claim 1 wherein the response is one or more possible next observations, and further including validating the one or more possible next observations to determine a possible next observation to return to the user.

4. The method as described in claim 3 further including returning a validated possible next observation to the user.

5. The method as described in claim 1 wherein the set of events in the data model are organized into a hierarchy.

6. The method as described in claim 4 wherein the one or more tables include a speech act table, and a physical act table.

7. The method as described in claim 1 wherein the new input is a sequence of words that is grammatically complete.

8. The method as described in claim 1 wherein at least one of the first and second look-ups is a constant-time look-up to retrieve a set of candidate interpretations is a single database query.

9. The method as described in claim 1 wherein the given one of the set of candidate interpretations is determined to extend an event in the set of events when appending the identified observation creates a new sequence of observations that exactly matches an existing event expression.

10. The method as described in claim 1 wherein the given one of the set of candidate interpretations is determined to extend an event in the set of events by filtering the candidate interpretations for coherence.

11. The method as described in claim 1 wherein the multi-turn conversation is one of:

chat, e-mail, SMS and a voice-based interaction.

12. The method as described in claim 1 wherein the new input is speech, and processing the new input includes:

using a statistical model to associate the new input to a cluster of utterances;

identifying a speech act associated to the cluster of utterances, together with an actor; and

mapping the observation from the identified speech act and the identified actor.

13. A software-as-a-service computing platform, comprising:

computing hardware;

computer software executing on the computer hardware, the computer software comprising computer program instructions executed on the computing hardware and configured as a network-accessible front end component, together with an Application Programming Interface (API)-accessible back-end system, the back-end system configured to provide query understanding to select a response in a multi-turn conversation between a user and a conversational bot, the conversation composed of a set of events, wherein an event is composed of a linear sequence of observations that are user speech or physical actions and that represent an expression of the event, the back-end system being shared across concurrent multi-turn conversations and comprising;

a corpus of annotated conversation transcripts organized into a relational database comprising a set of inter-related tables, the tables including at least a table of events, and a table of observations;

a data model instantiated in response to initiation of each multi-turn conversation;

program code operative as the respective multi-turn conversation proceeds to persist in the data model a conversation history between the user and the bot, the data model comprising an observation history, together with a set of events that have been determined to represent the conversation up to at least one turn, and wherein one or more events are active concurrently;

program code operative in response to receipt at the front-end component of a new input by the user that is one of;

a speech act, and a physical act, to determine a response to the new input using information derived from the data model and a first look-up into the relational database that returns a set of candidate interpretations given the conversation up to the one turn, wherein the program code is further operative (i) to determine whether a candidate interpretation in the set extends an event or logically starts a new event;

(ii) when no candidate interpretation in the set extends an event or logically starts a new event, to identify one other event whose event expression is an approximate match to an existing event, the other event being an aliased event;

(iii) when a candidate interpretation extends the one other event, to create an extension of the aliased event;

(iv) when the extension cannot be created for the aliased event, create a new aliased event; and

(v) using one of the aliased event as extended, and the new aliased event, as a key, performing a second look-up into the relational database to obtain the response to the new input; and

program code to return the response to the front-end component for delivery to the user.

14. The computing platform as described in claim 13 wherein the program code to determine the response comprises:

program code configured to process the new input to generate a result, and to map the result to an observation in the data model; and

program code configured to use the mapped observation as a key to perform the first look-up into the set of inter-related tables, thereby retrieving the set of candidate interpretations given the conversation up to the one turn.

15. The computing platform as described in claim 14 further including program code to update the set of events in the data model to include one of:

the extended event, the new event, the aliased event as extended, and the new aliased event.

16. The computing platform as described in claim 14 wherein the response is one or more possible next observations, and further including program code to validate the one or more possible next observations to determine a possible next observation to return to the user.

17. The computing platform as described in claim 16 further including program code to return a validated possible next observation to the front-end component.

18. A method for query processing against a set of annotated conversations that are organized as a set of inter-related data tables, the query arising during a multi-turn conversation between a user and a conversational bot and that is composed of a set of events, wherein an event is composed of a linear sequence of observations that are user speech or physical actions and that represent an expression of the event, and wherein events and observations are stored in distinct tables, comprising:

as the multi-turn conversation proceeds, persisting a data model comprising an observation history, together with a set of events that have been determined to represent the conversation up to at least one turn;

receiving from a user a new input; and

providing a response to the new input, wherein the response is determined by;

performing event recognition on the new input against events and observations stored in the set of inter-related data tables to attempt to identify a meaning associated with the new input, wherein attempting to identify a meaning includes ordered sub-steps of (i) performing a first look-up into the set of inter-related data tables that returns a set of candidate interpretations given the conversation up to the one turn, (ii) determining whether a candidate interpretation in the set extends an event or logically starts a new event;

(iii) when no candidate interpretation in the set extends an event or logically starts a new event, identifying one other event whose event expression is an approximate match to an existing event, the other event being an aliased event, (iv) when a candidate interpretation extends the one other event, creating an extension of the aliased event;

(v) when the extension cannot be created for the aliased event, creating a new aliased event;

approving a candidate interpretation;

based on the approved candidate interpretation, updating the data model;

based on the updated data model,

using at least one of the extension of the aliased event and the new aliased event as a second look-up into the set of inter-related data tables to identify a set of one or more observations for the conversational bot to present to the user; and

performing event recognition on the set one or more observations to select the response.

19. The method as described in claim 18 further including returning the response to the user.