Copyright (c) 2015, 2016 Sebastian Raschka Li-Yi Wei

https://github.com/1iyiwei/pyml

MIT License

Python Machine Learning - Code Examples

Chapter 3 - A Tour of Machine Learning Classifiers

• Logistic regression
  • Binary and multiple classes
• Support vector machine
  • Kernel trick
• Decision tree
  • Random forest for ensemble learning
• K nearest neighbors

Note that the optional watermark extension is a small IPython notebook plugin that I developed to make the code reproducible. You can just skip the following line(s).

The use of watermark is optional. You can install this IPython extension via "pip install watermark". For more information, please see: https://github.com/rasbt/watermark.

Overview

• Choosing a classification algorithm
• First steps with scikit-learn
  • Training a perceptron via scikit-learn
• Modeling class probabilities via logistic regression
  • Logistic regression intuition and conditional probabilities
  • Learning the weights of the logistic cost function
  • Handling multiple classes
  • Training a logistic regression model with scikit-learn
  • Tackling overfitting via regularization
• Maximum margin classification with support vector machines
  • Maximum margin intuition
  • Dealing with the nonlinearly separable case using slack variables
  • Alternative implementations in scikit-learn
• Solving nonlinear problems using a kernel SVM
  • Using the kernel trick to find separating hyperplanes in higher dimensional space
• Decision tree learning
  • Maximizing information gain – getting the most bang for the buck
  • Building a decision tree
  • Combining weak to strong learners via random forests
• K-nearest neighbors – a lazy learning algorithm
• Summary

Choosing a classification algorithm

There is no free lunch; different algorithms are suitable for different data and applications.

First steps with scikit-learn

In the linear perceptron part, we wrote the models from ground up.

• too much coding

Existing machine learning libraries

• scikit-learn
• torch7, caffe, tensor-flow, theano, etc.

Scikit-learn

• will use for this course
• not as powerful as other deep learning libraries
• easier to use/install
• many library routines and data-sets to use, as exemplified below for main steps for a machine learning pipeline.

Iris dataset

Let's use this dataset for comparing machine learning methods

Setosa	Versicolor	Virginica

Loading the Iris dataset from scikit-learn.

Here, the third column represents the petal length, and the fourth column the petal width of the flower samples.

The classes are already converted to integer labels where 0=Iris-Setosa, 1=Iris-Versicolor, 2=Iris-Virginica.

Data sets: training versus test

Use different data sets for training and testing a model (generalization)

Data scaling

It is better to scale the data so that different features/channels have similar mean/std.

Training a perceptron via scikit-learn

We learned and coded perceptron in chapter 2. Here we use the scikit-learn library version.

The perceptron only handles 2 classes for now. We will discuss how to handle $N > 2$ classes.

Training a perceptron model using the standardized training data:

Modeling class probabilities via logistic regression

• $\mathbf{x}$: input
• $\mathbf{w}$: weights
• $z = \mathbf{w}^T \mathbf{x}$
• $\phi(z)$: transfer function
• $y$: predicted class

Perceptron

$ y = \phi(z) = \begin{cases} 1 \; z \geq 0 \\ -1 \; z < 0 \end{cases} $

Adaline

$ \begin{align} \phi(z) &= z \\ y &= \begin{cases} 1 \; \phi(z) \geq 0 \\ -1 \; \phi(z) < 0 \end{cases} \end{align} $

Logistic regression

$ \begin{align} \phi(z) &= \frac{1}{1 + e^{-z}} \\ y &= \begin{cases} 1 \; \phi(z) \geq 0.5 \\ 0 \; \phi(z) < 0.5 \end{cases} \end{align} $

Note: this is actually classification (discrete output) not regression (continuous output); the naming is historical.

Logistic regression intuition and conditional probabilities

$\phi(z) = \frac{1}{1 + e^{-z}}$: sigmoid function

$\phi(z) \in [0, 1]$, so can be interpreted as probability: $P(y = 1 \; | \; \mathbf{x} ; \mathbf{w}) = \phi(\mathbf{w}^T \mathbf{x})$

