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:
- Scale: The ontology expanded from ~270 values to over 1,600 values across 30 slots.
- Missing Data: No SLU output was provided, requiring trackers to work directly from raw transcripts.
- 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.
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.
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