• Home
  • About
    • James Bockman photo

      James Bockman

      A place to organise my projects and research

    • Learn More
    • Email
    • LinkedIn
    • Instagram
    • Github
    • Youtube
  • Posts
    • All Posts
    • All Tags
  • Projects

[Report/Code] Adaptive Boosting

31 Jan 2019

Reading time ~16 minutes

Introduction

Ensemble learning methods take the perspective that by constructing a classifier that uses several hypothesises pooled together, it would be less likely to misclassify samples than any of the singular hypothesis acting on their own. Boosting is a specific case where the classifiers used in the ensemble are weighted and each subsequent classifier is trained on a modified dataset that penalises the previous classifiers correctly classified samples and rewards classification of the mistakes. Therefore, the final ensemble becomes a group of experts in particular areas of the space being classified. This creates a model which is able to compensate for other classifiers yielding a complete model. In the accompanying figure the coloured regions represent areas where a given hypothesis yields incorrect classifications. As an ensemble no three hypothesises are never wrong about a single point's classification, consequently three out of five classifiers are always correct. Therefore a majority vote from the collection of hypothesises will classify the samples in the space with 100% accuracy. There are many examples of algorithms that are based on the idea of boosting, in this document the processes and procedures used to adjust the weights of the samples in the dataset and form the ensemble are consistent with Adaptive Boosting also referred to as AdaBoost. This particular algorithm assumes that the ensemble of classifiers are examples of weak learners, which are only slightly better at classifying samples than randomly assigning them a label. When this assumption is met AdaBoost returns models that are guaranteed to classify the training set perfectly given a large enough ensemble size. It is also extremely resilient to over-fitting as a result of model complexity. In many cases it has been shown that accuracy on the testing set continues to increase as more hypothesis are added to the ensemble after the training classification has reached 100%. This seems to contradict the traditional rule of Ockham's razor utilised so frequently in modelling, where model complexity is penalised in order to ensure generalisation. [4] Here in, binary classification problems are considered, but the techniques can be extended to multi-class and regression problems. [2] To examine the AdaBoost algorithm first the mathematics behind the formation of the ensemble will be explored, then a prototype of the boosting algorithm will be implemented in Python and compared to an open source implementation. These results will then be compared to a Support Vector Machine to contrast the two classifiers respective strengths and weaknesses.

Adaptive Boosting

Initialisation

Weak Learners

As stated above, the weighted ensemble of learners that form the final classifier must fall into the category of weak learners. This gives any individual hypothesis an accuracy of \(0.5+\delta\), where \(\delta\) is the advantage the classifier has over random label assignment. The condition of weak learner is met by a large number of classifier type, but in this case the ensembles will be formed of decision stumps, due to their simplicity. Each stump is a classification rule with a threshold value and a respective dimension, where either +1 or -1 will be assigned to values above or below the threshold. Each stump will have a mirror stump in which the assignment of labels relative to the threshold is reversed.

# Decision stump classifier, if rightPos is true everything to the 
# left of the threshold is assigned -1, to the right +1 
# if rightPos is false label assignment is flipped
class Stump:
    
    def __init__(self, dimension, value, rightPos):
        self.dimension = dimension
        self.value = value
        self.rightPos = rightPos
    
    error = 1
    alpha = 0

Initialising a collection of possible decision stumps for the input data is the first step of the Adaptive Boosting algorithm as the learners that ultimately form the classifier will be drawn from this pool. In this case every possible unique split was considered when forming the hypothesis space. Each dimension is ordered, then duplicate values removed and two decision stumps are initialised at each of the midpoints between consecutive unique values in the dimension; one that labels the samples to the right as positive and another to labels to the left as positive. Additionally an extra two stumps are created that label all samples as positive or negative are initialised to. This leads to a large space of possible learners, \(2\sum_{i}^{d}n_{i}\) where \(n\) is the number of unique values in the \(i\)th dimension and \(d\) is the dimensionality of the feature space.\

