Learning to Identify Unexpected Instances in the Test Set

Xiaoli Li, Bing Liu, See-Kiong Ng

Introduction

Most machine learning classifiers operate under the "closed world" assumption, presupposing that the test set will only contain classes encountered during training. However, real-world environments are dynamic; a classifier trained on historical data may encounter novel categories—such as new research topics or uncatalogued disease subtypes—that it is ill-equipped to handle. This challenge is framed as a Positive and Unlabeled (PU) learning problem, where the goal is to distinguish known "Positive" classes from "Negative" (unexpected) instances within an unlabeled test set.

The LGN Methodology

Existing PU algorithms often struggle when unexpected instances are rare, failing to identify a sufficient number of "reliable negatives" within the unlabeled pool to build an effective classifier. To address this "needle in a haystack" scenario, the authors introduce LGN (PU Learning by Generating Negative examples). Rather than searching for negatives, LGN synthesizes them through a three-step process:

  1. Entropy-Based Feature Selection: By comparing word frequencies between the training set ($P$) and the test set ($U$), the algorithm identifies words that appear frequently in the test set but rarely in the training data. These words are assigned high "negativeness" scores based on an entropy formula.
  2. Artificial Document Generation: LGN creates a single, representative artificial negative document ($A_N$). It samples word frequencies from a Gaussian distribution based on test set statistics, weighted by the negativeness scores.
  3. Classification: A Naive Bayes classifier is trained using the original positive data and the synthetic negative document, allowing it to effectively filter unexpected instances from the test set.

Experimental Evaluation

The researchers evaluated LGN using the 20 Newsgroups and Reuters datasets, simulating "unexpected" instances by introducing small percentages ($a$) of documents from categories outside the training set.

F-score performance across varying percentages of unexpected documents.

As shown in Figure 1, LGN maintains a high F-score even when the proportion of unexpected documents is extremely low. While other methods like S-EM and Roc-SVM improve as the outlier population grows, LGN provides robust performance across the entire spectrum, particularly excelling when $a$ is between 5% and 20%.

Key Results and Discussion

The most significant advantage of LGN is its performance in "rare outlier" scenarios. At $a = 5\%$, LGN achieved an average F-score of 77.0%, vastly outperforming traditional PU methods.

Comparison of F-scores at 5% unexpected documents across multiple datasets.

The results in Figure 4 highlight LGN's consistency across diverse datasets. Methods like PEBL, which rely on identifying reliable negatives from the unlabeled pool, often fail entirely (0.5% average F-score) when those negatives are scarce. LGN’s strategy of synthesizing a "statistical signature" of the unknown proves far more resilient than selection-based approaches.

Conclusion

LGN demonstrates that when outliers are rare, synthesis is superior to selection. By leveraging entropy to model novelty, the approach provides a mathematically sound way to handle open-world classification. Future work may involve extending this "artificial instance generation" to non-textual data and more complex models like Support Vector Machines or Neural Networks.

Summary updated

Abstract

Traditional classification involves building a classifier using labeled training examples from a set of predefined classes and then applying the classifier to classify test instances into the same set of classes. In practice, this paradigm can be problematic because the test data may contain instances that do not belong to any of the previously defined classes. Detecting such unexpected instances in the test set is an important issue in practice. The problem can be formulated as learning from positive and unlabeled examples (PU learning). However, current PU learning algorithms require a large proportion of negative instances in the unlabeled set to be effective. This paper proposes a novel technique to solve this problem in the text classification domain. The technique first generates a single artificial negative document AN. The sets P and {AN} are then used to build a naive Bayesian classifier. Our experiment results show that this method is significantly better than existing techniques.
BibTeX
@inproceedings{li2007learning,
  author = {Xiaoli Li and Bing Liu and See-Kiong Ng},
  title = {{Learning to Identify Unexpected Instances in the Test Set}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
}
Figure