Hierarchical Concept Embedding & Pursuit for Interpretable Image Classification

AI summary

Overview

Research area: Interpretable machine learning and computer vision, specifically interpretable-by-design image classification built on sparse concept recovery in vision-language model embedding spaces.

Technical level: Advanced. The paper combines a geometric embedding theory (cones, orthogonality, simplex constraints, necessary dimension conditions) with a hierarchical sparse-coding algorithm (a beam-search variant of Orthogonal Matching Pursuit), and evaluates both on synthetic and real-world data.

Scope: This one paper proposes a geometric framework for embedding concept hierarchies and a hierarchical sparse-coding pursuit algorithm (HCEP) for recovering concepts from image embeddings, and evaluates whether this improves concept precision/recall and classification accuracy relative to sparse and supervised interpretable baselines.

What This Paper Is About

Interpretable-by-design image classifiers recover human-interpretable concepts from an image and use only those concepts to classify it. Existing sparse concept recovery methods represent an image embedding as a sparse combination of concept embeddings, but they treat all concepts as unrelated atoms and ignore the fact that concepts form a hierarchy (for example, animal → mammal → cat).

The goal of this paper is to make concept recovery respect that hierarchy, so that a model recovers a rooted path of concepts in the hierarchy and produces explanations that are consistent with it, rather than selecting concepts such as vehicle for a cat image.

Key Contributions

1. Hierarchical Concept Embedding: A geometric framework for embedding a given hierarchy of semantic concepts, specifying two ideal properties — well-clustered synset embeddings (children cluster around their parent but sibling synsets remain separated) and hierarchical orthogonality (the child-parent difference vector is orthogonal to the parent embedding, and children differences form a simplex). The properties are analyzed theoretically and verified empirically in vision-language models.

2. Hierarchical Concept Pursuit: A concept recovery procedure that first builds a hierarchical dictionary from pre-trained vision-language embeddings by taking differences between parent and child synset embeddings, then uses hierarchical sparse coding (Hierarchical Beam OMP) to recover a rooted path in the hierarchy as the concept explanation.

3. Theoretical recovery conditions: Sufficient conditions under which the true concepts (assumed to form a rooted path) are recoverable in the embedding space, including a well-clustered cone condition guaranteeing unique parent assignment, a geometrically decreasing half-angle schedule that satisfies it, and a depth-branch-dimension necessity condition. The paper also states an informal proposition explaining why HB-OMP's selections are less likely than OMP's to introduce atoms outside the true hierarchical support.

4. Empirical validation with interpretable image classification: Experiments on synthetic data and on CIFAR-100, ImageNette, and ImageNet showing improvements in concept precision/recall over sparse recovery baselines at competitive classification accuracy, with larger gains in few-shot settings, plus a demonstration that a meaningful hierarchy can be induced with taxonomy induction methods for datasets without a predefined hierarchy.

Main Findings

• Standard sparse coding fails on hierarchical structure: The paper states that hierarchical sparse coding reliably recovers hierarchical concept embeddings whereas standard sparse coding fails, because standard OMP treats all dictionary columns equally and may select atoms that violate the hierarchy (for example, choosing both animal and vehicle at the same level).

• HB-OMP beats OMP on synthetic data: On synthetic data generated from the hierarchical concept embedding model (branching ratio b = 3, depth L = 7, dimension d = 50, which satisfies d = 50 ≥ 7 + 3 = 10), producing 2,187 leaf synsets, 3,280 atoms in the dictionary, and 10,935 samples (5 per leaf), HB-OMP consistently outperformed OMP in both precision and recall across varying noise levels and hierarchy depths.

• Improved support precision and recall on real datasets: Across ImageNet, CIFAR-100, and ImageNette, HB-OMP achieved higher support precision and recall than the other interpretable baselines, evaluated at sparsity level 5 for CIFAR-100 and 4 for ImageNette (matching the depth of the hierarchy) and at sparsity level 14 for ImageNet.

• Few-shot advantage: In the few-shot ImageNet setting, HCEP outperformed all interpretable baselines in both classification accuracy and support precision/recall. The paper attributes this to OMP and HB-OMP needing only to estimate synset embeddings by averaging image embeddings, whereas CBMs must learn a concept classifier from labels.

• Beam search helps with modest runtime cost: On ImageNet with 12-shot and sparsity level 14, increasing HCEP's beam width from 1 to 32 improved support precision with only a modest runtime overhead, enabled by parallelizing beam-search hypotheses on GPU.

• Geometry holds in pre-trained models: For CLIP image embeddings on ImageNet, most branches are tightly clustered and well separated from other branches (well-clustered synset condition), and the cosine similarity between child-parent difference vectors and their parent embeddings is close to zero, while random pairings have significantly higher cosine similarity — evidence that hierarchical orthogonality holds even in pre-trained models. The same orthogonality check is reported for CIFAR-100.

• Generalizes across vision-language models: Replacing CLIP with SigLIP on ImageNet yielded similar improvements in interpretability metrics.

• Handles large and DAG hierarchies: WordNet, used for ImageNet-based datasets, has L = 14 levels with branching ratios up to b = 25. The evaluation does not assume a unique root-to-leaf path — in DAG-structured hierarchies a synset may have multiple parents, and scores are computed against the closest among all valid root-to-leaf paths.

Methodology in Plain English

The approach starts from a concept hierarchy, such as WordNet. Each synset (a categorical concept grouping synonyms) is assigned a vector embedding, and the authors specify what a good hierarchy of embeddings should look like: children stay close in direction to their parent, siblings are far apart, and the difference between a child's embedding and its parent's embedding is perpendicular to the parent. They prove that a shrinking angle schedule across levels makes sibling subtrees disjoint and gives every node a unique parent, and that the embedding dimension must be at least the depth plus the branching ratio minus one (d ≥ L + b − 1) for the orthogonality and simplex conditions to be satisfiable.

