Bottom-up Hierarchical Classification
Using Confusion-based Logit Compression

A generalized logit [6] is a derived logit for an aggregation of terminal label logits from a flat classifier. It assumes the softmax value of a Super-class label is the sum of softmax values of its terminal descendant labels in the label hierarchy. For instance, a terminal label set $C=\{bird,dog,fish,cat,truck,car\}$ with a Super-class Vehicle consisting of terminal labels truck and car has a softmax value $s_{Vehicle}=s_{truck}+s_{car}=\sum_{i\in\{\textit{truck},\textit{car}\}}s_{i}$. Expanding $S_{Vehicle}$ based on the logit-softmax relationship, we acquire

where $l$ denotes the logit of a terminal label and $\hat{l}$ denotes the generalized logit of a Super-class label. The generalized logit relationship between the Super-class Vehicle and its children is given by $e^{\hat{l}_{\textit{Vehicle}}}=\sum_{i\in\{\textit{truck},\textit{car}\}}e^{l_{i}}$. Therefore, the corresponding logit value of the non-terminal label Vehicle can be derived by $\hat{l}_{\textit{Vehicle}}=ln(e^{\hat{l}_{\textit{Vehicle}}})=ln(\sum_{i\in\{\textit{truck},\textit{car}\}}e^{l_{i}})$. In this work, we will adopt this generalized logit formulation to acquire the logit value corresponding to a subset of terminal labels that are least confusing with the argmax predicted label.

Unlike data-driven compression techniques that are usually designed to compress large amounts of data, we are motivated to compress the logit vector due to a lack of validation data but large logit dimensionality. We propose to construct a subset of labels (to be compressed) using the confusion matrix of the base classifier $f$ evaluated on the validation set. For a given predicted label, we aggregate the logit values of its least confused labels (not including the ground truth label) and compress them into a single generalized logit. The intuition is that logit values of the least confusing labels carry little information for posterior estimation. Furthermore, logit values preserve more residual confusion information than the exponential operation with softmax which ‘squashes’ the probability mass of non-argmax selected classes close to 0.

The columns in the confusion matrix $M$ of $f$ correspond to the predicted labels, and the rows in $M$ are the associated ground truth labels. The aggregation procedure takes $M_{i}$, the $i^{th}$ column of $M$ corresponding to predicted label $i$, and a given compression level $c$ ($1\leq c\leq|C|$) as input, and outputs $Q^{c}_{i}$, a list containing the ground truth label, the $(c-2)$ most confusing labels, and the single subset of the remaining least confusing labels (for label $i$). For a real application scenario, proper selection of compression level $c$ can be achieved via cross validation using the validation set (see Sect. 4.5).

To acquire $Q^{c}_{i}$, we first apply stable-sort (retains the order of ties) to the column vector $M_{i}$ in descending order while tracking the corresponding labels (i.e., ground truth row indices in $M_{i}$). Then, we set $Q^{c}_{i}$ to include the first $(c-1)$ individual labels in the sorted list (ground truth label and most confusing labels for class $i$). Finally, we aggregate the remaining labels (the ‘tail’ labels whose logits are to be compressed into a single generalized logit) into one set and append it to $Q^{c}_{i}$. Employing this procedure for each column in $M$, we acquire $Q^{c}$.

For a given example $x$ and its corresponding logit vector $L_{x}$$=$$f(x)$, the initial label hypothesis is given by $\hat{y}$$=$$argmax(L_{x})$. We then select $Q^{c}_{\hat{y}}$ from $Q^{c}$ and use the generalized logit formulation to compress the appropriate least confusing labels. For example, if $C=\{\textit{bird},\textit{dog},\textit{fish},\textit{cat},\textit{truck},\textit{car}\}$ and $\hat{y}=\textit{dog}$, then perhaps $Q^{c}[\hat{y}]$ $=$ $Q^{c}_{dog}$ $=$$\{dog,cat,\{bird,fish,truck,car\}\}$ with $c$ $=$ $3$. The initial logit vector $L_{x}$ $=$ $[l_{\textit{bird}},l_{\textit{dog}},l_{\textit{fish}},l_{\textit{cat}},l_{\textit{truck}},l_{\textit{car}}]$ would be compressed to $L^{Q^{c}_{\textit{dog}}}_{x}$ $=$ $[l_{\textit{dog}},l_{\textit{cat}},\hat{l}_{\{\textit{bird},\textit{fish},\textit{truck},\textit{car}\}}]$, reducing the dimensionality from 6 to 3. The compressed logit vector $L^{Q^{c}_{\textit{dog}}}_{x}$ will be used in label posterior estimation and inference for the examples initially classified as dog by base classifier.

