The only hint I can see anywhere on the page is "Statistics > Machine Learning" above the abstract title.
I really want it to be about actual biological trees being studied on the scale of forests growing with smooth edges over long periods of time, but I suspect that's not what it is about.
I will leave here a geometrical intuition of why they work in case it can help someone:
To simplify things, I will talk about regression, and say we want to predict some value y, that we know depends on x, and we have some noisy measurements of y.
y = f(x) y_observed = f(x) + noise
If you want some mental image, think about f(x)=sin(x).
Now, a (over fitted) regression tree in this case is just a step function where the value at x is y_observed. If there is no noise, we now that by doing more measurements, we can approximate y with as much precision as we want. But if there is noise, the regression tree will over fit the noisy values, creating some artificial spikes.
If you want to avoid this over fitting, you sample a lot of times the values of X, and for each sample you build a regression tree, and then average them. When you average them, every tree will contain its own particular artificial spikes, and if they are noise, they won't appear in the majority of the other trees. So when you average them, the spikes will attenuate, creating the smoother behaviour that the article talks about.
I hope it helps!
I've always thought there should be a deep connection between ReLU neural nets and regularized adaptive smoothers as well, since the ReLU function is itself a spline basis (a so-called truncated linear spline) and happens to span the same functional basis as B-splines of the same degree.
Context:
A random forest is an ML model that can be trained to predict an output value based on a list of input features: eg, predicting a house's value based on square footage, location, etc. This paper focuses on regression models, meaning the output value is a real number (or a vector thereof). Classical ML theory suggests that models with many learned parameters are more likely to overfit the training data, meaning that when you predict an output for a test (non-training) input, the predicted value is less likely to be correct because the model is not generalizing well (it does well on training data, but not on test data - aka, it has memorized, but not understood).
Historically, a surprise is that random forests can have many parameters yet don't overfit. This paper explores the surprise.
What the paper says:
The perspective of the paper is to see random forests (and related models) as _smoothers_, which is a kind of model that essentially memorizes the training data and then makes predictions by combining training output values that are relevant to the prediction-time (new) input values. For example, k-nearest neighbors is a simple kind of smoother. A single decision tree counts as a smoother because each final/leaf node in the tree predicts a value based on combining training outputs that could possibly reach that node. The same can be said for forests.
So the authors see a random forest as a way to use a subset of training data and a subset of (or set of weights on) training features, to provide an averaged output. While a single decision tree can overfit (become "spikey") because some leaf nodes can be based on single training examples, a forest gives a smoother prediction function since it is averaging across many trees, and often other trees won't be spikey for the same input (their leaf node may be based on many training points, not a single one).
Finally, the authors refer to random forests as _adaptive smoothers_ to point out that random forests become even better at smoothing in locations in the input space that either have high variation (intuitively, that have a higher slope), or that are far from the training data. The word "adaptive" indicates that the predicted function changes behavior based on the nature of the data — eg, with k-NN, an adaptive version might increase the value of k at some places in the input space.
The way random forests act adaptively is that (a) the prediction function is naturally more dense (can change value more quickly) in areas of high variability because those locations will have more leaf nodes, and (b) the prediction function is typically a combination of a wider variety of possible values when the input is far from the training data because in that case the trees are likely to provide a variety of output values. These are both ways to avoid overfitting to training data and to generalize better to new inputs.
Disclaimer: I did not carefully read the paper; this is my quick understanding.
From my understanding, in a statistical setting, low variability in bias leads to high variability in variance whereas low variability in variance leads to high variability in bias. The example I saw was with K-means, where K = N leads to high variance (the predicted cluster is highly variable) but low bias (take an input point, you get that exact input point back), vs. K=1 low variance (there's only one cluster) but bad bias (input point is far away from the cluster center/representative point).
I'm not sure I've characterized it well but there's a Twitter post from Alicia Curth that explains it [0] as well as a paper that goes into it [1].
Also, the very first sentence of the actual paper (after the abstract) is
> Random forests (Breiman, 2001) have emerged as one of the most reliable off-the-shelf supervised learning algorithms [...]
arxiv.org is overwhelmingly used for math and computer science papers, though not exclusively.
The paper will also likely be submitted to a machine learning venue.
The idea that you can take hundreds of bad models that over fit (the individual decision trees), add even more randomness by randomly picking training data and features*, and averaging them together - it's frankly amazing that this leads to consistently OK models. Often not the best but rarely the worst. There's a reason they're such a common baseline to compare against.
*Unless you're using Sklearn, whose implementation of RandomForestRegressor is not a random forest. It's actually bagged trees because they don't randomly select features. Why they kept the misleading classname is beyond me.
https://youtube.com/playlist?list=PLblh5JKOoLUIE96dI3U7oxHaC...
> since the ReLU function is itself a spline basis (a so-called truncated linear spline) and happens to span the same functional basis as B-splines of the same degree.
... you literally just spelled out the entire "depth" of it.
[1] http://proceedings.mlr.press/v80/balestriero18b/balestriero1...
For example, one could ask, what if instead of an approximation by step functions, we use a piecewise linear approximation (which is as good)? You can do that with a fully connected artificial neural network with ReLU nonlinearity, and if you check it experimentally, you will see that the results are equivalent.
Why do people often use ensembles of tree structures? The ensembling part is included in the programming packages and that is not the case for ANN, so it is quicker to experiment with. Appart from that, if you have some features that behave like categorical variables, trees also behave better in training.
If you have a particular algorithm, the bias will not increase if you train n versions in ensemble, but the variance will decrease as more anomalous observations won’t persistently be identified in submodel random samples and so won’t the persist in the bagging process.
You can test this. The difference between train and test auc will not increase dramatically as you increase number of trees in sklearn random forest for same data and hyperparameters.