We can then choose class by interpreting the probability: $ \begin{align} y &= \begin{cases} 1 \; \phi(z) \geq 0.5 \\ 0 \; \phi(z) < 0.5 \end{cases} \end{align} $

The probability information can be very useful for many applications

• knowing the confidence of a prediction in addition to the prediction itself
• e.g. weather forecast: tomorrow might rain versus tomorrow might rain with 70% chance

Perceptron:

Adaline:

Logistic regression:

Learning the weights of the logistic cost function

$J(\mathbf{w})$: cost function to minimize with parameters $\mathbf{w}$

$z = \mathbf{w}^T \mathbf{x}$

For Adaline, we minimize sum-of-squared-error: $$ J(\mathbf{w}) = \frac{1}{2} \sum_i \left( y^{(i)} - t^{(i)}\right)^2 = \frac{1}{2} \sum_i \left( \phi\left(z^{(i)}\right) - t^{(i)}\right)^2 $$

Maximum likelihood estimation (MLE)

For logistic regression, we take advantage of the probability interpretation to maximize the likelihood: $$ L(\mathbf{w}) = P(t \; | \; \mathbf{x}; \mathbf{w}) = \prod_i P\left( t^{(i)} \; | \; \mathbf{x}^{(i)} ; \mathbf{w} \right) = \prod_i \phi\left(z^{(i)}\right)^{t^{(i)}} \left(1 - \phi\left(z^{(i)}\right)\right)^{1-t^{(i)}} $$

Why? $$ \begin{align} \phi\left(z^{(i)}\right)^{t^{(i)}} \left(1 - \phi\left(z^{(i)}\right)\right)^{1-t^{(i)}} = \begin{cases} \phi\left(z^{(i)} \right) & \; if \; t^{(i)} = 1 \\ 1 - \phi\left(z^{(i)}\right) & \; if \; t^{(i)} = 0 \end{cases} \end{align} $$

This is equivalent to minimize the negative log likelihood: $$ J(\mathbf{w}) = -\log L(\mathbf{w}) = \sum_i -t^{(i)}\log\left(\phi\left(z^{(i)}\right)\right) - \left(1 - t^{(i)}\right) \log\left(1 - \phi\left(z^{(i)}\right) \right) $$

Converting prod to sum via log() is a common math trick for easier computation.

Relationship to cross entropy

Optimizing for logistic regression

From $$ \frac{\partial \log\left(x\right)}{\partial x} = \frac{1}{x} $$ and chain rule: $$ \frac{\partial f\left(y\left(x\right)\right)}{\partial x} = \frac{\partial f(y)}{\partial y} \frac{\partial y}{\partial x} $$

We know $$ J(\mathbf{w}) = \sum_i -t^{(i)}\log\left(\phi\left(z^{(i)}\right)\right) - \left(1 - t^{(i)}\right) \log\left(1 - \phi\left(z^{(i)}\right) \right) $$

$$ \frac{\partial J(\mathbf{w})}{\partial \mathbf{w}} = \sum_i \left(\frac{-t^{(i)}}{\phi\left(z^{(i)}\right)} + \frac{1- t^{(i)}}{1 - \phi\left(z^{(i)}\right)} \right) \frac{\partial \phi \left(z^{(i)}\right)}{\partial \mathbf{w}} $$

For sigmoid $ \frac{\partial \phi(z)}{\partial z} = \phi(z)\left(1-\phi(z)\right) $

Thus $$ \begin{align} \delta J = \frac{\partial J(\mathbf{w})}{\partial \mathbf{w}} &= \sum_i \left(\frac{-t^{(i)}}{\phi\left(z^{(i)}\right)} + \frac{1- t^{(i)}}{1 - \phi\left(z^{(i)}\right)} \right) \phi\left(z^{(i)}\right)\left(1 - \phi\left(z^{(i)}\right) \right) \frac{\partial z^{(i)}}{\partial \mathbf{w}} \\ &= \sum_i \left( -t^{(i)}\left(1 - \phi\left(z^{(i)}\right)\right) + \left(1-t^{(i)}\right)\phi\left(z^{(i)}\right) \right) \mathbf{x}^{(i)} \\ &= \sum_i \left( -t^{(i)} + \phi\left( z^{(i)} \right) \right) \mathbf{x}^{(i)} \end{align} $$

