Adapting RNN Sequence Prediction Model to Multi-label Set Prediction

Kechen Qin, Cheng Li, Virgil Pavlu, Javed A. Aslam

Introduction

Multi-label text classification (MLTC) is the task of assigning a set of relevant labels to a document. While Recurrent Neural Networks (RNNs) have revolutionized sequence prediction, their application to set prediction remains challenging because sets lack a natural order. Standard approaches often impose an arbitrary sequence (e.g., alphabetical or frequency-based), which can lead to "early estimation errors." If a model mispredicts the first label in a sequence, the error propagates through the remaining predictions, a phenomenon common in Classifier Chains.

Researchers from Northeastern University have introduced set-RNN, a framework that treats multi-label targets as true sets. By redefining set probability as the sum of all possible label permutations, the model is empowered to discover the most "natural" label order for any specific document, leading to significant performance gains over previous state-of-the-art methods.

Methodology

The fundamental innovation of set-RNN lies in its principled definition of set probability. Unlike traditional sequence-to-sequence models that maximize the probability of a single "correct" sequence, set-RNN defines the probability of a label set $y$ as the sum of probabilities of all its permutations $s$:

$$p(y|x) = \sum_{s \in \pi(y)} p(s|x)$$

This approach contrasts with previous "order-agnostic" models that often used mathematically inconsistent objectives, such as forcing the model to assign high probabilities to every possible permutation simultaneously (e.g., Vinyals-RNN-uniform).

Comparison of training and prediction objectives between set-RNN and baseline models.

Training and Prediction

To handle the computational complexity of summing over all permutations (which grows factorially with set size), the authors implemented two key procedures:

  1. Approximate Training: A modified beam search identifies the top $K$ highest-probability sequences for a given set. The model then maximizes the log-sum of these specific probabilities.
  2. Two-Level Prediction: During inference, the model generates candidate sequences, maps them back to their corresponding sets, and re-evaluates those sets by summing the probabilities of their permutations. This ensures the most likely set is selected, even if its individual sequences are not the top-ranked ones.

Experimental Setup

The model was evaluated on four diverse datasets:

  • RCV1-v2: A standard benchmark of Reuters news articles.
  • AAPD: The Arxiv Academic Paper Dataset.
  • Slashdot & TheGuardian: Two new datasets featuring a mix of editor-assigned and user-generated tags, providing a complex multi-label environment with higher cardinality.

Key Insights

A major finding is that the "natural" order of labels often varies between documents. Forcing a global order (like alphabetical) is counter-intuitive and restricts the model's ability to learn document-specific features. By using a summation objective rather than a product (which would force all permutations to be equally likely), set-RNN only needs to find one or a few high-quality paths to the target set.

Furthermore, the authors demonstrated that the most probable sequence is not necessarily the most probable set. A set with many moderately likely paths can be more probable than a set with one highly likely path but no alternatives. This is a crucial distinction between sequence-based and set-based modeling.

Results and Discussion

The set-RNN model consistently outperformed Binary Relevance, Classifier Chains, and previous RNN-based sequence models across all benchmarks.

Performance comparison (F1 scores) across four datasets.

As shown in the results, set-RNN achieved a label-F1 of 0.361 on the TheGuardian dataset, outperforming the standard seq2seq-RNN (0.331) and Vinyals-RNN-max (0.343). The model also showed superior performance on rare labels. Because it is not constrained by a rigid frequency-based order, it can better attend to document features that trigger less common tags. Analysis of prediction entropy confirmed that set-RNN successfully explores multiple valid paths to reach correct set predictions, rather than collapsing onto a single arbitrary sequence.

Limitations and Future Work

Despite its success, set-RNN has some limitations. The training and prediction processes are approximately $K$ times slower than a vanilla RNN due to the beam search requirements. Additionally, the method's accuracy depends on the beam search's ability to find the true best permutations. Future work may focus on optimizing search algorithms for extremely large label spaces (tens of thousands of labels) and exploring more efficient ways to approximate the set probability sum.

Summary updated

Abstract

We present an adaptation of RNN sequence models to the problem of multi-label classification for text, where the target is a set of labels, not a sequence. Previous such RNN models define probabilities for sequences but not for sets; attempts to obtain a set probability are after-thoughts of the network design, including pre-specifying the label order, or relating the sequence probability to the set probability in ad hoc ways. Our formulation is derived from a principled notion of set probability, as the sum of probabilities of corresponding permutation sequences for the set. We provide a new training objective that maximizes this set probability, and a new prediction objective that finds the most probable set on a test document. These new objectives are theoretically appealing because they give the RNN model freedom to discover the best label order, which often is the natural one (but different among documents). We develop efficient procedures to tackle the computation difficulties involved in training and prediction. Experiments on benchmark datasets demonstrate that we outperform state-of-the-art methods for this task.
BibTeX
@inproceedings{qin2019adapting,
  author = {Kechen Qin and Cheng Li and Virgil Pavlu and Javed A. Aslam},
  title = {{Adapting RNN Sequence Prediction Model to Multi-label Set Prediction}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2019},
  doi = {10.18653/v1/n19-1321},
}
Figure