Lecture 5: Trees and forests

Let \((\mathcal X, \mathcal F)\) and \((\mathcal Y, \mathcal E)\) be measurable spaces and consider the supervised learning problem corresponding to the product space \((\mathcal X \times \mathcal Y, \mathcal F \otimes \mathcal E, P)\) where \(P\) is some probability measure.
A tree model \(T\) consists of some finite system \(\mathcal B \subseteq \mathcal F\) of \(\mathcal F\)-measurable sets and a function \(f: \mathcal B \smallsetminus \{\mathcal X\} \rightarrow \mathcal B\) that fulfill the following conditions:

• \(\mathcal X \in \mathcal B\) (Root node)
• \(\forall B_1, B_2 \in \mathcal B : B_1 \cap B_2 = \emptyset \vee B_1 \subseteq B_2 \vee B_2 \subseteq B_1\) (Nodes cannot partially overlap)
• \(\forall B_1, B_2 \in \mathcal B : B_1 \subseteq B_2 \Rightarrow B_2 \smallsetminus B_1 \in \mathcal B\) (Splitting a node always produces two nodes)
• \[ \forall B \in \mathcal B \exists d_B \in \mathbb N_{0} : f^{d_B}(B) := \underbrace{f \circ \cdots \circ f}_{d_B \text{ times}}(B) = \mathcal X \] We say that \(d_B\) is the depth of the node \(B\).

Given a tree model \(T = (\mathcal B, f)\), we say that \[ \mathcal A = \mathcal A(T) = \{A \in \mathcal B \mid f^{-1}(\{A\}) = \emptyset\} \] is the set of leaves (or terminal nodes) for the tree.

• \(T\) tree model
• Data \(\mathcal D_n = (X_i, Y_i)_{i = 1, \ldots, n}\).

In the case of regression, the emprical squared loss-minimizing decision function produced by the tree model is \[ \hat{m}_n(x) = \sum_{A \in \mathcal A} \mathbb 1{x \in A}\left(\frac{\sum_{i=1}^n \mathbb 1\{X_i \in A\}Y_i}{\sum_{i=1}^n \mathbb 1\{X_i \in A\}}\right). \] In the case of classification, the empirical classification error minimizing decision function is \[ \hat{m}_n(x) = \sum_{A \in \mathcal A} \mathbb 1\{x \in A\}\cdot \textrm{argmax}_{y \in \mathcal Y}\left(\sum_{i=1}^n \mathbb 1\{X_i \in A\}\mathbb 1\{Y_i = y\}\right). \]

Note that a decision function stemming from a decision tree is uniquely defined by the leaves of the tree.

• Start with the whole space \(\mathcal X\) (=root node).
• Pick variable \(j=1,\dots,p\) and split-point \(c \in \textrm{supp}(X_j)\) that gives the best loss improvement.
• Split \(\mathcal X\) into two nodes according to variable and split point.
• Next, if no stopping rule applies, both nodes (otherwise only one or none) are split into two further nodes.
• Continue until stopping rule applies to all nodes.

Start with \(\mathcal X\) as initial node for splitting.

• Input: node \(B\subseteq \mathcal X\)
• For every dimension \(j=1,\dots,p\) and every point \(s_j\in \{x_j| \exists\ x_1,\dots,x_{j-1},x_{j+1},\dots,x_p\ \text{with} (x_1,\dots,x_p)\in B\}\) define \[B_1(j,s_j)=\{(x_1,\dots,x_p)\in B| \ x_j \leq s_j\}, \quad B_2(j,s_j)=\{(x_1,\dots,x_p)\in B| \ x_j > s_j\}.\]
• We pick the minimizer \[ (j^\ast,s^\ast)= \arg\min_{j,s} Q_n(B_1(j,s_j)) + Q_n(B_2(j,s_j)) \]
• Each of the new nodes \((B_1(j^\ast,s^\ast),B_2(j^\ast,s^\ast))\) is further split as long as stopping criterion does not apply.

For regression the most common loss function is the squared loss:

