PaperlayerView exact revision on arXiv

Source-linked AI summary

Statistical Topic Models for Multi-Label Document Classification

Timothy N. Rubin, America Chambers, Padhraic Smyth, Mark Steyvers

arXiv:1107.2462v2stat.MLcs.LG

TL;DR

Multi-label classifiers face declining performance when datasets contain many labels, many labels per document, and highly skewed label frequencies. The paper evaluates LDA-based generative models that assign words to labels and model label priors and dependencies, finding that Dependency-LDA generally outperforms SVMs on large-scale power-law datasets, especially for rare labels. The models are less uniformly advantageous on smaller or more densely represented benchmarks.

  • Problem

    Discriminative multi-label methods can perform poorly when datasets contain many labels, many labels per document, and highly skewed frequencies with numerous rare labels.

  • Method

    The paper evaluates Flat-LDA, Prior-LDA, and Dependency-LDA, comparing them with one-vs-all SVMs across five datasets and document-based and label-based prediction tasks.

  • Results

    Dependency-LDA generally outperforms SVMs on large-scale power-law datasets, particularly for document-pivoted predictions and rare labels, while performance is comparable on Yahoo! datasets and favors tuned SVMs on RCV1-V2.

  • Takeaways & Limitations

    Modeling label dependencies and assigning words to labels makes probabilistic topic models competitive or better than discriminative methods under large-scale, sparse-label conditions.

  • Takeaways & Limitations

    Hyperparameters were selected heuristically rather than optimized for evaluation metrics, so modest performance improvements may be possible through optimization.

Abstract

from arXiv · show

Machine learning approaches to multi-label document classification have to date largely relied on discriminative modeling techniques such as support vector machines. A drawback of these approaches is that performance rapidly drops off as the total number of labels and the number of labels per document increase. This problem is amplified when the label frequencies exhibit the type of highly skewed distributions that are often observed in real-world datasets. In this paper we investigate a class of generative statistical topic models for multi-label documents that associate individual word tokens with different labels. We investigate the advantages of this approach relative to discriminative models, particularly with respect to classification problems involving large numbers of relatively rare labels. We compare the performance of generative and discriminative approaches on document labeling tasks ranging from datasets with several thousand labels to datasets with tens of labels. The experimental results indicate that probabilistic generative models can achieve competitive multi-label classification performance compared to discriminative methods, and have advantages for datasets with many labels and skewed label frequencies.

1. Introduction

Real-world multi-label corpora often contain thousands of labels, many rare labels, and multiple labels per document, exposing weaknesses in conventional discriminative methods. This paper investigates LDA-based generative models that assign words to labels and model label frequencies and dependencies, finding strong performance on large-scale datasets.

  • 1. Introduction: Independent binary classifiers struggle to identify label-specific words when labels co-occur, because sparse labels provide too little positive training data and introduce confounding features.Words relevant to frequent co-occurring labels can be incorrectly emphasized for a rare label.
  • 1. Introduction: LDA-based models address this problem by assigning individual word tokens to labels, enabling an explaining-away effect that separates words associated with co-occurring labels.The approach avoids treating all words in a document as equally relevant to every label.
  • 1. Introduction: The paper evaluates Flat-LDA, Prior-LDA, and Dependency-LDA against two one-vs-all SVM variants on five datasets with contrasting statistics and multiple prediction tasks.The tasks include document-based and label-based rankings and binary predictions.
  • 1. Introduction: Dependency-LDA generally outperforms SVMs on large-scale power-law datasets, with especially clear advantages for document-based predictions and rare labels.It remains competitive with SVMs on smaller benchmark datasets and on many label-based comparisons.

2. Related Work

