PaperlayerView exact revision on arXiv

Source-linked AI summary

Evaluation Measures for Hierarchical Classification: a unified view and novel approaches

Aris Kosmopoulos, Ioannis Partalas, Eric Gaussier, Georgios Paliouras, Ion Androutsopoulos

arXiv:1306.6802v2cs.AIcs.LG

TL;DR

Hierarchical classification lacks evaluation measures that properly account for relations among classes and differing error severity. The paper abstracts existing measures into two generic frameworks, proposes two corresponding measures, and evaluates them with existing approaches on three large text-classification datasets. The proposed measures show more robust behavior, while the results support the inadequacy of flat measures for hierarchical categorization.

  • Problem

    Hierarchical classification needs evaluation measures that account for class relations and distinguish errors with different hierarchical severity.

  • Method

    The paper analyzes existing measures through flow-network and set-theoretic frameworks, proposes two corresponding measures, and evaluates them on selected cases and three large datasets.

  • Results

    The proposed measures showed more robust behavior than their counterparts, and hierarchical measures behaved differently especially on multi-label data and DAG hierarchies.

  • Takeaways & Limitations

    The results support using hierarchy-aware evaluation because flat measures are not adequate for hierarchical categorization systems.

  • Takeaways & Limitations

    Most existing pair-based measures handle only tree hierarchies and single-label problems, while DAG and multi-label phenomena increase the complexity of evaluation.

Abstract

from arXiv · show

Hierarchical classification addresses the problem of classifying items into a hierarchy of classes. An important issue in hierarchical classification is the evaluation of different classification algorithms, which is complicated by the hierarchical relations among the classes. Several evaluation measures have been proposed for hierarchical classification using the hierarchy in different ways. This paper studies the problem of evaluation in hierarchical classification by analyzing and abstracting the key components of the existing performance measures. It also proposes two alternative generic views of hierarchical evaluation and introduces two corresponding novel measures. The proposed measures, along with the state-of-the art ones, are empirically tested on three large datasets from the domain of text classification. The empirical results illustrate the undesirable behavior of existing approaches and how the proposed methods overcome most of these methods across a range of cases.

1 Introduction

Hierarchical classification requires evaluation measures that account for relations among classes, because flat measures treat errors with different hierarchical severity equally. This paper organizes existing measures, proposes two new ones, and compares them empirically on large text-classification datasets.

  • Motivation: Hierarchical classification is important for large-scale systems that organize data into taxonomies, where flat classifiers are poorly suited to hundreds of thousands of related classes.Hierarchical classifiers have shown promising results for improving information retrieval.
  • Evaluation gap: No established evaluation measures adequately address hierarchical classification, whose class relations make algorithm assessment more complicated than in flat classification.Upper-level mistakes can be more severe than errors between closely related classes.
  • Contributions: The paper groups existing measures into flow-network and set-theoretic frameworks and provides a generic framework for each type.It uses these frameworks to analyze and abstract the key components of existing measures.
  • Contributions: It critically reviews existing hierarchical measures and introduces two new measures intended to address important deficiencies in state-of-the-art approaches.The new measures correspond to the two proposed generic frameworks.
  • Empirical study: The study provides comparative empirical results on large hierarchical-classification datasets using a variety of hierarchical-classification algorithms.The datasets come from text classification.

2 A Framework of Hierarchical Classification Performance Measures

The paper develops a framework for describing and characterizing hierarchical-classification performance measures. It defines notation, discusses evaluation requirements, and uses the framework to analyze existing and proposed measures.

  • Framework: The framework defines supporting notation and general requirements for evaluating hierarchical-classification systems.The requirements are based on problems that arise in hierarchical classification.
  • Framework: The paper presents the framework before using it to describe and analyze existing performance measures and introduce new ones.The framework is applied in subsequent sections.

2.1 Notation

Hierarchical classification organizes classes in taxonomies rather than treating them as unrelated. The paper focuses on acyclic hierarchies and allows instances to belong to any hierarchy class.

  • Notation: A training set is denoted as S, while each instance is represented by a feature vector x_i and a set of classes y_i ⊆ C.The class universe is C = {c_1, . . . , c_K}.
  • Hierarchy types: Hierarchical taxonomies are usually trees with one parent per node or DAGs whose nodes can have multiple parents.The hierarchy imposes parent-child relations among classes.
  • Hierarchy properties: The class relationship is assumed to satisfy asymmetry and transitivity in the acyclic hierarchies considered by the paper.The paper denotes descendants, ancestors, and parents as De(c), An(c), and Pa(c), respectively.
  • Classification setting: The paper assumes that an instance may be classified in any class of the hierarchy, not only in a leaf class.This assumption is stated for hierarchies without cycles.

2.2 General Problems in Hierarchical Classification Evaluation

