Half Transductive Ranking

Bing Bai, Jason Weston, David Grangier, Ronan Collobert, Corinna Cortes, Mehryar MohriAISTATS 2010 · OpenReview

This paper introduces Half Transductive Ranking (HTR), a hybrid machine learning approach designed for information retrieval (IR) scenarios where the document collection is relatively static, but queries are dynamic and unpredictable. Presented by researchers from NEC Labs, Google, and NYU, HTR bridges the gap between inductive models that generalize to new data and transductive models that capture complex relationships within a fixed set.

The Challenge of Out-of-Sample Queries

In search and retrieval, systems must handle two types of data: a "library" of documents and user-generated queries. Standard machine learning approaches typically fall into two camps:

  1. Inductive Ranking: These models learn general functions based on features (e.g., word counts). While they handle new queries and documents well, they often struggle to capture deep, non-linear relationships within a specific collection.
  2. Transductive Ranking: These models (e.g., manifold learning) excel at capturing hidden structures within a fixed set but suffer from the "out-of-sample" problem—they cannot process new queries or documents introduced after training.

HTR addresses this by treating documents transductively (learning specific representations) and queries inductively (learning a functional mapping).

Methodology

The core innovation of HTR is its hybrid scoring function: $$f(x, y_i) = v_i^\top W\phi(x)$$

  • $v_i$ (Transductive): Each document $y_i$ in the fixed collection is assigned a learnable vector, allowing the model to "memorize" complex, non-linear embeddings.
  • $W\phi(x)$ (Inductive): Queries $x$ are mapped into the same space using a functional embedding $W$ applied to query features $\phi(x)$, ensuring the model can process unseen queries.

The authors propose three training variants: a reconstruction-based approach ($\frac{1}{2}$TR) similar to non-linear LSI, a graph-based approach for manifold preservation, and a supervised ranking setup using a margin-based loss. Training is scaled via Stochastic Gradient Descent (SGD) on triplets.

Experimental Results

The HTR framework was evaluated across several large-scale datasets, demonstrating significant improvements over traditional baselines.

Unsupervised Retrieval on RCV1

On the Reuters Corpus (RCV1), which contains over 800,000 news stories, the HTR version of Latent Semantic Indexing (LSI) significantly outperformed standard linear LSI and TF-IDF in precision-recall benchmarks.

Precision-recall curves on the RCV1 dataset comparing HTR (HALFTRANS) with LSI and TF-IDF.

Supervised Ranking on Wikipedia

In a massive-scale supervised task involving 1.8 million Wikipedia documents, HTR outperformed strong baselines such as Supervised Semantic Indexing (SSI) and Margin Ranking Perceptrons. As shown in the table below, HTR achieved the lowest Rank-Loss and the highest Mean Average Precision (MAP) and Precision@10 (P@10).

Performance comparison of HTR against standard baselines on the supervised Wikipedia ranking task.

Conclusion

Half Transductive Ranking provides a powerful "best of both worlds" solution for modern IR. By allowing documents to have their own learned representations while maintaining a functional mapping for queries, HTR achieves high representational power and scalability. While the fixed document set remains a constraint, the framework's ability to handle millions of items via sparse SGD updates makes it a highly practical choice for large-scale search engines.

Summary updated

Abstract

We study the standard retrieval task of ranking a fixed set of items given a previously unseen query and pose it as the half transductive ranking problem. The task is transductive as the set of ite...
BibTeX
@inproceedings{bai2010half,
  author = {Bing Bai and Jason Weston and David Grangier and Ronan Collobert and Corinna Cortes and Mehryar Mohri},
  title = {{Half Transductive Ranking}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2010},
  url = {https://openreview.net/forum?id=UO6_Q9-IhR3},
}
Figure