PaperlayerView exact revision on arXiv

Source-linked AI summary

Unsupervised Extraction of Dialogue Policies from Conversations

Makesh Narsimhan Sreedhar, Traian Rebedea, Christopher Parisien

arXiv:2406.15214v1cs.CL

TL;DR

Task-oriented dialogue policies are difficult to derive from existing conversations, despite the availability of conversational data. The paper combines LLM-generated canonical forms with graph traversal to extract flows, and reports better performance than prompt-based LLM methods alongside greater controllability and interpretability.

  • Problem

    Although conversational corpora are available, deriving dialogue policies from them remains a complex, relatively underexplored task.

    Source: §1 · p. 1

  • Method

    The approach converts conversation turns into canonical forms, combines them in a weighted interaction graph, and applies graph algorithms to extract dialogue policies.

    Source: §1 · p. 1, §3.2 · p. 4, §3.3 · p. 4

  • Results

    The hybrid graph-and-LLM approach outperforms prompt-based LLM methods and provides greater controllability, interpretability, and robustness.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The extracted policies can serve as a productivity aid for conversation designers, who can control policy granularity by including digressions.

    Source: §6 · p. 8

    Generated policies are not ready for implementation without careful inspection and iterative improvement by a conversation designer or domain expert.

    Source: §7 · p. 9

Abstract

from arXiv · show

Dialogue policies play a crucial role in developing task-oriented dialogue systems, yet their development and maintenance are challenging and typically require substantial effort from experts in dialogue modeling. While in many situations, large amounts of conversational data are available for the task at hand, people lack an effective solution able to extract dialogue policies from this data. In this paper, we address this gap by first illustrating how Large Language Models (LLMs) can be instrumental in extracting dialogue policies from datasets, through the conversion of conversations into a unified intermediate representation consisting of canonical forms. We then propose a novel method for generating dialogue policies utilizing a controllable and interpretable graph-based methodology. By combining canonical forms across conversations into a flow network, we find that running graph traversal algorithms helps in extracting dialogue flows. These flows are a better representation of the underlying interactions than flows extracted by prompting LLMs. Our technique focuses on giving conversation designers greater control, offering a productivity tool to improve the process of developing dialogue policies.

1 Introduction

Task-oriented dialogue systems need dialogue policies, but deriving them from existing conversations remains a relatively underexplored challenge. The paper combines LLM-generated canonical forms with graph methods to extract policies, reporting better performance than prompt-based LLM methods.

1 Introduction

  • Existing conversation corpora can support intent discovery, but extracting dialogue policies from them remains a more complex challenge with relatively few studies.The authors note that policy extraction requires understanding conversational dynamics and objectives.Source: §1 · p. 1
  • The method converts task-specific conversation turns into canonical forms, clusters variants, and builds a flow-network graph whose nodes are forms and edges are turn transitions.Graph traversal then extracts dialogue policies from the graph.Source: §1 · pp. 1–2
  • The paper presents policy extraction as combining user-and-assistant canonical-form sequences, allowing policies to include branching digressions and to be evaluated with text-generation metrics.The authors also report that these metrics correlate well with human evaluation.Source: §1 · p. 2
  • The hybrid graph-and-LLM approach outperforms prompt-only LLM policy generation and offers greater controllability, interpretability, and robustness.The authors frame it as a practical aid for conversation designers, unlike the more opaque prompt-based approaches.Source: §1 · p. 2

2 Background

Task-oriented dialogue systems commonly use NLU and dialogue-management components, while prior work has explored intent discovery and dialogue-flow extraction. This paper uses canonical forms and graph methods to derive flows without relying on predefined dialogue-act taxonomies.

2 Background

  • Task-oriented systems commonly separate intent and slot understanding in NLU from dialogue-policy selection in a Dialogue Manager.The paper notes that both components typically rely on expert intervention and predefined intents, slots, or policies.Source: §2 · p. 2
  • Canonical forms are concise, descriptive turn representations that offer a flexible alternative to expert-defined intent classes for encoding dialogue policies.The paper's intent-discovery approach generates these forms with an LLM and applies an additional clustering step to user and bot intents.Source: §2 · pp. 2–3
  • Earlier policy-extraction approaches used predefined speech-act or dialogue-act classes, while unsupervised dialogue-structure methods generally produce latent structures not readily usable by a Dialogue Manager.The paper distinguishes its task from workflow discovery, which it describes as explored in a low-data rather than fully unsupervised regime.Source: §2 · p. 3