Hierarchical evaluation must distinguish error severity and resolve how predicted and true classes are paired. The paper identifies distance, alternative-path, multi-label pairing, and long-distance cases requiring special handling.

  • Error severity: Flat measures can assign equal penalties to predictions whose hierarchical errors differ substantially in severity.A prediction in an unrelated subtree is more severe than one near the true class.
  • Problem types: Evaluation problems divide into pairing problems, which select compared class pairs, and distance-measuring problems, which score each selected pair.The paper associates pairing with Figures 2(d) and 2(e), and distance measurement with Figures 2(c), 2(a), and 2(b).
  • Distance measurement: For over-specialization and under-specialization, a desirable measure reduces the penalty according to the distance between predicted and true classes.Over-specialization predicts a descendant of the true class; under-specialization predicts an ancestor.
  • Alternative paths: Alternative paths arise when multiple routes connect a predicted class to the true class, requiring a choice between one path or both for evaluation.The paper considers selecting the path that minimizes distance reasonable.
  • Pairing: In multi-label classification, different pairings between true and predicted classes can produce different evaluation scores.A predicted class may be compared with one or multiple true classes, or left unmatched, depending on the pairing.
  • Long-distance errors: The long-distance problem concerns predictions that are too distant from true classes to be matched to any of them.The paper treats this as a distinct case requiring special handling.

2.3 Pair-based Measures

Pair-based hierarchical measures model evaluation as a minimum-cost pairing between predicted and true classes, represented through constrained flow networks. Existing approaches often restrict hierarchy or label structure, while MGIA extends matching to multi-label cases.

  • Pair-based evaluation: Pair-based measures assign costs to predicted–true class pairs, with total error obtained from the selected pair costs.The costs commonly reflect shortest-path distance in the hierarchy, so closer classes incur less severe errors.
  • Pair-based evaluation: Predicted and true class sets are augmented with default classes to collect unmatched labels, including cases exceeding a distance threshold.The default classes are excluded from pairing with each other.
  • Pair-based evaluation: The pairing problem minimizes overall classification error subject to binary alignment and bounds on how many true or predicted classes each class may match.Setting αp = βp = 1 requires each predicted class to pair with exactly one true class; analogous bounds apply to true classes.
  • Flow-network framework: A flow network connects the source, predicted classes, true classes, default classes, and sink, with capacities encoding admissible pairings and flow values yielding the minimum-cost solution.Integer capacities guarantee an integer-valued minimum-cost flow when a feasible flow exists.
  • Existing measures and extension: Most existing pair-based measures handle only tree hierarchies and single-label problems, while GIE’s best matching can mishandle multi-label pairings.MGIA allows each class to participate in more than one pair, making it more suitable for multi-label pairing.

2.4 Set-based Measures

Set-based measures augment true and predicted class sets with hierarchical information, then calculate costs over those augmented sets. Existing approaches differ in their augmentation and cost calculations, while LCA-based measures address over-penalization and account for true positives.

  • Set-based evaluation: Set-based measures operate on entire true and predicted class sets rather than pairing individual classes.This avoids pairing and long-distance problems identified for pair-based measures.
  • Set-based evaluation: They have two phases: augmenting both class sets with hierarchy information, then calculating a cost measure over the augmented sets.Augmentation may add ancestors or descendants of true and predicted classes.
  • Existing set-based measures: The main cost approaches are symmetric difference loss and hierarchical precision and recall.Symmetric difference expresses false-positive and false-negative components, whereas hierarchical precision and recall use augmented-set overlap.
  • Existing set-based measures: Adding descendants can assign maximum penalty when true and predicted classes lie in different subgraphs, even if several ancestors were correctly predicted.This illustrates how augmentation choices can produce undesirable penalties.
  • Existing set-based measures: Tolerance adjustments remove selected augmented classes to reduce penalties for over-specialization and under-classification, but may favor systems that stop predictions early.The adjustment treats descendant predictions and ancestor predictions differently while introducing an early-stopping bias.
  • Lowest Common Ancestor measures: LCA-based PLCA, RLCA, and FLCA measures use lowest common ancestors to address over-penalization from nodes with many ancestors.The measures extend hierarchical precision, recall, and F1 using LCA-based representations for true and predicted classes.
  • Lowest Common Ancestor measures: LCAall collects the lowest common ancestors for each true class relative to predictions and each predicted class relative to true classes.For DAGs, shortest paths and potentially multiple lowest common ancestors are considered.
  • Lowest Common Ancestor measures: The LCA approach removes ancestors when descendants coexist in the same true or predicted set, preventing extra ancestors from artificially increasing F1.This preprocessing is applied symmetrically to the true and predicted class sets.

3 Case Studies

