1
$\begingroup$

In this MS tech report at section 2.2.3 (p. 15) the authors talk about the randomness model in random forests. They say that the two most popular ways to inject randomness are bagging and randomized node optimization (RNO).

However, I have trouble to understand the abstract definition of RNO given there. The paper says:

If $\tau$ is the entire set of all possible parameters $\theta$ then when training the $j^{th}$ node we only make available a small subset $\tau_j \subset \tau$ of such values.

I don't know to what the term parameters refers to in this context. My guesses for how RNO works are either

  • randomly reduce the dimensionality of the feature space at each node by selecting $d$ out of $n$ features, so that $d<<n$

or

  • randomly reduce the number of values each feature can have by shrinking the training set at each node

Can someone explain me what RNO is actually doing with the training set at a certain node?

$\endgroup$

1 Answer 1

1
$\begingroup$

The definitions in the report are probably "over-parametized".

A given element $\theta_i \in \mathcal{T}_j \subset \mathcal{T}$ represents a complete set of "parameters" that can be used to make a decision at a particular node. For example, given a feature vector $X$ for which we want to make a decision on, an example of such $\theta_i$ can be $\theta_i=(g(X),f(g(X)),\tau)$, where

$g(x)$ is a selector function that selects a subset of the features or components of $X$

$f(g(x))$ defines the decision primitive. For example a line, circle, square, cube, sphere e.t.c

$\tau$ is the threshold which when combined with $f(g(x))$ forms the decision boundary that $\theta_i$ corresponds to.

Now, if you think of it well, you find that there is an infinite amount of these 3 decision "parameters". However, we only select a few of them. Let the number of selector functions, $g(X)$, we want to consider for our decision forest be $S_g$, the number of primitives, $f(g(x))$, be $S_f$, and the number of thresholds, $\tau$, be $S_\tau$. Now we have that the total number of possible candidates to select from for a node in a tree would be $S_g \times S_f \times S_\tau$.

Given these definitions, let $\mathcal{T}$ be the set of all such possible parameters. Then we have $|{\mathcal{T}}|=S_g \times S_f \times S_\tau$. If you train your decision forest on all elements in $\mathcal{T}$, then the trees that make the forest will be highly correlated with no difference. However, if at each node, you randomly pick a subset of the elements in $\mathcal{T}$, then the correlation reduces in relation to the degree of the randomization you choose. This reduction in correlation will then help improve generalization of the decision forest. Randomly selecting from $\mathcal{T}$ for each node, and using the selected subset of "parameters" to train is what is referred to as Randomized Node optimization. The randomly selected parameters for node $j$ is $\mathcal{T}_j \subset \mathcal{T}$

Note that $\mathcal{T}$ is different from $\tau$. I used it because I believe those were the parameters used in the report (Springer's decision forest for computer vision A. Criminisi and Jamie shotton, section 2.1)

$\endgroup$
2
  • $\begingroup$ Wow, I didn't expect to get an answer on this after that time period. So I was on the right track with my first bullet point, right? But we do not only subsample our feature vector, but also our split function and the threshold for that split function? $\endgroup$
    – Timo
    Commented Mar 17, 2018 at 21:03
  • 1
    $\begingroup$ Yes. Your first bullet point was on the right track. It's all just about optimizing across the entire space of possibilities. Your selector function is in charge of the dimension reduction you mentioned. But it's best not to see it as dimension reduction but feature selection, as the goal is find the features that best optimize whatever energy function you choose (e.g entropy/information fain). $\endgroup$
    – I L
    Commented Mar 17, 2018 at 22:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.