11.3 BOOSTED REGRESSION TREES

11.3 BOOSTED REGRESSION TREES

Regression trees provide a simple way to map a $(K\times 1)$ vector of predictors $z_t=(z_{t1},z_{t2},...,z_{tK})\prime$ to some univariate outcome, $y_{t+1}$ . We provide here a brief description of such methods following Hastie, Tibshirani, and Friedman (2009) and Rossi and Timmermann (2015).

Each regression tree splits the sample space defined by the predictors into “flat spots,” so that the predicted value is modeled as a constant, $c_j$ , within each state, $S_j$ . If the sample is split into $J$ separate subregions or states, $S_1,S_2,\dots ,S_J$ , the fitted value from a regression tree, $g(z,{\theta }_J)$ , with J terminal nodes and parameters, ${\theta }_J=\{S_j,c_j{\}}_{j=1}^J$ , takes the form

$$g(z,{\theta }_J)=\sum _{j=1}^J{c}_{j}1(z\in S_j),\text{\hspace{1em}(11.12)}$$

where $1(z\in S_j)$ is an indicator variable that equals 1 if $z\in S_j$ and is 0 otherwise. Implementation of (11.12) requires deciding on which predictor variables to use to split the sample space and which split points to use. For example, if $J=2$ , a forecast may be based on a split of the predictors according to whether a particular variable takes a high or a low value.

Given a set of split points, $S_1,\dots ,S_J$ , the constant term, $c_j,$ is easily estimated. Under MSE loss, the estimated constant, ${\hat{c}}_j$ , is simply the sample average of $y_{t+1}$ state $S_j$ :

$${\hat{c}}_j=\frac{1}{{\sum }_{t=1}^{T-1}1(z_t\in S_j)}\sum _{t=1}^{T-1}{y}_{t+1}1(z_t\in S_j).\text{\hspace{1em}(11.13)}$$

Split points are more difficult to determine, particularly if the list of predictors, $z_{kt},k=1,\dots ,K$ , is large. Often a sequential algorithm is used to split the sample space. For a given starting model, predictor, $z_k$ , and split point s , the algorithm would construct half-planes,

$$S_1(k,s)=\{z|z_k\le s\}\mathrm{and}{S}_2(k,s)=\{z|z_k>s\},$$

so as to minimize the sum of squared residuals:

$$\underset{k,s}{\min }\left[\underset{c_1}{\min }\sum _{z_t\in S_1(k,s)}(y_{t+1}-c_1{)}^2+\underset{c_2}{\min }\sum _{z_t\in S_2(k,s)}(y_{t+1}-c_2{)}^2\right].\text{\hspace{1em}(11.14)}$$

Given choices of k and s the fitted values, ${\hat{c}}_1$ and ${\hat{c}}_2,$ , are then

$$\begin{array}{l}{\hat{c}}_1=\frac{1}{{\sum }_{t=1}^{T-1}1\left(z_t\in S_1(k,s)\right)}\sum _{t=1}^{T-1}{y}_{t+1}1\left(z_t\in S_1(k,s)\right),\\ {\hat{c}}_2=\frac{1}{{\sum }_{t=0}^{T-1}1\left(z_t\in S_2(k,s)\right)}\sum _{t=1}^{T-1}{y}_{t+1}1\left(z_t\in S_2(k,s)\right).\end{array}\text{\hspace{1em}(11.15)}$$

The best pairing of splitting variables and split points $(k,s)$ used in the first iteration can be determined by searching through each of the predictors, $k=1,\dots ,K$ . Given the best partition from the first step, the data can next be partitioned into two additional states and the splitting process is repeated for each of the subsequent partitions. Predictor variables that are never used to split the sample space do not influence the forecast so the choice of splitting variable is similar to variable selection. This process is known as boosting.