For gradient descent $$ \begin{align} \delta \mathbf{w} &= -\eta \delta J = \eta \sum_i \left( t^{(i)} - \phi\left( z^{(i)} \right) \right) \mathbf{x}^{(i)} \\ \mathbf{w} & \leftarrow \mathbf{w} + \delta \mathbf{w} \end{align} $$ as related to what we did for optimizing in chapter 2.

Handling multiple classes

So far we have discussed only binary classifiers for 2 classes.

How about $K > 2$ classes, e.g. $K=3$ for the Iris dataset?

Multiple binary classifiers

One versus one

Build $\frac{K(K-1)}{2}$ classifiers, each separating a different pair of classes $C_i$ and $C_j$

The green region is ambiguous: $C_1$, $C_2$, $C_3$

One versus rest (aka one versus all)

Build $K$ binary classifiers, each separating class $C_k$ from the rest

The green region is ambiguous: $C_1$, $C_2$

Ambiguity

Both one-versus-one and one-versus-all have ambiguous regions and may incur more complexity/computation.

Ambiguity can be resolved via tie breakers, e.g.:

• activation values
• majority voting
• more details: http://scikit-learn.org/stable/modules/multiclass.html

One multi-class classifier

Multiple activation functions $\phi_k, k=1, 2, ... K$ each with different parameters $$ \phi_k\left(\mathbf{x}\right) = \phi\left(\mathbf{x}, \mathbf{w_k}\right) = \phi\left(\mathbf{w}_k^T \mathbf{x} \right) $$

We can then choose the class based on maximum activation: $$ y = argmax_k \; \phi_k\left( \mathbf{x} \right) $$

Can also apply the above for multiple binary classifiers

Caveat

• need to assume the individual classifiers have compatible activations
• https://en.wikipedia.org/wiki/Multiclass_classification

Binary logistic regression:

$$ J(\mathbf{w}) = \sum_{i \in samples} -t^{(i)}\log\left(\phi\left(z^{(i)}\right)\right) - \left(1 - t^{(i)}\right) \log\left(1 - \phi\left(z^{(i)}\right) \right) $$

Multi-class logistic regression: $$ J(\mathbf{w}) = \sum_{i \in samples} \sum_{j \in classes} -t^{(i, j)}\log\left(\phi\left(z^{(i, j)}\right)\right) - \left(1 - t^{(i, j)}\right) \log\left(1 - \phi\left(z^{(i, j)}\right) \right) $$

For $\phi \geq 0$, we can normalize for probabilistic interpretation: $$ P\left(k \; | \; \mathbf{x} ; \{\mathbf{w}_k\} \right) = \frac{\phi_k\left(\mathbf{x}\right)}{\sum_{m=1}^K \phi_m\left(\mathbf{x}\right) } $$

Or use softmax (normalized exponential) for any activation $\phi$: $$ P\left(k \; | \; \mathbf{x} ; \{\mathbf{w}_k\} \right) = \frac{e^{\phi_k\left(\mathbf{x}\right)}}{\sum_{m=1}^K e^{\phi_m\left(\mathbf{x}\right)} } $$

For example, if $\phi(z) = z$: $$ P\left(k \; | \; \mathbf{x} ; \{\mathbf{w}_k\} \right) = \frac{e^{\mathbf{w}_k^T\mathbf{x}}}{\sum_{m=1}^K e^{\mathbf{w}_m^T \mathbf{x}} } $$

For training, the model can be optimized via gradient descent.

The likelihood function (to maximize): $$ L(\mathbf{w}) = P(t \; | \; \mathbf{x}; \mathbf{w}) = \prod_i P\left( t^{(i)} \; | \; \mathbf{x}^{(i)} ; \mathbf{w} \right) $$

The loss function (to minimize): $$ J(\mathbf{w}) = -\log{L(\mathbf{w})} = -\sum_i \log{P\left( t^{(i)} \; | \; \mathbf{x}^{(i)} ; \mathbf{w} \right)} $$

