TLDR: A new research paper by Marques-Silva and Ignatiev introduces efficient and correct polynomial-time algorithms for identifying predictively equivalent decision trees. This work addresses critical flaws in a previous method (MBDSR) that relied on the computationally expensive and potentially incorrect Quine-McCluskey method, which suffered from exponential runtime and unsoundness due to non-canonical DNF representations. The new algorithms significantly improve speed and guarantee accuracy, enhancing the analysis of Rashomon sets and feature importance in machine learning.
Decision trees are a popular and intuitive type of machine learning model, often used for classification tasks. When training these models, it’s common to find many different decision trees that perform almost equally well on a given problem. This collection of high-performing models is known as the “Rashomon set.” Understanding this set is crucial for tasks like determining which features are most important for a prediction.
However, a significant challenge arises when multiple decision trees within this Rashomon set are “predictively equivalent.” This means they make the exact same predictions for every possible input, even if their internal structure looks different. Such redundancy can skew analyses, particularly when trying to understand feature importance. Removing these redundant trees helps ensure that the Rashomon set truly represents diverse ways of solving the problem.
Addressing Flaws in Previous Methods
A recent approach, known as MBDSR (proposed by McTavish et al.), aimed to tackle this problem by converting decision trees into a simplified logical form called Disjunctive Normal Form (DNF) using a method from the 1950s called Quine-McCluskey (QM). These simplified DNF representations were then compared to identify predictive equivalent trees. The MBDSR method also applied this DNF conversion to other important problems, such as explaining predictions and handling missing data.
However, a new research paper, titled “Efficient & Correct Predictive Equivalence for Decision Trees”, by Joao Marques-Silva and Alexey Ignatiev, identifies two critical issues with the MBDSR approach.
First, the paper demonstrates that the QM method, while historically significant, is computationally very expensive. It can take an exponentially long time and require an exponential amount of memory, especially for certain types of decision trees. This means that for even moderately complex decision trees, the MBDSR approach becomes impractical, consuming vast amounts of time and resources.
Second, and perhaps more critically, the new paper reveals that the MBDSR algorithm can produce incorrect results. The MBDSR approach incorrectly assumes that the minimum-size DNF representations generated by the QM method are unique for any given logical function. In reality, a single logical function can have multiple distinct minimum-size DNF forms. This “non-canonicity” means that two truly predictively equivalent decision trees might be incorrectly identified as non-equivalent by MBDSR, leading to flawed conclusions about the Rashomon set.
Also Read:
- Unlocking Efficient Influence Functions in Large AI Models with Dropout Compression
- Steering Data for Fairer AI: A New Approach to Bias Reduction
Introducing Faster and Reliable Solutions
To overcome these limitations, Marques-Silva and Ignatiev propose a suite of novel algorithms that address the same computational problems but do so in polynomial time, directly based on the size of the original decision tree. This means their algorithms are significantly faster and more scalable, avoiding the exponential bottlenecks of the QM method.
Crucially, these new algorithms also guarantee correctness. By not relying on the flawed assumption of canonical minimum-size DNF forms, they ensure that predictive equivalent decision trees are always correctly identified. This provides a reliable foundation for working with Rashomon sets, improving the accuracy of tasks like feature importance analysis.
Experimental results presented in the paper vividly illustrate the performance difference. For decision trees that cause the QM method to struggle exponentially, the new algorithms are orders of magnitude faster. For instance, while the QM method might fail to complete for a decision tree with 45 nodes, the new algorithms can process trees with thousands of nodes and hundreds of features in mere seconds or minutes, making them practical for real-world applications.
The paper also explores interesting connections between predictive equivalence and logic-based explanations, such as Abductive Explanations (AXps), and even “corrected SHAP scores” for feature importance. This highlights the broader implications of having a correct and efficient method for identifying equivalent models.
In conclusion, this research offers a significant advancement in the field of interpretable machine learning. By providing efficient and provably correct algorithms for identifying predictive equivalent decision trees, it enhances our ability to analyze and understand complex machine learning models, paving the way for more trustworthy and insightful AI applications.