# Takes in the dataframe and geenrates possible 
# decision stumps for each dimension of the set
def generateStumps(dataFrame):
    # For each dimension (variable) order the data along it
    # find the midpoints between consecutive points
    # create a stump for each midpoint value
    
    tmpDF = dataFrame # Creates a copy of the data
    
    # Extract information about the data frame
    columns = list(tmpDF)
    numberOfVariables = dataFrame.shape[1]
    numberOfSamples = dataFrame.shape[0]
    
    # Multidemisionaly array of stumps
    allStumps = list()
    oneDStumps = list()
    
    # for each variable sort by it and make stumps
    # between points
    for i in range(1, numberOfVariables):
        # Sorts the samples in ascending order in the
        # desired dimension
        tmpDF.sort_values(by = [columns[i]])
        
        # Find the mid-point between sequentialy ordered samples
        # disregarding duplicate entries along the demision
        tmp = tmpDF.loc[0, columns[i]]
        
        for j in range(1, numberOfSamples):
            # Get the next largest value in the ith dimension
            tmpNext = tmpDF.loc[j, columns[i]]
            # Compare it to the previous
            if (tmp != tmpNext):
                newSplit = (tmpNext+tmp)/2
                newStump = Stump(i, newSplit, True)
                oneDStumps.append(newStump)
                newStump = Stump(i, newSplit, False)
                oneDStumps.append(newStump)
            # Get the next value in the dimension
            tmp = tmpNext
        
        # Add the generated stumps to the overall
        allStumps.append(oneDStumps)
        # Clear the oneDStump list
        oneDStumps = list()
    
    return allStumps

Sample Weights

Initially the samples weights need to form a uniform distribution, as the weights are a distribution they are subject to the law of total probability and are therefore constrained by: \[ \sum_{1=1}^{n} w_{i_{t}} = 1 \] Where \(n\) is the total number of samples in the set and t is the current iteration. As the distribution begins uniform all samples have the same weight, \(w_{i} = c\) for \(i = 0, 1, ... , n\) giving the initial value for each sample's weight as: \[ w_{i_{1}} = \frac{1}{n} \]

# Create an array of wieghts the same size as the data frame
# where each wieght starts at 1/n where n is the total number
# of samples
def initialiseWeights(dataFrame):
    numberOfVariables = dataFrame.shape[1] - 1
    numberOfSamples = dataFrame.shape[0]
    wieghts = np.ones((numberOfSamples))*(1/numberOfSamples)
    
    return wieghts

Iteration

Learner Selection - Error Evaluation

Each of the possible learners is evaluated against the weighted error of itself. To calculate the weighted error all the samples that are misclassified have their respective weights summed together: \[ \epsilon = \sum_{i=1}^{n} w_{i_{t}} \text{ for } h(x_{i}) \neq y(x_{i}) \] Where \(x_{i}\) is the sample, \(h(x_{i})\) is the classifiers label of the \(i\)th sample and \(y(x_{i})\) is the true label of the \(i\)th sample. The classifier for which this weighted error is minimised is selected from the space of possible learners. This classifier is then used in the final.

# Takes a sample and returns a label
def classify(self, sample):
    if self.rightPos:
        if (sample >= self.value):
            return +1
        else:
            return -1
    else:
        if (sample < self.value):
            return +1
        else:
            return -1

# Vectorisable method for evaluating errors, 
# returns weight or zero
def vecError(self, sampleValue, label, weight):
	# Is the sample classified correctly
	if (classify(sample) == label):
    	return 0.0
    else:
    	return weight

# Vectorised evaluation of error
def evaluateError(self, dataFrame, sampleLabels, sampleWeights):
    # vectorise the error function
    vectorError = np.vectorize(self.vecError)
    errors = vectorError(dataFrame[:, self.dimension], sampleLabels, sampleWeights)
    # Sum up the array of wieghts for incorrectly classified samples
    self.error = np.sum(errors)
# For each of the possible decisions update their error
# then return the stump with the least error
def selectBestStump(possibleStumps, dataFrame, weights, labels):   
    # Set the best stump to false
    bestStump = Stump('Null', 'Null', False)
    
    # Testing counter to see how many equivelent decisions exist
    counter = 0 
    
    # Update the error of each possible stump
    for i in range(len(possibleStumps)):
        
        for j in range(len(possibleStumps[i])):
            possibleStumps[i][j].evaluateError(dataFrame.values, labels.values, weights)
            # If the current stump has lees error than the current best
            # update the current stump as the current best
            if (bestStump.value == 'Null'):
                bestStump = possibleStumps[i][j]
            else:
                if (possibleStumps[i][j].error < bestStump.error):   
                    bestStump = possibleStumps[i][j]
                elif (possibleStumps[i][j].error == bestStump.error):
                    counter += 1
    
    return bestStump, counter
        