The case studies expose when hierarchical measures behave undesirably and compare pair-based, set-based, and proposed LCA approaches across these situations. Overall, the proposed measures generally match or improve on existing measures, while LCA measures are usually preferred over MGIA because multiple path counting often overestimates error.

  • 3.1 Handling the Pairing Problem: Case 1 shows that ancestor-inclusive hierarchical precision and recall can increase merely when extra nodes are added above the lowest common ancestor.The proposed LCA versions avoid this effect by ignoring nodes above the lowest common ancestor.
  • 3.1 Handling the Pairing Problem: MGIA handles Case 1’s nearby unmatched prediction more suitably than GIE, which pairs one label and assigns the other the maximum cost.MGIA permits multiple categorial matches in this situation.
  • 3.2 Ancestor Augmentation: In Case 2, existing set-based measures fail to distinguish a farther misclassification, whereas LCA-SDL differentiates the cases through their nearest common ancestors.The augmented LCA sets change between the two cases, while the other augmented sets remain identical.
  • 3.3 Alternative Paths: In DAGs with alternative paths, pair-based measures remain unaffected by an additional equal-length path, while existing set-based measures are affected.The pair-based behavior follows from using the shortest path.
  • 3.4 Multiple Path Counting: Pair-based methods can overestimate error by counting shared paths repeatedly, although MGIA’s extra penalty can better reflect more severe errors in some cases.In Figure 16(b), MGIA error rises from 7 to 10, while symmetric-difference loss rises from 5 to 6 and FLCA falls from 0.44 to 0.25.
  • 3.5 Long Distances: Maximum-distance thresholds affect pair-based measures more strongly than set-based measures because repeated path counting amplifies threshold changes.In the example, l∆(Yaug, ˆYaug) decreases by 2 points, whereas MGIA decreases by 4.
  • 3.6 Over and under-specialization: Over- and under-specialization are both treated as errors, and all measures assign greater error when the predicted category is farther from the true category.The simplest inner-node cases receive the same scores, while moving the predicted node farther upward increases the error estimate.
  • 3.7 Summary: Across the studied cases, proposed measures perform at least as well as existing measures in their categories; LCA measures are usually preferred over MGIA, with exceptions where multiple-path counting helps.Pair-based measures handle alternative paths and long distances by definition, while proposed LCA measures address alternative paths among set-based methods.

4 Empirical Study

Experiments on LSHTC2 and LSHTC3 datasets show that evaluation-measure choice changes system rankings, with effects depending on hierarchy structure, multi-labeling, and measure design. The results also expose computational constraints at large scale and illustrate differing behavior among proposed and existing hierarchical measures.

  • Cross-measure ranking effects: Flat accuracy and hierarchical measures produce different system rankings, and hierarchical measures also disagree with one another across experimental conditions.The study’s goal was to assess how evaluation choice affects rankings using real systems and datasets.
  • Multi-labeling and hierarchy: Multi-labeling substantially affects measure behavior: systems assigning more labels can be rewarded or penalized differently depending on how a measure handles extra predictions.This effect is limited in nearly single-labeled DMOZ but becomes more consequential in datasets with greater multi-labeling.
  • Measure-specific behavior: Set-based measures avoid over-penalizing system X2, which predicts 10.649 labels per instance versus 1.8550 true labels, because it predicts ancestor paths rather than only leaves.Pair-based measures penalize this behavior more severely, while MGIA and FLCA are comparatively less extreme.
  • Scale and robustness: On DBpedia Large, computational issues from the large DAG required maximum path thresholds of 2 and 4, although most rankings remained stable when the threshold was reduced.The authors advise keeping the maximum-path parameter as large as possible.
  • Measure-specific behavior: MGIA and FLCA become less correlated in the more complex, multi-labeled setting, while MGIA’s multi-pairing changes its ranking of systems C3 and E3.MGIA ranks C3 better than E3 because it does not over-penalize unmatched true categories in the same way as GIE.
  • Overall findings: Across three datasets, flat measures often give a false indication of system quality by ignoring hierarchical dependencies, while hierarchical measures yield condition-dependent rankings.The experiments demonstrate that task scale and measure choice both require attention rather than identifying one universally best measure.

5 Conclusions

The paper organizes hierarchical evaluation measures into pair-based and set-based approaches, introduces generic frameworks and one new measure for each group, and compares them analytically and empirically. Across selected cases and three varied large datasets, the proposed measures generally behave more robustly, with FLCA usually preferable to MGIA, while combining their advantages remains open.

  • Pair-based measures match predictions to true classes and measure their distance, whereas set-based measures augment predicted and true label sets before applying set operations.
  • Flow networks provide the generic framework for pair-based measures, while set operations provide the framework for set-based measures.These frameworks present salient measure features under a common formalism.
  • Two new measures address several deficiencies of existing measures and are evaluated through selected cases and experiments on three large DMOZ- and Wikipedia-based datasets.The datasets vary by single-label versus multi-label settings and tree versus DAG hierarchies.
  • The analysis found that hierarchical measures behave differently, especially for multi-label data and DAG hierarchies, and that the proposed measures show more robust behavior than their counterparts.
  • In most cases FLCA exhibits more desirable behavior than MGIA, although a measure combining the advantages of both remains an open issue.Pair-based measures may behave more desirably in certain rare cases.
Loading 1306.6802v2…