Decision tree is a non-parametric supervised learning method used for classification and regression. Goal is to create a model that predicts the value of a target variable by learning simple decision rule inferred from data feature.

Motivation: Interpretability

We want to find best suit for data sets with “region” properties

Contrast decision tree and linear classifier

                           left - linear classifier                                    right- decision tree

Decision Tree Setup

• Set of possible instances X
  • Each instance $x\in X$ is a feature vector
• Set of possible labels Y
  • Y is discrete valued
• Unknown target function $f: X\to Y$
• Model/Hypothesis: $H=\{h|h:X\to Y\}$
• Each hypothesis h is a decision tree

Goal: Train/induce/learn a function h that maps instance to a label

In the model, 3 things are learned:

• Structure of the tree
• The threshold values ($\theta_i$)
• Values of the leaves

How to create decision tree

Procedure