Evaluating Extreme Hierarchical Multi-label Classification (2022)

Abstract: Several natural language processing (NLP) tasks are defined as a classification problem in its most complex form: Multi-label Hierarchical Extreme classification, in which items may be associated with multiple classes from a set of thousands of possible classes organized in a hierarchy and with a highly unbalanced distribution both in terms of class frequency and the number of labels per item. We analyze the state of the art of evaluation metrics based on a set of formal properties and we define an information theoretic based metric inspired by the Information Contrast Model (ICM). Experiments on synthetic data and a case study on real data show the suitability of the ICM for such scenarios.

## introduction many natural language processing (nlp) problems involve classification, such as sentiment analysis, entity linking, etc. however, the adequacy of evaluation metrics is still an open problem. different metrics such as accuracy, f-measure or macro average accuracy (maac) may differ substantially, seriously affecting the system optimization process. for example, assigning all elements to the majority class may be very effective according to accuracy and score low according to maac. in addition, in many scenarios such as tagging in social networks @xcite or topic identification @xcite , the classifier must assign several labels to each item (multi-label classification). this greatly complicates the evaluation problem since, in addition to the class specificity (frequency), other variables appears such as the distribution of labels per item in the gold standard, the excess or absence of labels in the system output, etc. the evaluation problem becomes even more complicated if we consider hierarchical category structures, which are very common in nlp. for example, toxic messages are divided into different types of toxicity @xcite , named entities could be organized in nested categories @xcite , etc. in these scenarios, the category proximity in the hierarchical structure is an additional variable. even, the problem can be further complicated. extreme classification scenarios address with thousands of highly unbalanced categories @xcite , where a few categories are very frequent and others completely infrequent @xcite . in addition, some items have no category at all and some have many. an example scenario that we will use as a case study in this article is the labelling of adverse events in medical documents. in this paper, we analyse the state of the art on metrics for multi-label, hierarchical and extreme classification problems. we characterize existing metrics by means of a set of formal properties. the analysis shows that different metric families satisfy different properties, and that satisfying all of them at the same time is not straightforward. then, propose an information-theoretic based metric inspired by the information contrast model similarity measure (icm), which can be particularized to simpler scenarios (e.g. flat, single labeled) while keeping its formal properties. later, we define a set of five tests on synthetic data to compare empirically icm against existing metrics. finally, we explore a case study with real data which shows the suitability of icm for such extreme scenarios. the paper ends with some conclusions and future work. ## background in this section, we analyze the literature on the two main evaluation problems tackled in this paper: multi-labeling and class hierarchies, keeping the focus on extreme scenarios (numerous and unbalanced classes). ## formal properties in order to define the set of desirable properties, we formalize both the gold standard g and the system output s as sets of item/category assignments (i, c) ∈ i × c, where i and c represent the set of items and categories respectively. we will denote as p (c j ) the probability of items to be classified as c j in the gold standard (p ((i, c j ) ∈ g|@xmath0. we also assume that the categories in the hierarchical structure are subsumed. for instance, items in a person_named_entity category are implicitly labeled with the parent category named_entity. the common ancestor with maximum depth is denoted as lso(c 1 , c 2 ) and the descendant categories are denoted as desc(c) including itself. note that we do not claim that all properties are necessary in any scenario. the purpose of this article is to provide at least one metric that is capable of capturing all aspects simultaneously when necessary. the first property is related to hits. in order to make this aspect independent from the ability of the metrics to capture hierarchical relationships or multi-labeling, we define monotonicity over hits in the simplest case (flat single label scenario): property 1 [strict monotonicity] a hit increases effectiveness. given a flat single label category structure, if (i, c) ∈ g \s, then 3 eff(s∪{(i, c)}) > eff(s) the next two properties state that the specificity of both the predicted and the true category affects the metric score. that is, an error or a hit in an infrequent category should have more effect than in the majority category. for instance, identifying a rare symptom in a medical report should be rewarded more than identifying a common malady present in the vast majority of patients. in addition, both the specificity of the actual category and the specificity of the category predicted by the system must be taken into account. again, we make this aspect independent of hierarchical structures and multi-labeling. property 2 [true category specificity] given a flat single label category distribution, if p (c 1 ) < p (c 2 ) and (i, c 1 ), (i, c 2 ) ∈ g \ s, then eff(s ∪ {(i, c 1 )}) > eff(s ∪ {(i, c 2 )}). property 3 [wrong category specificity] given a flat single label category distribution, if p (c 1 ) the following property captures the effect of the hierarchical category structure. a common element of any hierarchical proximity measure is that it is monotonic with respect to the common ancestor. that is, our brother is always closer to us than our cousin, regardless of which family proximity criterion is applied.in this property we do not consider multi-labelling. property 4 [hierarchical proximity] under equiprobable categories (p (c 1 ) = p (c 2 ) = p (c 3 )), the deepness of the common ancestor affects similarity. given a single label hierarchical category structure, if s the last two properties are related with the multilabeling problem. property 5 rewards the amount of predicted categories per item. property 5 [multi-label monotonicity] the amount of predicted categories increases effectiveness. given a flat multi-label category structure, if (i, c) ∈ g \ s, then eff(s ∪ {(i, c)}) > eff(s) property 6 rewards hits on multiple items regarding a single item with multiple categories. to understand the motivation for this property, we can consider an extreme case. identifying 1000 symptoms in one patient report is of less health benefit than identifying one symptom in 1000 patients. property 6 [label vs. item quantity] n hits on different items are more beneficial than n labels assigned to one item. given a flat multi-label category distribution, if ∀@xmath1..n((j, c j ) ∈ g \ s) and ∀@xmath2..n, @xmath3, c j ) ∈ g \ s) then eff(s ∪ {(1, c 1 ), .., (n, c n )}) > eff(s ∪ {(i, c 1 ), .., (i, c n )}). ## metric analysis in this section, we analyze existing metrics on the basis of the proposed formal properties ( ## information contrast model the information contrast model (icm) is a similarity measure that unifies measures based on both object feature sets and information theory @xcite . given two feature sets a and b, icm is computed as: where ic(a) represents the information content (-log(p (a)) of the feature set a. in our scenario, objects are items to be classified and features are categories. the intuition is that the more the category sets are unlikely to occur simultaneously (large ic(a ∪ b)), the less they are similar. given a fixed joint ic, the more the category sets are specific (ic(a) and ic(b)), the more they are similar. icm is grounded on similarity axioms supported by the literature in both information access and cognitive sciences. in addition, it generalizes the pointwise mutual information and the tversky's linear contrast model @xcite . ## experiments on synthetic data different evaluation aspects such as error rate, category specificity, hierarchical structures, etc., may have more or less weight depending on the scenario. these aspects correspond to the formal properties defined in the previous section. we perform a set of tests in order to quantify the suitability of metrics with respect to each property or evaluation aspect. first, we generate the following synthetic data set. first, we definea hierarchical structure structure of 700 categories exposed in figure 1 . note that categories {1..10} are parent categories spread throughout the hierarchy, and categories {11..700} are leaf categories. secondly, we distributed 100 items across all categories. we generate assignments for each pair item/category (i, c) with a probability of p i • p c where p @xmath4, 1 2225 with @xmath5..1000 and p @xmath6,1) 1713 where @xmath7..700. we repeat this 1000 times. the result is a distribution (300, 150, 40, .., 0.6, 0.6) items per category and (22.5, 22, 21.6, 21.1, ..., 0.5, 0.5) labels per item. the purpose is to ensure unbalanced assignments across items and classes. we generate 1000 gold standards by reordering the category identifiers c each time in the p c computation in order to alter the distribution of items in the hierarchical structure. we consider in this experiment the metrics labelbased accuracy and f-measure (lb-acc and lb-f), the example-based metrics hamming (eb-hamm), jaccard (eb-jacc), subset accuracy (eb-subacc), f-measure (eb-f) and propensity f-measure (prop-f), the hierarchical f-measure (hf) and icm. the ontological similarity metrics are discarded given that they are not defined for the multi-label case. ranking based metrics are discarded as the synthetic data set does not include graded assignments. after this, we perform the following tests by comparing two noisy versions of the gold standard. the test result is the percentage of cases in which the hypothetically worse noised output is outscored by the best noised output ( in the first experiment referred in the second experiment is the true category specificity test. the intuition is that a gap in a frequent category should have less effect than a gap in an infrequent category. with an error rate of 0.05, for the best output, we remove a single label assignment randomly selected from all the goldstandard. for the worst output, we first select randomly a category and then we remove an assignment from this category. the result is that the best output tends to concentrate the gaps in frequent categories to a greater extent than the worst output. at the table shows, the metrics that satisfy the corresponding property achieve high scores (lb-f, prop-f and icm). the third experiment is the wrong category specificity test. the intuition is that a wrong assignment in a frequent category should have less effect than a wrong assignment in an infrequent category. with an error rate of 0.05, we select an assignment (i, c) randomly from items with a single label. for the best output we replace c with the most frequent class different than c. for the worst output, we replace c with a randomly selected category different than c. we obtain the same result than in the previous experiment. the fourth experiment is the hierarchical similarity test. the intuition is that the more a wrong assignment is far away from the correct category, the more it has effect in the effectiveness score. again, with an error rate of 0.05, we select an assignment (i, c) randomly from single labeled items with leaf categories. for the best output we replace c with a sister wrong category. for the worst output, we replace c with a randomly selected wrong category. again, the metrics that satisfy the corresponding property achieve high scores. the last test is item specificity. the intuition is that a wrong assignment in an item with many labels should have more effect than an error in an item with one or a few labels. for the best output, for each error insertion iteration, we randomly select an assignment (i, c) (with the same error rate 0.05). for the worst output, we randomly select an item i, and we take one of its assignments (i, c). in both cases, the category is replaced with a randomly selected wrong label. in other words, we distribute errors uniformly across item/category assignments in the best output and we distribute errors uniformly across items in the worst output. the effect is that the best output concentrates errors in items with many labels. again, those metrics that satisfy the corresponding metric achieve high performance. the label-based f-measure tends to reward the worst output. the reason is that items with many labels tend to concentrate diverse labels. therefore, the label-based f measure penalizes the best output. as discussed in the previous section, although icm does not satisfy the property, the hit gain on items with many categories is smoothed out if the categories are related to each other by a hierarchical structure. ## a case study the problem addressed is the automatic encoding of discharge reports @xcite ) from a spanish hospital to detect adverse events (aes) from cie-10-es foot_4 , the spanish version of the tenth revision of the international classification of diseases (icd-10). aes detection fits to the scenario tackled in this article due to the following reasons: (i) extreme: cie-10-es contains 4816 codes related to aes, which probability follows a power-law distribution since most of them rarely appear in health records or even they do not appear; (ii) hierarchical: cie-10-es is a hierarchy with six levels: an empty root (c ∅ such that ic(c ∅ ) = 0), and then a level composed by three-character-codes categories which can be divided into successive nested subcategories adding characters until seven-character-codes at most; and (iii) multi-label classification: each discharge report could have associated with several aes codes. we have used a corpus composed of 36264 real anonymized discharge reports @xcite annotated with aes codes by experts. the corpus has been divided into three data sets, training, development and test, following the proportion 50%-30%-20% respectively. the corpus includes only 671 aes codes of 4816 and 84% of the discharge reports have no aes, so the data is highly biased and unbalanced. we have applied five simple baselines in order to analyze the behaviour of the metrics: (i) all none does not assign any code to each item; (ii) most freq. assigns the most frequent ae code in the training data set (t45.1x5a) to each item, which just appears in 68 items of 7253; (iii) match 75% divides each item into sentences and assigns a code if a sentence contains 75% of the words of the code description avoiding stop-words; (iv) svm descr. creates a binary classifier for each ae code in the training set using the presence of words of the aes codes descriptions in the items as features, excepting stop-words; (v) svm codes: similar to the previous one but using as features the annotated non-aes codes in order to check if aes codes are related to non-aes codes. note that match 75% is able to assign any ae, but the svm baselines are only able to assign aes appearing in the training data set. ## conclusions and future work the definition of evaluation metrics is an open problem for extreme hierarchical multi-label classification scenarios due to the role of several variables, for instance, a huge number of labels, unbalanced and biased label and item distributions, proximity between classes into the hierarchy, etc. our formal analysis shows that metrics from different families (label, example, set-based, ontological similarity measures etc.) satisfy different proper-ties and capture different evaluation aspects. the information-theoretic metric icm proposed in this paper, combines strengths from different families. just like example-based multi-label metrics, it computes scores by items. just like set-based metrics, it compares hierarchical category sets. just like some ontological similarity measures (lin or jiang and conrath), it considers the specificity of categories in terms of information content. our experiments using synthetic and real data show the suitability of icm with respect to existing metrics. icm does not strictly hold the label vs. item quantity property. we propose to adapt icm in order to guarantee all the formal properties as future work.