4
$\begingroup$

Disclaimer: Although the Partial Dependence Plot derives from a textbook, and the method in question is mentioned in an exercise, I'm not trying to solve this for a class or homework assignment. I'm trying to develop code for computing of this plots for a real world problem in my company. Regardless, added the self-study tag.

I'm using gradient boosting for a classification task. As this is approach is a little more "Black Boxed" than traditional Logistic Regression for classification, I'm looking into methods that offer some insight on the dependence of the target with my inputs.

In "Elements of Statistical Learning (Hastie, Tibshirani, Friedman)", the authors propose Partial Dependence Plots as a tool for this task. Partial Dependence defines a set of Selected variables $X_s$ and their complement, $X_c$, and gives us the partial dependence function

$f_s(X_s) = E_{X_c}f(X_s,X_c)$

The evaluation of this formula using the training data is given by

$\bar{f}_s(X_s) = \frac{1}{N}\sum\limits_{i=1}^N{f(X_s,x_{ic})}$

This implementation would take a pass over the entire data for each evaluated value of the partial dependence function, which is incredibly expensive.

The book mentions that this evaluation can be done without the data for tree based models, but it leaves it as an exercise (10.11). I've been trying to figure out how for the past week, but I have no clue on how it can be done. I've tried searching the web for an implementation, or even for the solution of the exercise of the book, to no avail.

In short, how can I implement partial dependence plots for tree based models without resorting to the training data?

$\endgroup$
6
  • $\begingroup$ Since this is a textbook exercise, please add the [self-study] tag & read its wiki. $\endgroup$
    – Silverfish
    Sep 21, 2016 at 21:07
  • 1
    $\begingroup$ @Silverfish Actually this is not a homework or class assignment. I'm trying to develop a tool for application on a real world problem in my company. I'll clarify it on the question. $\endgroup$
    – hemagso
    Sep 21, 2016 at 21:14
  • $\begingroup$ Thanks. If you read our wiki you'll see that the [self-study] isn't just for homework or class assignments (after all, how would we know why someone is attempting an exercise?). It's the fact that you're essentially asking for a solution to a textbook exercise (10.11) that renders it self-study, even if you have an application in mind! It's a slightly confusing tag name really. $\endgroup$
    – Silverfish
    Sep 21, 2016 at 22:14
  • $\begingroup$ If $N$ is large why not use a subsample of the training data? $\endgroup$ Aug 27, 2018 at 1:31
  • $\begingroup$ I have the same question as yours. This webpage is of great help, nicolas-hug.com/blog/pdps. But I don't think the fast way always have the same result as the slow method (the definition). The fast way is more like averaging on the conditional distribution of the other covariates (not the strictly defined conditional distribution, but in the tree structure). $\endgroup$ Jun 20, 2020 at 6:54

4 Answers 4

1
$\begingroup$

Question:

In short, how can I implement [empirical] partial dependence plots for tree based models without resorting to the training data?

Answer: You can't.


I agree with Xiangyu Zheng's answer and expand it. I further argue that Jerome H. Friedman himself made a mistake in his 1999/2001 paper "Greedy Function Approximation: A Gradient Boosting Machine" (preprint pdf). If he has an account on StackExchange, please ping him, I would highly appreciate his comment.

