1What the method is for

Not the classification itself, but what is doing the dividing.

Suppose there are \(n\) objects, each with \(p\) explanatory variables and one group label. Building a rule that assigns the label is a classification problem, but in the places where Onohara's research calls on this method, getting the label right is usually not the point.

In the work on the upper Ibi River basin, a phylogenetic estimate of the settlements is made first from basic vocabulary, and the groupings of branches obtained there are then handed back as classification labels. On that footing, random forest is used to ask which vocabulary items are the factors dividing the settlements. It is not the accuracy of the classifier but the ranking of the variables that contributed to the classification that is the output worth reading.

The survey on statistics education uses it the same way. It was applied in order to separate the free-text answers of students from a science background from those of the rest, and to pull out, as “characteristic words”, the words whose frequency of occurrence differed markedly between the two groups.

2Origin — from a single tree to a stand

CART decision trees, bundled by bootstrapping and random variable selection.

The starting point is CART (Classification and Regression Trees) of Breiman, Friedman, Olshen and Stone (1984). Split the objects in two on the value of an explanatory variable, choose the split by how far the impurity falls, and repeat recursively to grow a tree.

A single tree is easy to interpret but unstable: change the data slightly and the shape of the tree changes. Breiman (2001) gave a framework that treats this instability not as a defect but as a resource to be used. Grow a great many trees that differ a little from one another, and take their vote. Onohara's paper summarizes it as: random forest can be called ensemble learning over CART decision trees.

The design says that each individual tree may be weak

The two papers on the upper Ibi River basin introduce the method as one that combines several classification methods that are by no means accurate, thereby improving accuracy for the analysis. Naively this reads as an odd description, but the variance formula in the next section shows it to be a plain statement of the design principle. The bet is not on building one strong predictor but on building many that are weak and unlike one another.

3Correspondence with Perspective 4, learning theory

A third answer to the gap between expected and empirical risk — neither a bound nor a measurement.

The question learning theory deals with comes down to one thing: how to hold down the gap between the empirical risk \(\hat{R}(f)\) that can be computed at hand and the expected risk \(R(f)\) that one actually wants small. Perspective 4 of the seven perspectives gives the form of a generalization bound, which holds that gap down from above with a complexity term.

THE BASIC FORM OF PERSPECTIVE 4 (RESTATED)
\[ R(f) \;=\; \mathbb{E}_{(x,y)\sim P}\bigl[\ell(f(x),y)\bigr], \qquad \hat{R}(f) \;=\; \frac{1}{n}\sum_{i=1}^{n} \ell\bigl(f(x_i),y_i\bigr) \]

\(P\) … the distribution the data follow; its contents are unknown, but it is taken to exist
\(\ell\) … the loss function; no probability model is set up

LOO cross-validation, placed under the same perspective, closes that gap by measurement: take the sample apart one point at a time, refit, and average the loss at the removed point. Random forest answers differently from either. It neither restricts the hypothesis set nor measures by removal; it averages the predictors themselves and brings the variance down.

What Breiman proved was convergence, not invincibility

Breiman (2001) makes two claims. First, as the number of trees increases, the generalization error of the forest converges almost surely to some limit — a claim of the form “it does not diverge”. Second, the upper bound on that limit is set by two quantities: the strength of the individual trees and the correlation between them. The variance formula in the next section is the intuitive face of this second claim.

4What the two randomizations are for

Averaging predictors with low correlation lowers the variance. That the fall has a floor is what matters.

Randomness enters in two places when a tree is built. One is bootstrapping: resample with replacement for each tree, so that each sees different data. The other is random selection of variables at each split, narrowing the candidates for the split from all \(p\) to a subset each time. Onohara's paper states both stages explicitly: in generating a decision tree, not all objects are used — the objects are selected by the bootstrap method — and in addition the variables are selected at random, and one decision tree is generated.

Why are two needed? Write the predictions of \(B\) trees as \(T_1(x),\dots,T_B(x)\), let each have variance \(\sigma^2\), and let the correlation between any two be \(\rho\). The variance of the averaged predictor then takes this form.

VARIANCE OF AN AVERAGE OF CORRELATED PREDICTORS
\[ \mathrm{Var}\!\left(\frac{1}{B}\sum_{b=1}^{B} T_b(x)\right) \;=\; \rho\,\sigma^{2} \;+\; \frac{1-\rho}{B}\,\sigma^{2} \]

The second term … divided by \(B\), it vanishes as trees are added. This is where bootstrapping works
The first term … contains no \(B\). However many trees are added, it remains
\(\rho\) … the correlation between trees. Unless it falls, the first term does not