Boosted regression trees are very flexible and can capture local features of the data that linear models may overlook. Boosting methods can be used to identify which of a large number of possible variables help to improve forecasting performance. They build on the idea that combining a series of simple prediction models can lead to more accurate forecasts than those available from any individual model.

A boosted regression tree is simply the sum of individual regression trees:

$$f_B(z)=\sum _{b=1}^B{g}_b(z;{\theta }_{J,b}),\text{\hspace{1em}(11.16)}$$

where $g_b(z;{\theta }_{J,b})$ is a regression tree of the form (11.12) used in the bth boosting iteration and B is the number of boosting iterations. Given the previous model, $f_{B-1}(z)$ , the subsequent boosting iteration searches for parameters ${\theta }_{J,B}=\{S_{j,B},c_{j,B}{\}}_{j=1}^J$ for

the next tree to solve a problem of the form

$${\hat{\theta }}_{J,B}=\arg \underset{{\theta }_{J,B}}{\min }\sum _{t=1}^{T-1}{\left[y_{t+1}-(f_{B-1}(z_t)+g_B(z_t;{\theta }_{J,B}))\right]}^2.\text{\hspace{1em}(11.17)}$$

For a given set of state definitions ${(}^{\mathfrak{c}}{\mathrm{splits}}^{\mathfrak{s}}),S_{j,B},j=1,\dots ,J$ , the optimal constants, $c_{j,B}$ , in each state are derived iteratively by solving the problem

$${\hat{c}}_{j,B}=\arg \underset{c_{j,B}}{\min }\sum _{z_t\in S_{j,B}}{\left[e_{t+1,B-1}-c_{j,B}\right]}^2,\text{\hspace{1em}(11.18)}$$

where $e_{t+1,B-1}=y_{t+1}-f_{B-1}(z_t)$ is the forecast error remaining after $B-1$ boosting iterations. The solution to this problem is the regression tree that most reduces the average of the squared residuals ${\sum }_{t=0}^{T-1}{e}_{t+1,B-1}^2$ and ${\hat{c}}_{j,B}$ is the mean of the residuals in the j th state.

Boosting algorithms iteratively reweight data used in the initial fit by adding new trees in a way that increases the weight on observations modeled poorly by the existing collection of trees. However, since the approach is sequential and successive splits are performed on fewer and fewer observations, this increases the risk of fitting idiosyncratic data patterns. Furthermore, there is no guarantee that the sequential splitting algorithm leads to the globally optimal solution.

Shrinkage in this context means that each iteration of the model moves only a small fraction of the optimal step of the learning algorithm

$$f_B(z_t)=f_{B-1}(z_t)+\delta \sum _{j=1}^J{c}_{j,B}1(z_t\in S_{j,B}),\text{\hspace{1em}(11.19)}$$

where δ is a small number such as $\delta =0.001$ . Subsampling means that each tree is fitted on a randomly drawn subset of the training data. Fitting the tree only on a subset of the data reduces the risk of overfitting or getting stuck in a local optimum. Finally, by minimizing mean absolute errors, $\begin{array}{r}{T}^{-1}{\sum }_{t=0}^{T-1}|y_{t+1}-f(z_t)|\end{array}$ the algorithm fits the conditional median of $y_{t+1}$ rather than the conditional mean used under MSE loss. The latter is often found to place too much weight on outliers in the data.

Forecasts from the boosted regression trees are simple to generate. The boosted regression tree is first estimated using data from $t=1,\dots ,T$ . Then a forecast of ${\gamma }_{T+1}$ is based on the model estimates and the value of the predictor variable at time $T,z_T$

Rossi and Timmermann (2015) use boosted regression trees to predict time variations in the US equity premium. They find strong evidence that linear prediction models are misspecified, whereas boosted regression trees manage to pick up nonlinearities. Out-of-sample evidence suggests that the boosted regression trees yield better out-of-sample forecasts of both stock returns and stock market volatility than a range of benchmark models. Bai and Ng (2009) is another application of this method to diffusion indexes and macro data.