This paper is the source of "the single traversal weight allocation algorithm", which was mentioned in other answers (with references to scikit-learn and http://nicolas-hug.com/blog/pdps). Friedman writes [I changed notation to match the question]:

For regression trees based on single-variable splits, however, the partial dependence of $f(X)$ on a specified target variable subset $X_S$ is straightforward to evaluate given only the tree, without reference to the data itself. For a specific set of values for the variables $X_S$, a weighted traversal of the tree is performed. At the root of the tree, a weight value of $1$ is assigned. For each nonterminal node visited, if its split variable is in the target subset $X_S$, the appropriate left or right daughter node is visited and the weight is not modified. If the node’s split variable is a member of the complement subset $X_C$, then both daughters are visited and the current weight is multiplied by the fraction of training observations that went left or right, respectively, at that node.

Each terminal node visited during the traversal is assigned the current value of the weight. When the tree traversal is complete, the value of $f_S(X_S)$ is the corresponding weighted average of the $f(X)$ values over those terminal nodes visited during the tree traversal.

However, this algorithm does not calculate correctly the estimated partial dependence $\bar{f}_s(x_S) = \frac{1}{N}\sum_{i=1}^N{f(x_S,x^{(i)}_{C})}$. We see, that the algorithm only uses the number of training observation in each split (equivalently, at each node), but the partial dependence function depends on more than that. Formally, I claim:

Claim. It is possible to modify the training data in such a way that the inputs to the algorithm (the decision tree and the number of training-set datapoints at each node) remains the same, yet the partial dependence function changes.

Let's first look at how the partial dependence is calculated. For this, I crudely adapt a picture from Nicolas Hug's blog. Here each terminal node corresponds to an unsplit rectangular region. The training samples $x^{(i)}=(x^{(i)}_S,x^{(i)}_C)$ (red lozenges) are replaced with their orthogonal projections onto $X_S=x_S$, i.e. $(x_S,x^{(i)}_C)$ (green plusses). Then the values of $f$ assigned to these projected points and averaged: $$\bar{f}_s(x_S) = \frac{1}{N}\sum_{i=1}^N{f(x_S,x^{(i)}_{C})} = \frac{1}{6}(2 v_G + v_I + 3 v_H).$$ enter image description here

Now let us move one datapoint (red lozenge) as shown, in such a way that the datapoint remains within the same region, but its projection moves from one region to another. The empirical partial dependence function has clearly changed: $$\bar{f}_s(x_S) = \frac{1}{N}\sum_{i=1}^N{f(x_S,x^{(i)}_{C})} = \frac{1}{6}(2 v_G + 2 v_I + 2 v_H).$$ enter image description here

Of course, one could argue that if we move training points like this, there is a good chance that we learn a completely different tree if we run the training again (recall that decision trees are unstable learners). But this is not the point. The point is that the proposed algorithm does not have a solid foundation (none was provided). Anyway, the partial dependence value the algorithm returns happens to match our second exact (empirical) calculations: $$ \text{algorithm}(x_S) = \frac{1}{3} v_G + \frac{1}{3} v_I + \frac{1}{3} v_H$$ enter image description here

Further, I again agree with Xiangyu Zheng, who writes in their answer:

The fast way is more like averaging on the conditional distribution of the other covariates (not the strictly defined conditional distribution, but in the tree structure).

Intuitively, "conditional distribution" $p(x_c|x_s)$ provided by the tree structure should not be too far from its estimate that is suitable for computing $E[f(X_S,X_C)|X_S=x_s]$:

  • where $f(x_S,x_C)$ changes fast, the decision tree is incentivised to make additional splits and create smaller regions;
  • where $f(x_S,x_C)$ changes slowly, inaccuracies in $p(x_c|x_s)$ will probably cancel out and yield a reasonable average value.

Ironically, both in the paper and in the ESL book, Friedman elaborates on how $E[f(x_S,X_C)]$ is different from $E[f(X_S,X_C)|X_S=x_s]$, but provides an algorithm that claims to compute the former while seemingly approximating the latter.

$\endgroup$
2
$\begingroup$

This webpage answers your question, http://nicolas-hug.com/blog/pdps.

A minor issue is that I don't think the fast way always have the same result as the slow method (the definition). The fast way is more like averaging on the conditional distribution of the other covariates (not the strictly defined conditional distribution, but in the tree structure).

$\endgroup$
1
$\begingroup$

If you walk through sklearn implementation of partial dependence routine, you will find the description of the procedure for trees:

    For each row in ``X`` a tree traversal is performed.
    Each traversal starts from the root with weight 1.0.

    At each non-terminal node that splits on a target variable either
    the left child or the right child is visited based on the feature
    value of the current sample and the weight is not modified.
    At each non-terminal node that splits on a complementary feature
    both children are visited and the weight is multiplied by the fraction
    of training samples which went to each child.

    At each terminal node the value of the node is multiplied by the
    current weight (weights sum to 1 for all visited terminal nodes).
$\endgroup$
0
$\begingroup$

I agree with paperskilltrees observation that the proposed recursive algorithm seems to compute the conditional expectation $E[f(x_S,X_C)|X_S=x_s]$ and not the interventional $E[f(x_S,X_C)| \mathbf{do}(X_S=x_s)]$.

The algorithm discards the information of split proportion on nodes which split on $X_S$. But we need exactly that info to compute the proportions of training samples that would have followed each path.

It seems to me that we should reverse the roles of complementary and target variable in the above recipes.

I created this notebook with a concrete example and a demonstration of differences between method = "recursion" and method = "brute" for the sklearn function partial_dependence().

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.