Automatic Agenda Graph Construction from Human-Human Dialogs using Clustering Method

Cheongjae Lee, Sangkeun Jung, Kyungduk Kim, Gary Geunbae LeeNAACL 2009

TL;DR

This paper tackles the laborious task of manually creating "agenda graphs" – crucial knowledge structures for dialog management. By employing a novel clustering and linking approach on human-human dialogs, the authors demonstrate a way to automatically construct these graphs, significantly reducing human effort and potentially improving dialog system robustness.

What Problem Does This Paper Address?

Modern spoken dialog systems often rely on sophisticated knowledge sources to manage conversations effectively. Among these, "agenda graphs" play a vital role in representing the discourse structure, guiding the system's progress towards task completion and improving its ability to handle recognition uncertainties. Traditionally, these agenda graphs are meticulously hand-crafted by domain experts. This process is not only time-consuming but also labor-intensive, especially when adapting dialog systems to new applications. The authors aim to automate this knowledge acquisition process, making it more scalable and efficient.

Methods

The core of this paper lies in a two-step automatic construction process for agenda graphs:

  1. Node Clustering: Dialog examples (utterances or turns) are first converted into feature vectors. These features include word-level (unigrams, bigrams, trigrams), utterance-level (dialog act, main goal, slot filling status, system act), and discourse-level (previous dialog act, main goal, system act) information. K-means clustering is then applied to group these feature vectors into clusters, where each cluster represents a potential "node" in the agenda graph. The goal is to group semantically similar dialog examples together.
  2. Node Linking: Once clusters (nodes) are formed, the next step is to establish connections (edges) between them to form a directed acyclic graph (DAG). This is achieved by analyzing the sequential nature of dialog examples within the corpus. The relative frequencies of transitions between clusters are calculated to determine edge weights. The algorithm then prunes underweighted edges and removes cycles to ensure a valid DAG structure. Finally, transition probabilities are estimated by normalizing the remaining edge weights.

Datasets

The paper uses a human-human dialog corpus collected for a building guidance task. This corpus consists of approximately 880 user utterances from 214 dialogs. The authors do not introduce a new benchmark dataset but rather leverage an existing corpus for their experiments.

Key Insights and Ideas

  • Automating Knowledge Acquisition: The most significant insight is the successful demonstration that agenda graphs, a complex form of prior knowledge, can be automatically constructed from dialog data. This bypasses the need for manual design, a major bottleneck in dialog system development.
  • Feature Engineering for Dialog States: The paper highlights the importance of combining various feature types (word-level, utterance-level, and discourse-level) to effectively represent dialog states for clustering. This multi-faceted approach captures richer semantic and contextual information.
  • Clustering as a Proxy for Dialog States: The K-means clustering algorithm effectively groups similar dialog examples, providing a data-driven way to define the nodes (dialog states) of the agenda graph.
  • Sequential Analysis for Transitions: Using the sequential nature of dialogs to infer transitions between clusters is a logical and effective way to build the directed edges of the agenda graph.

Key Results

  • Reduced Error Rates: When evaluating the node clustering performance, using all feature sets (word-level, utterance-level, and discourse-level) resulted in a significantly lower error rate (31.20%) compared to using only word-level (46.51%) or utterance-level (34.63%) features.
  • Comparable System Performance: While the manually crafted agenda graph (HC-AG) slightly outperformed the automatically constructed one (AC-AG) in terms of Task Completion Rate (TCR: 92.96% vs. 89.95%) and average user turns (AvgUserTurn: 4.41 vs. 4.39), the difference was marginal. The authors argue that the AC-AG is still highly beneficial due to the substantial reduction in human effort.

Limitations and Future Work

  • Clustering Performance Improvement: The authors suggest improving clustering performance by exploring distance metric learning algorithms that can account for feature correlations.
  • Discovering New Dialog Flows: They propose using techniques like random walks to discover hidden links and explore new dialog flows within the constructed graph.
  • Marginal Performance Gap: While the automatic approach is promising, there's a slight performance gap compared to manual construction. Further research could focus on bridging this gap.

Summary updated

BibTeX
@inproceedings{lee2009automatic,
  author = {Cheongjae Lee and Sangkeun Jung and Kyungduk Kim and Gary Geunbae Lee},
  title = {{Automatic Agenda Graph Construction from Human-Human Dialogs using Clustering Method}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2009},
}
Figure