Prior work includes supervised topic-model adaptations, Labeled-LDA for multi-label settings, probabilistic multilabel models, and predominantly binary-transformation discriminative methods. This paper extends that work with more flexible models and broader experiments focused on many labels and skewed frequencies.

  • Supervised LDA adaptations were designed for single-label classification or regression and are not directly applicable to multilabel classification.
  • Labeled-LDA puts topics in one-to-one correspondence with labels and restricts each document’s topics to its assigned labels.
  • The paper proposes more flexible LDA models that incorporate prior label frequencies and label dependencies, with L-LDA as a special case.
  • Unlike earlier comparisons focused mainly on small Yahoo! subsets, this work evaluates large, systematic experiments including datasets with many labels and skewed frequencies.
  • Earlier mixture-model work associated document labels with word distributions and anticipated the broader LDA frameworks developed here.
  • Most discriminative multilabel approaches transform the task into binary classification problems, commonly training one independent classifier per label.

3. Topic Models for Multilabel Documents

The paper develops three LDA-based generative models for multilabel documents, progressing from observed labels to label-frequency priors and label dependencies. It also introduces fast inference for Dependency-LDA and illustrates improved rare-label predictions over simpler models and SVMs.

  • Model framework: The models represent each label as a word distribution and each document as a distribution over observed labels, generating words through label assignments.The three models differ in how they model the generative process for labels.
  • Flat-LDA: Flat-LDA treats document labels as given and makes no generative assumptions about how labels are generated.It extends LDA by substituting labels for the usual set of topics.
  • Prior-LDA: Prior-LDA adds a corpus-wide label distribution, making predictions sensitive to highly non-uniform label frequencies.This addresses a limitation of Flat-LDA during test-time prediction.
  • Dependency-LDA: Dependency-LDA adds a topic model over labels to capture label dependencies; Flat-LDA and Prior-LDA are special cases, with Prior-LDA obtained when T = 1.Its topics are corpus-wide label distributions, and document-specific topic mixtures generate label tokens.
  • Inference and limitations: Heuristically selected hyperparameters were not optimized for evaluation metrics, so hyperparameter optimization could modestly improve the reported results.The paper also notes computational limitations for proper Gibbs inference, while the proposed fast method requires substantially less time and achieves similar or better prediction performance.
  • Inference and limitations: The fast inference method was well over an order of magnitude faster per iteration than proper inference and converged in fewer iterations.The authors used fast inference for all reported experiments; an alternative optimized sampler remained slower by an order of magnitude per iteration and required longer burn-in.
  • Prediction comparison: Dependency-LDA leverages label frequencies and correlations to improve predictions over Flat-LDA and Prior-LDA, including performance on rare labels where binary SVMs missed IMMUNITY FROM PROSECUTION.In the illustrated NYT document, Flat-LDA ranked two of four true labels among its top ten predictions, including that rare label.

4. Experimental datasets

The experiments emphasize large multi-label datasets with many labels and skewed label-frequency distributions, while also reporting statistics that characterize label sparsity and label combinations.

  • Datasets: The experimental focus is on the NYT annotated corpus and EUR-Lex, both featuring many labels and skewed label-frequency distributions.The NYT subset contains 30,658 articles and over 4,000 manually assigned labels; the EUR-Lex dataset contains 19,800 legal documents.
  • Preprocessing: Straightforward feature selection and document-representation methods were used to avoid confounding model-performance differences.Feature selection removed stop words and highly infrequent words.
  • Dataset statistics: Table 4 reports dataset statistics intended to illustrate classification difficulties in large-scale power-law datasets.The statistics extend measures previously used in multi-label research.
  • Dataset statistics: Cardinality measures the average number of labels per document, while density measures this average relative to the number of unique labels.A single-label corpus has cardinality equal to 1.
  • Dataset statistics: Mean, median, and mode label frequency describe how many training examples exist for each label and reflect label sparsity.These statistics differ substantially between the two groups of datasets.
  • Dataset statistics: Distinct label sets, label-set frequency, and unique label-set proportion characterize combinations of labels across documents.These measures are particularly relevant to handling dependencies between labels.

5. Experiments

