Abstract
We introduce the framework of recall systems for efficient learning and retrieval of categories when the number of categories is large. A recall system here is a simple feature-based intermediate filtering step which reduces the potential categories for an instance to a small manageable set. The correct categories from this set can then be determined using traditional classifiers. We present a formalization of the index learning problem and establish NP-hardness and approximation hardness. We proceed to give an efficient heuristic for learning indices, and evaluate it on several large data sets. In our experiments, the index is learned within minutes, and reduces the number of categories by several orders of magnitude, without affecting the quality of classification overall.
Introduction: The Challenge of Large-Scale Classification
In modern machine learning, many real-world applications—such as tagging web pages in the Yahoo! hierarchy or predicting the next word in a sentence—face the "curse of cardinality." When the number of possible categories reaches thousands or millions, standard "one-vs-all" classification approaches become computationally prohibitive. Training and running a separate classifier for every single category for every new instance is a computational nightmare.
This paper addresses the need for a high-speed filtering layer that can quickly discard the vast majority of irrelevant categories, leaving a manageable "shortlist" for more sophisticated classifiers to process.
The Recall System Framework
The core contribution is the Recall System, an architectural shift in how classification is handled. Instead of a direct mapping from instance to classifiers, the system introduces an intermediate indexing step.
As shown in Figure 1, the recognition process follows a two-stage pipeline:
- Recall System (Index): Maps the input instance $x$ to a reduced set of candidate categories.
- Classifier Application: Applies specific classifiers only to the candidates identified in the first step to determine the final recognized categories.
The fundamental insight is that this first stage prioritizes recall over precision. It is acceptable to include false positives (wrong categories), as the second-stage classifiers will filter them out. However, false negatives (missing the correct category) are fatal, as a missed category cannot be recovered later in the pipeline.
Learning the Index
The authors formalize the index learning problem as finding an index that minimizes false positives while keeping false negatives below a predefined threshold. They prove that finding an optimal index is NP-hard and difficult to approximate, justifying the use of a heuristic approach.
The proposed Indexer Algorithm is a fast, online, mistake-driven heuristic:
- Initialization: Feature weights are set using inverse document frequency ($1/df$).
- Promotion: If a true category is missed (false negative), the weights of active features for that category are increased.
- Demotion: If the system returns too many incorrect categories (exceeding a tolerance $\tau$), the weights of active features for those false positives are decreased.
- Thresholding: A category is included in the candidate set only if the weight of at least one active feature exceeds a specific threshold.
Experimental Evaluation
The system was evaluated on four diverse, large-scale datasets: Reuters RCV1 (text categorization), Ads (Yahoo! advertisements), ODP (Open Directory Project with >70,000 categories), and a word prediction task using Jane Austen's novels.
As summarized in Figure 5, the results demonstrate the efficiency of the recall system:
- Massive Pruning: On the Reuters dataset, the average number of candidates ($W$) was reduced from 453 to approximately 68-72. On the massive ODP dataset, over 74 million potential mappings were pruned down to a few hundred candidates.
- Speed: The indexer typically learned the mapping within minutes (e.g., $T^{(20)} = 0.46h$ for Reuters).
- Accuracy Preservation: False negative rates ($FN$) remained extremely low across all datasets, ensuring that the final classification accuracy was not compromised by the filtering step.
Conclusion
Recall systems provide a pragmatic solution to large-scale classification by using features as a layer of indirection. By avoiding the need to evaluate every category for every instance, the framework achieves significant speedups in both training and inference. The mistake-driven learning approach ensures efficiency, making it highly suitable for sparse, high-dimensional data common in web-scale applications.
Summary updated