Mathematics of Random Forest Classifier

Question

I was going through the this 2001 paper on Random Forest Classifier (RFC). I understood most of the concepts but there are some probability equations that I am finding hard to understand.

Definitions

1. Random Forest - Collection of tree structured classifiers $\{h(X, \Theta_k), k=1,2,3...\}$ where $\Theta_i$s (trees) are i.i.d random vectors. Each tree casts a unit vote to the output of input $X$ and the most popular output class is chosen.
2. Raw Margin Function - $rmg(\Theta, X, Y) = \mathbf{I}(h(X, \Theta)=Y) - \mathbf{I}(h(X, \Theta)=\hat{j})$ where $\mathbf{I}$ is the identity function and $\hat{j} = argmax_{j \neq Y} P_\Theta(h(X, \Theta)=j)$.
3. Margin Function - $mr(X, Y) = \mathbf{E}_\Theta [rmg(\Theta, X, Y)] = P_\Theta(h(X, \Theta)=Y) - max_{j \neq Y} P_\Theta(h(X, \Theta)=j)$. The margin measures the extent to which the average number of votes at $X,Y$ for the right class exceeds the average vote for any other class.
4. Generalization error - $PE^* = P_{X, Y}(mr(X, Y)<0)$.

THE RESULT I am referring to states that the performance of the RFC is dependent on the correlation between the trees and the individual accuracies. In mathematical terms this is, \begin{equation} PE^* \leq \hat{\rho} \left(\frac{1-s^2}{s^2}\right) \end{equation}

I cannot understand the derivation of the above result. In the above inequality $s = \mathbf{E}_{X, Y}[mr(X, Y)]$. Now using Chebychev’s inequality, definition of $PE^*$ and $s$ we get,

\begin{equation} PE^* \leq \frac{Var(mr)}{s^2} \end{equation}

There is a identity that states for i.i.d random vectors $\Theta$ and $\Theta'$, $\mathbf{E}_\Theta^2[f(\Theta)] = \mathbf{E}_{\Theta, \Theta'}[f(\Theta)(\Theta')]$. Using the definition of $mr(X, Y)$ and the identity this gives $mr^2(X, Y) = \mathbf{E}_{\Theta, \Theta'}[rmg(\Theta, X, Y)rmg(\Theta', X, Y)]$.

Using this the following equations are derived. I need help understanding this section onwards. I cannot understand how these equations are derived and the form of $\hat{\rho}$ that is derived.

\begin{align} Var(mr) &= \mathbf{E}_{\Theta, \Theta'}[cov_{X, Y}[rmg(\Theta, X, Y)rmg(\Theta', X, Y)]]\\ &= \mathbf{E}_{\Theta. \Theta'}[\rho(\Theta, \Theta')sd(\Theta)sd(\Theta')]\\ &= \hat{\rho}\mathbf{E}_\Theta^2[sd(\Theta)]\\ &\leq \hat{\rho}\mathbf{E}_\Theta[Var(\Theta)] \end{align}

where, $\hat{\rho} = \frac{\mathbf{E}_{\Theta. \Theta'}[\rho(\Theta, \Theta')sd(\Theta)sd(\Theta')]}{\mathbf{E}_{\Theta, \Theta'}[sd(\Theta)sd(\Theta')]}$ which is the mean value of the correlation.

Continuing on the troublesome section,

\begin{align} \mathbf{E}_\Theta[Var(\Theta)] &\leq \mathbf{E}_\Theta[\mathbf{E}_{X, Y}^2[rmg(\Theta, X, Y)]] - s^2\\ &\leq 1-s^2 \end{align}

Can someone please break down the steps of the section of the proof that I have mentioned above?

NOTE: This is my first post here. So if you are downvoting the question then please let me know how I can improve the question.

Answer 1

IMO, there is quite a jump in the original paper from $Var(mr)$ to $\mathbb{E}_{\Theta, \Theta'}[\text{Cov}_{X, Y}[rmg(\Theta, X, Y)rmg(\Theta', X, Y)]]$, and I think that is the most troublesome part of the proof. The remainder of the derivation uses fairly standard facts about correlation and covariance. Luckily, the intermediate steps are mostly algebra.

From this point onward, I'll abbreviate variance to $\mathbb{V}$ and try to be as explicit as possible about what variables that expectations, variances, and the like are taken with respect to.

Here are some starting assumptions/definitions that we will use:

• [A1] The generalization error $PE^*$ is at most $\mathbb{V}_{X, Y}(mr(X, Y)) / s^2$.
• [A2] We have that $mr(X, Y) \triangleq \mathbb{E}_{\Theta}[rmg(\Theta,X,Y)]$ (the function $rmg(\Theta, \cdot, \cdot)$ is defined in this way).
• [A3] Similarly, we also know that $(mr(X,Y))^2 = \mathbb{E}_{\Theta, \Theta'}[rmg(\Theta,X,Y)rmg(\Theta', X,Y)]$, where $\Theta, \Theta'$ are some parameters for each tree in the random forest.
• [A4] The correlation coefficient $\bar{\rho}$ is defined as the average correlation (over all $\Theta, \Theta'$) between $rmg(\Theta, X, Y)$ and $rmg(\Theta', X, Y)$, or $\mathbb{E}_{\Theta, \Theta'}[\rho(rmg(\Theta, X, Y), rmg(\Theta', X, Y))]$, as $X, Y$ vary.

This is all based on definitions from the paper that you've stated in your question.