For the label posterior estimation process, we only need to estimate the posteriors of the terminal labels conditioned on the associated compressed logit vector. The posterior of any Super-class can be acquired by summing over the posteriors of its associated terminal descendants.

The posterior estimator $\hat{p}_{j|i}$ approximates the conditional probability $P(y=j|\hat{y}=i,L^{Q^{c}_{i}}_{x})$, where $y=j$ denotes the ground truth of example $x$ to be label $j$, $\hat{y}=i$ denotes the argmax-selected base prediction for $x$ to be label $i$, and $L^{Q^{c}_{i}}_{x}$ is the compressed logit vector with dimension of $c$ computed from $L_{x}$. The posterior estimator $\hat{p}_{j|i}$ for any $i,j\in C$ in the algorithm is modeled independently with a logistic sigmoid function given by

where $W_{j|i}\in\rm I\!R^{c}$ and $B_{j|i}\in\rm I\!R$ denote the parameters for the posterior estimator. To estimate $W_{j|i}$ and $B_{j|i}$, we employed logistic regression with the Limit-memory Broyden-Fletcher-Goldfarb-Shanno algorithm (L-BFGS-B) [27].

During posterior estimation, each terminal label $i$ is assigned its own subset $V_{i}$ of the validation set $V$ based on the initial argmax predictions from the base classifier on $V$, i.e., $V_{i}=\{x\>|\>i=argmax(L_{x})\>and\>L_{x}\in V\}$. This argmax-selected validation subset inherently captures the confusing examples directly for the posterior estimation process. A set of posterior estimators for all terminal labels ($\forall j\in C$) conditioned on the same base prediction $i$ is trained with the same subset of validation data $V_{i}$ using the ground truth indicating whether the example actually belongs to the associated label ($j$). This is done for all combinations of terminal label posteriors ($\forall j\in C$) that are conditioned on any possible initial base prediction ($\forall i\in C$), leading to a total of $|C|\times|C|$ posterior estimators. In the unlikely case of $V_{i}=\emptyset$, the base classifier’s terminal softmax output can be used for the label posteriors.

For inference with test example $x$, we acquire the original logit vector from the base classifier $L_{x}=f(x)$ and use its base prediction label $\hat{y}=argmax(L_{x})$ to retrieve the label aggregation result $Q^{c}_{\hat{y}}$. Next, we compress its logit vector from $L_{x}$ to $L^{Q^{c}_{\hat{y}}}_{x}$. Lastly, the estimated terminal label posterior value $\hat{p}_{i}$ for any terminal label $i\in C$ (previously learned using validation set $V_{\hat{y}}$) is given by

The L1-normalization is used to ensure no numerical imprecision and the probabilities across the terminal labels sum to 1. At this point we could either return the terminal label with the largest posterior (flat classification) or perform hierarchical inference.

The proposed hierarchical inference approach starts with checking if $\hat{p}_{\hat{y}}$ surpasses the given confidence threshold $T$. If so, $\hat{y}$ is returned as the prediction result along with $\hat{p}_{\hat{y}}$. Otherwise, we set our label hypothesis to the parent label of $\hat{y}$ using the semantic label hierarchy $H$. We compute the label posterior of the non-terminal label hypothesis via summation of its associated terminal descendant posteriors and check if this posterior surpasses the confidence threshold. This upward label generalization process is repeated until we find a label on the ancestral path of $\hat{y}$ with its posterior $\geq$ $T$. As the label posterior of any non-terminal label is computed from the summation of its L1-normalized terminal descendant posteriors, monotonic non-decreasing posterior inference behavior upward through the hierarchy is ensured (not guaranteed in [5]). The overall hierarchical classification approach is provided in Algorithm 1.