3 Method

The method turns task-specific conversations into unified canonical-form sequences, merges those sequences into a weighted interaction graph, and extracts dialogue flows using graph traversal. It also identifies alternative paths as digressions to represent more than the main path.

3 Method

  • The pipeline takes a task-specific conversation corpus and outputs dialogue policies as combinations of canonical-form sequences.Its three stages are intent identification, graph construction, and graph traversal.Source: §3 · p. 3

3.1 Intent Identification

  • An LLM assigns canonical forms to user and agent turns; clustering groups variant forms and replaces them with each cluster's most frequent representative.The method uses weakly supervised training from 200 conversations across two ABCD tasks, then applies the trained model across ABCD tasks and to SGD.Source: §3.1 · pp. 3–4

3.2 Graph Construction

  • Each conversation becomes a linear path of canonical-form turns, and paths from all conversations for a task are merged into a directed graph with transition-frequency edge weights.The graph's nodes are user and agent canonical forms, and its edges connect successive forms in conversations.Source: §3.2 · p. 4

3.3 Policy Extraction via Graph Traversal

  • For the main flow, the method seeks a source-to-target path with the largest minimum edge capacity, using the most common opening and final canonical forms as endpoints.Fattest-Path Dijkstra maximizes the minimum edge weight along a path.Source: §3.3 · pp. 4–5

3.3.1 Dialogue Flow Digressions

  • To add digressions, the method flags neighbors dissimilar to the next main-flow node, finds widest paths from candidates to the end, and retains paths sufficiently dissimilar to the main trajectory.The experiment uses κ = 0.8, selected through manual evaluation on a small set of extracted digressions.Source: §3.3.1 · p. 5

4 Experimental Settings

The experimental settings compare graph-traversal and prompting-based policies on SGD and ABCD, using automatic text and sequence metrics plus human evaluation.

4.1 Datasets

  • SGD contains 20 domains and 20k annotated conversations, while ABCD has over 10k human-to-human customer-service dialogues with agent action sequences.SGD dialogues were generated from automatically created dialogue sketches; ABCD conversations involve non-expert clients and agents following realistic support scripts.Source: §4.1 · pp. 5–6

4.2 Baselines

  • The baselines include longest-path and maximum-weighted-path graph traversal, alongside GPT-4-turbo and GPT-3.5-turbo prompting on canonical-form conversations.The weighted path sums transition frequencies to maximize the number of conversations modeled.Source: §4.2 · p. 6

4.3 Evaluation

  • Policies are evaluated as sequences of canonical forms against conversations represented in the same form.The paper frames extraction as translation and multi-document summarization, and assesses coverage and quality with BLEU, ROUGE, METEOR, and BERTSCORE.Source: §4.3 · p. 6, §4.3.1 · p. 6

4.3.1 Automatic Evaluation

  • Longest Common Subsequence measures how many conversation utterances a policy handles in the same order, allowing non-contiguous matches.Exact matching requires identical canonical forms; similarity-based matching uses embedding similarity above a threshold to accommodate some intent-identification errors.Source: §4.3.1 · pp. 6–7

4.3.2 Human Evaluation

  • Human evaluation samples five SGD domains and 10 conversations per domain, comparing graph-based and GPT-4-turbo dialogue flows.Annotators map flow steps to conversation turns and rate canonical-form relevance: 1 indicates comprehensive description, while 0.5 indicates omitted details.Source: §4.3.2 · p. 7

5 Results and Analysis

The graph-based methods outperform prompting-based alternatives on automatic and human evaluations, while also offering conversation designers more control over dialogue flows. The analyses further examine structural alignment, intent identification, digressions, and robustness.

5.1 Automatic Metrics

  • Graph-extracted policies achieve higher mean LCS scores than GPT-4 policies, while manual intent-identification accuracy is 70% for users and 87% for bots.The automatic metrics, including LCS, depend on unsupervised intent identification.Source: §5.1 · p. 7, Table 2 · p. 8
  • Fattest-width Dijkstra outperforms other graph methods by +8/+12 BLEU and +8/+11 ROUGE across both datasets, and GPT-4 by +1.5 BLEU and +2 ROUGE.Source: §5.1 · p. 7, Table 1 · p. 8