Training a logistic regression model with scikit-learn

The code is quite simple.

Tackling overfitting via regularization

Recall our general representation of our modeling objective: $$\Phi(\mathbf{X}, \mathbf{T}, \Theta) = L\left(\mathbf{X}, \mathbf{T}, \mathbf{Y}=f(\mathbf{X}, \Theta)\right) + P(\Theta)$$

• $L$ - loss/objective for data fitting
• $P$ - regularization to favor simple model

Need to balance between accuracy/bias (L) and complexity/variance (P)

• If the model is too simple, it might be inaccurate (high bias)
• If the model is too complex, it might over-fit and over-sensitive to training data (high variance)

A well-trained model should

• fit the training data well (low bias)
• remain stable with different training data for good generalization (to unseen future data; low variance)

The following illustrates bias and variance for a potentially non-linear model

$L_2$ norm is a common form for regularization, e.g. $ P = \lambda ||\mathbf{w}||^2 $ for the linear weights $\mathbf{w}$

$\lambda$ is a parameter to weigh between bias and variance

$C = \frac{1}{\lambda}$ for scikit-learn

Reading

• PML Chapter 3

Maximum margin classification with support vector machines

Another popular type of machine learning algorithm

• basic version for linear classification
• kernel version for non-linear classification

Linear classification

• decision boundary $ \mathbf{w}^T \mathbf{x} \begin{cases} \geq 0 \; class +1 \\ < 0 \; class -1 \end{cases} $
• similar to perceptron
• based on different criteria

Perceptron

• minimize misclassification error
• more sensitive to outliers
• incremental learning (via SGD)

SVM

• maximize margins to nearest samples (called support vectors)
• more robust against outliers
• batch learning

Maximum margin intuition

Maximize the margins of support vectors to the decision plane $\rightarrow$ more robust classification for future samples (that may lie close to the decision plane)

Let us start with the simple case of two classes with labels +1 and -1. (We choose this particular combination of labeling for numerical simplicity, as follows.) Let the training dataset be $\{\mathbf{x}^{(i)}, y^{(i)}\}$, $i=1$ to $N$.

The goal is to find hyper-plane parameters $\mathbf{w}$ and $w_0$ so that $$y^{(i)} \left( \mathbf{w}^T\mathbf{x}^{(i)} + w_0\right) \geq 1, \; \forall i$$.

Note that $y^{(i)} = \pm1$ above.

We use t or y for target labels depending on the context

We separate out $w_0$ from the rest of $ \mathbf{w} = \begin{bmatrix} w_1 \\ w_2 \\ \vdots \\ w_n \end{bmatrix} $ for math derivation below </ul> </font>

Geometry perspective

For the purpose of optimization, we can cast the problem as maximize $\rho$ for: $$\frac{y^{(i)} \left( \mathbf{w}^T\mathbf{x}^{(i)} + w_0\right)}{||\mathbf{w}||} \geq \rho, \; \forall i$$ ; note that the left-hand side can be interpreted as the distance from $\mathbf{x}^{(i)}$ to the hyper-plane.

Scaling

Note that the above equation remains invariant if we multiply $||\mathbf{w}||$ and $w_0$ by any non-zero scalar.

To eliminate this ambiguity, we can fix $\rho ||\mathbf{w}|| = 1$ and minimize $||\mathbf{w}||$, i.e.: min $\frac{1}{2} ||\mathbf{w}||^2$ subject to $y^{(i)}\left( \mathbf{w}^T \mathbf{x}^{(i)} + w_0\right) \geq 1, \; \forall i$

Optimization

We can use Lagrangian multipliers $\alpha^{(i)}$ for this constrained optimization problem: $$ \begin{align} L(\mathbf{w}, w_0, \alpha) &= \frac{1}{2} ||\mathbf{w}||^2 - \sum_i \alpha^{(i)} \left( y^{(i)} \left( \mathbf{w}^T \mathbf{x}^{(i)} + w_0\right) -1 \right) \\ &= \frac{1}{2} ||\mathbf{w}||^2 - \sum_i \alpha^{(i)} y^{(i)} \left( \mathbf{w}^T \mathbf{x}^{(i)} + w_0\right) + \sum_i \alpha^{(i)} \end{align} $$