Weight of Classifier in Final Model

Once the best hypothesis has been select from the pool of possible, the weight of this classifier in the final model can be evaluated. This weight assignment is at the core of AdaBoost and is derived in order to ensure the overall error of the model is bounded by exponential loss. [1] The weight given to the \(i\)th classifier in the final model, \(\alpha_{i}\), is calculated by: \[ \alpha_{i} = \frac{1}{2}\ln{\left(\frac{1-\epsilon_{i}}{\epsilon_{i}}\right)} \]

# Updates the stump's alpha value
def updateAlpha(self):
    newAlpha = (1-self.error)/(self.error)
    newAlpha = np.log(newAlpha)
    newAlpha /= 2
    # Raptors got a new alpha
    self.alpha = newAlpha   

Updated Sample Weights

Using the calculated classifier weight \({\alpha_{i}}\) the samples weight distribution is updated so on the next iteration the samples classified incorrectly by the current learner are rewarded more than those already classified correctly. To do this each weight is scaled by \(\alpha\), up for incorrectly classified samples and down for correctly classified: \[ w_{i_{t+1}} = \frac{w_{i_{t}}}{Z} \text{ }\alpha_{i} \text{ If } h(x_{i}) \neq y(x_{i}) \] \[ w_{i_{t+1}} = \frac{w_{i_{t}}}{Z \alpha_{i}} \text{ If } h(x_{i}) = y(x_{i}) \] Where \(Z\) is a normalisation term given by: \[ Z = 2\sqrt{\epsilon_{i}(1-\epsilon_{i})} \] The process is then repeated from the error evaluation step until the desired number of classifiers are found. Therefore, the final model will be in form of a linear sum of classification functions multiplied by their respective \(\alpha\). [3]

# Update the samples weights for the next classifier
def updateWeights(stump, weights, dataFrame, labels):
    # Use the stump to classify the set
    predictions = stump.classifySet(dataFrame.values)
    
    # Calculates Z the normalisation constant
    Z = 2*np.sqrt(stump.error*(1-stump.error))
    
    # Check which where correct/incorrect and update the 
    # corresponding wieght
    for i in range(len(predictions)):
        if (labels[i] == predictions[i]):
            weights[i] /= np.exp(stump.alpha)
            weights[i] /= Z
        else:
            weights[i] *= np.exp(stump.alpha)
            weights[i] /= Z    
    
    return weights

Classification

To classify a new sample as +1 or -1 using the model, each classifier is used on the sample sequentially with each classifiers prediction being multiplied by its respective alpha. This weighted prediction is then added to a cumulative summation. Once all the learners in the ensemble have contributed to the summation, is reduced to a label by taking the sign: \[ H(x) = \text{Sign}\left(\alpha_{1} h_{1}(x) + \alpha_{2} h_{2}(x) + \dots + \alpha_{j} h_{j}(x)\right) \]

 # Using the trained model, predict the classes of the data
    def predict(self, dataFrame):
        # Reset summation
        predictions = np.zeros(dataFrame.shape[0])
            
        # Get the wieghted prediction from each classifier in the model
        for classifier in self.model:
            # Classify and weight all samples by a classifier
            tmp = (classifier.alpha) * (classifier.classifySet(dataFrame.values))

            # Sum into the prediction
            predictions += tmp
        
        return np.sign(predictions)

Implementation

A prototype Adaptive Boosting algorithm was implemented in Python, using Jupyter notebook as the development environment. The prototype uses an implemented decision stump class to form the ensemble of learners. AdaBoost is then applied in order to train, select and weight classifiers, which construct the final model. To achieve this the work-flow in the figure to the right was used. Some aspects of the implementation were vectorised in order to reduce training time to a reasonable length. The major source of computation time comes from the nested loops which evaluate the error for each possible weak learner in the set of hypothesises.




