A k-Nearest Neighbor Approach towards Multi-level Sequence Labeling

Yue Chen, John ChenNAACL 2019 · DOI

Abstract

Building robust Spoken Language Understanding (SLU) systems often requires vast amounts of annotated data, which is rarely available in specialized domains. This paper explores a k-Nearest Neighbor (k-NN) approach for multi-level sequence labeling in the noisy food-ordering domain. By combining symbolic and vector features and applying targeted post-processing, the proposed system achieves competitive performance using less than 1% of the data typically required by deep learning models, significantly outperforming complex neural architectures on real-world, noisy speech recognition output.

Introduction: The Cold Start Problem in SLU

Developing SLU systems for niche domains like restaurant ordering faces a significant "cold start" challenge: high-performing models are needed to collect data, but large datasets are required to train those models. While state-of-the-art Bi-directional LSTMs (BiLSTMs) are powerful, they are notoriously data-hungry. Researchers often bridge this gap with synthetic data, but these datasets fail to capture the "messiness" of human speech—hesitations, background noise, and complex, mixed-initiative ordering patterns.

This research investigates whether a simpler, more efficient k-NN learner can effectively handle multi-level sequence labeling—identifying fine-grained entities, broader items, and high-level intents—under low-resource conditions.

Multi-level Sequence Labeling Task

The task involves assigning tags to words across three hierarchical levels: fine-grained entities (e.g., TOPPING), broader items (e.g., BRKFST_ITEM), and high-level intents (e.g., IN_ADD_ITEM).

Multi-level annotation example showing entities, items, and intents for a single customer utterance.

As shown in the figure above, a single utterance can contain multiple intents (e.g., a greeting followed by an addition to the order), a complexity that the authors found in 42.2% of their real-world dataset. This multi-layered structure allows the system to extract both specific details and the overall user goal simultaneously.

Methodology: k-NN with Heterogeneous Features

The authors treat sequence labeling as a classification task using a k-NN learner (TiMBL). The core innovation is the use of a heterogeneous feature set that blends traditional symbolic features with modern vector representations:

  • Windowed Word Unigrams & POS Tags: An 11-word window (target word plus five words on either side) provides local context.
  • GloVe Embeddings: 25-dimensional pre-trained vectors capture distributional semantics.

To ensure sequence consistency, a post-processing layer applies tag correction (e.g., ensuring I- tags follow B- tags) and majority voting to unify overlapping spans into single labels.

Experimental Setup

The study compared two primary data sources:

  • Authentic Data: 462 customer utterances from 95 real human-human restaurant dialogues.
  • Synthetic Data: 55,000 utterances generated via a context-free grammar (CFG).

Models were evaluated on both clean Human Transcribed (HT) text and noisy Automatic Speech Recognition (ASR) output.

Key Results and Insights

The k-NN approach demonstrated remarkable resilience to noise compared to more complex models.

Authenticity vs. Volume

A critical finding was that a tiny amount of real-world data (3,610 instances) yielded better results than a massive synthetic dataset (nearly 465,000 instances). Synthetic data, while plentiful, lacks the nuanced linguistic patterns found in actual human interaction.

Robustness to ASR Noise

On noisy ASR input, the k-NN system achieved an F-score of 60.71, significantly outperforming the state-of-the-art BiLSTM-CRF (47.57) and a Maximum Entropy Markov Model (48.26). While BiLSTMs excel on clean text, they are highly sensitive to global context disruptions caused by ASR errors. The k-NN model’s reliance on local windows makes it more robust to these localized errors.

Efficiency

The k-NN model trained in just 0.19 seconds, whereas the BiLSTM-CRF required an hour. This efficiency is vital for rapid iteration in early-stage system development.

Conclusion

This work highlights that in the era of deep learning, simpler algorithms like k-NN remain highly relevant for specialized, low-resource domains. By prioritizing authentic data and combining symbolic linguistic features with dense embeddings, researchers can build effective SLU systems that are both robust to real-world noise and extremely efficient to train.

Summary updated

BibTeX
@inproceedings{chen2019k,
  author = {Yue Chen and John Chen},
  title = {{A k-Nearest Neighbor Approach towards Multi-level Sequence Labeling}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2019},
  doi = {10.18653/v1/n19-2019},
}
Figure