5.2 Human Evaluation

  • Human annotations show graph-extracted flows have significantly higher precision and marginally better recall than GPT-4 flows.Source: §5.2 · p. 7, Table 3 · p. 8
  • In some evaluated areas, graph scores are lower because the main dialogue flows used for human evaluation lack digressions.Source: §5.2 · p. 8

5.3 Considerations for Developers

  • Graph methods let designers set dialogue-flow length, identify and select digressions, and balance precision against recall; prompting-based methods offer less fine-tuned control and interpretability.Source: §5.3 · p. 8
  • Adding one digression improves all metrics by about 1 point, and graph methods support precise digression mapping and visual representation of dialogue progression.Source: §5.3 · p. 8

5.2 Human Evaluation

  • Manual scores track automatic evaluation trends in BookAppointment and SearchHotel, indicating a strong correlation between automatic metrics and human ratings.Source: §5.2 · p. 7, Table 4 · p. 8

5.3 Considerations for Developers

  • Graph methods produce deterministic outputs regardless of input order, whereas prompting-based approaches can vary with conversation presentation order.Source: §5.3 · p. 8

6 Conclusion

The paper proposes extracting dialogue policies from conversation datasets without predefined dialogue acts, aiming to reduce expert effort. It presents network-flow modeling and canonical-form sequences as means to make policies explainable and their granularity controllable.

6 Conclusion

  • The hybrid LLM-and-graph method extracts dialogue policies without relying on a predefined set of dialogue acts.Generating policies from conversational datasets can reduce the effort required of conversation designers and domain experts.Source: §6 · p. 8
  • Dialogue policies can be computed using network flow over conversations, while canonical-form sequences enhance explainability and controllability.Digressions represented as high-flow paths let designers control policy granularity.Source: §6 · p. 8

7 Limitations and Risks

The authors caution that generated policies need expert inspection and iterative refinement, and identify unresolved evaluation and safety risks. They also note that intent-identification choices and automatic-metric validity beyond the evaluated tasks remain uncertain.

7 Limitations and Risks

  • Generated policies are imperfect and require inspection by a conversation designer or domain expert before implementation in a task-oriented dialogue system.The authors characterize the method primarily as a productivity tool, with policies iteratively improved by experts.Source: §7 · p. 9
  • The impact of intent-identification methods remains underexplored, including how clustering and sentence embeddings may affect graph-method performance.The authors also call for comparison with other intent-extraction methods.Source: §7 · p. 9
  • Text-generation metrics correlated well with human evaluation on five conversational tasks, but may not do so on other datasets.Developers are encouraged to check metric-human correlation against a small human-annotated dataset before using the metrics to evaluate extracted flows.Source: §7 · p. 9
  • Policies may include irrelevant or malicious canonical forms drawn from the input corpus, so designers should investigate and curate them.The authors identify this as a risk of the approach.Source: §7 · p. 9

8 Broader Impact

The authors describe planned releases of code, generated policies, and conversations annotated with Llama3-70B-Instruct. The ABCD and SGD materials are intended for research use only, and the authors expect such a tool to benefit developers and companies with task-oriented conversation datasets.

8 Broader Impact

  • The authors aim to release code and generated policies for the ABCD and SGD datasets, with use restricted to research purposes.They state that these materials would not be commercially usable.Source: §8 · p. 9
  • They also aim to release conversations annotated with Llama3-70B-Instruct to support better annotation quality.Source: §8 · p. 9
  • The authors expect a dialogue-policy extraction tool to benefit companies and developers with task-oriented conversation datasets.Source: §8 · p. 9

A Implementation Details for Intent Identification

The appendix describes prompt-based weak-label creation and a p-tuned language model for intent identification. It specifies the prompt’s canonical-form instructions and the model’s training setup.

A.1 Prompt Template for Creating Weak Labels.

  • Initial weak labels used text-davinci-003 on 200 ABCD conversations across two tasks, with greedy decoding at temperature 0.The authors report that gpt-3.5-turbo-instruct achieved similar performance for canonical-form generation in initial experiments.Source: §A.1 · p. 12
  • The prompt asks for short canonical-form summaries of utterance intent, reusing forms for similar intents and annotating each conversation turn.The annotated conversation is output with its canonical forms.Source: §A.1 · p. 12

