What functions do decision trees and random forests learn?

Question

We know that training a function $y = f_\theta(x)$ (parameterised by $\theta$ in some fashion, for e.g., the class of linear functions) using data $\{(x_i, y_i)\}$ drawn i.i.d from some unknown distribution $p(x,y)$, by optimising the empirical mean squared loss objective function, essentially learns to represent the function $y = E[y|x]$.

I am curious to know if there's a similar formulation for decision trees and random forests. What do they learn? That is, suppose I am given samples $\{(x_i,\tilde{y_i})\}$ (drawn i.i.d from some unknown distribution), where the $\tilde{y}$ is (say) the 0-1 class label, what function the decision tree learn to represent?

I have read [1] that training a classifier under the cross-entropy loss function results in a minimiser that approximates $p(\tilde{y}|x)$, where $\tilde{y}$ is the 0-1 class label.

[1] https://github.com/JohnLangford/vowpal_wabbit/wiki/Loss-functions

Answer 1

There are overall two ways to represent decision trees. First the trees structure themselves, whom if not too deep or too many can be inspected and understood. Tree-structure representation is closely related to rule-based representation where the randomForest is seen as a large number of rules which can be reduced to smaller (often still incomprehensible) number of rules when accepting a small increase in bias. A given random forest fit could be formulated as an equation it would just be terribly long and incomprehensible.

To answer the question: "What do they learn?" I find the following overall approach more illuminating. The random forest fit can be understood as geometrical mapping function which can be visualized. If feature space is the space of any combination of features and target space is the space of any possible prediction, the random forest fit can be seen as a geometrical structure mapping between these spaces. The random forest fit can be probed with a large number of samples and the mapping curvature can be explored. It is not straight forward to visualize a mapping curvature of more than 3 dimensions. Methods such sensitivity analysis(in R: rminer,forestFloor) and partial dependence plot (in R randomForest) probes the curvature only in specific slices, namely being those slices which will characterize all main effect of a model fit. A given mapping function $\hat{y} = f(X)$, where X is the a matrix describing a p-dimension feature space and y is some target space, classification or regression, then $\hat{y} = f(X) \approx h_1(x_1) + h_2(x_2) ... + h_d(x_d)$ where $x_d$ is an individual feature. Each slice of the structure parallel to an feature axis can be understood as probing such a partial function and can be plotted in 2D(y-axis $\hat{y}$ x-axis $x_d$). This approach works well if no dominant interactions are present. If there are, these interactions can be difficult to find. It is also possible visualize two-way interactions between two variables. Three-way interactions are again difficult to visualize as three axis would often be used for features and at least one axis for target space. Lastly I work with "feature contributions" whom are a decomposition of the target predictions which can plotted similarly to sensitivity analysis, but with the extra perk that any major interactions will reveal themselves. I investigate this concept in the R-package forestFloor.