To show the final result, it is sufficient to prove that $\mathbb{V}_{X, Y}(mr(X, Y)) \leq \bar{\rho}(1 - s^2)$ ([A1]). Recall that the variance of random variable can be written as

$$\mathbb{V}_{X, Y}(mr(X, Y)) = \mathbb{E}_{X, Y}(mr(X, Y)^2) - \mathbb{E}_{X, Y}(mr(X, Y))^2.$$

Substituting using [A2] and [A3]:

$$\mathbb{V}_{X, Y}(mr(X, Y)) = \mathbb{E}_{X, Y}(\mathbb{E}_{\Theta, \Theta'}[rmg(\Theta,X,Y)rmg(\Theta', X,Y)]) - \mathbb{E}_{X, Y}(\mathbb{E}_{\Theta}[rmg(\Theta,X,Y)])\mathbb{E}_{X, Y}(\mathbb{E}_{\Theta'}[rmg(\Theta',X,Y)]).$$

We can switch the ordering of expectations and combine terms of the form $\mathbb{E}_\Theta[(\cdot)] {\mathbb{E}_\Theta'}[(\cdot)]$ via independence (if this isn't straightforward, try to derive the following equation as an exercise), showing that the preceding is equal to

$$\mathbb{E}_{\Theta, \Theta'}[\mathbb{E}_{X,Y}[rmg(\Theta,X,Y)rmg(\Theta', X,Y)] - \mathbb{E}_{X, Y}[rmg(\Theta,X,Y)]\mathbb{E}_{X, Y}[rmg(\Theta',X,Y)]] = \mathbb{E}_{\Theta, \Theta'}[Cov_{X, Y}(rmg(\Theta,X,Y), rmg(\Theta',X,Y))]. $$

where we simply applied the definition of covariance (i.e., $Cov(X,Y) = \mathbb{E}[XY] - \mathbb{E}[X]\mathbb{E}[Y]$) to the term inside the outer expectation (the one w.r.t. $\Theta, \Theta'$). An application of the correlation-covariance formula yields

$$\mathbb{E}_{\Theta, \Theta'}[Cov_{X, Y}(rmg(\Theta,X,Y), rmg(\Theta',X,Y))] = \mathbb{E}_{\Theta, \Theta'}\left[\rho(rmg(\Theta,X,Y), rmg(\Theta',X,Y))\sqrt{\mathbb{V}_{X, Y}(rmg(\Theta,X,Y))\mathbb{V}_{X, Y}(rmg(\Theta',X,Y))}\right],$$

and since the $\rho(\cdot, \cdot)$ term doesn't depend on $\Theta, \Theta'$ (the correlation is evaluated over $X, Y$ for a fixed $\Theta, \Theta'$ pair), we can break apart the expectation and substitute [A4], yielding

$$\mathbb{V}_{X, Y}(mr(X, Y)) = \bar{\rho}\mathbb{E}_{\Theta, \Theta'}\left[\sqrt{\mathbb{V}_{X, Y}(rmg(\Theta,X,Y))}\right] \mathbb{E}_{\Theta, \Theta'}\left[\sqrt{\mathbb{V}_{X, Y}(rmg(\Theta',X,Y))}\right] \\= \bar{\rho}\mathbb{E}_{\Theta}\left[\sqrt{\mathbb{V}_{X, Y}(rmg(\Theta,X,Y))}\right]^2 \\\leq \bar{\rho}\mathbb{E}_{\Theta}\left[\mathbb{V}_{X, Y}(rmg(\Theta,X,Y))\right].$$

This is exactly the term you notate as $\hat{\rho}\mathbf{E}_\Theta[Var(\Theta)]$. If the final inequality isn't clear, try to justify that to yourself as well (Hint: recall the definition of variance. We know that $Var(X) \geq 0$ as well; what else does that imply?).

We only have only last step -- to show that $\mathbb{E}_{\Theta}\left[\mathbb{V}_{X, Y}(rmg(\Theta,X,Y))\right] \leq 1 - s^2$. We can rewrite the variance term as follows:

$$\mathbb{E}_{\Theta}\left[\mathbb{V}_{X, Y}(rmg(\Theta,X,Y))\right] = \mathbb{E}_{\Theta}\left[\mathbb{E}_{X, Y}[rmg(\Theta,X,Y)^2]\right] - \mathbb{E}_{\Theta}\left[\mathbb{E}_{X, Y}[rmg(\Theta,X,Y)]^2\right].$$

First, since $\mathbb{E}_{X, Y}[mr(X, Y)]$ is defined as $s$, we can use [A2] and replace the 2nd term with $s^2$. For the first term, we know that $rmg(\Theta,X,Y)^2 \in [0, 1]$ for any choice of $\Theta, X, Y$ (since $rmg(\cdot)$ itself is either -1 or 1), so $\mathbb{E}_{\Theta}\left[\mathbb{E}_{X, Y}[rmg(\Theta,X,Y)^2]\right]$ is at most 1 (if this isn't clear, try substituting in the definitions for $mr(\cdot), rmg(\cdot)$, and thinking about what the requisite indicators/probabilities could be). This yields $$\mathbb{E}_{\Theta}\left[\mathbb{V}_{X, Y}(rmg(\Theta,X,Y))\right] \leq 1 - s^2.$$

Hence, $\mathbb{V}_{X, Y}(mr(X, Y)) \leq \bar{\rho}(1 - s^2)$, and one last substitution yields the conclusion that $$PE* \leq\frac{ \bar{\rho}(1-s^2)}{s^2}$$ as desired.