A Non-negative Matrix Factorization Based Approach for Active Dual Supervision from Document and Word Labels

Chao Shen, Tao LiEMNLP 2011

Introduction

In traditional active learning, models typically query human experts for document-level labels to improve classification performance. However, in text classification, human annotators can often provide more efficient feedback by labeling specific features—namely, words—that are highly indicative of a particular class (e.g., "puck" for sports). This paradigm, known as dual supervision, promises higher accuracy at lower costs. The primary challenge lies in the "apples-to-oranges" comparison: determining whether it is more beneficial to label a single document or a set of words. This paper introduces a unified framework that bridges this gap using matrix factorization.

Methodology: Constrained Tri-NMF

The authors address the dual supervision challenge using a Constrained Non-negative Tri-Factorization (Tri-NMF) framework. The document-word matrix $X$ is decomposed into three components: $X \approx GSF^T$, where $G$ represents document-class probabilities, $F$ represents word-class probabilities, and $S$ is a class-alignment matrix.

A critical innovation in this work is the addition of an explicit constraint on the $S$ matrix to ensure it remains approximately diagonal. This forces the document clusters and word clusters to align with the same underlying classes, preventing the model from producing inconsistent or near-random results when labeled data is scarce. This alignment is essential for the model to learn which word-clusters correspond to which document-clusters effectively.

The impact of the S-matrix constraint on classification accuracy across the baseball-hockey, ibm-mac, and med-space datasets.

Unified Utility via Reconstruction Error

The "secret sauce" of this approach is the use of reconstruction error as a unified metric for informativeness. Because NMF treats documents (rows) and words (columns) symmetrically, the potential reduction in reconstruction error—how much better the factors $G, S, F$ can recreate the original matrix $X$ after receiving a new label—serves as a common currency for both types of queries.

The active learning algorithm estimates the "Expected Utility" for each potential query (word or document) by calculating the expected decrease in reconstruction error. This allows the model to automatically decide whether a word or a document is more valuable at any given stage of the learning process, avoiding the need for arbitrary and hard-to-tune "interleaving" ratios used in previous methods.

Experimental Results

The framework was evaluated on binary classification tasks from the 20-Newsgroups collection and a Movie Review dataset for sentiment analysis. The results demonstrate that the "Expected Reconstruction Error" scheme consistently outperforms baseline methods, such as "Expected Log Gain" and fixed interleaving strategies.

Performance comparison of the Expected Reconstruction Error method against various baseline active learning strategies on the ibm-mac dataset.

Key findings from the experiments include:

  • Early-Stage Efficiency: Labeling words is exceptionally effective in the early stages of learning when data is sparse. Words act as "early bloomers," providing broad signals that help the model form its initial clusters.
  • Cost-Effectiveness: Assuming a document label is five times more expensive than a word label, the proposed method achieves target accuracy significantly faster and cheaper than traditional active learning.
  • Robustness: The unified utility metric allows the model to adaptively switch between document and word queries as the model matures, ensuring that the most informative item is always selected regardless of its type.

Conclusion

By framing dual supervision within a Tri-NMF reconstruction framework, the authors provide a principled solution to the query selection problem in active learning. This unified approach eliminates the need for manual tuning of document-to-word ratios and demonstrates superior performance across multiple text classification benchmarks, making it a robust tool for real-world labeling tasks where human expertise is a bottleneck.

Summary updated

BibTeX
@inproceedings{shen2011non,
  author = {Chao Shen and Tao Li},
  title = {{A Non-negative Matrix Factorization Based Approach for Active Dual Supervision from Document and Word Labels}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2011},
}
Figure