Expanding Data-Agnostic Pivotal Instances Selection Models with Proximity Trees and Ensemble Learning

Technical Summary: Expanding Data-Agnostic Pivotal Instances Selection Models with Proximity Trees and Ensemble Learning

Problem Statement
Machine learning models have become essential for complex decision-making in domains such as healthcare and finance, yet their "black-box" nature often hinders interpretability. While humans naturally reason by comparing new cases to representative examples (case-based reasoning), many existing interpretable models rely on abstract feature-based rules that do not align with this cognitive process. Furthermore, current instance-based approaches often struggle with data modalities where features lack clear semantic meaning (e.g., images, text, time series) or fail to balance predictive performance with the number of representative instances (pivots) required for explanation. The paper addresses the need for a unified, data-agnostic framework that selects high-quality pivotal instances to construct interpretable predictive models capable of reasoning through similarity.

Methodology
The authors propose PivotTree, a hierarchical, interpretable-by-design model inspired by decision trees but grounded in similarity to selected pivots rather than feature thresholds. The methodology encompasses three main components:

1. Pivot Selection and Tree Induction:
   PivotTree greedily constructs a decision tree where each node splits instances based on their similarity to specific "pivots" (representative training instances). The algorithm identifies two types of pivots at each step:

   • Discriminative Pivots: Instances that maximize impurity gain when partitioning the data based on similarity.
   • Descriptive Pivots: Instances that maximize similarity to other instances of the same class within the current node.
     The tree induction process encodes instances into a similarity space relative to these pivots, allowing the model to function as both a pivot selector and a standalone predictive model.

2. Splitting Strategies:
   To enhance expressivity and adaptability, PivotTree implements three distinct splitting mechanisms:

   • Univariate Split (pt): Uses a single pivot per node with a threshold condition ($s(x, p_i) \geq \beta$).
   • Oblique Split (opt): Uses a linear combination of similarities to two pivots ($\omega_i s(x, p_i) + \omega_j s(x, p_j) \geq \beta$), allowing for more complex decision boundaries.
   • Proximity Split (ppt): Compares an instance's similarity to two pivots directly ($s(x, p_i) > s(x, p_j)$), routing the instance based on which pivot it is closer to. This offers a relative, rather than absolute, interpretation of similarity.

3. Ensemble Learning (RandomPivotForest):
   The authors extend the single-tree approach to an ensemble framework, RandomPivotForest, which aggregates predictions from multiple PivotTree estimators using majority voting. To manage complexity, they also explore a "splitting stump forest" approach, where compact ensembles of weak learners (stumps) are extracted from the forest and used either for direct voting or combined with a logistic regression classifier.

4. Data Agnosticism:
   A core feature of the methodology is its decoupling of similarity computation from object representation. By leveraging pre-trained networks (e.g., ResNet for images, Sentence Transformers for text) to map data into a latent vector space ($\mathbb{R}^m$), PivotTree can be applied uniformly across tabular data, time series, images, and text.

Key Contributions

• Unified Framework: Introduction of PivotTree, a model that simultaneously performs pivot selection and predictive modeling, bridging the gap between instance selection and interpretable classification.
• Versatile Splitting Mechanisms: Development of univariate, oblique, and proximity-based splitting strategies that allow the model to adapt to different data structures and interpretability needs.
• Data Modality Independence: Demonstration that the approach is effective across diverse modalities (tabular, time series, images, text) by utilizing pre-trained embeddings and a unified similarity metric (Euclidean distance, with cosine and Manhattan also evaluated).
• Ensemble Integration: Proposal of RandomPivotForest and its compressed variants, offering a trade-off between the robustness of ensemble methods and the interpretability of case-based reasoning.

Experimental Results
The authors evaluated PivotTree and its variants on 45 datasets spanning four modalities. Key findings include:

• Predictive Performance: PivotTree variants (specifically $ptc_Z$ and $pts_Z$) achieved competitive results against state-of-the-art interpretable models (e.g., decision trees, rule sets) and standard classifiers (kNN, Random Forests). In many cases, they outperformed competitors, particularly on non-relational data like images and text.
• Interpretability: The models maintained high performance while utilizing a minimal number of pivots (often capped at 20), significantly reducing model complexity compared to black-box alternatives.
• Ensemble Performance: RandomPivotForest variants generally matched or approached the performance of standard Random Forests and boosting methods (XGBoost, LightGBM) on tabular and time-series data. Notably, proximity-based variants ($rppt$) showed superior performance on image datasets.
• Distance Measures: While Euclidean distance was the primary metric, experiments with Cosine and Manhattan distances showed comparable overall performance, with Cosine distance yielding particularly strong results for image data.
• Efficiency: Training times varied by dataset size and dimensionality, with univariate variants generally faster than oblique ones. The use of 10% subsampling for ensemble training significantly reduced training time with minimal impact on predictive performance.

Significance and Claims
The paper claims that PivotTree offers a significant step forward in Explainable AI (XAI) by aligning machine learning decision processes with human cognitive strategies (case-based reasoning). Its primary significance lies in its ability to provide interpretable, transparent models that do not sacrifice predictive accuracy, even in complex domains where traditional feature-based interpretable models struggle.

The authors modestly note that while the ensemble approach (RandomPivotForest) achieves high performance, it introduces variance in model complexity. They also acknowledge that for tasks where absolute performance is the sole priority, black-box models or PivotTree combined with kNN may outperform standalone tree structures, though the latter offers superior structural interpretability. The work suggests that the choice of model should depend on the specific trade-off required between global interpretability, local reasoning, and predictive power. Future directions identified include exploring hybrid splitting strategies and validating the approach in real-world human-in-the-loop decision scenarios.