Robust Dialog State Tracking for Large Ontologies

Franck Dernoncourt, Ji Young Lee, Trung Bui, Hung H. Bui

Abstract

The Dialog State Tracking Challenge 4 (DSTC 4) introduces significant complexity compared to previous editions, featuring a much larger ontology, the absence of spoken language understanding (SLU) output, and subdialog-level labeling. This paper presents a novel dialog state tracking method designed for robustness under these conditions. By employing elaborate string matching, custom coreference resolution, and a hybrid machine-learning approach, our system correctly identifies values not explicitly present in utterances. In the final evaluation, our method placed first among 7 competing teams and 24 entries, outperforming the runner-up by 9 and 7 percentage points in utterance-level and subdialog-level F1-scores, respectively.

Introduction

Dialog State Tracking (DST) is the "brain" of a spoken dialog system, maintaining a record of user goals throughout a conversation. Historically, DST research focused on small ontologies with limited values. The DSTC 4 challenge introduced three major hurdles that broke traditional models:

  1. Scale: The ontology expanded from ~270 values to over 1,600 values across 30 slots.
  2. Missing Data: No SLU output was provided, requiring trackers to work directly from raw transcripts.
  3. Label Sparsity: Dialogs were labeled at the subdialog level rather than per utterance, introducing significant noise for standard machine learning models.

Methodology

To address these challenges, we developed a system that combines linguistic intuition with machine learning.

System Architecture

The high-level architecture (Figure 1) processes the current utterance and dialog history against a knowledge base containing the ontology and synonym lists. The Dialog State Tracker generates a list of slot-value pairs, which are then fed back into the dialog history to inform future turns.

High-level architecture of the Dialog State Tracking system.

The Elaborate Rule-Based Tracker

The core innovation of our approach is an elaborate rule-based tracker designed to mimic human linguistic processing. It consists of four primary modules (Figure 2):

  • Robust Synonym Matching: Uses Part-of-Speech (POS) tagging, lemmatization, and Levenshtein distance to handle misspellings and multi-word values (e.g., ensuring "Amoy Hotel" is only triggered if all keywords appear).
  • Coreference Resolution: A custom system handles anaphoras like "here" or "there" by referencing the most recent entities in the dialog history.
  • Slot-Value Pair Pruning: Employs domain knowledge to select the most likely value when multiple related candidates are detected.
  • Slot-Value Pair Carrying Over: Determines whether to maintain a state from a previous utterance or clear it based on detected topic changes.
Internal components of the Elaborate Rule-Based Tracker.

Hybrid Tracker

While pure machine learning models struggled with class imbalance in the large ontology, our final "best" model used a hybrid approach. We used the outputs of the rule-based modules as features for a Random Forest classifier, allowing the model to weigh the evidence from different linguistic modules to make a final binary decision on value presence.

Results

The system was evaluated on the DSTC 4 corpus, consisting of 35 recorded Skype dialogs between tour guides and tourists in Singapore (~31,000 utterances). Our method achieved first place among all 24 entries.

Evaluation Level Our Method (F1) Runner-up (F1) Improvement
Utterance-level 0.5306 ~0.44 +9%
Subdialog-level 0.5786 ~0.51 +7%

The rule-based tracker alone performed nearly as well as the hybrid version, proving that linguistic logic was the primary driver of performance in data-sparse environments.

Conclusion and Future Work

Our results demonstrate that hand-crafted rules incorporating linguistic knowledge are more robust than pure "black box" models when data is scarce and the search space is large. Future work will focus on automatically generating synonym lists from resources like WordNet, improving negation handling, and refining subject identification to better distinguish the main topic of conversation from incidental mentions.

Summary updated

Abstract

The Dialog StateDernoncourt, Franck TrackingLee, Ji Young ChallengeBui, Trung H. 4 (DSTC 4) differentiatesBui, Hung H. itself from the previous three editions as follows: the number of slot-value pairs present in the ontology is much larger, no spoken language understanding output is given, and utterances are labeled at the subdialog level. This article describes a novel dialog state tracking method designed to work robustly under these conditions, using elaborate string matching, coreference resolution tailored for dialogs and a few other improvements. The method can correctly identify many values that are not explicitly present in the utterance. On the final evaluation, our method came in first among 7 competing teams and 24 entries. The F1-score achieved by our method was 9 and 7 percentage points higher than that of the runner-up for the utterance-level evaluation and for the subdialog-level evaluation, respectively.
BibTeX
@inproceedings{dernoncourt2016robust,
  author = {Franck Dernoncourt and Ji Young Lee and Trung Bui and Hung H. Bui},
  title = {{Robust Dialog State Tracking for Large Ontologies}},
  booktitle = {IWSDS},
  year = {2016},
  url = {https://openreview.net/forum?id=njj2fTFYbiR},
}
Figure