With some calculus/algebraic manipulations: $$\frac{\partial L}{\partial \mathbf{w}} = 0 \Rightarrow \mathbf{w} = \sum_i \alpha^{(i)} y^{(i)} \mathbf{x}^{(i)}$$ $$\frac{\partial L}{\partial w_0} = 0 \Rightarrow \sum_i \alpha^{(i)} y^{(i)} = 0$$

Plug the above two into $L$ above, we have: $$ \begin{align} L(\mathbf{w}, w_0, \alpha) &= \frac{1}{2} \mathbf{w}^T \mathbf{w} - \mathbf{w}^T \sum_i \alpha^{(i)}y^{(i)}\mathbf{x}^{(i)} - w_0 \sum_i \alpha^{(i)} y^{(i)} + \sum_i \alpha^{(i)} \\ &= -\frac{1}{2} \mathbf{w}^T \mathbf{w} + \sum_i \alpha^{(i)} \\ &= -\frac{1}{2} \sum_i \sum_j \alpha^{(i)} \alpha^{(j)} y^{(i)} y^{(j)} \left( \mathbf{x}^{(i)}\right)^T \mathbf{x}^{(j)} + \sum_i \alpha^{(i)} \end{align} $$ , which can be maximized, via quadratic optimization with $\alpha^{(i)}$ only, subject to the constraints: $\sum_i \alpha^{(i)} y^{(i)} = 0$ and $\alpha^{(i)} \geq 0, \; \forall i$

Note that $y^{(i)} = \pm 1$.

Once we solve $\{ \alpha^{(i)} \}$ we will see that most of them are $0$ with a few $> 0$.

The $>0$ ones correspond to lie on the decision boundaries and thus called support vectors: $$y^{(i)} \left( \mathbf{w}^T \mathbf{x}^{(i)} + w_0\right) = 1$$ from which we can calculate $w_0$.

Dealing with the nonlinearly separable case using slack variables

Soft margin classification

Some datasets are not linearly separable

Avoid thin margins for linearly separable cases

• bias variance tradeoff

For datasets that are not linearly separable, we can introduce slack variables $\{\xi^{(i)}\}$ as follows: $$y^{(i)} \left( \mathbf{w}^T \mathbf{x}^{(i)} + w_0\right) \geq 1 - \xi^{(i)}, \; \forall i$$

• If $\xi^{(i)} = 0$, it is just like the original case without slack variables.
• If $0 < \xi^{(i)} <1$, $\mathbf{x}^{(i)}$ is correctly classified but lies within the margin.
• If $\xi^{(i)} \geq 1$, $\mathbf{x}^{(i)}$ is mis-classified.

For optimization, the goal is to minimize $$\frac{1}{2} ||\mathbf{w}||^2 + C \sum_i \xi^{(i)}$$ , where $C$ is the strength of the penalty factor (like in regularization).

Using the Lagrangian multipliers $\{\alpha^{(i)}, \mu^{(i)} \}$ with constraints we have: $$L = \frac{1}{2} ||\mathbf{w}||^2 + C \sum_i \xi^{(i)} - \sum_i \alpha^{(i)} \left( y^{(i)} \left( \mathbf{w}^{(i)}\mathbf{x}^{(i)} + w_0\right) - 1 + \xi^{(i)}\right) - \sum_i \mu^{(i)} \xi^{(i)}$$ , which can be solved via a similar process as in the original case without slack variables.

Coding with SVM via scikit learn is simple

Alternative implementations in scikit-learn

Solving non-linear problems using a kernel SVM

SVM can be extended for non-linear classification

This is called kernel SVM

• will explain what kernel means
• and introduce kernel tricks :-)

Intuition

The following 2D circularly distributed data sets are not linearly separable.

