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:
- 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.
- 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.
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).
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