Abstract
In many real-world classification tasks, categories are organized into hierarchical taxonomies, and systems are often required to provide a list of $k$ likely candidates rather than a single prediction. This paper introduces a framework for "top-$k$ hierarchical classification" by proposing a novel loss function and a Bayes-optimal algorithm, Algorithm K-H. This approach balances the probability of a perfect match with the value of "near-misses" within the hierarchy. Empirical evaluations on functional genomics and expertise matching datasets demonstrate that Algorithm K-H consistently outperforms standard top-$k$ and hierarchical classification methods by ensuring prediction diversity and minimizing hierarchical error.
Introduction: The Challenge of Structured Guesses
In many machine learning applications, such as search engines or automated HR systems, providing a single answer is often insufficient. Instead, these systems offer a list of top-$k$ candidates. Simultaneously, the categories in these domains—such as job roles, species, or product types—are frequently structured in a tree-like hierarchy.
Traditional approaches have treated top-$k$ classification and hierarchical classification as separate problems. Standard top-$k$ methods treat all incorrect predictions as equally bad, ignoring the fact that a "near-miss" (e.g., misclassifying "Soccer" as "Basketball" under a "Sports" node) is more useful than a complete miss (e.g., "International Politics"). Conversely, hierarchical methods typically focus on a single prediction. This paper bridges the gap, addressing scenarios where multiple guesses are allowed and the cost of error depends on the taxonomy.
Methodology
The authors propose two primary contributions to solve this integrated problem.
A New Hierarchical Top-k Loss Function
The researchers extended traditional hierarchical loss—which penalizes errors based on the depth of the first mistake in the tree—to the top-$k$ setting. The new error metric is defined as the minimum hierarchical loss among all $k$ predictions. This ensures that if even one of the $k$ guesses is a "near-miss," the overall error is reduced, incentivizing the model to provide a "safety net" of related categories.
Algorithm K-H: The Bayes-Optimal Solution
A significant challenge in top-$k$ hierarchical classification is the "diversity trap." If a system simply selects the $k$ most likely leaf nodes, they may all cluster within the same branch. If that branch is incorrect, all $k$ guesses fail.
Algorithm K-H addresses this through a backward recursion (dynamic programming) approach on the class tree. It calculates rewards for each node starting from the leaves and moving toward the root, crucially assigning the reward of a parent node only to its best child. This logic forces the system to select candidates from different branches when appropriate, ensuring the $k$ guesses cover more "hierarchical ground."
Empirical Evaluation
The authors evaluated Algorithm K-H against two baselines: K-only (standard top-$k$ ignoring hierarchy) and H-only (hierarchical selection ignoring the joint impact of multiple guesses). Testing was conducted on two distinct domains: functional genomics (12 datasets involving yeast genes) and expertise matching (a dataset of 539 job positions).
Key Results
Algorithm K-H demonstrated superior performance across nearly all tested scenarios.
As shown in the genomics results, K-H consistently achieved the lowest misclassification costs. In the expertise matching data, the advantage of K-H was particularly pronounced when partial matches were highly valued. Furthermore, as $k$ increased (e.g., $k=10$), the H-only method's performance degraded due to a lack of diversity, while K-H maintained its lead by strategically picking a diverse set of high-quality candidates.
Insights and Future Work
The study highlights that near-misses matter significantly for human-in-the-loop systems. By accounting for the hierarchy, the system recognizes that a "close" guess is more valuable than a "far" one. However, some limitations remain. The current model assumes a perfect tree structure, whereas many real-world taxonomies are Directed Acyclic Graphs (DAGs). Additionally, while the selection logic is optimal, the model relies on pre-existing probability distributions. Future work could involve scaling this recursion to massive, non-tree taxonomies and integrating the selection logic directly into the training process of neural networks.
Summary updated