The experiments compare three LDA-based models with two SVM methods across document-pivoted and label-pivoted binary and ranking tasks. Evaluation includes ranking and F1-based measures, with Macro-F1 particularly sensitive to performance on infrequent labels.

  • Experimental design: The experiments compare Dependency-LDA with Prior-LDA and Flat-LDA, and compare LDA-based models with SVM methods across five datasets.The stated objectives include evaluating model differences and performance across prediction settings.
  • SVM baselines: The SVM baselines use one-vs-all binary classifiers trained independently for each label on normalized word-count vectors.Training uses LibLinear version 1.33.
  • SVM baselines: Tuned-SVM selects the positive-instance weight using a hold-out set before retraining the final classifier on the full training set.The hold-out set contains 10% of positive and negative training instances.
  • Prediction tasks: The evaluation covers document-pivoted and label-pivoted prediction perspectives, each with binary-prediction and ranking tasks.This design supports comparisons between LDA-based and SVM-based models across both prediction formats.
  • Ranking evaluation: Ranking evaluation includes AUCROC, AUCPR, average precision, one-error, margin, ranking loss, and IS-error.The measures assess the ordering of relevant and irrelevant labels for test documents.
  • Binary evaluation: Binary predictions are evaluated with macro-averaged and micro-averaged F1 scores computed from document-level or label-level confusion matrices.Macro-F1 averages item-level F1 scores, whereas Micro-F1 pools confusion counts before computing F1.
  • Binary evaluation: Poor performance on infrequent labels can produce poor Macro-F1 while leaving Micro-F1 reasonably good in power-law datasets.Infrequent labels constitute the vast majority of labels in such datasets.

6. Experimental Results

Across these experiments, Dependency-LDA generally outperformed SVMs on power-law datasets, especially on metrics emphasizing rare labels, while results were more mixed on non-power-law datasets. Its relative advantage varied with label frequency, dataset characteristics, and prediction direction.

  • Dependency-LDA outperformed SVMs on 13/13 measures for NYT and 12/13 measures for EUR-Lex, the two power-law datasets.
  • Dependency-LDA’s relative performance decreased as training data per label increased, eventually becoming worse than Tuned-SVMs on the highest-data dataset.The pattern was observed when datasets were ordered by median label frequency.
  • Dependency-LDA’s advantage over Flat-LDA increased with labels per document, and the authors attributed this difference to test-time inference.Both models learn the same label-word distributions during training.
  • On EUR-Lex, Dependency-LDA outperformed SVMs on all Macro-F1 measures, while on NYT all three LDA models did so.Macro-F1 gives equal weight to labels, so these measures reflect performance on rare labels in power-law datasets.
  • On non-power-law datasets, Dependency-LDA and SVM performance was mixed, with SVMs generally outperforming on Health and RCV1-v2.
  • Dependency-LDA significantly outperformed Tuned-SVMs on the rarest labels in both NYT and EUR-Lex, although SVMs caught up or surpassed it for more frequent labels on EUR-Lex.On NYT, Dependency-LDA performed better across all frequency quintiles, with one nonsignificant exception.

7. Conclusions

The experiments support LDA-based generative models for multi-label classification, especially when datasets contain many labels, rare labels, and skewed frequencies. Dependency-LDA improves over simpler LDA variants and generally outperforms binary SVMs on large-scale datasets.

  • Dependency-LDA significantly improves performance over Flat-LDA and Prior-LDA by accounting for label dependencies.
  • Accounting for label dependencies yields larger relative improvements on datasets with many labels per document.
  • On large-scale datasets with power-law-like statistics, Dependency-LDA generally outperforms binary SVMs, particularly for document-pivoted predictions.
  • Dependency-LDA’s advantage is partly attributable to improved performance on rare labels and remains competitive with or better than SVMs across most training-frequency groups.
  • Large-label, long-tail annotation settings motivate further attention because human labeling is expensive and rare labels are common.
  • Future work could combine generative LDA models with discriminative learning to integrate their respective advantages.

Appendix A. Details of Experimental datasets

The New York Times Annotated Corpus contains manually labeled news articles spanning approximately two decades. The experimental corpus selects articles with body text and at least three hand-assigned News\U.S descriptor labels, then uses a random train-test split.

  • The corpus contains nearly every New York Times article published from January 1, 1987, through June 19, 2007.
  • More than 1.5 million articles have manually assigned descriptor tags corresponding to subjects mentioned in each article.
  • The experimental corpus retains documents with body text and at least three descriptor labels from the News\U.S taxonomic directory.
  • After stopword removal, 40% of selected articles were used for training and the remainder for testing.
  • Test articles containing labels absent from training were reassigned to training so every label had at least one positive training instance.