The first term is the whole reason for drawing variables at random

Grow trees by bootstrapping alone and, if there is one strong explanatory variable, every tree will use it near the root. The trees end up resembling one another — that is, \(\rho\) grows — and the first term above stays high. No number of trees will remove it. Narrowing the candidate variables at every split is the operation that forbids every tree from jumping at the strong variable, and so lowers \(\rho\). That Breiman wrote the bound on generalization error in terms of strength and correlation, and this formula, are the same statement in different words.

Why there is no pruning — a division of labour between bias and variance

With a single decision tree, growing it too deep fits the data at hand too closely, so it is usual to prune the tree back using cross-validation. Random forest does not do this. Onohara's paper says that in random forest, unpruned decision trees are generated and combined in order to improve classification accuracy. The division of labour is clear: each tree is grown deep so that bias is small, and the variance is handed over to the averaging. That the second term in the formula above vanishes with \(B\) is what supports this arrangement.

5Variable importance and the Gini coefficient — a bridge to Perspective 5

Average over the whole forest “how far the uncertainty fell by splitting”.

Write the proportion of class \(k\) at node \(t\) as \(p_{k|t}\). Two impurity measures are in common use for judging how good a split is in CART.

GINI IMPURITY AND ENTROPY
\[ G(t) \;=\; 1-\sum_{k} p_{k|t}^{2}, \qquad\qquad H(t) \;=\; -\sum_{k} p_{k|t}\log p_{k|t} \]

Both are 0 when a node is occupied by a single class, and grow as the node becomes more mixed

The split chosen is the one that makes this fall the most. The fall can be written as the weighted difference between parent and children.

DECREASE IN IMPURITY FROM A SPLIT
\[ \Delta G(t) \;=\; G(t) \;-\; \frac{n_L}{n_t}G(t_L) \;-\; \frac{n_R}{n_t}G(t_R) \]

Subtract the impurity of the left and right children, weighted by the proportion of objects that flowed into each. It has the same shape as the information gain of Perspective 5, \(\mathrm{IG} = H(\text{parent}) - \sum_c \frac{n_c}{n}H(\text{child}_c)\)

The importance of a variable \(x_j\) is the sum of these decreases at every split where that variable was used, across all trees in the forest, averaged. R returns it under the name MeanDecreaseGini.

MEAN DECREASE IN GINI
\[ \mathrm{MDG}(x_j) \;=\; \frac{1}{B}\sum_{b=1}^{B}\ \sum_{t\in\mathcal{T}_b\,:\,v(t)=j} \Delta G(t) \]

\(v(t)=j\) … indicates that variable \(x_j\) was used for the split at node \(t\)
The larger the value, the more the variable is read as having contributed to the classification

The Gini coefficient stands in for entropy

Onohara's doctoral thesis makes this explicit, writing that the Gini coefficient in random forest is a substitute for entropy, used to compute the importance of feature variables — here, vocabulary items — in classification. Gini impurity and information gain are different measures, but both sit on the same idea: measuring how far the uncertainty falls by splitting. That is why Perspective 5 (information theory) in the seven perspectives carries a section headed “a decision tree splits on how much information is gained”. Though the method belongs to Perspective 4, the variable-importance part of it runs on the ruler of information theory.

The definition of importance differs from paper to paper

The three reports on the upper Ibi River basin (the 2012 research report, “Types and geographical distribution of vocabulary in the upper Ibi River basin”, and the doctoral thesis) all use MeanDecreaseGini, that is, importance based on the decrease in impurity above. The survey on statistics education (2013), by contrast, explains it as noise being given to one of the variables, with the importance being the normalized average, over all decision trees, of the difference between the impurity under noise and the correct impurity — which is a description of a different family of importance measure, one that perturbs a variable and watches how far accuracy falls. Under the same method name, which importance is being read changes the meaning of the result.

6How it is used in this research

Three settings. The first two to read variable importance, the last to draw a map.

