# US 12,087,287 B1 · Induction of dialog flow within a conversational natural language system

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

- Number: US 12,087,287 B1
- Document ID: US12087287B1
- Status: Granted
- Kind: B1
- Application number: 17/235,804
- Filed: 2021-04-20
- Granted: 2024-09-10
- Earliest claimed: 2021-04-20
- Assignees: Interactions LLC
- Applicants: Interactions LLC
- Inventors: Michael Johnston; Minhua Chen; Seyed Eman Mahmoodi; Badrinath Jayakumar
- Web page: https://patentgrep.com/patent/US12087287B1

## CPC

- G10L 15/1815: {Semantic context, e.g. disambiguation of the recognition hypotheses based on word meaning}
- G06F 3/167: {Audio in a user interface, e.g. using voice commands for navigating, audio feedback}
- G06F 8/38: for implementing user interfaces
- G06F 40/279: Recognition of textual entities
- G06F 40/35: Discourse or dialogue representation
- G06T 11/26: Drawing of charts or graphs
- G10L 15/22: Procedures used during a speech recognition process, e.g. man-machine dialogue
- G10L 21/10: Transforming into visible information
- G06F 40/30: Semantic analysis
- G06N 3/044: Recurrent networks, e.g. Hopfield networks
- G06N 3/0442: characterised by memory or gating, e.g. long short-term memory [LSTM] or gated recurrent units [GRU]
- G10L 15/1822: {Parsing for meaning understanding}
- G10L: SPEECH ANALYSIS TECHNIQUES OR SPEECH SYNTHESIS; SPEECH RECOGNITION; SPEECH OR VOICE PROCESSING TECHNIQUES; SPEECH OR AUDIO CODING OR DECODING
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

Structure of conversations between users and agents and/or systems is discovered and interactively displayed to analysts, thereby better supporting development of automated conversation handling systems for different domains. A corpus of prior dialogs of users with agents (without preexisting semantic labels indicating purposes for different parts of the dialogs) is taken as input, and embeddings are generated for textual units (e.g., rounds) of the dialogs. The embeddings are used to cluster the textual units, and the clusters and their relationships are visualized within a user interface that analysts may use to explore and fine-tune the structure of the conversations.

## Claims

### Claim 1

A computer-implemented method of visualizing dialog flow in an agent-user dialog system, the method comprising:
segmenting text for a plurality of dialogs between an agent and a user into a plurality of conversation units;
generating a plurality of embeddings corresponding to the plurality of conversation units by applying a pre-trained model to the conversation units of the dialogs, the pre-trained model comprising:
a first Bi-LSTM trained to encode a conversation unit into a dense vector, and
a second Bi-LSTM trained to generate an embedding for a set of dense vectors generated by the first Bi-LSTM,
wherein the first Bi-LSTM and the second Bi-LSTM are trained using examples encoded using a third Bi-LSTM, the examples comprising positive examples comprising rounds of stored dialogs and negative examples comprising randomly sampled stored dialogs;
clustering the embeddings into a plurality of embedding clusters;
forming a dialog flow graph, wherein the embedding clusters are nodes of the dialog flow graph and edges of the dialog flow graph are formed based on transitions in the dialogs corresponding to the embeddings of the conversation units; and
providing an interactive graphical user interface for visualizing the dialog flow graph.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, wherein the plurality of conversations comprised audio conversations, and wherein the text for the plurality of conversations is obtained by applying speech-to-text algorithms to the audio conversations.

### Claim 3 (depends on 1)

The computer-implemented method of claim 1, wherein the conversation units are conversation rounds, each conversation round consisting of agent text corresponding to a message of the agent to the user and user text corresponding to a response of the user to the agent.

### Claim 4 (depends on 1)

The computer-implemented method of claim 1, further comprising labeling the embedding clusters with keywords obtained from textual statistics derived from text of the conversation units corresponding to the embeddings in the clusters.

### Claim 5 (depends on 4)

The computer-implemented method of claim 4, wherein the keywords comprise both agent-representative keywords derived from agent utterances and user-representative keywords derived from user utterances.

### Claim 6 (depends on 1)

The computer-implemented method of claim 1, wherein forming the dialog flow graph comprises, for each of a plurality of the dialogs, counting transitions between clusters corresponding to the conversation units of the dialog.

### Claim 7 (depends on 1)

The computer-implemented method of claim 1, wherein the interactive graphical user interface comprises a dialog flow view portion depicting the dialog flow graph, and a cluster view portion depicting text of the conversation units corresponding to a cluster node that is currently selected within the dialog flow view.

### Claim 8 (depends on 7)