We seek to evaluate our approach on different sizes of the validation set to examine its robustness against fewer examples. For CINIC-10, we randomly shuffled the original validation set $V$ in a class-wise manner and then split it into eight validation sets ($V^{i},i=1,..,8$) with reducing sizes of 9K (original size), 5K, 1K, 500, 250, 100, 50, and 25 validation examples per label. Similar shuffling and splitting was applied to the validation set of Places-20 to acquire validation sets with reducing sizes of 10K (original size), 5K, 1K, 500, 250, 100, 50, and 25 validation examples per label.

We compared our logit compression approach with the following alternative compression methods:

• •

  Global PCA compression. A global PCA transformation using all of the logit data from a given validation set is computed. Logit vectors are then compressed (projected) to the specified dimensionality (i.e., using the principal components retained).

• •

  Local PCA compression. A local PCA transformation is associated with each terminal label $i\in C$ and computed using the validation examples initially predicted as the terminal label $i$. The base prediction for any new input is used to index the corresponding local PCA transformation for logit compression to the specified dimensionality.

• •

  Tree-based compression. The tree-based logit compression method proposed by [6] reduces the original logit vector to a smaller set containing logits of the base prediction label and (generalized) logits of labels corresponding to the upper side nodes/labels branching out from the ancestral path of the base prediction. The compressed logit vector size is dependant on both the given tree structure and the associated base prediction.

For all compression methods, we used the same label posterior estimation and hierarchical classification procedures introduced in Sect. 3.3-3.4.

We employed the bottom-up hierarchical evaluation metrics from [5, 6] that focus on the two resulting subsets from test examples that were either correctly ($S_{c}$) or incorrectly ($S_{ic}$) classified by the base classifier $f$ and also a measure that correlates with their label depth in the tree:

• •

  C-persist, C-corrupt, C-withdrawn are the fractions of the correct base predictions ($S_{c}$) that are unchanged as terminal labels, corrupted to incorrect predictions, or assigned to the whole set of terminal labels $C$ (i.e., the root Unknown), respectively. Unlike [8], our hierarchical classification approach does not corrupt any base predictions (C-corrupt = 0). C-soft is the remaining fraction in $S_{c}$ being generalized to a non-root Super-class that has the ground truth label as a descendant.

• •

  IC-persist and IC-withdrawn are similar to C-persist and C-withdrawn but for the incorrect base predictions ($S_{ic}$). IC-reform is the fraction of base predictions in $S_{ic}$ that are generalized to a correct non-root label. IC-remain is the remaining fraction of examples in $S_{ic}$ being generalized to a non-root Super-class that does not have the ground truth as a descendant.

• •

  Avg-sIG is the average scaled Information Gain, adapted from [8]’s metric of Information Gain (IG). Scaled Information Gain (sIG) is IG normalized with the maximum possible IG for a given terminal label set, and Avg-sIG is the average sIG across all test examples and correlates with the average label depth. Avg-sIG is given by

  $$\text{Avg-sIG}=\frac{1}{|S|}\sum_{x\in S}\frac{log_{2}|C|-log_{2}|y|}{log_{2}|C|}\mathbbm{1}_{\{t_{x}\in y\}}$$

  (5)

  where $y$ is the final prediction of input $x$, $|y|$ is the number of terminal descendants of $y$, $t_{x}$ is the ground truth of test example $x$, $S=S_{c}\cup S_{ic}$, and $\mathbbm{1}_{\{.\}}$ is the indicator function. An incorrect prediction has Information Gain of 0, as defined in [8].

We adopted the Technique of Order Preference Similarity to the Ideal Solution (TOPSIS) [11] as an overall evaluation metric that unifies the 9 individual hierarchical metrics for the comparison across alternative approaches. TOPSIS is a commonly used metric for multiple criteria decision analysis. It treats the multi-criteria evaluation results (e.g., the 9 hierarchical metrics listed above) of an approach as vector $a$ and computes the L2-distance to the best alternative ($b$) and worst alternative ($w$) vectors. The final TOPSIS score for $a$ ranges from zero to one (larger is better) and is given by