However, we can elevate them to a higher dimensional space for linear separable: $ \phi(x_1, x_2) = (x_1, x_2, x_1^2 + x_2^2) $ , where $\phi$ is the mapping function.

Animation visualization

https://youtu.be/3liCbRZPrZA

https://youtu.be/9NrALgHFwTo

Using the kernel trick to find separating hyperplanes in higher dimensional space

For datasets that are not linearly separable, we can map them into a higher dimensional space and make them linearly separable. Let $\phi$ be this mapping: $\mathbf{z} = \phi(\mathbf{x})$

And we perform the linear decision in the $\mathbf{z}$ instead of the original $\mathbf{x}$ space: $$y^{(i)} \left( \mathbf{w}^{(i)} \mathbf{z}^{(i)} + w_0\right) \geq 1 - \xi^{(i)}$$

Following similar Lagrangian multiplier optimization as above, we eventually want to optimize: $$ \begin{align} L &= \frac{1}{2} \sum_i \sum_j \alpha^{(i)} \alpha^{(j)} y^{(i)} y^{(j)} \left(\mathbf{z}^{(i)}\right)^T \mathbf{z}^{(j)} + \sum_i \alpha^{(i)} \\ &= \frac{1}{2} \sum_i \sum_j \alpha^{(i)} \alpha^{(j)} y^{(i)} y^{(j)} \phi\left(\mathbf{x}^{(i)}\right)^T \phi\left(\mathbf{x}^{(j)}\right) + \sum_i \alpha^{(i)} \end{align} $$

The key idea behind kernel trick, and kernel machines in general, is to represent the high dimensional dot product by a kernel function: $$K\left(\mathbf{x}^{(i)}, \mathbf{x}^{(j)}\right) = \phi\left(\mathbf{x}^{(i)}\right)^T \phi\left(\mathbf{x}^{(j)}\right)$$

Intuitively, the data points become more likely to be linearly separable in a higher dimensional space.

Kernel trick for evaluation

Recall from part of our derivation above: $$ \frac{\partial L}{\partial \mathbf{w}} = 0 \Rightarrow \mathbf{w} = \sum_i \alpha^{(i)} y^{(i)} \mathbf{z}^{(i)} $$

Which allows us to compute the discriminant via kernel trick as well: $$ \begin{align} \mathbf{w}^T \mathbf{z} &= \sum_i \alpha^{(i)} y^{(i)} \left(\mathbf{z}^{(i)}\right)^T \mathbf{z} \\ &= \sum_i \alpha^{(i)} y^{(i)} \phi\left(\mathbf{x}^{(i)}\right)^T \phi(\mathbf{x}) \\ &= \sum_i \alpha^{(i)} y^{(i)} K\left(\mathbf{x}^{(i)}, \mathbf{x}\right) \end{align} $$

Non-linear classification example

x	y	xor(x, y)
0	0	0
0	1	1
1	0	1
1	1	0

Xor is not linearly separable

• math proof left as exercise

Random point sets classified via XOR based on the signs of 2D coordinates:

This is the classification result using a rbf (radial basis function) kernel

Notice the non-linear decision boundaries

Types of kernels

A variety of kernel functions can be used. The only requirement is that the kernel function behaves like inner product; larger $K(\mathbf{x}, \mathbf{y})$ for more similar $\mathbf{x}$ and $\mathbf{y}$

Linear

$ K\left(\mathbf{x}, \mathbf{y}\right) = \mathbf{x}^T \mathbf{y} $

Polynomials of degree $q$

$ K\left(\mathbf{x}, \mathbf{y}\right) = (\mathbf{x}^T\mathbf{y} + 1)^q $

Example for $d=2$ and $q=2$ $$ \begin{align} K\left(\mathbf{x}, \mathbf{y}\right) &= \left( x_1y_1 + x_2y_2 + 1 \right)^2 \\ &= 1 + 2x_1y_1 + 2x_2y_2 + 2x_1x_2y_1y_2 + x_1^2y_1^2 + x_2^2y_2^2 \end{align} $$ , which corresponds to the following kernel function: $$ \phi(x, y) = \left[1, \sqrt{2}x, \sqrt{2}y, \sqrt{2}xy, x^2, y^2 \right]^T $$