# Accepts a pandas data frame and the number of iterations
# the algorithm of adaptive boosting before retuning the model
def train(self, dataFrame, labels, iterations):
    # Initialisation
    possibleStumps = generateStumps(dataFrame)
    weights = initialiseWeights(dataFrame)
    # Training the model
    for i in range(iterations):
        # Select the best classifier
        bestStump, counter = selectBestStump(possibleStumps, dataFrame, weights, labels)
        # Update its alpha value
        bestStump.updateAlpha()
        # Update the weights
        weights = updateWeights(bestStump, weights, dataFrame, labels)
        # Add best stump to the model
        self.model.append(bestStump)

Evaluation

To access the implemented algorithm two datasets were adapted from the UCI Machine Learning Repository. The first was reduced to a binary classification of emails as spam or not [8], the second are C and G samples from the letter image recognition database, [9]. On importing the datasets respective labels were encoded such that Cs are +1, Gs are -1 and Spam is -1, not spam is +1.

For both datasets the implemented algorithm achieved classification accuracies of over 90% when the ensemble consisted of 50 learners, see the below figures. The algorithm appears to be increasing towards a perfect model for the training data in both cases, but was yet to reach it with 500 learners in the model. Diminishing returns of accuracy form adding model complexity is evidenced clearly here, with the majority of testing accuracy increase seen in the first 50 learners, from this point increasing the ensemble size by ten fold the accuracy is observed to increase by  4% on the Letters data and  2% on Emails. It is important to note that with an increase of learners comes a corresponding increase in compute time as seen in the appended tables of results

Training and testing accuracies for the implemented AdaBoost algorithm on the Letters dataset. Training and testing accuracies for the implemented AdaBoost algorithm on the Emails dataset.

Throughout the implementation time complexity was identified as a significant factor in the ability to increase model complexity and is exacerbated by higher dimensionality and larger datasets. However there is a large amount of optimisation still available, as most of the operations are completed by generic loops and can be vectorised to leverage parallel processing. The room to develop is evidenced by the runtime results seen for the imported AdaBoost algorithm, evidenced in the appended tables. Towards this goal the space of possible hypothesises was considered as something that could be reduced. Currently the implemented algorithm conducts an exhaustive comparison based search on the set of all possible mid-points between sequential samples and their inverse labelling rules. Over the course of implementation emphasis was placed on the best possible decision stump being returned, but the error metric used to evaluate this is not guaranteed to be unique. The number of these redundancies changes as the algorithm progresses, but the maximum observed was 686 equivalent decisions when applied to the Letters dataset. Initially this was viewed as problematic and measures to separate which of the equivalent decisions are better were considered, but under the conditions of Adaptive Boosting it becomes clear that sub-optimal choices in learner have little overall impact on the accuracy of the model. This is likely a consequence of the assumption that the ensemble's learners should be weak in nature. Continuing this line of reasoning, informed reductions in the space of possible classifiers could be made without the loss of the ensembles classification power, or perhaps an early end to the search when the first decision that is suitably strong is found. Ultimately this will require further testing to investigate and will likely effect the rate of convergence on a perfect training model, perhaps trading search time for larger ensembles.\ The imported AdaBoost algorithm finds a model to fit the training data somewhere between 50-100 learners, seen in the below plots. It also shows a steeper ascent to this in comparison to the prototype. A feature of the imported algorithm is once a model that classifies the training data completely it will not add further learners to the ensemble. This is why the testing accuracy is shown to stagnate after the first model that gets 100% accuracy on the training data is found. The faster convergence of the model on a perfect fit is likely due to the variant of Adaptive Boosting the imported package uses Stage-wise Additive Modelling using a Multi-class Exponential loss function - Real (SAMME.R). [5] Although literature suggests this approach reduces to AdaBoost when the classification problem is binary, [7] the example in the packages documentation shows that on a binary classification problem SAMME and SAMME.R preform differently. [6]

Training and testing accuracies for the imported AdaBoost algorithm for different ensemble sizes on the Letters dataset. Training and testing accuracies for the imported AdaBoost algorithm for different ensemble sizes on the Emails dataset.

