Decision Tree Learning & Bias-Variance Trade-Off

An Introduction into Machine Learning

Lukas Schmoigl

lukas.schmoigl@wifo.ac.at

Data Scientist at WIFO

Introduction

What do we even mean with learning?

What is Machine Learning?

  • Pattern recognition: abstraction of patterns and regularities from data
  • Predictive modelling: optimized prediction of outcome given a set of inputs
  • Broad range of methods and models
  • Methods are often a “black box” compared to estimating causal effects
  • Often used synonymously with artificial intelligence (AI)

Branches of Machine Learning

  • Supervised learning:
    • Data set contains outcomes
    • Algorithm optimizes parameters in the model for training data such that predictions are as “accurate” as possible in test data
    • e.g., decision trees, linear models with regularization term, neural networks, etc.
  • Unsupervised learning:
    • No predetermined outcome
    • Algorithm comes up with a systematization of the input data
    • e.g., principal component analysis, latent dirichlet analysis, clustering algorithms, etc.
  • Reinforcement learning:
    • Outcome is implicitly determined
    • Algorithm finds “accurate” outcome via reward function
    • e.g., robotic movement, gaming, etc.

Supervised Learning in a Nutshell

  • An outcome is to be predicted
    • Continuous outcome → regression problem
    • Discrete outcome → classification problem
  • Outcome for a set of input variables (features) is known (labelled/annotated)
  • Is split into training and test data
    • Model is fit into training data
    • Performance is evaluated in test data
    • Parameters are chosen to optimize performance
    • Model can be used to predict in new data

Uses of Machine Learning

  • Spam filter
  • Recommender systems
  • Optical character recognition
  • Natural language processing
  • Data imputation
  • Prediction models in science
  • Statistical profiling

Classification and Regression Trees

A simple and powerful algorithm to understand

CART

  • CART (Classification and Regression Trees) methodology by Leo Breiman (1984)
  • Algorithmically: Use of binary decision rules for dealing with classification and regression problems
  • Geometrically: Partitioning of the support space spanned by a set of predictors
  • Statistically: Assigning an outcome by fitting a very simple function (a piecewise constant) over partitions

Tree Graph and Partitioning of the Support Space

Tree Graph

Support Space

Tree Graph and Regression Line

Tree Graph

Regression Line

Classification Problem

  • For a discrete response, the underlying minimization problem can be written as:

\[ \min_{R_t} \left\{ \sum_{t=1}^{T} w_t \cdot G_{R_t} + C(\lambda, T) \right\} \]

    • \(R_t\) is the partition on the support corresponding to the \(t\)-th terminal node
    • \(T\) is the number of terminal nodes of the tree
    • \(w_t\) is the fraction of observations in the \(t\)-th terminal node
    • \(G_{R_t}\) is the Gini impurity for partition \(R_t\) / the \(t\)-th terminal node
    • \(C(\lambda, T)\) is some cost function, sometimes called a regularization term
    • (\(\lambda\) is the tuning parameter that decides the complexity of the model by adding cost)

Example of Gini Impurity

  • The Gini impurity is a measure of information given by \[ G = 1 - \sum_{j=1}^{J} p_j^2 \]
  • Where \(p_j\) is the fraction of class \(j\)
  • Looking at the first node from the classification tree from before, we obtain \[ G = 1 - 0.49^2 - 0.51^2 = 0.4998 \]
  • By splitting at the first node we get a weighted impurity of \[ G = 0.56*(1 - 0.37^2 - 0.63^2) + 0.44*(1 - 0.66^2 - 0.34^2) = 0.4585 \]
  • In the terminal nodes we end up with a weighted Gini impurity of: \[ G = 0.47*(1 - 0.32^2 - 0.68^2) + 0.06*(1 - 0.58^2 - 0.42^2) + ... = 0.4484 \]

