Random forest algorithm: Foundations — AI-ML deep dive

This page assumes you know nothing. Before you can read the parent note's variance formula or its OOB derivation, you must own every letter, ratio, and squiggle it throws at you. We build them one at a time, each on top of the last.

0. The characters in this story (a first look)

Every symbol below will reappear in the parent note. Meet them once here so nothing is a surprise.

Symbol	Plain words	Lives where
$n$	how many rows (examples) we have	the data table's height
$p$	how many features (columns/clues) each example has	the data table's width
$x_{i}$	the $i$ -th example's clues	one row
$y_{i}$	the $i$ -th example's true answer/label	one cell
$B$	how many trees in the forest	count of learners
$f_{b}$	the prediction of tree number $b$	one tree's output
$\overset{ˉ}{f}$	the average of all tree predictions	the forest's final answer
$σ^{2}$	how spread out one tree's predictions are	"moodiness" of a tree
$ρ$	how alike two trees' answers are (correlation)	agreement between trees
$m$	how many features a tree may peek at per split	a small piece of $p$

We now earn each of these, in order.

1. Data as a table: $n$ , $p$ , rows and columns

Picture a spreadsheet. Every row is one example (one animal, one house, one patient). Every column is one feature — a measured clue about that example.

$x_{i}$ (read "x sub i") means: take row number $i$ — all its clues bundled together. The little $i$ underneath is just an address label ("which row"), like a seat number.
$y_{i}$ (read "y sub i") means: the true answer sitting in row $i$ .

2. A decision tree: the single "moody expert"

Before a forest you need one tree. A decision tree is a flowchart of yes/no questions. Each question splits the examples into two groups; you keep asking until a group is pure enough to guess a label.

The tree chooses each question to make the two resulting groups as pure as possible (mostly one label). "Purity" is measured by Gini impurity or entropy — you don't need the formula here, only the idea: a good split separates the classes.

3. Prediction, and why one tree is "high variance"

Run a tree on a new example $x$ ; it walks the flowchart and lands in a leaf. That leaf's guess is the prediction, written $f_{b} (x)$ — "the answer of tree $b$ for input $x$ ."

Now the key personality trait: variance.

4. Averaging: $\overset{ˉ}{f}$ and the summation symbol $\sum$

The forest's answer is the average of all its trees. Two pieces of notation carry this.

5. Correlation $ρ$ : how alike two trees are

Averaging only helps if the trees disagree in their mistakes. If every tree makes the same error, averaging their identical wrong answers still gives that wrong answer. We measure "sameness of answers" with correlation.

6. Bootstrap sampling: $m$ , "with replacement", and $(1 - \frac{1}{n})^{n}$

Two last tools power the randomness.

Bootstrap sample — draw $n$ rows from your $n$ rows with replacement: after picking a row you put it back, so it can be picked again. Some rows appear twice, some not at all.

$m$ out of $p$ features — at each split a tree may only look at a random handful $m$ of the $p$ features. Typical $m = p$ . This forces trees onto different clues → lowers $ρ$ .

The expression $(1 - \frac{1}{n})^{n}$ — this shows up in the OOB derivation. Read it as: one draw misses a fixed row with chance $\frac{n - 1}{n} = 1 - \frac{1}{n}$ ; do that $n$ independent times → multiply → $(1 - \frac{1}{n})^{n}$ . As $n$ grows this settles onto a famous number: $(1 - \frac{1}{n})^{n} n \to \infty e^{- 1} \approx 0.368.$

The prerequisite map

Read top to bottom: the table feeds the tree; the tree gives predictions with variance; averaging pools them; bootstrap and feature-subsetting control correlation; all of it converges on the forest.

Equipment checklist

Self-test: cover the right side, answer, then reveal.

What does

n

count, and where do you see it in the table?

The number of examples (rows) — the table's height.

What does

p

count?

The number of features (columns/clues) — the table's width.

Read

x_{i}

and

y_{i}

in words.

Row

i

's clues, and row

i

's true label.

What is a split in a decision tree?

A yes/no question that cuts the examples into two more-pure groups.

What does variance

σ^{2}

measure for a tree?

How much its answer scatters when the training data changes slightly (its moodiness).

Why do we square the gap from the mean in variance?

So too-high and too-low errors both count as positive and don't cancel.

Expand

\sum_{b = 1}^{B} f_{b}

f_{1} + f_{2} + \dots + f_{B}

What does the bar in

\overset{ˉ}{f}

mean?

The average of all tree predictions (the forest's output).

What does

ρ = 1

mean for two trees, and why is it bad?

They are clones that always agree; averaging clones removes no error.

What does "with replacement" mean?

A drawn row goes back in the bag and can be drawn again.

What is

m

The small random subset of features a tree may consider at each split.

What number does

(1 - \frac{1}{n})^{n}

approach, and to what value?

e^{- 1} \approx 0.368

Connections

Parent: Random Forest Algorithm — where all these symbols get used.
Decision Trees — the base learner, section 2 here.
Bagging (Bootstrap Aggregating) — the row-resampling, section 6.
Bias-Variance Tradeoff — why high-variance trees are worth averaging, section 3.
Gini Impurity & Entropy — how a split's purity is measured, section 2.
Cross-Validation — what the left-out (OOB) rows replace, section 6.
Feature Importance — a later payoff once you own $m$ and features.
2.3.07 Random forest algorithm (Hinglish) — same topic in Hinglish.