Breaking the Closed World Assumption in Text Classification

Geli Fei, Bing LiuNAACL 2016 · DOI

TL;DR

This paper tackles the challenge of "open world" text classification, where new, unseen categories can appear during testing. They propose a novel "center-based similarity space learning" (CBS learning) approach that effectively reduces the risk of misclassifying unknown documents by creating tighter boundaries around known categories, outperforming existing methods.

What Problem Does This Paper Address?

Traditional text classification systems operate under a "closed world assumption," meaning they are trained on a fixed set of categories and are expected to classify new documents only into these known categories. However, in real-world scenarios, such as analyzing vast amounts of online content, new topics or categories can emerge over time. This "open world" scenario requires a classifier not only to assign documents to known categories but also to identify and reject documents belonging to unknown categories. Existing methods often struggle with this, either by overgeneralizing and misclassifying unknown documents into known categories or by being too restrictive. This paper aims to bridge this gap by developing a more robust open-world classification system for text.

Methods

The core of the paper's contribution lies in its proposed "center-based similarity space learning" (CBS learning) strategy. Instead of working directly with document feature vectors (e.g., n-grams), CBS learning transforms these vectors into a "similarity space." In this space, each document is represented by its similarity to predefined "centers" of known classes. This approach has two key advantages:

  • Reduced Open Space Risk: Traditional methods often define the "positive" space for a class as an infinite half-space. CBS learning, by contrast, aims to define a bounded, spherical area around the class center. This significantly reduces the "open space risk" – the chance of misclassifying unknown documents as belonging to a known class.
  • Balancing Empirical and Open Space Risk: The method seeks to balance the accuracy on known classes (empirical risk) with the ability to correctly reject unknown classes (open space risk).

For multiclass classification, the authors adapt this binary approach by using a set of one-vs-rest classifiers. The output scores from these classifiers are then converted to probabilities, and a threshold is applied to decide whether to assign a document to a known class or reject it as unknown. The paper also discusses the underlying assumptions of CBS learning, which include the idea that document classes are generated by mixture models and that within a class, documents are distributed around a central point, ideally following a Gaussian distribution.

Datasets

The paper evaluates its proposed method on two publicly available datasets:

  • 20-newsgroup: A standard dataset containing documents from 20 different newsgroups.
  • Amazon reviews: A dataset of product reviews from 50 different product categories.

For both datasets, the authors randomly sampled 70% of documents for training and used the remaining 30% for testing. They also employed an "open world cross-validation style analysis," where some classes were held out during training and mixed back into the test set, allowing for evaluation across varying numbers of known and unknown classes.

Key Insights and Ideas

  • The "Closed World" is Unrealistic: The paper strongly emphasizes that real-world text classification often involves encountering new, previously unseen categories, making the traditional closed-world assumption impractical.
  • Geometric Intuition for Open Space Risk: By visualizing the problem, the paper illustrates how CBS learning creates a more contained "positive" region for a class, akin to a ball, compared to the unbounded half-space of traditional SVMs. This geometric insight is crucial for understanding why it reduces open space risk.
  • Similarity Space as a Solution: Shifting from raw feature space to a similarity space is a key innovation. This allows the model to learn relationships between documents and class centers in a way that is more robust to variations and less prone to overgeneralization.
  • The Importance of "Rejection": The paper highlights that a critical component of open-world classification is the ability to confidently reject documents that don't fit any known category, rather than forcing them into an incorrect one.

Key Results

The paper demonstrates that their proposed CBS learning method, referred to as "cbsSVM," consistently outperforms several state-of-the-art baselines across various experimental settings.

  • Superior Performance: In most scenarios (23 out of 28 settings), cbsSVM achieved the best results in terms of F1 scores.
  • Robustness: Even in the traditional closed-world scenario (100% of test classes used in training), cbsSVM still performed competitively.
  • Specific Dataset Performance: For Amazon domains, cbsSVM achieved F1 scores ranging from 0.566 to 0.873 depending on the percentage of training classes. For 20-newsgroup, results ranged from 0.417 to 0.855.
  • Comparison to Baselines: cbsSVM generally outperformed baselines like 1-vs-rest-SVM, 1-vs-set-linear, W-SVM, and P1-SVM, particularly in scenarios with a significant number of unknown classes.

Limitations and Future Work

  • Performance with Few Known Classes: The authors acknowledge that when only a very small number of known classes are available (e.g., 2 classes), cbsSVM's performance can degrade. This is attributed to the difficulty in accurately estimating the radius ($r_0$) for the positive class when positive and negative training examples are far apart.
  • Future Work: The paper explicitly states that future work will focus on designing a more robust solution that can effectively handle scenarios with a small number of known classes.

Summary updated

BibTeX
@inproceedings{fei2016breaking,
  author = {Geli Fei and Bing Liu},
  title = {{Breaking the Closed World Assumption in Text Classification}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2016},
  doi = {10.18653/v1/n16-1061},
}
Figure