Computing Partial Dependence Plots for Trees 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?
 A: 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).
A: 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).

