🤖 machine learning

Woodelf++: A Fast and Unified Partial Dependence Plot Algorithm for Decision Tree Ensembles

Woodelf++ is a unified, high-performance algorithm that significantly accelerates the computation of Partial Dependence Plots, Joint-PDPs, and Any-Order-PDIVs for decision tree ensembles, achieving speedups of up to five orders of magnitude over existing methods like scikit-learn.

Original authors: Ron Wettenstein, Alexander Nadel, Udi Boker

Published 2026-05-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ron Wettenstein, Alexander Nadel, Udi Boker

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a very smart, but mysterious, robot chef (a Decision Tree Ensemble) that decides what meal to serve you based on your ingredients. You want to know: "If I use more salt, does the soup get saltier?" or "How do salt and pepper work together?"

To answer this, data scientists use tools called Partial Dependence Plots (PDPs). Think of these as a "what-if" simulator. You tell the robot, "Ignore your usual ingredients, pretend every customer ordered with exactly 5 grams of salt," and then you ask, "What's the average meal prediction?" You do this for 5g, 10g, 15g, and so on, to draw a line showing the trend.

The problem? The current tools to run this simulation are incredibly slow. If you have a massive dataset (like 400,000 customers), the old methods are like trying to count every grain of sand on a beach one by one. Some calculations would take millions of years to finish.

Enter WOODELF++, a new, super-fast algorithm introduced in this paper. Here is how it works, using simple analogies:

1. The Old Way: The "Brute Force" Tourist

Imagine you want to know how the robot reacts to salt. The old method (used by popular tools like scikit-learn) is like a tourist who walks up to the robot, changes the salt to 5g, asks for a prediction, writes it down, then changes it to 6g, asks again, and so on.

The Issue: If you have thousands of customers and hundreds of ingredients, the robot has to run its entire brain thousands of times for every single question. It's exhausting and slow.

2. The New Way: The "Magic Blueprint" (WOODELF++)