The computer-implemented method of claim 7, wherein the interactive graphical user interface additionally comprises an individual dialog view portion depicting text of a dialog that contains a conversation unit that is currently selected within the cluster view.

### Claim 9

A non-transitory computer-readable storage medium storing instructions that when executed by a processor perform actions comprising:
segmenting text for a plurality of dialogs between an agent and a user into a plurality of conversation units;
generating a plurality of embeddings corresponding to the plurality of conversation units by applying a pre-trained model to the conversation units of the dialogs, the pre-trained model comprising:
a first Bi-LSTM trained to encode a conversation unit into a dense vector,
a second Bi-LSTM trained to generate an embedding for a set of dense vectors generated by the first Bi-LSTM, and
wherein the first Bi-LSTM and the second Bi-LSTM are trained using examples encoded using a third Bi-LSTM, the examples comprising positive examples comprising rounds of stored dialogs and negative examples comprising randomly sampled stored dialogs;
clustering the embeddings into a plurality of embedding clusters;
forming a dialog flow graph, wherein the embedding clusters are nodes of the dialog flow graph and edges of the dialog flow graph are formed based on transitions in the dialogs corresponding to the embeddings of the conversation units; and
providing an interactive graphical user interface for visualizing the dialog flow graph.

### Claim 10 (depends on 9)

The non-transitory computer-readable storage medium of claim 9, wherein the plurality of conversations comprised audio conversations, and wherein the text for the plurality of conversations is obtained by applying speech-to-text algorithms to the audio conversations.

### Claim 11 (depends on 9)

The non-transitory computer-readable storage medium of claim 9, wherein the conversation units are conversation rounds, each conversation round consisting of agent text corresponding to a message of the agent to the user and user text corresponding to a response of the user to the agent.

### Claim 12 (depends on 9)

The non-transitory computer-readable storage medium of claim 9, the actions further comprising labeling the embedding clusters with keywords obtained from textual statistics derived from text of the conversation units corresponding to the embeddings in the clusters.

### Claim 13 (depends on 12)

The non-transitory computer-readable storage medium of claim 12, wherein the keywords comprise both agent-representative keywords derived from agent utterances and user-representative keywords derived from user utterances.

### Claim 14 (depends on 9)

The non-transitory computer-readable storage medium of claim 9, wherein forming the dialog flow graph comprises, for each of a plurality of the dialogs, counting transitions between clusters corresponding to the conversation units of the dialog.

### Claim 15 (depends on 9)

The non-transitory computer-readable storage medium of claim 9, wherein the interactive graphical user interface comprises a dialog flow view portion depicting the dialog flow graph, and a cluster view portion depicting text of the conversation units corresponding to a cluster node that is currently selected within the dialog flow view.

### Claim 16 (depends on 15)

The non-transitory computer-readable storage medium of claim 15, wherein the interactive graphical user interface additionally comprises an individual dialog view portion depicting text of a dialog that contains a conversation unit that is currently selected within the cluster view.

### Claim 17

A computer system comprising:
a computer processor; and
a non-transitory computer-readable storage medium storing instructions that when executed by the processor perform actions comprising:
segmenting text for a plurality of dialogs between an agent and a user into a plurality of conversation units;
generating a plurality of embeddings corresponding to the plurality of conversation units by applying a pre-trained model to the conversation units of the dialogs, the pre-trained model comprising:
a first Bi-LSTM trained to encode a conversation unit into a dense vector, and
a second Bi-LSTM trained to generate an embedding for a set of dense vectors generated by the first Bi-LSTM,
wherein the first Bi-LSTM and the second Bi-LSTM are trained using examples encoded using a third Bi-LSTM, the examples comprising positive examples comprising rounds of stored dialogs and negative examples comprising randomly sampled stored dialogs;
clustering the embeddings into a plurality of embedding clusters;
forming a dialog flow graph, wherein the embedding clusters are nodes of the dialog flow graph and edges of the dialog flow graph are formed based on transitions in the dialogs corresponding to the embeddings of the conversation units; and
providing an interactive graphical user interface for visualizing the dialog flow graph.

### Claim 18 (depends on 17)

The computer system of claim 17, wherein the plurality of conversations comprised audio conversations, and wherein the text for the plurality of conversations is obtained by applying speech-to-text algorithms to the audio conversations.

### Claim 19 (depends on 17)

The computer system of claim 17, wherein the conversation units are conversation rounds, each conversation round consisting of agent text corresponding to a message of the agent to the user and user text corresponding to a response of the user to the agent.

### Claim 20 (depends on 17)

The computer system of claim 17, the actions further comprising labeling the embedding clusters with keywords obtained from textual statistics derived from text of the conversation units corresponding to the embeddings in the clusters.