Radial basis function (RBF)

Scalar variance: $$ K\left(\mathbf{x}, \mathbf{y} \right) = e^{-\frac{\left|\mathbf{x} - \mathbf{y}\right|^2}{2s^2}} $$

General co-variance matrix: $$ K\left(\mathbf{x}, \mathbf{y} \right) = e^{-\frac{1}{2} \left(\mathbf{x}-\mathbf{y}\right)^T \mathbf{S}^{-1} \left(\mathbf{x} - \mathbf{y}\right)} $$

General distance function $D\left(\mathbf{x}, \mathbf{y}\right)$: $$ K\left(\mathbf{x}, \mathbf{y} \right) = e^{-\frac{D\left(\mathbf{x}, \mathbf{y} \right)}{2s^2}} $$

RBF essentially projects to an infinite dimensional space.

Sigmoid

$$ K\left(\mathbf{x}, \mathbf{y} \right) = \tanh\left(2\mathbf{x}^T\mathbf{y} + 1\right) $$

Kernel SVM for the Iris dataset

Let's apply RBF kernel

The kernel width is controlled by a gamma $\gamma$ parameter for kernel influence $ K\left(\mathbf{x}, \mathbf{y} \right) = e^{-\gamma D\left(\mathbf{x}, \mathbf{y} \right)} $ and $C$ for regularization

Reading

• PML Chapter 3
• IML Chapter 13-1 to 13.7
• The kernel trick

Decision tree learning

Machine learning can be like black box/magic; the model/method works after tuning parameters and such, but how and why?

Decision tree shows you how it makes decision, e.g. classification.

Example decision tree

• analogous to flow charts for designing algorithms
• every internal node can be based on some if-statement
• automatically learned from data, not manually programmed by human

Decision tree learning

1. Start with a single node that contains all data
   1. Select a node and split it via some criterion to optimize some objective, usually information/impurity $I$
   2. Repeat until convergence: good enough classification measured by $I$; complex enough model (overfitting);
2. Each leaf node belongs to one class
   • Multiple leaf nodes can be of the same class
   • Each leaf node can have misclassified samples - majority voting

• usually split along one dimension/feature
• a finite number of choices from the boundaries of sample classes

Maximizing information gain - getting the most bang for the buck

$I(D)$ information/impurity for a tree node with dataset $D$

Maximize information gain $IG$ for splitting each (parent) node $D_p$ into $m$ child nodes $j$: $$ IG = I(D_p) - \sum_{j=1}^m \frac{N_j}{N_p} I(D_j) $$ Usually $m=2$ for simplicity (binary split)

Commonly used impurity measures $I$

$p(i|t)$ - probability/proportion of dataset in node $t$ belongs to class $i$

Entropy

$$ I_H(t) = - \sum_{i=1}^c p(i|t) \log_2 p(i|t) $$

• $0$ if all samples belong to the same class
• $1$ if uniform distribution $ 0.5 = p(0|t) = p(1|t) $

Entropy (information theory)

Random variable $X$ with probability mass/density function $P(X)$

Information content $ I(X) = -\log_b\left(P(X)\right) $

Entropy is the expectation of information $$ H(X) = E(I(X)) = E(-\log_b(P(X))) $$

log base $b$ can be $2$, $e$, $10$

Continuous $X$: $$ H(X) = \int P(x) I(x) \; dx = -\int P(x) \log_b P(x) \;dx $$ Discrete $X$: $$ H(X) = \sum_i P(x_i) I(x_i) = -\sum_i P(x_i) \log_b P(x_i) $$

$-\log_b P(x)$ - number of bits needed to represent $P(x)$

• the rarer the event $\rightarrow$ the less $P(x)$ $\rightarrow$ the more bits

Gini index

Minimize expected value of misclassification

$$ I_G(t) = \sum_{i=1}^c p(i|t) \left( 1 - p(i|t) \right) = 1 - \sum_{i=1}^c p(i|t)^2 $$

• $p(i|t)$ - probability of class $i$
• $1-p(i|t)$ - probability of misclassification, i.e. $t$ is not class $i$

