A question about Dynamic Random Forest

Question

On this article, Simon Bernard proposes a new approach for constructing Random Forest called Dynamic Random Forest. I am new on this subject, so after reading the article, I have a doubt regarding the algorithm about how he uses the weights. To follow notation:

Let $T=\{(x_1,y_1),\ldots,(x_N,y_N)\}$ the training set. I think the algorithm is as follows for $l=1$ and $l=2$.

• $l=1$: We obtain a sample of $N$ training samples from $T$ according to an uniform distribution, and we call it $T_1$. Then we obtain a sample of $N$ training instances from $T_1$ according to $D_1$ (in this case, it would also be uniform). We build the tree and perform the calculation below.
• $l=2$: We obtain a sample of $N$ training samples from $T$ according to an uniform distribution, and we call it $T_2$. Then we obtain a sample of $N$ training instances from $T_2$ according to $D_2$, which is no longer an uniform distribution.

Example:

Let $T=\{(x_1,y_1),\ldots,(x_5,y_5)\}$

$l=1$ $\longrightarrow$ $T_1=\{(x_2,y_2),(x_4,y_4),(x_2,y_2),(x_5,y_5),(x_4,y_4)\}$ and we use to build the tree (using $D_1$) $\{(x_4,y_4),(x_2,y_2),(x_2,y_2),(x_5,y_5),(x_2,y_2)\}$

$l=2$ $\longrightarrow$ $T_2=\{(x_3,y_3),(x_4,y_4),(x_1,y_1),(x_4,y_4),(x_3,y_3)\}$ and we use to build the tree (according to $D_2$) $\{(x_4,y_4),(x_1,y_1),(x_3,y_3),(x_3,y_3),(x_1,y_1)\}$

Questions:

Did I understand the algorithm correctly?

When you are finished, if we give the forest a new input $x$, how do we decide its class? By majority vote?

Article: Simon Bernard, Sébastien Adam, Laurent Heutte. Dynamic Random Forests. Pattern Recognition Letters, Elsevier, 2012, 33 (12), pp.1580-1586.

Answer 1

Even if it has been few months these questions have been asked, I can still give some answers...

Regarding the hyperparameter $K$, in all our works with DRF that follows the publication of this paper, we have always used a completely random value, that is to say, a value randomly chosen between $1$ and $M$, with equal probabilities. It has proven to be efficient in a large majority of cases.

The process proposed in the paper is based on a previous work that shows that when there are a lot of irrelevant features in the dataset, the traditional value $M^.5$ is a very poor choice. In this case, selecting a value at random for each node of the trees allows us to overcome this phenomenom. In all other cases $M^.5$ is a good choice.

Regarding the weighting process, I admit it could have been better explained. At each step (before growing a new tree in the forest), the idea is: (i) to evaluate for each training instance the ratio of trees that have predicted the true class but only considering trees for which the concerned instance is an out-of-bag; and (ii) replace the previous weights by the new ones computed from this ratio.

Then, when the weights have been computed, they are used in two parts of the learning algorithm: (i) in generating the bootstrap samples (a high weight means a high probability to be selected in the bootstrap sample use for the new tree) and (ii) in the computation of the gini index.

For combining the tree predictions, we use a majority voting, as it is done in most of the random forest methods.

Unfortunately, I cannot give any stable implementation of this algorithm for now, but as soon as I have properly re-written it, I plan to publish it on my website.

Feel free to contact me if you need further details.

Answer 2

Thank you for making me read this article :)

@Did I understand the algorithm correctly?

As I read the article. DRF deviates from RF in two ways. First the number of tried features(called K) in each node is selected either: a) randomly chosen from 1 to M features(M= total number features) with equal probability, or b) K is sampled from a normal distribution with mean=M^.5 and standard deviation=M/50 [and probably some rounding of numbers... and why 50?]. Thus either a) K is uniform sampled or b) K is often something close to default mtry=M^.5. Whether a or b, is decided on some information gain criteria which is not described very well. It is not described in his referenced earlier article (18) where K always is chosen as situation a. It may be described in his thesis (17), but that is written in French so I'm lost there.

Ok, secondly DRF will re-evaluate total OOB-CV accuracy after each tree trained. After bootstrap, those samples being inbag will recieve a weighting(D) there inverse proportional to OOB-CV accuracy of that sample.

You ask if this weighting(D) is implemented by "bootstrapping the bootstrap" accordingly to this weightng(D). That would effectively be the same as down-sampling of already predicted training examples. I think, this is not what is referred to, although I agree it is not very clearly stated. I think the weightings is used when computing gini impurity, such that highly weighted samples will have higher leverage. I speculate down-sampling and "sample-weighting" would work equally well. Because "down-sampling" and "sample-weighting" work equally well to counter class unbalanced training data, see this article.

@When you are finished, if we give the forest a new input x, how do we decide its class? By majority vote?

Well that would be default. Other voting regimes could be used as in any other forest, see e.g. this answer. Basicly the forest left with after training is no different from regular random forest. Only the method of how splits were made differs. xi will run through all trees and the terminal predictions will be some kind of vote decide the class.

Lastly an unaccounted opinion. Boosting is a paper tiger, strong but fragile. It is likely the extra of boosting will outperform(meassured by CV) regular RF or the mtry chosen in random implementation. If the true hidden structure, our model have learned to replicate is not static. Then, when sampling a entirely new data set, this data set will represent a slightly changed structure, and for such problems classic RF is likely to yield more stable predictions. At best this boosting-bagging hybrid DRF may have overcomed this boosting Achilles heel.

I think DRF is difficult to reproduce from this article alone, because the a-b criterion is not well described and neither is the weighting scheme. An actual implementation should have been submitted with the article.