Machine Learning and Applications - Decision Trees and Ensembling Methods¶

David Picard¶

École des Ponts ParisTech¶

david.picard@enpc.fr¶

Region based classification¶

region

  1. Memorizing all regions is cumbersome
    • R 1 = {(a 1 , b 1 , c 1 , d 1 ), y 1 }
    • R 2 = {(a 2 , b 2 , c 2 , d 2 ), y 2 }
    • ...
  1. Classification requires to check all regions
for region Ri in all regions:
    if x ∈ Ri:
      return yi

Tree based equivalent¶

tree1

tree2

tree3

Tree representation¶

dt

Decision Tree¶

A decision tree is a hierarchical classifier with a tree structure where each node partitions the feature space along a specified component (Breiman et al, 1984).

Leo Breiman (1928 - 2005)

leo

Growing the tree¶

  1. Tree($\mathcal{S} = \{\mathbf{x}_i, y_i\}$):
  2. $\quad$if $\vert\mathcal{S}\vert < T$:
  3. $\quad\quad$return $\text{Leaf}(\text{argmax}_c\sum_i 1_{y_i=c}$)
  4. $\quad d^\star, \theta^\star = \text{argmax}_{d,\theta} \text{Gain}(\mathcal{S}, d, \theta)$
  5. $\quad T_1 = \text{Tree}(\{\mathbf{x}_i, y_i\}\in\mathcal{S} \vert \mathbf{x}_i[d^\star] < \theta^\star)$
  6. $\quad T_2 = \text{Tree}(\{\mathbf{x}_i, y_i\}\in\mathcal{S} \vert \mathbf{x}_i[d^\star] \geq \theta^\star)$
  7. $\quad$return $\text{Node}(d^\star, \theta^\star, T_1, T_2)$

Gain measure¶

Proportion of class $k$ in $\mathcal{S}$

$$ p_k(\mathcal{S}) = \frac{1}{\vert\mathcal{S}\vert} \sum_{y_i = k} 1 $$

Prediction for $\mathcal{S}$

$$f(\mathcal{S}) = \text{argmax}_k p_k(\mathcal{S}) $$

0-1 loss