Regression Problem

  • For a continuous response, the underlying minimization problem can be written as

    \[ \min_{R_t} \left\{ \; \sum_{t=1}^{T} \sum_{x_i \in R_t} (y_i - \overline{y}_{R_t})^2 \; + \; {C}(\lambda,T) \right\} \]

where \(\overline{y}_{R_t}\) is the mean of the variables in partition \(R_t\)

Algorithm I

  • How are the partitions \(R_t\) determined?
    • Beginning from the first node, each split is determined by the variable and value which minimizes the RSS (regression problem) or impurity (classification problem)
    • End up with the most complex tree explaining every data point
  • Pruning the tree
    • Pre-pruning: additional splits are created until cost of depth is too high
    • Post-pruning: complex tree is created and cut down to a size where cost is met
    • Post-pruning is preferred because stopping too early bears the danger of missing some split down the line

Algorithm II

  • How is the tuning parameter \(\lambda\) determined?
    • Employing cross-validation, we choose the parameter value which minimizes some prediction error in the test/validation data (more on that later)
  • Exact implementation of the algorithm differs
    • Different packages may use different impurity/information measures (e.g., entropy) and different cost functions/tuning parameters
    • e.g., rpart uses post-pruning where the complexity parameter cp regulates the minimum gain in \(R^2\) or minimum decrease of Gini impurity to create another node

Growing the Tree

Advantages and Drawbacks

  • Trees have many advantages
    • Easy to understand and very flexible
    • No theoretical assumptions needed
    • Computationally cheap
    • Automatic feature selection
    • No limitation in number of features
    • Do not necessarily discard observations
  • Drawbacks include
    • No immediate (causal) interpretation of decision
    • Algorithm is “greedy”
    • The curse of dimensionality

The Curse of Dimensionality

  • Volume of the support space increases exponentially with dimensions
    • Data points become dispersed in a high-dimensional space
    • Splits become very volatile
  • To mitigate the problem, random forest is used in practice

A Perfect Summary I

Synthetic Unemployment Data

synthetic_unemployment_data <- read_parquet("data/synthetic_unemployment_data.parquet")

set.seed(123)

data <- synthetic_unemployment_data |>
  mutate(
    train_index = sample(
      c("train", "test"),
      nrow(synthetic_unemployment_data),
      replace=TRUE,
      prob=c(0.75, 0.25)
    )
  )

train <- data |>
  filter(train_index=="train")

test <- data |>
  filter(train_index=="test")