(1) Finding the vocabulary that divides the dialect phylogeny

  1. Do the phylogenetic estimation first　On the basis of the basic vocabulary reported by Yamada (1978, 1980), phylogenetic estimation is carried out with NeighborNet over the 21 sites of the upper Ibi River basin plus Tokyo and Kyoto (see Phylogenetic networks, in Japanese). Branch support is obtained from 1000 bootstrap replicates.
  2. Turn the branch groupings into labels　The groupings obtained are coded into six: reference type (Tokyo, Kyoto, Kinomoto), Tokuyama (Kadonyū, Tonyū, Tsuka, Hazehara, Yamate, Kami-Kaiden, Hongō, Shimo-Kaiden), Sakauchi (Kawakami, Hirose, Sakamoto), Fujihashi-Kuze (Higashi-Yokoyama, Nishi-Tsugumi, Higashi-Tsugumi, Hisaka, Soto-Tsugumi), Ozu-Tsurumi (Ozu, Tsurumi), and periphery (Imajō, Ikeda).
  3. Drop columns　Words that correspond to both Tokyo and Kyoto, and words containing a missing-data symbol at even one settlement, have the column itself deleted, since a column showing the same value throughout is not taken into the analysis.
  4. Grow the forest　The number of decision trees per run is 500, and this is repeated 100 times to obtain the distribution of mean decrease in Gini. The figure caption records rf. 23cases, 37vars, loop=100 and the random seed seed = 200.
  5. Set the top words against the correspondence analysis　The items that came out high in importance were grease, good, bite, fish, correct, they, he, sit and lie. These are set against the characteristic words extracted by correspondence analysis, and the overlaps confirmed.

Figures and words are quoted from the body text of the printed paper and the doctoral thesis. The target is 23 cases × 37 variables.

(2) Seeing whether the words in free-text answers differ by background

In the survey on statistics education, a 38-question questionnaire was administered to 303 students taking a data science course (21 December 2012, three seminar rooms in the Information Media Building of the Kyotanabe campus, Doshisha University, self-administered), and the free-text questions were put through morphological analysis. Characteristic words were extracted as unigrams and bigrams over four parts of speech: nouns, verbs, adjectives and adverbs. The external criterion is a supplementary question on which stream of class the respondent was in at high school, splitting science from non-science. The number of decision trees is 500. The result was that the word “データサイエンス” (data science) appeared characteristically in the answers of students from a science background, while the bigrams “理解”–“できる” (understand – be able to) and “説明”–“ほしい” (explain – would like) appeared more often among those from other backgrounds.

This paper is inconsistent about what the number 500 refers to

In its description of the method, the paper on statistics education writes that 500 decision trees were generated and random forest carried out. On the following page, however, having cited earlier work (Kin & Murakami 2007) that repeated random forest 100 times and took the average, it states that the 500 repetitions of random forest in the present study are a reasonable number. The same 500 is written in a way that reads both as the number of trees and as the number of repetitions.

On the dialect side the two are kept clearly apart: the number of decision trees per run is 500 and this is repeated 100 times. Here the printed wording is simply presented as it stands; no judgment is made as to which is correct.

(3) Estimating land suitable for growing wine grapes

A collaborative study led by Nobusuke Iwasaki, with Onohara as third author. Over the 1104 tertiary mesh cells of the Chikuma River Wine Valley (eastern district) special zone, the locations of wine grape plots were established by field survey and interview and used as the response variable, with terrain, climate, geology and land use as explanatory variables. Since only 44 mesh cells contain a plot, the cells without one are downsampled. Random forest was applied as the machine learning model and logistic regression as the linear regression model, and the estimates were output as maps.

SettingLabelsVariablesTreesOutput wanted
Dialect phylogenetic classificationPhylogenetic branches (6 groups)37 vocabulary items500 × 100 runsTop words by Gini decrease
Free-text answers on statistics educationScience / non-scienceunigrams, bigrams500Characteristic words
Estimating suitable landPlot present / absentTerrain, climate, geologynot statedMap of suitable land

“Not stated” indicates that no mention of the number of trees could be found in the abstract. Nothing is supplied by guesswork.

7Limits — what the method cannot say

Landing often and landing for the right reason are different things.

Similar F1 scores, different maps

The study on suitable land is itself the example. On the data used for training, the F1 score was 0.67 for random forest and 0.62 for logistic regression. The difference is small. Yet the estimated maps differed greatly. Logistic regression estimated land at high elevations as suitable, whereas the evaluation by random forest did not include those areas, as the study reports.

That one evaluation score is close is no evidence that two methods are saying the same thing. Where the deliverable is a map in particular, the conclusion is the spatial arrangement of where the suitable land lies, not a single summarized number. Note too that this F1 score was computed on the data used for training, and does not show how either method lands on unseen mesh cells.

Variable importance says only what can be used to tell groups apart, not what is at work

In a preliminary analysis in the same study, the contribution of the “other agricultural land” category from the National Land Numerical Information was highest under both random forest and logistic regression. This was judged not to indicate a property of land suitable for cultivation but to reflect the clustered siting of agricultural land, and the analysis was redone with the land-use variables removed.

