Jackknife variance estimates for random forest

The sampling variance of bagged learners is:

:$V(x)\; =\; Var[\backslash hat\{\backslash theta\}^\{\backslash infty\}(x)]$

Jackknife estimates can be considered to eliminate the bootstrap effects. The jackknife variance estimator is defined as:{{cite journal|last1=Wager|first1=Stefan|last2=Hastie|first2=Trevor|last3=Efron|first3=Bradley|title=Confidence Intervals for Random Forests: The Jackknife and the Infinitesimal Jackknife|journal=Journal of Machine Learning Research|date=2014-05-14|volume=15|issue=1|pages=1625–1651|pmid=25580094|pmc=4286302|arxiv=1311.4555|bibcode=2013arXiv1311.4555W}}

:$\backslash hat\{V\}\_j\; =\; \backslash frac\{n-1\}\{n\}\backslash sum\_\{i=1\}^\{n\}(\backslash hat\backslash theta\_\{(-i)\}\; -\; \backslash overline\backslash theta)^2$

In some classification problems, when random forest is used to fit models, jackknife estimated variance

is defined as:

:$\backslash hat\{V\}\_j\; =\; \backslash frac\{n-1\}\{n\}\backslash sum\_\{i=1\}^\{n\}(\backslash overline\; t^\{\backslash star\}\_\{(-i)\}(x)\; -\; \backslash overline\; t^\{\backslash star\}(x))^2$

Here, $t^\{\backslash star\}$denotes a decision tree after training, $t^\{\backslash star\}\_\{(-i)\}$ denotes the result based on samples without $ith$ observation.

E-mail spam problem is a common classification problem, in this problem, 57 features are used to classify spam e-mail and non-spam e-mail. Applying IJ-U variance formula to evaluate the accuracy of models with m=15,19 and 57. The results shows in paper( Confidence Intervals for Random Forests: The jackknife and the Infinitesimal Jackknife ) that m = 57 random forest appears to be quite unstable, while predictions made by m=5 random forest appear to be quite stable, this results is corresponding to the evaluation made by error percentage, in which the accuracy of model with m=5 is high and m=57 is low.

Here, accuracy is measured by error rate, which is defined as:

:$Error\; Rate\; =\; \backslash frac\{1\}\{N\}\backslash sum\_\{i=1\}^\{N\}\backslash sum\_\{j=1\}^\{M\}y\_\{ij\},$

Here N is also the number of samples, M is the number of classes, $y\_\{ij\}$ is the indicator function which equals 1 when $ith$ observation is in class j, equals 0 when in other classes. No probability is considered here. There is another method which is similar to error rate to measure accuracy:

:$logloss\; =\; \backslash frac\{1\}\{N\}\backslash sum\_\{i=1\}^\{N\}\backslash sum\_\{j=1\}^\{M\}y\_\{ij\}log(p\_\{ij\})$

Here N is the number of samples, M is the number of classes, $y\_\{ij\}$ is the indicator function which equals 1 when $ith$ observation is in class j, equals 0 when in other classes. $p\_\{ij\}$ is the predicted probability of $ith$ observation in class $j$.This method is used in Kaggle{{cite web|url=https://www.kaggle.com/c/otto-group-product-classification-challenge/details/evaluation|website=Kaggle|accessdate=|title=Otto Group Product Classification Challenge }}

These two methods are very similar.

When using Monte Carlo MSEs for estimating $V\_\{IJ\}^\{\backslash infty\}$ and $V\_\{J\}^\{\backslash infty\}$, a problem about the Monte Carlo bias should be considered, especially when n is large, the bias is getting large:

:$E[\backslash hat\{V\}\_\{IJ\}^B]-\backslash hat\{V\}\_\{IJ\}^\{\backslash infty\}\backslash approx\backslash frac\{n\backslash sum\_\{b=1\}^\{B\}(t\_b^\{\backslash star\}-\backslash bar\{t\}^\{\backslash star\})^2\}\{B\}$

To eliminate this influence, bias-corrected modifications are suggested:

:$\backslash hat\{V\}\_\{IJ-U\}^B=\; \backslash hat\{V\}\_\{IJ\}^B\; -\; \backslash frac\{n\backslash sum\_\{b=1\}^\{B\}(t\_b^\{\backslash star\}-\backslash bar\{t\}^\{\backslash star\})^2\}\{B\}$

:$\backslash hat\{V\}\_\{J-U\}^B=\; \backslash hat\{V\}\_\{J\}^B\; -\; (e-1)\backslash frac\{n\backslash sum\_\{b=1\}^\{B\}(t\_b^\{\backslash star\}-\backslash bar\{t\}^\{\backslash star\})^2\}\{B\}$

{{reflist}}

Category:Classification algorithms