AdaBoost

At this week's labs we will implement the AdaBoost algorithm. The AdaBoost algorithm takes a class of “weak” classifiers and boosts their performance by combining them together to a “strong” classifier with adaptive weights assigned to each of the weak classifiers (AdaBoost stands for “adaptive boosting”). This way even relatively simple classifiers can be boosted to practically interesting accuracy levels.

In Adaboost, the classification function $H(x)$ has the form $$H(x) = \mbox{sign}(F(x))$$ $$F(x)=\sum^T_{t=1}\alpha_t h_t(x) $$ where $h_t(x)\;: \mathcal{X} \to \{-1, +1\}$ are the selected weak classifiers and $\alpha_t$ are the mixing weights.

The training algorithm itself is relatively simple:

In this assignment, we will use the AdaBoost learning algorithm to train a digit classifier. The input to the algorithm will be a set of 13×13 grayscale images of digits and their corresponding labels (0-9). We will select one of the digits as positive class ($y_i = +1$) and the rest of the images will form the negative part of the training set ($y_i = -1$). The task is then to distinguish the selected digit from the rest of the digits.

We are also free to choose the set of weak classifiers, $\mathcal{H}$. Ideally, we would like them to be discriminative enough for the given task but they do not necessarily need to be “too strong”. In our case, possible weak classifiers include local binary patterns (LBP), we may compute various histogram based features, use some edge-based features,… We may use single threshold decisions, build decision trees or use some form of regression. Note, that this is the strength of the AdaBoost algorithm – you are free to combine various weak classifiers and the algorithm determines which ones are useful for the task. Our dataset is rather small and simple, so to see the effects of weak classifiers combination into a stronger one, we will keep the weak classifiers intentionally rather simple.

Each weak classifier $h_{r,c}(I; \theta, p)\in\mathcal{H}$ is based on intensity value of one pixel and is parametrised by four numbers: its coordinates in the image $I$, row $r$ and column $c$, and by an intensity threshold $\theta\in R$ and a parity flag $p \in \{+1, -1\}$ indicating whether the positive class is above or below the threshold. Each such weak classifier takes the image intensity at position $(r, c)$, compares it with the threshold $\theta$ and returns the class using the parity: $$h_{r,c}(I; \theta, p) = \mbox{sign}(p * (I(r,c) - \theta))$$ Note, that we have 13×13=169 weak classifiers which are further parametrised by the threshold and parity. This gives us large variety of weak classifiers while keeping them rather weak and simple (much stronger weak classifiers could be easily used if we consider the relations between pixels, like the above mentioned LBPs). When searching for the best weak classifier in step 1 of the AdaBoost learning algorithm we are thus searching over $\theta$ and $p$ parameters of each of the 169 “template” classifiers and select the one with the lowest weighted error.

1. Choose one digit as a positive class.
   
   
2. Complete the function [strong_class, wc_error, upper_bound] = adaboost(X, y, num_steps) so that it implements the AdaBoost training.
   The function accepts a training set, labels and the number of training steps. It should return: strong_class - the found strong classifier (see the comments in the code for its structure), wc_error - the weighted error of the selected weak classifier in each iteration, and upper_bound - the training error upper bound $\prod Z_t$.
   
   To find the best weak classifier, use the function findbestweak which implements vectorised search for the optimal $\theta$ and $p$.
   
   To reduce the effect of an unbalanced training set (1:9 positive to negative sample size ratio) which would put too much emphasis on the negative samples, initialise the weights $D_1$ such that the $\sum_{i: y_i=-1}D_1(i) = \sum_{i: y_i=+1}D_1(i) = 0.5$.
   
   Hint 1: The update of weights $D_{t+1}$ could be easily implemented using vector notation. Try to understand what it does. If there is something unclear feel free to ask us.
   
   Hint 2: The update of $D_{t+1}$ can be also written as (substituting in $\alpha_t$) $D_{t+1} = \frac{1}{Z_t} D_t \sqrt{\frac{\varepsilon_t}{1 - \varepsilon_t}}$ if $y_i = h_t(x_i)$ and $D_{t+1} = \frac{1}{Z_t} D_t \sqrt{\frac{1 - \varepsilon_t}{\varepsilon_t}}$ if $y_i \neq h_t(x_i)$.
   
   Hint 3: To test the correctness of your solution, the curves and classification results below are for the digit 6 and you should get the same values.
   
   
3. Train a strong classifier for a digit of your choice with num_steps = 30.
   
   
4. Complete the function errors = compute_error(strong_class, X, y) which returns the evolution of the error on the set X over the training iterations (using longer and longer strong classifier). Apply it to computing both the training and test error evolution.
   
   
5. Plot all the collected errors into one graph and save it as error_evolution.png
   
   
6. Complete the function classify = adaboost_classify(strong_class, X) which uses the strong classifier to classify new data X.
   
   
7. Show the classification results and save the picture as classification.png.
   
   
   
8. The assignment_09.m script contains also a simple visualisation of the found weak classifiers. Feel free to use it or even improve it to see what weak classifiers were chosen as useful for the given classification task. Save the result into weak_classifiers.png.
   

Fill the correct answers to your answers.txt file.

Implement the AdaBoost classifier for the data described in the lecture slides [2]. Each weak classifier is a threshold/parity decision on a radial line from the data center (the thresholds are actually what is drawn in the slides). Discretise the angles of the directions of the radial lines to a reasonable number (e.g. every 5 degrees).

Feel free to use the functions generate_data.m, show_data.m, showclassif.m and vis_boundary.m available in the template.

[1] short support text on AdaBoost
[2] AdaBoost lecture