A variable with high importance is a variable that predicts the label well. Whether it explains a property of the subject has to be judged outside the method. Here the analyst made that judgment and acted on it by dropping the variables.

Gini-based importance is biased by the type of the variable

Importance based on the decrease in impurity is not even-handed between variables that can take many values and variables that differ in the coarseness of their scale. Strobl et al. (2007) showed that this importance is unreliable in situations where the predictor variables vary in their scale of measurement or their number of categories, and offered a solution using subsampling without replacement. In a design that mixes continuous and categorical variables, the ranking itself has to be suspected of being a by-product of the method.

On this point, “Types and geographical distribution of vocabulary in the upper Ibi River basin” records that the check was made with another importance measure: random forest was run not only with the Gini coefficient but with a different method of determining variable importance, and the words that came out high as characteristic words agreed with the result from the Gini coefficient. That all the variables are binary vocabulary data of the same type also works, in this case, in the direction of making bias less likely.

“Does not overfit” cannot be written as a flat statement

The paper on statistics education contains the sentence that random forest is said not to overfit (Breiman, 2001). What the original showed is a more limited claim: as the number of trees increases, the generalization error converges almost surely to some limit — that is, it does not diverge — and the upper bound on that limit is set by the strength of the individual trees and the correlation between them.

So overfitting caused by adding too many trees does not occur. But there is no guarantee that the limit converged to is low. Where labels carry much error, where the sample is small, or where only a very few variables are informative, the limit itself can remain high. Adding trees and not fitting the data too closely are separate matters.

What 100 repetitions removes is only the jitter of the random draws

In the dialect work the forest is rebuilt 100 times and importance is shown as the distribution of the mean decrease in Gini. That is why the figures are drawn as box plots rather than points. This evens out the fluctuation in ranking that comes from how the random numbers fall. But that is only the spread obtained when the same data are put through the same procedure. It says nothing about what would have come out on top had the sample been a different 23 settlements. Increasing the repetitions does not reduce the uncertainty of the estimate itself.

How the labels are made decides half the answer

In the dialect work, the classification labels given to random forest are themselves the result of the preceding phylogenetic estimation. What the procedure answers is therefore “which words best reproduce the divisions the phylogenetic estimate created”, not “how the settlements really divide”. Had a different grouping been taken at the phylogeny stage, the words coming out on top would change too. The study on suitable land has the same structure: the model is built taking places that currently hold plots as suitable, while the paper itself states that a place without a plot at present is not necessarily unsuitable for cultivation.

8Sources and data

Onohara's reports in which this method is used are as follows. Affiliations are as recorded at the time of publication in each case.

References for the method

  • Breiman, L. (2001) Random forests. Machine Learning, 45(1), 5–32. doi:10.1023/A:1010933404324
  • Breiman, L., Friedman, J. H., Olshen, R. A. & Stone, C. J. (1984) Classification and Regression Trees. Wadsworth, Belmont, California.
  • Strobl, C., Boulesteix, A.-L., Zeileis, A. & Hothorn, T. (2007) Bias in random forest variable importance measures: Illustrations, sources and a solution. BMC Bioinformatics, 8, 25. doi:10.1186/1471-2105-8-25
  • Kin, M. & Murakami, M. (2007) Identifying the writer of a text by the random forest method. Proceedings of the Institute of Statistical Mathematics, 55(2), 255–268.

In the reference list of the paper on statistics education, the bibliographic entry for Breiman, Friedman, Olshen and Stone spells Friedman as “Freidman”. The spelling of the original work is used here.

Which perspective this method belongs to

Random forest assumes neither the distribution the data follow nor the form of the error. It takes making the loss small as its only goal, and improves how it lands on data not yet seen by averaging predictors. In handling prediction without setting up a probability model, it belongs to Perspective 4 (learning theory, risk minimization) in Reading the seven perspectives in equations. Where LOO cross-validation, under the same perspective, closes the gap with expected risk by measurement, this one narrows it by lowering the variance. The variable-importance part alone, however, is measured on the ruler of Perspective 5 (information theory), the decrease in impurity.

This page sets out, for readers in the same field, a method Onohara uses in actual research. Every figure is quoted from the body text of printed papers, abstracts and the doctoral thesis; no estimates or approximations are given.
The whole layout of where the methods sit is in Reading the seven perspectives in equations; which teaching session falls under which perspective is in Methods & Mathematics.