  How can we identify the training examples that contribute most to the
prediction of a tree ensemble? In this paper, we introduce TREX, an explanation
system that provides instance-attribution explanations for tree ensembles, such
as random forests and gradient boosted trees. TREX builds on the representer
point framework previously developed for explaining deep neural networks. Since
tree ensembles are non-differentiable, we define a kernel that captures the
structure of the specific tree ensemble. By using this kernel in kernel
logistic regression or a support vector machine, TREX builds a surrogate model
that approximates the original tree ensemble. The weights in the kernel
expansion of the surrogate model are used to define the global or local
importance of each training example.
  Our experiments show that TREX's surrogate model accurately approximates the
tree ensemble; its global importance weights are more effective in dataset
debugging than the previous state-of-the-art; its explanations identify the
most influential samples better than alternative methods under the remove and
retrain evaluation framework; it runs orders of magnitude faster than
alternative methods; and its local explanations can identify and explain errors
due to domain mismatch.
