Jointly Modeling Inter-Slot Relations by Random Walk on Knowledge Graphs for Unsupervised Spoken Language Understanding

Yun-Nung Chen, William Yang Wang, Alexander I. RudnickyNAACL 2015 · OpenReview

TL;DR

This paper tackles the challenge of automatically building coherent semantic slot sets for spoken language understanding (SLU) systems. They propose a novel approach using random walks on two interconnected knowledge graphs (one for slots, one for words) guided by syntactic dependencies, which leads to more accurate slot induction and improved SLU performance.

What Problem Does This Paper Address?

Designing effective spoken dialogue systems (SDSs) hinges on a robust spoken language understanding (SLU) component. A crucial part of SLU is defining a "slot set" – the categories of information (like "restaurant type" or "price") that the system needs to extract from user utterances. Traditionally, domain experts manually define these slots, which is time-consuming and difficult, especially when considering the complex relationships between different slots (e.g., "cheap" relates to "price"). This paper aims to automate this process by discovering these inter-slot relationships in an unsupervised manner, leading to more comprehensive and coherent slot sets.

Methods

The core of this work lies in leveraging typed syntactic dependency theory to build and connect two knowledge graphs:

  1. Slot-based Semantic Knowledge Graph: Nodes represent potential semantic slots (derived from frame-semantic parsing), and edges represent relationships between these slots.
  2. Word-based Lexical Knowledge Graph: Nodes represent words, and edges represent syntactic dependencies between them.

These two graphs are then combined. The key innovation is a mutually-reinforced random walk algorithm that propagates scores across both graphs. This allows the system to consider:

  • Word-to-word relations: How words relate syntactically.
  • Slot-to-slot relations: How potential semantic slots relate to each other.
  • Word-to-slot relations: How words function as fillers for specific slots.

The algorithm uses dependency parsing to estimate edge weights in these graphs. Two methods for estimating these weights are explored: frequency-based and embedding-based (using dependency-based word embeddings). The random walk process then iteratively updates importance scores for slots, ultimately ranking them to identify the most relevant and coherent set for the domain.

Datasets

The experiments were conducted on the Cambridge University SLU corpus. This corpus consists of dialogues from an in-car setting where users were asked to interact with SDSs for restaurant recommendations. It includes approximately 2,166 dialogues and 15,453 utterances. The data was transcribed using an ASR system, resulting in a word error rate of 37%. The paper notes 10 domain-expert-defined slots for this domain.

Key Insights and Ideas

  • Inter-slot relations are crucial: The paper strongly demonstrates that considering how slots relate to each other is vital for building better SLU systems, moving beyond treating slots independently.
  • Syntactic dependencies as a bridge: Using typed syntactic dependencies provides a principled way to extract meaningful relationships between words and, by extension, between slots.
  • Two knowledge graphs are better than one: Combining a semantic (slot-level) graph with a lexical (word-level) graph through a random walk leads to more robust and comprehensive slot induction.
  • Dependency-based embeddings offer advantages: Using word embeddings trained on syntactic dependencies (rather than just bag-of-words) helps smooth edge weights and mitigate overfitting, especially in smaller datasets.
  • Interpretability boost: The automatically discovered inter-slot relations provide insights into the domain's semantic structure, making the SLU system more interpretable.

Key Results

The paper reports significant improvements across various metrics:

  • Slot Induction: The best performing approach, using a double-graph random walk with embedding-based measurements, achieved 71.48% AP and 70.84% PR-AUC on ASR transcripts for slot induction, outperforming the baseline (frequency-only) by a substantial margin.
  • SLU Model Performance: For SLU evaluation, the same approach yielded 44.06% WAP and 47.91% AF on ASR transcripts. Notably, the single-graph random walk with embedding-based measurement performed even better for SLU tasks (46.29% WAP, 48.89% AF), suggesting a potential trade-off between slot coherence and decoder performance in the double-graph approach.
  • Qualitative Findings: The automatically generated slot-to-slot relations (e.g., "food" is related to "expensiveness" via "AMOD") were deemed reasonable and connected important semantic slots, forming a coherent domain-specific ontology.

Limitations and Future Work

  • Trade-off between coherence and performance: The authors note that while the double-graph approach leads to more coherent slots, it doesn't always translate to better SLU performance compared to the single-graph approach. They suggest future work on jointly optimizing slot coherence and SLU performance.
  • ASR performance impact: The experiments were conducted on ASR transcripts with a 37% word error rate. The performance of the SLU system is inherently limited by the quality of the ASR output.
  • Domain specificity: While the approach is unsupervised in terms of slot induction, the initial frame-semantic parsing and the reference slots are domain-specific. Future work could explore methods for cross-domain adaptation more effectively.
  • Parameter tuning: The damping factor for the random walk was empirically set. Further investigation into optimal parameter selection could be beneficial.

Summary updated

Abstract

A key challenge of designing coherent semantic ontology for spoken language understanding is to consider inter-slot relations. In practice, however, it is difficult for domain experts and professional annotators to define a coherent slot set, while considering various lexical, syntactic, and semantic dependencies. In this paper, we exploit the typed syntactic dependency theory for unsupervised induction and filling of semantics slots in spoken dialogue systems. More specifically, we build two knowledge graphs: a slot-based semantic graph, and a word-based lexical graph. To jointly consider word-to-word, word-toslot, and slot-to-slot relations, we use a random walk inference algorithm to combine the two knowledge graphs, guided by dependency grammars. The experiments show that considering inter-slot relations is crucial for generating a more coherent and compete slot set, resulting in a better spoken language understanding model, while enhancing the interpretability of semantic slots.
BibTeX
@inproceedings{chen2015jointly,
  author = {Yun-Nung Chen and William Yang Wang and Alexander I. Rudnicky},
  title = {{Jointly Modeling Inter-Slot Relations by Random Walk on Knowledge Graphs for Unsupervised Spoken Language Understanding}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2015},
  url = {https://openreview.net/forum?id=HyZafQ-ObH},
}
Figure