Random Forest Algorithm

The random forest algorithm was first proposed in the mid to late 1990’s and
was formalized and brought into a functional form by Leo Breiman and Adele
Cutler in the early 2000’s. This machine learning algorithm thrives on an idea
similar to the one explored in the famous study, ‘Wisdom of the Crowd’, with
the distinction of the decision makers being decision trees and focus shifted
from a pure median based analysis to a mode based analysis.

The overall idea of this algorithm is to train an ensemble of decision trees (and
thus the name Forest) and compare their Boolean values to train models. This
is achieved by a series of processes including but not limited to random data
set selection, evaluating raw margin and thereby optimising the margin
function of the forest and taking into account the accuracy trade offs between
selective optimisation of tree accuracy and correlation minimization.

The entire process beings with assigning randomized data sets from the known
input to trees in the ensemble. These trees are typical decision trees which
have a rigidly defined root along with several internal nodes which represent
the different decisions with each leading edge being a representative of one of
the two Boolean values (1,0). The leaf nodes of these trees represent the
actual decision taken by the tree after passing the given data through all the
conditionals present in its root and internal nodes.
 Is it a weekday?

YES (1) NO (0)

Is time of commute 8-10 am / 6-8

The train won’t be crowded
pm?

YES (1) NO (0)

The train will be The train won’t be

crowded crowded

The above is a small example of a decision tree. Here the node asking whether
or not it is a weekday is the root node while the subsequent nodes (with
children) are the internal nodes. The leaf nodes (nodes which don’t have any
children) give us a definite assessment of the asked question. The edges are
Boolean valued with a 1 for Yes and 0 for No. The Random Forest algorithm
uses an ensemble of such trees with each of them being fed random set of
input data (repetition in data is also allowed in certain cases). The general trees
used in this algorithm are also a lot bigger and thus more complex than the
example presented above.
One of the plus points of this algorithm is that increasing individual tree size
and/or the number of trees in the ensemble doesn’t affect the model accuracy.
This problem of overfitting, which is common for a lot of other training
algorithms is dealt with in this case due to the facts that we don’t reach to
conclusions based upon the output of a single tree and that each of these trees
is trained upon an independent random data subset. The algorithm takes into
account the ‘Raw Margin’ of each tree individually, which is a Boolean measure
of whether or not the tree came to the correct and intended conclusion. Such
raw margin of all trees is taken into consideration to compute the Margin
Function of the ensemble.

The Margin Function is given by:

mr ( X ,Y )=Pθ ( h ( X , θ )=Y ) −max Pθ ( h ( X , θ )= j )

j ≠Y

If we were to group the trees based upon the final outcome generated, then
the Margin Function is simply the difference in the set size of the correct
outcome and the largest incorrect one. For instance, if out of 100 trees, 50
arrived at the correct outcome and out of the remaining 50, 20 corresponded
to the same incorrect conclusion (which is assumed to be the maximum in this
example), then the Margin Function will be evaluated as 50 – 20 = 30 and be
represented as 0.30 according to practical notations.

In the beginning of the training, the trees basically guess the correct answer
the parameters are not yet fine-tuned. At this stage, the Margin Function
evaluates roughly to 0 in the best case and <0 in the worst case (this would
indicate the Random Forest is making more incorrect predictions than correct
ones). With training, the attempt is to maximise this function.
Beside the Margin Function, the random data subset selection also plays a
pivotal role in tackling overfitting. This happens because randomization of data
ensures that a particular datapoint/set of datapoints which were responsible
for skewed prediction in one of the trees is very less likely to cause a similar
skewed prediction in any other tree. Moreover, one can think of the
inaccuracies cancelling across when we move to the Margin Function from the
Raw Margin. Thus, using this logic and the Strong Law of Large Numbers it has
been proved that the accuracy of Random Forest algorithm actually converges
to a well-defined finite value if we keep adding more trees to the ensemble.

Two specific quantities, namely the Strength and Variance of the ensemble
need to be adjusted correctly in order to reach this theoretical limiting value of
accuracy. The Strength of the ensemble is defined simply as the mean of the
raw margins of all the trees while the Variance is a measure of disagreement of
the trees within themselves and is assessed by using the Chebyshev Inequality.

Another important term defined in relation to accuracy maximization is the

generalization error, which is denoted by P and is defined as PX,Y (mr(X,Y) < 0)
where mg is the margin. This generalization error has a definite upper bound
which is given by:

¿ ρ ( 1−s 2 )
PE ≤ 2
s

Here the term ‘s’ represents the strength of individual trees and ‘ρ’ represents
the correlation between them. Thus, it is clear from the above formulation that
the error term is directly dependent on how strong the trees are individually
and how diverse they are from each other (diversity arises out of random input
data selection as discussed earlier).

However, the problem lies in the paradoxical nature of optimisation.

Maximizing the strength of individual trees would mean to maximize the
number of correct intended outputs, however this results into a lower diversity
as the fundamental structure of all the trees would start to resemble each
other. On the other hand, an attempt at maximizing diversity results in a larger
number of very weak trees. Thus, reaching a critical point from both these axes
proves to be difficult. This is where the technique of Feature Bagging comes
into play. This practically tested technique given by Leo Breiman (one of the
two people who made Random Forest mainstream) encourages us to focus on
optimising the diversity in the trees rather than individual strength. The goal is
ρ
to maximize diversity while keeping the quantity 2 reasonably high. This ratio
s
(borrowed from above expressed formula for generalization error) is what
dictates the nature of the ensemble. A high ratio would mean a less accurate
ensemble while a lower ratio would point towards a high accuracy ensemble.

References:
1. Breiman, L. (2001). Random forests. University of California, Berkeley.
[Link]
2. IBM Technology. (2022, February 7). What is random forest? [Video].
YouTube. [Link]
3. YouTube. (n.d.). Video on machine learning concepts [Video].
[Link]
4. YouTube. (n.d.). Video on machine learning concepts [Video].
[Link]
5. YouTube. (n.d.). Video on machine learning concepts [Video].
[Link]
6. Google. (2025). Google Gemini (Used for conceptual understanding and
factual correctness examination of the written article).
[Link]
7. OpenAI. (2025). ChatGPT (Used for citation formatting and reference
standardization). [Link]