The authors realized that decision trees (the robot's brain) aren't actually random; they are built on strict rules (like "If salt > 5g, go left; if not, go right").

Instead of asking the robot to run its brain over and over, WOODELF++ does something clever:

It translates the robot's brain into a "Boolean Logic Blueprint." Imagine taking the robot's complex decision tree and turning it into a simple, compact map of "If/Then" rules (mathematically called a Weighted Disjunctive Normal Form or WDNF).
It uses "Local Attribution." Instead of simulating the whole world, it looks at specific "paths" through the map. It asks, "If I change just this one rule on this specific path, how does the outcome change?"
The Result: Because it's working with the blueprint rather than re-running the whole simulation, it can calculate the answer for all customers at once, instantly.

3. The Three Superpowers of WOODELF++

The paper claims this new method is a "unified" tool, meaning it does three specific jobs much faster than anyone else:

A. The Single-Feature Plot (PDP)

What it does: Shows how one ingredient (like salt) affects the meal on average.
The Speedup: On a dataset with 400,000 rows, WOODELF++ is 6 times faster than the current best tool (FastPD) and 100,000 times faster than the standard tool (scikit-learn).
The "Full PDP" Innovation: Usually, you have to pick specific points to test (e.g., 5g, 10g, 15g). If the robot has a weird rule that only triggers at exactly 12.3g, you might miss it. WOODELF++ can generate a "Full PDP" that checks every single threshold the robot actually uses. It's like checking every single step on a staircase instead of just guessing where the steps are.

B. The Two-Feature Plot (Joint-PDP)

What it does: Shows how two ingredients interact (e.g., "Does salt make the soup better only if there is also pepper?").
The Speedup: This is even harder to calculate because you have to test every combination of salt and pepper. WOODELF++ handles this efficiently by reusing the "blueprint" logic, making it 6 times faster than the competition.

C. The Interaction Detective (Any-Order-PDIVs)

What it does: This is the big one. It tries to figure out how groups of ingredients interact. Do salt, pepper, and garlic all work together in a weird way?
The "Million-Year" Gap: The paper makes a staggering claim here. For a large dataset, the current best tool (FastPD) would theoretically take over 1,000,000 years to calculate all these interactions.
WOODELF++'s Feat: It does the same calculation in 5 minutes.
How? The old tools treat the problem as exponential (doubling the work with every new ingredient). WOODELF++ breaks the problem down by looking at the "paths" inside the trees, reducing the complexity from exponential to something much more manageable.

4. Why This Matters (According to the Paper)

The paper doesn't claim this will cure diseases or predict the stock market directly. Instead, it claims to solve a computational bottleneck.

Accessibility: It makes complex explanations (like "Full PDPs") possible on large datasets where they were previously too slow to compute.
Accuracy: By being able to check every split threshold, it reveals hidden patterns (like a sudden spike in fraud risk at a specific salary amount) that standard, sampled plots would miss.
Efficiency: It runs in pure Python and can even use computer graphics cards (GPUs) to go even faster.

Summary Analogy

If the old methods were like counting every single leaf on a forest of trees one by one, WOODELF++ is like taking a satellite photo of the forest and using a formula to count the leaves instantly. It doesn't just count faster; it changes the way you look at the problem, turning an impossible task (taking a million years) into a trivial one (taking five minutes).

Technical Summary: WOODELF++

Problem Statement

Decision tree ensembles are ubiquitous in real-world applications, yet interpreting their predictions remains a critical challenge for trust and decision-making. Three primary tools for interpreting these models are Partial Dependence Plots (PDPs), Joint Partial Dependence Plots (Joint-PDPs), and Partial Dependence Interaction Values (PDIVs).

PDPs visualize how a single feature affects the average model prediction.
Joint-PDPs extend this to pairs of features to reveal combined effects.
PDIVs (specifically the "Any-Order" task) quantify interaction effects across all possible feature subsets for every row in a dataset.

Current state-of-the-art methods, such as those in scikit-learn and the FastPD algorithm (implemented in the GLEX package), suffer from prohibitive computational complexity. Naive approaches scale linearly with the number of samples and features but exponentially with tree depth and the number of features involved in interactions. For large datasets (e.g., 400,000 rows) and complex interaction tasks (Any-Order-PDIVs), existing methods are either impractically slow (taking days or years) or rely on approximations that may miss critical model behaviors like sharp discontinuities.

Methodology

The authors introduce WOODELF++, a unified and efficient framework for computing PDPs, Joint-PDPs, and Any-Order-PDIVs on decision tree ensembles. The approach builds upon the authors' previous work, WOODELF, which efficiently computes SHAP values by modeling decision tree ensembles as Pseudo-Boolean (PB) functions represented in Weighted Disjunctive Normal Form (WDNF).

The core technical innovations include:

Unification via WDNF and Linearity:
The authors formulate PDP, Joint-PDP, and PDIV tasks as cooperative-game metrics over WDNF formulas. By leveraging the linearity property of these metrics, they can compute complex global explanations by aggregating results from individual "cubes" (conjunctions of literals) within the WDNF representation. This avoids the need to re-evaluate the model for every sample-feature combination individually.
Efficient Consumer Dataset Construction:
To compute PDPs and Joint-PDPs efficiently, the authors construct compact "consumer datasets" ( $C$ ) that allow local-attribution algorithms to compute global dependence plots.
- For PDPs, they construct a dataset with $k$ rows representing sampled feature values.
- For Joint-PDPs, they introduce a novel construction that reduces the dataset size from $O(k^2 f)$ to $O(k^2 \log f)$ by encoding feature indices in binary and using np.tile and np.repeat operations to ensure all pairwise value combinations are represented without redundant rows.
Full PDPs:
Recognizing that standard PDPs with sampled values ( $k$ ) can miss narrow spikes or single-value effects (e.g., a fraud model flagging a specific default salary), the authors propose Full PDPs. Instead of arbitrary sampling, Full PDPs use all split thresholds from the tree nodes as the x-axis values. Because decision tree predictions are piecewise constant between thresholds, this method captures the exact behavior of the ensemble with minimal evaluation points.
Complexity Reduction for Any-Order-PDIVs:
The most significant theoretical contribution is the reduction of complexity for Any-Order-PDIVs.
- Naive/FastPD: FastPD processes trees independently, resulting in a complexity dependence of $2^{2D}$ (where $D$ is tree depth) in the worst case.
- WOODELF++: By processing each root-to-leaf path separately and utilizing the specific structure of the PDIV metric on WDNF, the complexity dependence is reduced to $4^D$ . This represents an exponential improvement over the state of the art.
Approximation and GPU Support:
The framework naturally supports Path-Dependent approximations (equivalent to setting the background dataset to empty) and is implemented in pure Python with support for GPU acceleration.

Key Contributions

Speedup in PDP and Joint-PDP: WOODELF++ achieves approximately 6× speedup over FastPD and up to five orders of magnitude over scikit-learn for PDP and Joint-PDP tasks on large datasets.
Exponential Complexity Improvement for Any-Order-PDIVs: The authors demonstrate that for balanced trees, the complexity shifts from exponential in the input size (FastPD's $2^{2D}$ ) to polynomial in the input size (WOODELF++'s $4^D$ ). Empirically, this reduces the runtime for Any-Order-PDIVs on 400,000 samples from an estimated 1,000,000 years (FastPD) to 5 minutes (WOODELF++).
Introduction of Full PDPs: A novel method to capture the complete piecewise-constant structure of tree ensembles, enabling the detection of overfitting and monotonicity violations that sampled PDPs miss.
Unified Framework: The paper establishes a simple connection between approximate PDPs, exact PDPs, and Path-Dependent SHAP, unifying them under a single algorithmic framework.

Experimental Results

The authors evaluated WOODELF++ on two large, widely used datasets: IEEE-CIS (472k rows, 397 features) and KDD Cup 1999 (4.9M rows, 127 features). Models were trained using HistGradientBoostingRegressor with 100 trees and a maximum depth of 6.

PDP Performance: On IEEE-CIS, WOODELF++ computed Exact PDPs (k=5) in 13.1 seconds (GPU) compared to 99 seconds for FastPD and 58.5 minutes for scikit-learn.
Joint-PDP Performance: For Joint-PDPs (k=5), WOODELF++ took 25 seconds (GPU) versus 130 seconds for FastPD and an estimated 35 days for scikit-learn.
Any-Order-PDIVs: On IEEE-CIS with 10,000 samples, WOODELF++ completed the task in 22.6 seconds (GPU). FastPD was estimated to require 60,000 years.
Correctness: The authors verified that WOODELF++ outputs match scikit-learn and direct PDIV calculations with a maximum difference of 0.00001.

Significance

The paper claims that WOODELF++ fundamentally changes the feasibility of interpreting decision tree ensembles. By reducing the complexity of Any-Order-PDIVs from intractable to practical, it enables the analysis of high-order feature interactions that were previously computationally impossible. Furthermore, the introduction of Full PDPs allows practitioners to visualize the exact decision boundaries of tree models, moving beyond the limitations of sampled approximations. The authors position WOODELF++ as a necessary tool for scalable, trustworthy AI in domains requiring deep model understanding, such as healthcare, finance, and ecology.