where $d_{ab}$ and $d_{aw}$ are the L2-distances from $a$ to the best ($b$) and worst ($w$) alternatives, respectively.

For the best case scenario ($b$), C-persist = IC-reform = Avg-sIG = 1, and the remaining criteria/metrics are 0. For the worst case scenario ($w$), C-corrupt = IC-persist = 1, and the remaining criteria are 0. We note that the metric/criterion values are typically rescaled in the range between 0 and 1 and can be weighted before computing the L2-distances. Our hierarchical metrics are naturally defined within the same range and are treated equally.

Lastly, we evaluated the calibration quality of the estimated label posteriors with Expected Calibration Error (ECE) [17], as the inference approach is highly dependent on the label posteriors. ECE is a scalar statistical summary of the quality of the estimated label posteriors. This is evaluated through histogram binning of the posterior values and comparing the average of the estimated label posteriors in each bin to the associated precision of the hierarchical predictions in the bin. Since our hierarchical predictions are acquired under a given confidence threshold, we apply the histogram binning for ECE on the probability range between the confidence threshold $T$ and 1 (with 10 bins), and it is only applied to predictions that are not withdrawn/generalized to the root of the hierarchy (which always has posterior of 1). Lower values of this metric are preferred.

We compared the results on CINIC-10 and Places-20 under various compression techniques with decreasing sizes of the validation set and report the TOPSIS and ECE scores of each method using the confidence threshold $T=0.9$. We show the TOPSIS and ECE scores of each method that corresponded to the compression level giving the best TOPSIS results (ranging from 1 to 10). To automatically select the compression level in an application scenario, cross validation could be used (to be demonstrated in Sect. 4.5). We note that the tree-based compression method does not support different choices of compression level, as it is specified by the tree itself.

The comparison results for experiments on CINIC-10 and Places-20 are shown in Fig. 2. The left y-axis of each subplot denotes the TOPSIS score (red), and the right y-axis denotes the associated ECE score (blue). The x-axis of each subplot denotes the size of the validation set used to acquire the associated TOPSIS and ECE scores. Axes of all subplots are given in the same range to make it easier for visual comparison. We only show the results derived from the smaller validation sets ($V^{3}$ – $V^{8}$) since all methods stabilized with any further increase of the validation data.

Notably, the results for TOPSIS and ECE derived from our proposed compression method and the tree-based compression approach are better than both PCA-based approaches when the validation set is small (i.e., 25, 50, 100 examples per label). The results of our method is better than the tree-based approach on CINIC-10 and on par with it for Places-20. This suggests that our compression approach derived from the confusion matrix of the base classifier is comparable to the tree-based compression approach that has injected knowledge of the semantic label relationships. Both methods employ extra knowledge (classifier confusions or label semantics) and have better performance than pure data driven PCA-based approaches when the validation set is small. Our method reached the highest TOPSIS score before saturation among the methods. Similar saturation is also observed for the ECE scores, where the tree-based compression method first reached saturation, with the lowest ECE score, followed closely by our compression approach. However, our method had the best ECE score for the smallest validation set in CINIC-10.

Since all four methods in the comparison rely on a given semantic hierarchy for their hierarchical classification, we next conducted experiments with the same settings but randomly corrupted the semantic hierarchies to study the influence of the tree itself. We applied a random shuffling of the terminal label positions only within each hierarchy while keeping the tree structure fixed. The results for 3 random terminal shufflings of the hierarchy for Places-20 are shown in Fig. 3. Comparing the results from the original label tree with the shuffled trees, the semantic information of the label relationships provided by the hierarchy does indeed play an important role in hierarchical classification, as degraded performance for all methods is present if an improper tree is used. Notably, the ECE scores for our approach and the tree-based method are still better than the PCA-based approaches for smaller validation sets. Similar results were seen with shuffled trees on CINIC-10.