A.2 The EUR-Lex Text Dataset

The EUR-Lex collection contains European Union legal documents labeled with EUROVOC descriptors. The study uses predefined cross-validation splits and applies split-specific preprocessing to remove empty documents and infrequent words.

  • The downloaded EUR-Lex dataset contains 19,940 documents and 3,993 EUROVOC descriptors used as labels.
  • Documents concern European Union law, including treaties and legislation, and were downloaded from the EUR-Lex repository.
  • The dataset provides 10 cross-validation splits equivalent to those used in prior work.
  • For each split, preprocessing removes empty documents and words appearing fewer than 20 times in the training set.

A.3 The RCV1-v2 Dataset

RCV1-v2 is a large newswire benchmark with over 800,000 documents and 103 labels, but its automatically expanded topic hierarchy creates important dataset limitations. These expansions affect training statistics and may complicate interpretation of model performance.

  • RCV1-v2 contains over 800,000 newswire stories assigned one or more of 103 available labels.
  • Many RCV1-v2 labels were assigned automatically through topic-hierarchy expansion rather than manually by editors.
  • Automatically assigned labels remain important during training even when evaluation is restricted to hierarchy-leaf labels.
  • Hierarchy expansion can create unusually few unique label sets relative to document count because originally single-label documents may appear multi-label.
  • The resulting statistics may deviate substantially from real-world power-law label distributions and may produce misleadingly positive model results.

A.4 The Yahoo! Subdirectory Datasets

The Yahoo! Arts and Health datasets use small label sets and fixed training/test splits, while LDA-based models are trained with shared, heuristically chosen parameters and MCMC sampling procedures.

  • Datasets: The Yahoo! Arts and Health datasets contain 19 and 14 unique labels, respectively, with 1,000 training documents per split and remaining documents used for testing.The datasets have relatively few labels per document compared with large-scale power-law corpora.
  • Parameter settings: Hyperparameters for the LDA-based models were chosen heuristically rather than optimized against evaluation metrics.The authors note that cross-validation could reasonably improve the reported performance.
  • Parameter settings: All models use η = 50 and βW = .01 for label-word distributions, with a strong Dirichlet prior on document-label distributions.The authors state that these values were generally unimportant provided η ≫1 and βW ≪1.
  • Parameter settings: For NYT and EUR-Lex, Dependency-LDA uses T = 200 topics, substantially fewer than the number of unique labels.For smaller datasets, T was set approximately equal to the number of unique labels.
  • Parameter settings: Testing explored T values from 50 to 1000; values at most 100 over-penalized infrequent labels, whereas T = 1000 produced additional problems.Labels with fewer than approximately 25 training documents rarely received high probabilities when T was too small.
  • Inference: Posterior estimates were obtained from multiple MCMC chains and samples, then averaged to produce final document-label predictions.Training used 48 chains for φ, while test-time inference used 900 total samples per document across 60 chains.

Appendix C. Derivation of Sampling Equation for Label-Token Variables (C)

The appendix derives the conditional sampling equation for document label-token variables by factoring the conditional probability into a label-assignment likelihood and a topic-conditioned label probability.

  • Conditional sampling: The derivation computes the conditional probability that a document label-token variable c_i^(d) equals label c given other label and topic assignments.The conditioning includes z^(d), z′^(d), and the remaining label variables c_-i^(d).
  • Conditional sampling: The conditional probability is expressed as the product of two factors.One factor concerns label-token assignments given document labels; the other concerns the selected label given its topic and remaining labels.
  • Likelihood factor: The first factor is the likelihood of label assignments given labels, obtained by marginalizing over the document’s label distribution θ^(d).The derivation uses the document’s label-assignment counts and the multinomial Beta function.
  • Topic-conditioned factor: The second factor is analogous to the probability of a word given a topic in standard unsupervised LDA.Here c_i^(d) plays the role of a word, z′_i^(d) the role of a topic assignment, and φ′^(t)_c is estimated during training.
  • Final equation: The appendix concludes by substituting the two factors into the final form of the sampling equation.The relevant topic-label distribution is learned during training time.