• Squared loss: \(Q_n(B_l)= \sum_{i: X_i \in B_l} (Y_i - \overline Y_i(B_l))^2\)
  • \(\overline Y_i(R_l)= \frac 1 {|R_l|}\sum_{i: X_i \in B_l}Y_i,\) \(|B_j|=\#\{i: X_i\in R_j\}\).

In the classification case, define \(\hat p_{lk}= \frac 1 {|B_l|} \sum_{i: X_i \in B_l} \mathbb 1(Y_i=k)\) (=the proportion of class \(k\) observation in \(B_l\))

Common loss functions are:

• Brier score: \(Q_n(B_l)= \sum_{i: X_i \in B_l} (Y_i - \overline Y_i(B_l))^2\) (=squared loss)
• Misclassification error: \(Q_n(B_l)= 1 - \max_{k}\hat p_{lk}\)
• Gini index: \(Q_n(B_l)= \sum_{k=1}^K \hat p_{lk}(1-\hat p_{lk})\)
• Entropy : \(Q_n(B_l)=-\sum_{k=1}^K \hat p_{lk}\log\hat p_{lk}\)

• The most common stopping criterion is specifying a min-node size, i.e. stop if \(|B_j|<c\). A common choice is \(c=5\).

• An alternative stopping criteria is the depth of \(B_j\), i.e., the number of parent nodes of \(B_j\).

Consider a tree model \(T = (\mathcal B, f)\). We say that a tree model \(T' = (\mathcal B', f')\) is a sub-tree if \(B' \subseteq \mathcal B\) and \(f = f'\) on \(\mathcal B'\). Note that we may abuse the notation and write \((\mathcal B', f)\) instead of \((\mathcal B', f')\).

Consider a tree \(\hat T_n\) with corresponding estimator \(\hat m_n^{\hat T_n}\). Given a parameter \(\alpha>0\), the \(\alpha\)-pruned tree is \[ \hat T_{n,\alpha} := \arg \min_{T\subseteq \hat T_n}\{\hat R_n(\hat m_n) + \alpha |T|\}, \] where \(|T|\) is the number of leaves of \(T\).

There are (at least) two major problems with decision trees

• Instability: Small variations in the data can lead to a very different tree

• Performance: The performance (measured via test error) is usually much weaker compared to other learning algorithms

• Given data \({(X_1,Y_1),\dots, (X_n,Y_n)}\), draw \(B\) bootstrap samples \(\tilde {\mathcal D}^{(b)}_n={(\tilde X^{(b)}_1,\tilde Y^{(b)}_1),\dots, (\tilde X^{(b)}_n,\tilde Y^{(b)}_n)}, b=1,\dots, B\), i.e., \(\tilde {\mathcal D}^{(b)}_n\) arises from \(\mathcal D_n\) by drawing \(n\) times with replacement.

• The bagging estimator is defined as

  • squared loss \(\rightarrow\) average: \(\hat m^{bagg}_n=\frac 1 B \sum_{b=1}^B \hat m_n(\tilde {\mathcal D}^{(b)}_n)\)
  • binary loss \(\rightarrow\) majority vote: \(\hat m^{bagg}_n(x)=\arg \max_{k\in {1,\dots K}} \#\{b: m_n(\tilde {\mathcal D}^{(b)}_n) (x)=k\}\)

• Note that \(\hat m^{bagg}_n\) is a stochastic estimator, even given \(\mathcal D_n\).

• Note: Usually, bagging is applied on non-pruned trees. (See it as an alternative way to reduce variance)

• As bagging random forest are an ensemble of decision trees.

• They add the following modification to bagging:

  • \(\texttt{mtry}\): Each time a node is split it is only done on a subset of size \(\texttt{mtry}\) of viable variables. I.e., each time you want to split a node, turn on a random generator and draw \(1\leq\texttt{mtry}<p\) viable variables from \(\{1,\dots,p\}\). Only those variables drawn are allowed to be considered for the next split.

• We denote the random forest estimator by \(\hat m^{rf}_n\). Note that \(\hat m^{rf}_n\), as \(\hat m^{bagg}_n\), is a stochastic estimator, even given \(\mathcal D_n\).

• Assume that we are given \(l\) estimators \(m_n(\mathcal D_n, U_1), \dots m_n(\mathcal D_n, U_l)\)

• Here, \(U_1,\dots, U_l\) are iid variables inducing the additional stochasticity of the estimators (e.g. through random forest or bagging).

• Assume that \(\hat m_n(\mathcal D_n, U_1), \dots \hat m_n(\mathcal D_n, U_l)\) have pairwise correlation \(\rho\) and variance \(\sigma^2\).

• We get \[\begin{aligned} \textrm{Var}\left (\frac 1 l \sum_{j=1}^l \hat m_n(\mathcal D_n, U_j)\right)&= \frac 1 {l^2} \sum_{jk} \textrm{Cov}(m_n(\mathcal D_n, U_j),m_n(\mathcal D_n, U_k))\\&=\frac 1 {l^2} \left( l\sigma^2+ (l^2-l)\rho\sigma^2\right)\\&= \rho \sigma^2 + \frac{1-\rho}{l}\sigma^2 \end{aligned}\]

• Meaning: Variance of an ensemble of trees is small the smaller the correlation between the trees.

  • The \(\texttt{mtry}\) parameter aims to make trees less alike and hence more uncorrelated.

• Consider \(m^\ast(x) = \sum_j^p \mathbb 1(x_j \leq 0)\) for large \(p\).
• For a perfect fit, a tree algorithm would have to grow a tree with depth \(p\), where each leaf is the result of splitting once with respect to each covariate.
• Hence, we end up with \(2^p\) leaves, which on average contain \(n/(2^p)\) data points.
• Even if all splits are optimal for \(2^p>n\), the tree will not be able to lead to a perfect decision rule.