Out-of-Distribution Detection through Soft Clustering with Non-Negative Kernel Regression

Aryan Gulati, Xingjian Dong, Carlos Hurtado, Sarath Shekkizhar, Swabha Swayamdipta, Antonio Ortega

TL;DR

This paper introduces NNK-Means, a novel soft clustering approach for Out-of-Distribution (OOD) detection in language models. It significantly reduces computational and storage costs compared to existing methods while achieving state-of-the-art performance, making OOD detection more practical for large-scale applications.

What Problem Does This Paper Address?

Modern language models (LLMs) are becoming increasingly versatile, but a critical challenge remains: ensuring they can reliably handle data that differs from what they were trained on. This "out-of-distribution" (OOD) data can lead to incorrect or unpredictable outputs, posing risks in sensitive domains like medicine and finance, or even in unexpected real-world scenarios. Existing OOD detection methods often struggle with scalability, requiring substantial computational resources and storage, which is a major hurdle for LLMs trained on massive datasets. This paper aims to bridge this gap by proposing a more efficient and effective OOD detection technique.

Methods

The core of this work is a novel OOD detection method based on Non-Negative Kernel Regression (NNK)-based soft clustering, specifically an extension called NNK-Means. Unlike traditional hard clustering (like k-Means) where data points are assigned to a single cluster, NNK-Means uses "soft clustering." This means each data point is associated with multiple cluster centers with varying degrees of similarity (non-negative weights). This soft assignment allows for a more flexible and accurate representation of the in-distribution (ID) data, leading to better OOD detection.

The authors also introduce an entropy-constrained version (EC-NNK-Means). This enhancement aims to automatically estimate the optimal number of clusters, further reducing storage requirements by penalizing less-selected clusters and favoring those that represent more data. This approach allows for a larger initial dictionary of cluster centers, increasing the likelihood of capturing representative data patterns, while efficiently pruning away less important ones.

Datasets

The proposed methods were evaluated on four benchmark datasets:

  • 20 Newsgroups: A widely used text classification dataset with 20 topics.
  • Banking77: A dataset focused on intent classification within the banking domain, with 77 distinct intents.
  • CLINC150: A dataset specifically designed for OOD intent detection, featuring 150 intent classes and a designated OOD class.
  • AG News: A large-scale topic classification dataset.

For evaluation, these datasets were partitioned into in-distribution (ID) and out-of-distribution (OOD) sets, with varying percentages of ID classes (25%, 50%, 75%) used to simulate different levels of OOD challenge.

Key Insights and Ideas

  • Soft Clustering for OOD Detection: The paper demonstrates that soft clustering, by allowing data points to belong to multiple clusters with varying weights, provides a more nuanced representation of the in-distribution data. This improved representation is key to distinguishing OOD samples more effectively.
  • Efficiency through Dictionary Learning: NNK-Means leverages dictionary learning principles, where a set of "cluster centers" (dictionary atoms) are learned to represent the data. This approach inherently reduces storage needs because the model only needs to store the dictionary, not the entire training dataset, unlike many distance-based methods.
  • Entropy Constraint for Adaptive Storage: The EC-NNK-Means variant is a significant contribution, as it adaptively determines the number of clusters. This is crucial because the optimal number of clusters is often unknown and can be a bottleneck in traditional clustering. By using an entropy constraint, the method can achieve comparable or better performance with substantially fewer clusters.
  • Label-Awareness and Label-Blindness: The methods are shown to be flexible, performing well even when ID labels are unavailable (label-blind) but also leveraging them effectively when present (label-aware), often outperforming other methods in label-aware settings.

Key Results

  • State-of-the-Art Performance: NNK-Means and its variants consistently achieved superior or comparable performance to existing OOD detection methods across four benchmark datasets, with improvements of up to 4 AUROC points.
  • Significant Efficiency Gains:
    • Storage: NNK-Means achieved up to an 87% reduction in storage requirements compared to baselines like KNN. The EC-NNK-Means further reduced storage by up to 97%.
  • Inference Time: NNK-Means offered up to an 11x improvement in inference time compared to KNN, making it much faster for processing new data.
  • Robustness to Embeddings: The methods demonstrated competitive performance regardless of the type of text embeddings used (e.g., pre-trained vs. Sentence-BERT).
  • Qualitative Clustering: Visualizations showed that NNK-Means effectively clusters ID data and separates OOD data, with some overlap observed in cases where OOD documents shared semantic similarities with ID classes.

Limitations and Future Work

  • English-Only: The current experiments and datasets are limited to English. Future work could explore applying these algorithms to multilingual settings.
  • Subset of Approaches: The authors acknowledge that they could only compare against a subset of existing OOD detection approaches.
  • Simulated OOD Data: The experiments used unseen classes to simulate OOD data. Real-world OOD scenarios can be more complex and varied, and future work could investigate these diverse scenarios.
  • Future Work: The authors suggest applying their algorithms to analyze large pre-trained datasets, indicating a clear path for future research and development.

Summary updated

Abstract

As language models become more general purpose, increased attention needs to be paid to detecting out-of-distribution (OOD) instances, i.e., those not belonging to any of the distributions seen during training. Existing methods for detecting OOD data are computationally complex and storage-intensive. We propose a novel soft clustering approach for OOD detection based on non-negative kernel regression. Our approach greatly reduces computational and space complexities (up to 11x improvement in inference time and 87% reduction in storage requirements) and outperforms existing approaches by up to 4 AUROC points on four different benchmarks. We also introduce an entropy-constrained version of our algorithm, which leads to further reductions in storage requirements (up to 97% lower than comparable approaches) while retaining competitive performance. Our soft clustering approach for OOD detection highlights its potential for detecting tail-end phenomena in extreme-scale data settings.
BibTeX
@inproceedings{gulati2024out,
  author = {Aryan Gulati and Xingjian Dong and Carlos Hurtado and Sarath Shekkizhar and Swabha Swayamdipta and Antonio Ortega},
  title = {{Out-of-Distribution Detection through Soft Clustering with Non-Negative Kernel Regression}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2024},
  doi = {10.18653/v1/2024.findings-emnlp.758},
}
Figure