Similar to entropy

• expected value of information: $-\log_2 p(i|t)$
• information and mis-classification probability: both larger for lower $p(i|t)$

Classification error

$$ I_e(t) = 1 - \max_i p(i|t) $$

$ argmax_i \; p(i|t) $ as the class label for node $t$

Compare different information measures

Entropy and Gini are probabilisitic

• not assuming the label of the node (decided later after more splitting)

Classification error is deterministic

• assumes the majority class would be the label

Entropy and Gini index are similar, and tend to behave better than classification error

• curves below via a 2-class case
• example in the PML textbook

Building a decision tree

A finite number of choices for split

Split only alone boundaries of different classes

Exactly where? Maxmize margins

Visualize the decision tree

Install Graphviz

dot -Tsvg tree.dot -o tree.svg

Note

If you have scikit-learn 0.18 and pydotplus installed (e.g., you can install it via pip install pydotplus), you can also show the decision tree directly without creating a separate dot file as shown below. Also note that sklearn 0.18 offers a few additional options to make the decision tree visually more appealing.

Decisions trees and SVM

• SVM considers only margins to nearest samples to the decision boundary
• Decision tree considers all samples

Case studies

Pruning a decision tree

Split until all leaf nodes are pure?

• not always a good idea due to potential over-fitting

Simplify the tree via pruning

Pre-pruning

• stop splitting a node if the contained data size is below some threshold (e.g. 5% of all data)

Post-pruning

• build a tree first, and remove excessive branches
• reserve a pruning subset separate from the training data
• for each sub-tree (top-down or bottom-up), replace it with a leaf node labeled with the majority vote if not worsen performance for the pruning subset

Pre-pruning is simpler, post-pruning works better

Combining weak to strong learners via random forests

Forest = collection of trees

An example of ensemble learning (more about this later)

• combine multiple weak learners to build a strong learner
• better generalization, less overfitting

Less interpretable than a single tree

Random forest algorithm

Decide how many trees to build

To train each tree:

• Draw a random subset of samples (e.g. random sample with replacement of all samples)
• Split each node via a random subset of features (e.g. $d = \sqrt{m}$ of the original dimensionality)

(randomization is a key)

Majority vote from all trees

Code example

Reading

• PML Chapter 3
• IML Chapter 9

Parametric versus non-parametric models

• (fixed) number of parameters trained and retained
• amount of data retained
• trade-off between training and evaluation time

Example

Linear classifiers (SVM, perceptron)

• parameters: $\mathbf{w}$
• data throw away after training
• extreme end of parametric

Kernel SVM

• depends on the type of kernel used (exercise)

Decision tree

• parameters: decision boundaries at all nodes
• number of parameters vary depending on the training data
• data throw away after training
• less parametric than SVM

Personal take: Parametric versus non-parametric is more of a continuous spectrum than a binary decision. Many algorithms lie somewhere in between.

K-nearest neighbors - a lazy learning algorithm

KNN keeps all data and has no trained parameters

• extreme end of non-parametric

How it works:

• Choose the number $k$ of neighbors and a distance measure
• For each sample to classify, find the $k$ nearest neighbors in the dataset
• Assign class label via majority vote

$k$ is a hyper-parameter (picked by human), not a (ordinary) parameter (trained from data by machines)

Pro:

• zero training time
• very simple

Con:

• need to keep all data
• evaluation time linearly proportional to data size (acceleration possible though, e.g. kd-tree)
• vulnerable to curse of dimensionality

Practical usage

Minkowski distance of order $p$: $ d(\mathbf{x}, \mathbf{y}) = \sqrt[p]{\sum_k |\mathbf{x}_k - \mathbf{y}_k|^p} $

• $p = 2$, Euclidean distance
• $p = 1$, Manhattan distance

Number of neighbors $k$ trade-off between bias and variance

• too small $k$ - low bias, high variance

Too small k can cause overfitting (high variance).

Too large k can cause under-fitting (high bias).

How about using different $p$ values for Minkowski distance?

Reading

• PML Chapter 3