A.2 P-Tuned LLM for Intent Identification with Weak Labels

  • Intent identification uses an in-house 43-billion-parameter decoder-only GPT model trained on 1.1 trillion tokens.P-tuning used 30 virtual tokens, batch size 8, learning rate 1e-4, and up to 50 epochs; training and validation sets contained 850 and 300 samples, respectively.Source: §A.2 · p. 12

A.3 Intent Detection Performance of the p-tuned LLM

The appendix reports canonical-form intent-identification accuracy and describes normalization, policy examples, and the prompting baseline. The prompt-based flow-generation setup uses batches of 100 conversations.

A.3 Intent Detection Performance of the p-tuned LLM

  • User intent accuracy was 70% and bot intent accuracy was 87% with the p-tuned LLM; text-davinci-003 yielded 86% and 93%, respectively.The predictions were compared with manual canonical-form annotations from 20 conversations, using a MiniLMv6 semantic-similarity threshold of 0.8.Source: §A.3 · p. 12

A.4 Intent Normalization

  • Agglomerative clustering used a 0.9 threshold for SGD and 0.7 for ABCD, selected by searching thresholds from 0.5 to 1.0.Euclidean distance was used as the clustering metric.Source: §A.4 · p. 12

B Examples of Generated Dialogue Policies

C Details for Prompting-Based Dialogue Policy Generation

  • The prompting baseline asks an LLM to produce the most commonly traversed path from dialogue flows represented with canonical forms.Because of context-length limits, each method receives a batch of 100 conversations for flow extraction.Source: C Details for Prompting-Based Dialogue… · p. 13

D Automatic Evaluation Metrics by Domain

The automatic evaluation extracts a dialogue flow from one batch of conversations and evaluates it on a distinct set. Across both SGD and ABCD, the graph method outperformed GPT-4 prompting on more than 60% of tasks.

D Automatic Evaluation Metrics by Domain

  • Each flow was extracted from a batch of 100 conversations and evaluated on distinct conversations excluded from that batch.For example, in a domain with 300 conversations, the remaining 200 were used for evaluation, which the authors say helps ensure fair evaluation and mitigate overfitting.Source: D Automatic Evaluation Metrics by Domain · p. 13
  • The graph method outperformed GPT-4 prompting on more than 60% of tasks in both the SGD and ABCD datasets.The task-level BLEU and ROUGE scores were ordered by the performance difference between the graph method and GPT-4 prompting.Source: D Automatic Evaluation Metrics by Domain · p. 13

E Manual Evaluation

The manual evaluation compares graph-based and GPT-4-generated policies using human annotations, while a separate experiment examines variation across GPT-4 prompting runs. The supplied results report higher graph-based precision and recall and narrow ranges across prompting runs.

E Manual Evaluation

  • Eight volunteers with at least an MSc in computer science or a related domain reviewed 25 conversation-flow pairs each, with methods balanced and undisclosed.Each pair was labeled by two annotators, with substantial agreement (Cohen’s κ=0.71) on whether a canonical form matched a turn; the annotation UI is shown in Figure 6.Source: E Manual Evaluation · p. 13, Figure 6 · p. 17

E.1 Precision and Recall of Policies

  • The graph-based approach obtained higher precision and recall than the prompt-based method for user and bot canonical forms.The evaluation treats user canonical forms as dialogue state and bot canonical forms as a measure of how well predicted responses match the conversation; Table 6 reports the comparison against human annotations.Source: §E.1 · p. 14, Table 6 · p. 15

F Variance in LLM output

  • Across five GPT-4-turbo runs with randomized conversation order, BLEU and ROUGE scores varied within a relatively narrow range.The authors nevertheless state that determinism is preferred for reproducibility and reliability; Table 5 presents the run-level metric variance.Source: F Variance in LLM output · p. 14, Table 5 · p. 14
  • Figures 4 and 5 show task-level BLEU and ROUGE scores for the graph method and GPT-4, ordered by their performance difference.The figures cover the SGD and ABCD datasets, respectively.Source: Figure 4 · p. 15, Figure 5 · p. 15

E Manual Evaluation

  • Table 7 presents extracted SGD dialogue-policy examples with and without digressions, alongside a sample conversation for each domain.Source: Table 7 · p. 16

Related papers

Loading 2406.15214v1…