Appendix D. Comparisons With Published Results

The appendix compares the paper’s SVM and LDA-based scores with published results on equivalent datasets and splits to contextualize performance within multi-label classification research.

  • Comparison rationale: The published-result comparison is motivated by the broader context of an active field containing both probabilistic and discriminative methods.The authors note variability in published results and a lack of consensus in the literature.
  • Comparison scope: The comparison includes two SVM approaches and three LDA-based approaches alongside published scores on equivalent training-test splits.The appendix uses these comparisons to situate the paper’s results within the broader field.
  • Comparison goals: One goal is to assess whether the Tuned-SVM approach is competitive with similar Tuned-SVM benchmarks used elsewhere.The appendix also aims to contextualize the paper’s own results among alternative classification methods.

Comparison With Published scores on the EUR-Lex Dataset

On EUR-Lex document-pivoted label-ranking evaluations, Dependency-LDA is competitive with published perceptron-based methods and generally outperforms MMP, although DMLPP remains comparable overall.

  • Evaluation: Figure 14 compares the paper’s results with all published results from Loza Mencía and Fürnkranz on EUR-Lex Eurovoc descriptors.The comparison concerns document-pivoted label-ranking evaluations.
  • Caveat: The comparison is not feature-matched: the published work used 5,000 features, whereas this paper retained approximately 20,000 per split.The difference resulted from distinct feature-selection procedures and memory constraints in the published algorithms.
  • Results: Dependency-LDA beats MMP at 5 epochs on all metrics except Is-Error, the metric MMP was tuned to optimize.Dependency-LDA was not optimized with respect to the evaluation measures.
  • Results: Against DMLPP at 2 epochs, Dependency-LDA wins on 2 of 5 measures and loses on 3, leaving no clear overall winner.The authors characterize Dependency-LDA as at least reasonably competitive with DMLPP(2).

Comparison With Published scores on Yahoo! Datasets

On the Yahoo! subdirectory datasets, the paper compares its models with published discriminative results. Its SVM scores closely match prior SVM scores, while MLLS outperforms all SVMs and other evaluated methods.

  • Published comparisons: The paper compares results on Yahoo! subdirectory datasets with numerous previously published discriminative methods.The comparison uses the Yahoo! Arts and Health datasets and considers prior results with differing dataset configurations.
  • SVM comparison: The paper’s SVM scores are quite similar to the SVM scores reported by Ji et al. (2008).The authors use this similarity to demonstrate that their discriminative comparison method is competitive with similar published methods.
  • Published-method results: MLLS outperforms all SVMs and the additional methods considered by Ji et al. (2008) on all scores.This result is reported as the strongest published-method comparison in the Yahoo! evaluation.

Comparison With Published scores on RCV1-v2 Datasets

On RCV1-v2, the paper compares its methods with results spanning a wide range of published algorithms. Dependency-LDA performs worse than SVMs overall, but leads non-SVM methods on Macro-F1 while remaining competitive with most non-SVM methods on Micro-F1.

  • Comparison setup: The RCV1-v2 comparison includes published results from Lewis et al. (2004) and Eyheramendy et al. (2003).The selected studies provide a wide range of algorithms, including popular discriminative methods.
  • Evaluation consistency: Published SVM-1 results required Macro-F1 recomputation to use predictions consistently across scores.The original Macro-F1 and Micro-F1 values came from distinct prediction sets; the paper recomputed Macro-F1 from the available confusion matrices.
  • LDA-based results: Dependency-LDA performs worse than SVMs on RCV1-v2 but outperforms every non-SVM method on Macro-F1.It also achieves Micro-F1 competitive with most non-SVM methods, though it is worse than most logistic-regression methods and SVMs.
Loading 1107.2462v2…