What is the honesty condition for regression trees?

I have a question pertaining to Stefan Wager's "Asymptotic Theory for Random Forests": http://arxiv.org/pdf/1405.0352v1.pdf

Wager first states that trees are "fully grown in the sense given training data $(X_i, Y_i)$, a tree makes predictions of the form $T(x) = Y_{i^*(x)}$ for some index $i^*(x)$.

With this notation, he goes on define condition (9) as the following:

$L(Y_{i^*(x)} | X_{i^*(x)} = x) \stackrel{d}{=} L(Y_i | X_i = x)$

I am not grasping the complete idea behind this condition, and I believe it relates to my confusion over the $i^*(x)$ index notation. Could someone help me understand this condition and how it leads to the condition that we cannot use training labels both to choose splits and make predictions? This condition is found at the top of page 8 in the paper.

The meaning of the "fully grown" condition, as the authors elaborate afterwards, is that each terminal node of the tree contains exactly one instance from the training data. The authors remark that this is a "theoretical convenience":

Meanwhile, (C) is a theoretical convenience that lets us simplify the exposition. In practice, trees are sometimes grown to have terminal node size $k$ rather rather than $1$ for regularization. In our setup, however, we already get regularization by drawing subsamples of size $s$ where $s/n \to 0$ and the regularization effect from using larger leaf sizes is not as important.

The notation $T(x) = Y_{i^*(x)}$ means that, for any example $x$ that you might want to predict, there's some integer index $i^*(x)$ such that the tree $T$ predicts that $x$ has the same label as the training data point in index $i^*(x)$.

On to their definition of "honesty". This basically means that the tree has to use a different set of points for constructing the splits and for predicting the labels (in contrast to how e.g. CART does it, as the authors note). I agree that that equation is pretty complicated to parse though! Here's how it works.

Suppose you have a point that $x$ in your data set. What the honesty condition says is that: the label that the tree outputs when you drop $x$ down the tree--treated as a random variable (dependent on the random data)--cannot depend on whether $x$ actually ends up inhabiting a leaf of the tree. In other words, the likelihood must be the same as if you had two data points with covariates $x$ in your data (and responses drawn separately, i.i.d.), and you used one of them to determine the splits, but then output the label of the other one.

• Thank you! Just one more question. Why use likelihood notation? It seems like $P(Y_{i^*(x)} | X_{i^*(x)} = x) \stackrel{d}{=} P(Y_i | X_i = x)$ better captures this notion of honesty. – andrew Apr 27 '15 at 19:06
• I'm not sure, to be honest! It was confusing to me as well. – Ben Kuhn Apr 27 '15 at 19:30