As the two datasets examined are seemingly non-linear in nature and contain high amounts of overlap the results of AdaBoost were compared with a Support Vector Machine (SVM). In this comparison the resistance that AdaBoost has to over fitting is clear. The imported SVM under hard-margin could not find a decision boundary for the linear or second degree polynomial kernel. A Gaussian kernel enables the formation of the decision boundary, but even when carefully tuned over-fits the dense overlapping feature space of the examined datasets, shown in the plots below. This achieved a maximum testing accuracy of  50% on the Letters dataset and  60% on the Emails. Even the efforts to maximise generalisation taken during the conception of SVMs over-fit on these dataset before reaching a decision rule that can perfectly classify the training set. Whereas AdaBoost's achieves exceptional classification accuracy and in these two examples, appearing experimentally immune to the negatives usually associated with increased model complexity.

Training and testing accuracies for the imported Support Vector Machine using a Gaussian kernel with different sigma values. The algorithm was applied to the Letters dataset. Training and testing accuracies for the imported Support Vector Machine using a Gaussian kernel with different sigma values. The algorithm was applied to the Emails dataset.

Adaptive Boosting - Tabulated Results

Ensemble Size Training Accuracy (%) Testing Accuracy (%) Training Time (s) Testing Time (s)
1 79.0 77.80 4.61 0.00
5 82.4 81.07 22.76 0.00
20 89.4 86.92 89.61 0.02
50 93.2 90.58 223.27 0.04
100 94.8 92.27 446.56 0.10
200 97.0 93.86 888.80 0.20
500 99.0 95.34 2228.55 0.47

Results of testing conducted using the implemented AdaBoost algorithm on the Letter recognition dataset.

Ensemble Size Training Accuracy (%) Testing Accuracy (%) Training Time (s) Testing Time (s)
1 80.6 77.92 22.75 0.00
5 84.6 82.34 111.37 0.01
20 91.5 89.28 446.63 0.05
50 92.5 90.50 1123.43 0.15
100 93.9 91.36 2247.44 0.34
200 94.5 91.78 4520.25 0.72
500 95.8 92.00 11259.84 1.71

Results of testing conducted using the implemented AdaBoost algorithm on the Emails dataset.

Ensemble Size Training Accuracy (%) Testing Accuracy (%) Training Time (s) Testing Time (s)
1 79.0 77.80 0.00 0.00
5 89.8 86.03 0.01 0.00
20 95.6 89.49 0.03 0.01
50 99.6 91.97 0.07 0.01
100 100.0 93.16 0.14 0.02
200 100.0 93.46 0.28 0.05
500 100.0 93.16 0.73 0.12

Results of testing conducted using sklearn’s AdaBoost algorithm on the Letter recognition dataset.

Ensemble Size Training Accuracy (%) Testing Accuracy (%) Training Time (s) Testing Time (s)
1 79.0 77.80 0.00 0.00
5 89.8 86.03 0.01 0.00
20 95.6 89.49 0.03 0.01
50 99.6 91.97 0.07 0.01
100 100.0 93.16 0.14 0.02
200 100.0 93.46 0.28 0.05
500 100.0 93.16 0.73 0.12

Results of testing conducted using sklearn’s AdaBoost algorithm on the Emails dataset.

References

[1] Breiman, L. 1997. “Predictions Games and Arcing Algorithms.” Technical Report 504, Statistics Department, University of California, December, 9–11.

[2] Freund, Y., and R. Schapire. 1997. “A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting.” Journal of Computer and System Sciences 55 (SS971504): 119–39.

[3] “A Short Introduction to Boosting.” Journal of Japanese Society for Artifical Intelligence 14 (5): 771–80, 1999

[4] Russell, S., and P. Norvig. 2010. Artificial Intelligence: A Modern Approach. Third. Pearson.

[5] Scikit-Learn. 2018a. “1.11.3 Adaboost.” Scikit-Learn. 2018. http://scikit-learn.org/stable/modules/ensemble.html#adaboost

[6] 2018b. “Discrete Versus Real Adaboost.” Scikit-Learn. 2018. http://scikit-learn.org/stable/auto_examples/ensemble/plot_adaboost_hastie_10_2.html

[7] Zhu, J., and H. Zou. 2009. “Multi-Class Adaboost.” Statistics and Its Interface 2: 349–60.

[8] M. Hopkins and E. Reeber, Spambase Data Set, University of California, Irvine, 1999 https://archive.ics.uci.edu/ml/datasets/Spambase

[9] D. Slate, Letter Image Recognition Data, University of California, Irvine, 1991 https://archive.ics.uci.edu/ml/machine-learning-databases/letter-recognition/`



Share Tweet +1