$$C(\mathcal{S}) = \frac{1}{N}\sum_i (1 - \delta(y_i, f(\mathbf{x}_i)) = 1 - p_{f(\mathcal{S})}(\mathcal{S})$$

How much did the error decrease with the split on component $d$ at threshold $\theta$ that leads to subsets $\mathcal{S}_1$ and $\mathcal{S}_2$:

$$ \text{Gain}(\mathcal{S}, d, \theta) = C(\mathcal{S}) - \left[ \frac{N_1}{N}C(\mathcal{S}_1) + \frac{N_2}{N}C(\mathcal{S}_2) \right] $$

Choose $d, \theta$ with maximal gain

Information Gain¶

Other popular gain measures:

  • Entropy

$$C(\mathcal{S}) = -\sum_k p_k(\mathcal{S})\log p_k(\mathcal{S}) $$

  • Gini index

$$C(\mathcal{S}) = -\sum_k p_k(\mathcal{S})(1- p_k(\mathcal{S}))$$

Small example¶

In [8]:
X = np.random.rand(75, 2)
y = 1.*(X[:,1] > X[:,0])
In [9]:
plt.scatter(X[:,0], X[:,1], c=y)
Out[9]:
<matplotlib.collections.PathCollection at 0x7b530f18ffa0>
No description has been provided for this image
In [10]:
def entropyGain(X, y, d, theta):
    if len(y) <= 1:
        return 0.
    p = y.mean()
    e = jax.scipy.special.entr(p)
    l = 1.*(X[:,d] < theta)
    p1 = (y * l).sum()/(l.sum()+1e-12)
    e1 = jax.scipy.special.entr(p1)
    r = 1-l
    p2 = (y * r).sum()/(r.sum()+1e-12)
    e2 = jax.scipy.special.entr(p2)
    return e - (l.sum()*e1 + r.sum()*e2)/len(y)
In [11]:
def findBestTheta(X, y, d, gain=entropyGain):
    n = len(y)
    best_g = -1.
    theta = None
    xx = jnp.sort(X[:,d])-1e-7
    for t in xx:
        g = gain(X, y, d, t)
        if g > best_g:
            best_g = g
            theta = t
    if theta == None:
        print('theta faillure!!')
    return theta, best_g
In [12]:
def findBestDTheta(X, y, gain=entropyGain):
    best_d = None
    theta = None
    best_g = -1
    for d in range(X.shape[1]):
        t, g = findBestTheta(X, y, d, gain)
        if g > best_g:
            best_d = d
            theta = t
            best_g = g
    if best_d is None:
        print('D failure!!')
    return best_d, theta
In [13]:
class BinaryClassificationTree():
    def __init__(self, X, y, gain=entropyGain, min_size=1):
        p = y.mean()
        if len(y) <= min_size or jax.scipy.special.entr(p) == 0.:
            self.label = 1.*(p>=0.5)
        else:
            self.label = None
            self.d, self.theta = findBestDTheta(X, y, gain)
            ind = 1.*(X[:,self.d] < self.theta) 
            if ind.sum() == 0 or ind.sum() == len(y):
                print('single split !!! {} {} {}'.format(ind, y, X))
            ind1 = ind.nonzero()
            X1 = X[ind1]
            y1 = y[ind1]
            ind2 = (1-ind).nonzero()
            X2 = X[ind2]
            y2 = y[ind2]
            self.T1 = BinaryClassificationTree(X1, y1, gain=gain, min_size=min_size)
            self.T2 = BinaryClassificationTree(X2, y2, gain=gain, min_size=min_size)
    def __call__(self, X):
        if self.label is not None:
            return self.label * jnp.ones(len(X))
        return jnp.concatenate([ self.T1([x]) if x[self.d] < self.theta else self.T2([x]) for x in X])
In [14]:
T = BinaryClassificationTree(X, y)
In [15]:
t = 50; tx = jnp.linspace(0, 1, t); ty = jnp.linspace(0, 1, t)
xv, yv = jnp.meshgrid(tx, ty, sparse=True); xv = xv.squeeze(); yv = yv.squeeze()
xx = jnp.array([[xx, yy] for yy in yv for xx in xv])
y_pred = jnp.array(T(xx)).reshape(t, t)
cmap = plt.get_cmap('PiYG')
levels=jnp.linspace(-1.5, .5, 10)
norm = matplotlib.colors.BoundaryNorm(levels, ncolors=cmap.N, clip=True)
plt.pcolormesh(xv, yv, -y_pred, shading='nearest', norm=norm);
plt.scatter(X[:,0], X[:,1], c=y)
Out[15]:
<matplotlib.collections.PathCollection at 0x7b52d4222f80>
No description has been provided for this image

Decision Trees¶

  • Interpretable

  • Fast

  • Handle categorical data

But

  • Poor accuracy

  • Unstable

  • Need a lot of examples

  • Finding the optimal tree is hard, growing is greedy

Unstable¶

In [10]:
y[6] = 1 - y[6]
T = BinaryClassificationTree(X, y)
In [11]:
t = 50; tx = jnp.linspace(0, 1, t); ty = jnp.linspace(0, 1, t)
xv, yv = jnp.meshgrid(tx, ty, sparse=True); xv = xv.squeeze(); yv = yv.squeeze()
xx = jnp.array([[xx, yy] for yy in yv for xx in xv])
y_pred = jnp.array(T(xx)).reshape(t, t)
cmap = plt.get_cmap('PiYG')
levels=jnp.linspace(-1.5, .5, 10)
norm = matplotlib.colors.BoundaryNorm(levels, ncolors=cmap.N, clip=True)
plt.pcolormesh(xv, yv, -y_pred, shading='nearest', norm=norm);
plt.scatter(X[:,0], X[:,1], c=y)
Out[11]:
<matplotlib.collections.PathCollection at 0x7fb5d6f7c310>
No description has been provided for this image

Generalization¶

Theorem: For a tree of $n$ nodes in dimension $d$ and for $m$ samples, we have with probability $\delta$

$$ R \leq R_e + \sqrt{\frac{(n+1)\log_2(d+3) + \log_2(2/\delta)}{2m}}$$

Exercise: What is the VC dimension of decision tree over $\{0, 1\}^d$ ?

Random Forest¶

Overcome DT instabilities by averaging $B$ randomized trees (Breiman, 2001)

  • Randomized training set $\mathcal{A}_b \subset \mathcal{A}$
  • Randomized components $\mathcal{x} \in \mathcal{X}_b \subset \mathcal{X}$

Final decision by majority vote: $f(\mathbf{x}) = \text{argmax}_d \left[\sum_b f_b(\mathcal{x})\right]_d$

  • Average value for regression

Limiting overfitting¶

Ensemble of classifier $h_1, \dots, h_K$, define margin function

$$ mg(\mathbf{x}, y) = \text{avg}_k \mathbb{1}[h_k(\mathbf{x}) = y] - \max_{j\neq y}\text{avg}_k \mathbb{1}[h_k(\mathbf{x}) = j] $$ (difference between true class vote and max false class vote)

Generalization error

$$ R = \mathbb{P}[ mg(\mathbf{x}, y) < 0 ] $$

Random forest: classifier drawn i.i.d. from a distribution of parameters $\Theta$

Theorem (Breiman, 2001): As the number of trees increases, for almost surely all sequences $\Theta_1, \dots$, the generalization error $R$ converges to

$$ \mathbb{P} \left[ \mathbb{P}_\Theta[ h_\theta(\mathbf{x}) = y ] - \max_{j\neq y}\mathbb{P}_\Theta[h_\theta(\mathbf{x}) = j] < 0\right] $$

R does not increase as the number of trees grows, limiting overfitting

In [12]:
class RandomForest():
    def __init__(self, X, y, nb_tree=25, p=0.5):
        self.trees = []
        n = len(y)
        k = int(p*n)
        for b in range(nb_tree):
            i = np.random.permutation(n)
            Xb = X[i[0:k], ...]
            yb = y[i[0:k]]
            DT = BinaryClassificationTree(Xb, yb)
            self.trees.append(DT)
    def __call__(self, X):
        y = []
        for DT in self.trees:
            y.append(DT(X))
        return 1.*(jnp.array(y).mean(axis=0))
In [13]:
T = RandomForest(X, y)
In [14]:
t = 20; tx = jnp.linspace(0, 1, t); ty = jnp.linspace(0, 1, t)
xv, yv = jnp.meshgrid(tx, ty, sparse=True); xv = xv.squeeze(); yv = yv.squeeze()
xx = jnp.array([[xx, yy] for yy in yv for xx in xv])
y_pred = jnp.array(T(xx)).reshape(t, t)
cmap = plt.get_cmap('PiYG')
levels=jnp.linspace(-1.5, .5, 10)
norm = matplotlib.colors.BoundaryNorm(levels, ncolors=cmap.N, clip=True)
plt.pcolormesh(xv, yv, -y_pred, shading='nearest', norm=norm);
plt.scatter(X[:,0], X[:,1], c=y)
Out[14]:
<matplotlib.collections.PathCollection at 0x7fb5ac716ce0>
No description has been provided for this image
In [15]:
t = 20; tx = jnp.linspace(0, 1, t); ty = jnp.linspace(0, 1, t)
xv, yv = jnp.meshgrid(tx, ty, sparse=True); xv = xv.squeeze(); yv = yv.squeeze()
xx = jnp.array([[xx, yy] for yy in yv for xx in xv])
y_pred = jnp.array(T(xx)).reshape(t, t)
cmap = plt.get_cmap('PiYG')
levels=jnp.linspace(-1.5, .5, 10)
norm = matplotlib.colors.BoundaryNorm(levels, ncolors=cmap.N, clip=True)
plt.pcolormesh(xv, yv, -1.*(y_pred>0.5), shading='nearest', norm=norm);
plt.scatter(X[:,0], X[:,1], c=y)
Out[15]:
<matplotlib.collections.PathCollection at 0x7fb5ac7b5870>
No description has been provided for this image
In [16]:
T = RandomForest(X, y, nb_tree=100, p=0.2)
In [17]:
t = 50; tx = jnp.linspace(0, 1, t); ty = jnp.linspace(0, 1, t)
xv, yv = jnp.meshgrid(tx, ty, sparse=True); xv = xv.squeeze(); yv = yv.squeeze()
xx = jnp.array([[xx, yy] for yy in yv for xx in xv])
y_pred = jnp.array(T(xx)).reshape(t, t)
cmap = plt.get_cmap('PiYG')
levels=jnp.linspace(-1.5, .5, 10)
norm = matplotlib.colors.BoundaryNorm(levels, ncolors=cmap.N, clip=True)
plt.pcolormesh(xv, yv, -y_pred, shading='nearest', norm=norm);
plt.scatter(X[:,0], X[:,1], c=y)
Out[17]:
<matplotlib.collections.PathCollection at 0x7fb5ac6463b0>