Hierarchical Concept Embedding & Pursuit for Interpretable Image Classification

1. Problem Statement

Current interpretable-by-design models in computer vision aim to make predictions based on human-interpretable concepts (e.g., "furry," "mammal," "cat") rather than raw pixel features. While sparse concept recovery methods (using vision-language models like CLIP) have shown promise by representing image embeddings as sparse linear combinations of concept embeddings, they suffer from a critical flaw: they ignore the hierarchical structure of concepts.

• The Issue: Semantic concepts naturally form hierarchies (e.g., Animal $\to$ Mammal $\to$ Cat). Existing sparse coding methods treat concepts as independent atoms. Consequently, they may recover a set of concepts that are semantically inconsistent with the hierarchy (e.g., predicting "Vehicle" and "Cat" simultaneously for an image of a cat), leading to unfaithful explanations and potential classification errors.
• The Goal: Develop a framework that enforces hierarchical consistency during concept recovery, ensuring that the identified concepts form a valid rooted path in the semantic hierarchy (e.g., Root $\to$ Animal $\to$ Mammal $\to$ Cat).

2. Methodology: HCEP Framework

The authors propose Hierarchical Concept Embedding & Pursuit (HCEP), which consists of two main components: a geometric embedding model and a hierarchical pursuit algorithm.

A. Hierarchical Concept Embedding Model

The authors define specific geometric conditions that concept embeddings must satisfy to ensure identifiability and hierarchical consistency within a vector space (e.g., CLIP's embedding space).

1. Well-Clustered Synsets:

   • Sibling Separation: Embeddings of sibling nodes (e.g., Dog and Cat) must be well-separated to be distinguishable.
   • Parent Clustering: Sibling nodes must cluster around their parent node (e.g., Dog and Cat are close to Mammal).
   • Geometric Constraint: This is formalized using cone containment. The subtree of any node must lie within a cone centered at the parent, and sibling cones must be disjoint. This requires the embedding angles to decrease geometrically as depth increases.

2. Hierarchical Orthogonality & Simplex Structure:

   • Orthogonality: The vector difference between a child and its parent (representing the specific concept distinguishing them, e.g., "has fur" vs. "has feathers") must be orthogonal to the parent's embedding vector. This ensures that adding a child-specific feature does not alter the parent's semantic meaning.
   • Simplex Structure: The difference vectors of a parent's $b$ children must form a regular $(b-1)$-simplex. This ensures that the children are conditionally independent given the parent.
   • Dimensionality Requirement: Theoretically, for a hierarchy of depth $L$ and branching factor $b$, the embedding dimension $d$ must satisfy $d \ge L + b$. The authors verify that standard models like CLIP ($d=768$) easily satisfy this for real-world hierarchies (e.g., WordNet).

B. Hierarchical Dictionary Construction

Instead of using raw concept embeddings as dictionary atoms, HCEP constructs a dictionary based on synset differences:
$$D = \{ a(j) - a(\text{par}(j)) \mid j \in \text{Nodes} \}$$

• The atom for a root child is just its embedding.
• The atom for a deeper node is the difference between the node and its parent.
• An image embedding $x$ is reconstructed as a sparse sum of atoms along the path from the root to the target leaf.

C. Hierarchical Concept Pursuit (Algorithm)

To recover the sparse representation, the authors propose Hierarchical Orthogonal Matching Pursuit (H-OMP) with Beam Search:

1. Top-Down Search: Unlike standard OMP which searches the entire dictionary, H-OMP starts at the root and iteratively selects the best child node.
2. Beam Search: To avoid greedy errors (where an early wrong choice leads to a dead end), the algorithm maintains a "beam" of $B$ candidate hypotheses (paths) at each level.
3. Extension: At each step, it extends the active dictionary only with the children of the currently selected nodes.
4. Pruning: The beam is pruned based on the residual error, keeping the top $B$ most promising paths.

3. Key Contributions

1. Geometric Framework: Theoretical derivation of necessary geometric conditions (cone containment, orthogonality, simplex structure) for hierarchical concept embeddings to be identifiable.
2. HCEP Algorithm: A novel sparse coding algorithm (H-OMP) that leverages these geometric properties and beam search to recover hierarchical paths rather than arbitrary concept sets.
3. Theoretical Guarantees: Proof that H-OMP has a strictly larger Exact Recovery Condition (ERC) success region compared to standard OMP on the full dictionary, meaning it is more robust to noise and dictionary coherence issues.
4. Empirical Validation: Demonstration that these geometric properties hold in pre-trained vision-language models (CLIP, SigLIP) on real-world datasets.

4. Experimental Results

The authors evaluated HCEP on ImageNette, ImageNet, and CIFAR-100.

• Concept Recovery (Precision & Recall):
  • HCEP significantly outperforms baselines (Standard OMP, Concept Bottleneck Models, Nearest Neighbor) in recovering the correct hierarchical path (support precision/recall).
  • Standard OMP often recovers concepts that are semantically inconsistent (e.g., mixing branches), whereas HCEP enforces path consistency.
• Classification Accuracy:
  • HCEP maintains competitive classification accuracy compared to black-box baselines and other interpretable models.
  • Few-Shot Performance: In low-data regimes (e.g., 12-shot or 25-shot settings), HCEP achieves superior classification accuracy compared to all baselines, demonstrating that hierarchical constraints act as a strong regularizer.
• Robustness: The method generalizes across different vision-language backbones (CLIP and SigLIP).
• Runtime: While beam search adds complexity, parallelization on GPUs keeps the runtime overhead modest compared to the gains in interpretability.

5. Significance and Impact

• Faithful Interpretability: HCEP addresses the "faithfulness" gap in interpretable AI. By ensuring explanations follow a logical semantic hierarchy, the model's reasoning aligns with human understanding of the world.
• Data Efficiency: The hierarchical structure provides strong inductive bias, allowing the model to learn effectively with very few labeled examples, a critical advantage in data-scarce domains.
• Scalability: The framework works with existing pre-trained models (like CLIP) without requiring expensive retraining or fine-tuning of the backbone, making it a practical solution for deploying interpretable systems.
• Theoretical Foundation: It bridges the gap between sparse coding theory and the geometric properties of large language/vision models, offering a blueprint for how to structure latent spaces for hierarchical reasoning.

In conclusion, HCEP demonstrates that incorporating hierarchical structure into sparse coding is not just a heuristic improvement but a theoretically grounded necessity for building reliable, interpretable, and data-efficient image classification models.