A similar comparative experiment among these methods without the use of a hierarchy was also conducted. The tree-based compression approach is not applicable here due to its requirement of a tree, so it is excluded from this comparison. We employed a basic label generalization method that takes the estimated label posteriors of all terminal labels and sorts them in descending order, then sums the sorted posteriors until reaching the given confidence threshold $T$. The set of aggregated terminal labels is then output as a (generalized) hierarchical prediction (i.e., a subset of terminal labels in $C$). Our evaluation metrics are still applicable to these set-based predictions. The results on CINIC-10 and Places-20 are shown in Fig. 4. Comparing results to Fig. 2, the TOPSIS and ECE scores for each approach without using a tree are worse for smaller validation sets, though the proposed approach is again better than the PCA methods. Additionally, the TOPSIS scores do not saturate as much as before (when employing a tree for inference).

We conducted an ablation study on the influence of the proposed confusion-based compression approach by comparing the associated hierarchical classification performance with and without the proposed compression method on CINIC-10 when the validation set is small (i.e., 25, 50, 100, and 250 examples per label). For the proposed approach, we show its best and worst TOPSIS scores across compression levels ranging from 1 to 9 in Table 1. In comparison, we also show the TOPSIS score of hierarchical classification using the original logit features with no compression. The results clearly show that the proposed compression approach improves the hierarchical classification performance significantly in comparison with using the original logits without compression. The results also indicate that a smaller validation set will likely require a smaller compression level to reach better performance.

We next compared our proposed framework against the related bottom-up hierarchical classification methods of [8], [5], and [6] (described in Sect. 2) under the same confidence threshold $T=0.9$. The experiments were conducted on Fashion-MNIST [23] (10 terminal labels), CIFAR-100 [13] (100 terminal labels), and ImageNet-Animal [5] (398 terminal labels) with increasing scale of the dataset and the related label hierarchy (provided in [6]). We applied a similar random partitioning on the original test sets of Fashion-MNIST and CIFAR-100 to obtain the associated validation and test sets. The validation and test sets for ImageNet-Animal were acquired by class-wise random 1:1 partition of the original validation set, since no test set is given. The validation sets of all three datasets were balanced with 500, 50, and 25 validation examples per terminal label for Fashion-MNIST, CIFAR-100, and ImageNet-Animal, respectively. A model based on VGGNet [20] was used for Fashion-MNIST, a ResNeXt model [24] was trained and used for CIFAR-100, and a pretrained ResNet-152 model [10] was employed as the base classifier for ImageNet-Animal.

For [8], the single logit feature of each label from the base (CNN) classifier was used to produce the hierarchical predictions instead of logits of SVMs used in the original work. For [5], we employed the setting of 10 histogram bins per label. To automatically determine the proper compression level for our method on each dataset, we applied class-wise Leave-One-Out Cross Validation (LOOCV) on each validation set. The search range was from 1 to the minimum of $|C|$ and the number of validation examples per label. The compression level that led to the highest TOPSIS score for each dataset was 5, 9, and 12 for Fashion-MNIST, CIFAR-100, and ImageNet-Animal, respectively. These compression levels were employed by our approach to produce the final hierarchical classification results.

The TOPSIS scores corresponding to each method are shown in Table 2, where ‘Base’ refers to the flat classification results of the associated base classifiers. The performance of our proposed approach reached the highest TOPSIS scores on all 3 datasets. Across the datasets, as the number of validation examples reduced (Fashion-MNIST $>$ CIFAR-100 $>$ ImageNet-Animal), the number of terminal labels increased. With this inverse relationship, the condition for posterior estimation is worsening. However, our proposed approach demonstrated robustness in each case.

The non-parametric histogram binning approach [5] demonstrated good performance closest to our proposed method across the datasets, though monotonicity of label posteriors along the hierarchy is not guaranteed in this approach. The lower performance of [8] was due to its consistently high IC-persist, indicating that more of the original misclassifications made by the base classifier were not corrected in their hierarchical process. The lower TOPSIS scores of the tree-based compression approach [6] on CIFAR-100 and ImageNet-Animal were due to a higher overall label generalization during inference (i.e., high C-soft and corresponding low Avg-sIG). We found that using argmax-selected validation data (as employed in the proposed approach) for [6] would significantly improve its performance, though [6] still requires the use of a specified hierarchy for both compression and inference, unlike the proposed approach.