target_high target_low region_1 promised_employment benefits benefits_amount social_security sex age education family_situation nationality disability nace1 job_sector asylum children age_youngest_child migrational_background employment_1m employment_unsubsidized_1m unemployment_1m out_of_labor_force_1m employment_3m unemployment_3m out_of_labor_force_3m employment_6m unemployment_6m out_of_labor_force_6m employment_1y unemployment_1y out_of_labor_force_1y employment_2y unemployment_2y out_of_labor_force_2y days_employment_unsubsidized_10j days_unemployment_10j days_out_of_labor_force_insured_10j days_employment_unsubsidized_5j days_unemployment_5j days_out_of_labor_force_insured_5j days_employment_unsubsidized_2j days_unemployment_2j days_out_of_labor_force_insured_2j days_to_last_job income_last_job employment_subsidy_1j qualification_subsidy_1j support_subsidy_1j employment_subsidy_4j qualification_subsidy_4j support_subsidy_4j contact_pes_6m contact_pes_2j job_mediation_6m job_mediation_2j regional_unemployment regional_long_time_joblessness regional_seasonal_unemployment regional_promise_employment regional_gdp regional_job_openings train_index
unsuccessful successful 409-Linz 0 Keine NA 0 M 17 Pflichtschulausbildung Ledig Russland - Öffentl. Verwaltung, Verteidigung, SV Produktionsberufe Konventionsflüchtling 0 NA 1. Generation 0 0 0 1 0 1 0 0 0 1 0 0 1 0 0 1 34 18 3602 34 18 1775 0 0 731 762 774 0 0 0 0 0 0 0 0 0 0 0.0786348 0.3696403 0.0657192 0.0704333 52400 0.2278938 train
unsuccessful successful Andere 1 NH 23.20 0 M 29 Lehrausbildung Ledig Österreich A-Laut AMS Bau Produktionsberufe ohne ASYL 0 NA Kein Migrationshintergrund 0 0 1 0 1 0 0 0 1 0 0 1 0 0 1 0 335 2257 386 0 1463 336 0 671 0 2331 280 1 0 0 1 1 0 1 6 1 1 0.0600450 0.2943468 0.2819971 0.3153480 29400 0.8180097 train
unsuccessful successful Andere 0 NH 33.26 0 M 26 Lehrausbildung Verheiratet Österreich - Beherbergung und Gastronomie Dienstleistungsberufe ohne ASYL 0 NA Kein Migrationshintergrund 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 2192 1243 46 1127 701 5 359 374 3 139 2592 0 0 0 0 0 0 4 9 1 1 0.0525828 0.1586341 0.2133195 0.2889534 46000 0.4919413 train
unsuccessful unsuccessful 900-Wien 0 NH 11.69 0 M 33 Hoehere Ausbildung Ledig Deutschland - Gesundheits- und Sozialwesen Produktionsberufe ohne ASYL 0 NA 1. Generation 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 396 1159 1630 382 982 168 0 731 0 940 712 0 1 0 0 1 0 3 12 0 1 0.1495503 0.4561777 0.0597223 0.0440014 49600 0.3659622 train
unsuccessful unsuccessful 900-Wien 0 NH 23.31 0 M 32 Pflichtschulausbildung Ledig Österreich - Sonst. wirtschaftliche DL Dienstleistungsberufe ohne ASYL 0 NA Kein Migrationshintergrund 0 0 1 0 0 1 0 0 1 0 0 1 0 1 0 0 975 1524 1179 366 889 804 82 639 0 527 1094 0 1 1 1 1 1 2 8 0 0 0.1495503 0.4561777 0.0597223 0.0440014 49600 0.3659622 train
unsuccessful unsuccessful 900-Wien 1 ALG 44.65 0 M 55 Lehrausbildung Ledig Österreich - Beherbergung und Gastronomie Saisonberufe ohne ASYL 0 NA Kein Migrationshintergrund 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 0 3623 35 22 1796 33 22 697 33 22 31 3641 0 0 0 0 0 0 1 1 0 0 0.1495503 0.4561777 0.0597223 0.0440014 49600 0.3659622 train
unsuccessful unsuccessful Andere 0 NH 28.89 0 M 58 Pflichtschulausbildung Ledig Polen A-Laut AMS Gesundheits- und Sozialwesen Produktionsberufe ohne ASYL 0 NA 1. Generation 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 322 2874 351 0 1461 350 0 588 145 2053 1269 0 0 0 0 0 0 3 8 0 0 0.0659340 0.3625010 0.1338427 0.1111248 32600 0.3064870 train

Fitting Trees with RPART

tree <- rpart(
  target_low ~ days_unemployment_2j + age + days_to_last_job,
  data = train |> select(-train_index, -target_high),
  cp = 0.007
  )

tree
n= 4830 

node), split, n, loss, yval, (yprob)
      * denotes terminal node

 1) root 4830 2356 unsuccessful (0.4877847 0.5122153)  
   2) days_to_last_job< 409.5 3183 1270 successful (0.6010053 0.3989947)  
     4) age< 53.5 2804 1017 successful (0.6373039 0.3626961)  
       8) age>=18.5 2563  878 successful (0.6574327 0.3425673)  
        16) days_to_last_job< 116.5 1873  581 successful (0.6898025 0.3101975) *
        17) days_to_last_job>=116.5 690  297 successful (0.5695652 0.4304348)  
          34) days_unemployment_2j< 515.5 567  215 successful (0.6208113 0.3791887) *
          35) days_unemployment_2j>=515.5 123   41 unsuccessful (0.3333333 0.6666667) *
       9) age< 18.5 241  102 unsuccessful (0.4232365 0.5767635) *
     5) age>=53.5 379  126 unsuccessful (0.3324538 0.6675462) *
   3) days_to_last_job>=409.5 1647  443 unsuccessful (0.2689739 0.7310261) *