For recovery, instead of using concept embeddings directly as dictionary atoms (which would make the trivial answer "cat" the sparsest explanation for a cat image), the authors build the dictionary from child-minus-parent difference vectors. A synset's embedding is then the telescoping sum of these differences along its root-to-node path, so recovering the concept means recovering a sparse code whose support is exactly the path.

Standard Orthogonal Matching Pursuit (OMP) picks the atom most aligned with the current residual at each step, ignoring hierarchy. The proposed Hierarchical Beam OMP restricts each step to children of the deepest node already selected, and keeps the top-B hypotheses ranked by residual norm so that an early mistake (for example, animal versus object) does not propagate to all lower explanations. Coefficient updates are least-squares re-fits, as in OMP.

In experiments, a class (leaf node) embedding is the average of that class's CLIP image embeddings, and non-leaf synset embeddings are the average of their children's embeddings; the dictionary is built once and kept fixed. Each image's CLIP embedding is converted by each method into an intermediate representation (a sparse code for OMP/HB-OMP, a 0/1 path code for hierarchical nearest neighbor, concept scores for CBMs), and a linear classifier is trained on those representations to predict labels. Baselines are OMP with the full dictionary, CBMs using supervised concept annotations, a nearest-neighbor classifier over class synset embeddings, and hierarchical nearest neighbor (HNN) that traverses the hierarchy level by level. Metrics are classification accuracy and support precision/recall. For CIFAR-100, which has no predefined hierarchy, the hierarchy is constructed with taxonomy induction methods.

Why This Matters

Impact on research. The paper argues that structured sparse coding is a scalable and flexible framework for interpretable machine learning, and it connects the geometric study of hierarchical concepts in large language models with hierarchical sparse coding, showing that hierarchy-aware dictionaries change what sparse recovery can guarantee. It also provides an alternative to concept bottleneck models that require costly concept annotations, since HCEP estimates synset embeddings by averaging pre-trained image embeddings while CBMs must learn a concept predictor from labels.

Real-world applications (as implied by the paper's setting and claims):

• Image classification systems where users need explanations consistent with a known category taxonomy rather than arbitrary attribute lists.
• Domains with scarce labeled data, where a few-shot interpretable classifier built on pre-trained vision-language embeddings is preferable to learning a concept predictor from annotations.
• Fine-grained recognition where distinguishing a specific synset from its parent (for example, polar bear from bear, described by attributes such as white fur) is the meaningful explanation.
• Settings that require scoring or auditing explanations against a taxonomy, since support precision and recall measure agreement with valid root-to-leaf paths.

Industry relevance. The reliance on pre-trained vision-language models (CLIP, and also SigLIP in a verification) means the method can be layered onto existing embedding infrastructure, and the reported GPU-parallel beam search with beam widths from 1 to 32 suggests a tunable accuracy-cost trade-off. The scalability claim rests on selecting a small number of concepts, with WordNet's 14 levels and branching ratios up to 25 used as a large-scale test.

Future Directions

• Extending the recovery guarantees beyond the assumption that the true concepts form a rooted path, including the DAG-structured and multi-parent cases the evaluation already accommodates.
• Reducing or bounding the runtime overhead of beam search further, given that the reported analysis only varies beam width from 1 to 32 at 12-shot and sparsity level 14.
• Broadening evaluation to additional vision-language models and datasets; the paper verifies CLIP and SigLIP on ImageNet and reports orthogonality checks on ImageNet and CIFAR-100.
• Improving hierarchy construction for datasets without a predefined taxonomy, where the paper relies on existing taxonomy induction methods.

Target Audience

Researchers and practitioners in interpretable machine learning and computer vision who work on interpretable-by-design classification, concept-based models, or sparse coding and dictionary learning. It is also relevant to readers interested in the geometry of representations in vision-language models, and to engineers who need faithful, taxonomy-consistent explanations for image classifiers in data-scarce settings. The theoretical sections on cone conditions, orthogonality, simplex structure, and the d ≥ L + b − 1 requirement assume comfort with linear algebra and sparse recovery.

Authors’ abstract

Interpretable-by-design models are gaining traction in computer vision because they provide faithful explanations for their predictions. In image classification, these models typically recover human-interpretable concepts from an image and use them for classification. Sparse concept recovery methods leverage the latent space of vision-language models to represent image embeddings as sparse combinations of concept embeddings. However, by ignoring the hierarchical structure of semantic concepts, these methods may produce correct predictions with explanations that are inconsistent with the hierarchy. In this work, we propose Hierarchical Concept Embedding & Pursuit (HCEP), a framework that induces a hierarchy of concept embeddings in the latent space and performs hierarchical sparse coding to recover the concepts present in an image. Given a hierarchy of semantic concepts, we introduce a geometric construction for the corresponding hierarchy of embeddings. Under the assumption that the true concepts form a rooted path in the hierarchy, we derive sufficient conditions for their recovery in the embedding space. We further show that hierarchical sparse coding reliably recovers hierarchical concept embeddings, whereas standard sparse coding fails. Experiments on real-world datasets show that HCEP improves concept precision and recall compared to existing methods while maintaining competitive classification accuracy. Moreover, when the number of samples available for concept estimation and classifier training is limited, HCEP achieves superior classification accuracy and concept recovery. Our results demonstrate that incorporating hierarchical structure into sparse concept recovery leads to more faithful and interpretable image classification models.