rpart.plot(tree, box.palette = "RdBu", nn = FALSE, type = 1)

Bias-Variance Trade-Off

Connecting to statistical theory

Root Mean Squared Error

  • For a regression problem, RMSE is typically used: \[ RMSE = \sqrt{\frac{1}{n}\sum_{i=1}^{n}(y_{i} - \hat{y}_{i})^{2}} \]
  • Or alternatively the (adjusted) \(R^2\): \[ R^2 = 1 - \frac{\sum_{i=1}^{n}({y_i}-\hat{y_i})^2}{\sum_{i=1}^{n}(y_i-\bar{y})^2} \]

Bias–Variance Trade-Off

  • The mean squared error \(MSE\) of a prediction can be written as:

\[ MSE(y, \hat{f}(x)) = \mathbb{E}\left[(y - \hat{f}(x))^2\right] \]

  • Where \(y = f(x) + \epsilon\) is the true data generating process and \(\mathbb{V}[\epsilon] = \sigma^2\) and \(\mathbb{E}[\epsilon] = 0\)
  • And \(\hat{f}(x)\) is the function predicting \(y\) given predictors \(x\)

\[ MSE(y, \hat{f}(x)) = \underbrace{(\mathbb{E}[f(x) - \hat{f}(x)])^2}_{\text{bias}} + \underbrace{\mathbb{E}[\hat{f}(x) - \mathbb{E}(\hat{f}(x))]^2}_{\text{variance}} + \underbrace{\mathbb{E}[(y - f(x))^2]}_{\text{irreducible error}} = \]

\[ = \underbrace{\mathrm{bias}^2 + \mathrm{variance}}_{\text{reducible error}} + \sigma^2 \]

Trade-Off

  • It is possible to specify \(\hat{{f}}(x)\) in such a way that introduces a bias but reduces the variance, so that the \(MSE\) reduces
  • Notice that this is well in line with what we know from the theory of the linear model
  • To exploit this trade-off in a linear model we can add a regularization term

Ridge Regression and LASSO

  • If we introduce the term \(\lambda \cdot || \beta ||_2\) into the well-known minimization task of a linear model, this is called ridge regression

    \[\widehat{\beta}_{RIDGE} = \min_\beta \left\{ || y - X\beta ||_2 + \lambda \cdot || \beta ||_2 \right\}\]

  • If we use the penalty \(\lambda \cdot || \beta ||_1\), we get the LASSO estimator
  • As a result, the coefficients of our parameters (and in many cases the \(MSE\)) shrink towards zero

Properties of Shrinkage Estimators

  • This can also be used as a method for variable selection
    • Coefficients of variables with low predictive power shrink close to zero (\(\widehat{\beta}_{RIDGE}\)) or to zero (\(\widehat{\beta}_{LASSO}\))
  • Introducing downward bias into coefficients \(\mathbb{E}\left[\widehat{\beta}_{RIDGE}\right] < \beta\)
  • For large \(k\) and fixed \(n\) we often times observe \(MSE(y, \hat{f}_{RIDGE}(x)) < MSE(y, \hat{f}_{OLS}(x))\)
  • For sample size \(n \to \infty\) and fixed number of coefficients \(k\) it holds that \(\widehat{\beta}_{RIDGE} = \widehat{\beta}_{OLS}\)

Coefficient Shrinkage

regularization term \(\lambda\) =