Ensemble Technique 2 : AdaBoost

 AdaBoost





AdaBoost or Adaptive Boosting is a boosting technique that is used as an Ensemble Method in Machine Learning. In this algorithm, the weights are re-assigned at each and every instances with higher weight for wrongly classified instances. The main motive behind this algorithm is to convert the weak learners to strong learners.






Boosting Technique
As we can see from the above figure, suppose the original data is D1 and the trained classifier seen below is a base learner BL1(say). BL1 can be any model/algorithm provided with a sample of data to train. After training the model, when the original data is used to validate the model, the incorrectly classified records are further treated by moving them to a next base learner (BL2). Now the BL2 will be trained with those wrong classified records and further if they classify some more records incorrectly then again a new base learning is created (BL3) and this process continues till we specify some limits to the base learner creation. This is in general how a boosting technique works.


Adaboost
Let us see how an Adaboost technique works for that we need to undergo few steps. Consider we have a dataset with 7 records and 3 features/columns.

Step1



Provide equal weights to all the records as shown in the above table (1/7).

Step2




In this stage we create our first base learner (BL1) which is created with the help of decision tree. In this case unlike in the general decision tree algorithm, we just have one depth here as seen in the above figure. This decision tree is called as stump. One thing to keep in mind is we need to create as many number of stumps as many features we have. In this scenario we have 3 features (Feature1, Feature2, Feature3) ,so we have to create 3 stumps on each features, where the feature will be in the root node position in the sequential manner. For better understanding consider the above figure, say this is the first stump so the blue colored node will be Feature1 and the two green coloured nodes will be Feature2 and Feature3. 

The selection of the stump among the three will be based on the entropy values. So, the stump with the lowest entropy value is selected.

Now we need to calculate the total error in the BL1/selected stump. Suppose in this case we have only one wrong classification in the 7 total records then in that case the total error will be 1/7 (number of errors/ total number of records).

Step3
In this step we need to calculate the performance of the stump.

where TE is the total error
Once we substitute the value of TE as 1/7 in the formula we get the performance as 0.896

Step4
We need to update the sample weight that is increase the weight of wrongly classified records and decrease the weight of the right classification.

Formula for new sample weight are:

Incorrectly classified Sample Weight = Sample Weight * e^(Performance) = 0.349

Correctly classified Sample Weight = Sample Weight * e^(Performance) = 0.05


Now we need to update the weights of each records. 



We can see an additional column named normalised weight is added which is the normalised version of the updated weight (the sum of the updated column was 0.649 and to make it standardized we need to divide each weight by 0.649).

Step5
Now using normalised weight value, we create a new dataset. The dataset based on the updated weight values selects the wrongly classified records for training our new stump/Base learner(BL2). To make this new dataset , the algorithm will divide it into buckets.




Now, our algorithm we will 7 iterations to select different records from old dataset. Suppose in first iteration, it selects a random value of 0.03 then it will check the value presence in the bucket. In this case, the first bucket record will be selected and populated in the new dataset. Here, the probability of selecting the wrongly classified records is maximum due to the higher range value of the bucket.

Again using the new dataset, algorithm will create second base learner(BL2)/stump. Like wise step 2 and other steps will take place here. We will consider that situation with lesser error rate compared to the initial state. 



Source: Datacamp


Suppose we have created in total of 3 base learners/stumps sequentially finally. Once the test data is passed to these stumps we get an output from each. Based on the voting classifier, majority of the value gets selected as we have seen in random forest also.


As I mentioned in the beginning, the main motive of the algorithm is to convert the weak learner into stronger ones.




Reference:

Comments

Post a Comment

Popular posts from this blog

Euclidean Distance and Manhattan Distance

Image
  Euclidean and Manhattan Distance Euclidean Distance and Manhattan Distance are the two distances that we generally use to find distance between two data points. Use of this distance can be seen in algorithms like KNN, Kmean and Hierarchical clustering. We can check if there are any similarities between the two data points with the help of these distances. Euclidean distance The smallest possible distance between any two points is named as euclidean distance. This distance is calculated based on Pythagoras theorem as shown in the below figure. Source:  cdn-images-1.medium.com This is the case for 2-D data.  For higher dimensions we can add the additional dimension. This is case for any number of dimensions. Euclidean distance is used where we calculate the distance between any two points in a straight line irrespective of whether there are any other data points in between them. Ex. when we google to check distance between Cochin and Delhi in case of flight we get a straight point from
Read more

k-nearest neighbor

Image
 KNN The k-nearest neighbor algorithm is a supervised machine learning algorithm that can be used to solve both classification and regression problems. Classification usage Let us understand the algorithm using the below figure where we have two classes of data points ( A and B).  Source:  www.kdnuggets.com The first step is to determine the K value ( 'k' here is the number of nearest data points from the new data point). Let us take k = 3 as per the above figure. We can see that 2 out of 3 neighbors are from class B. So, in this case we go with the majority votes, i.e., the new data point will be classified as class B. We can use either Euclidean or Manhattan distance to get the nearest neighbor. Regression usage Below we can see the difference in the regression and classification usage. We will focus on the left figure for regression under this topic. Source:  www.jeremyjordan.me Similar to the classification problem, here also we need to come up with a k value. If the k val
Read more

K means clustering

Image
 K means clustering K-means  is a non-parametric method of clustering where we pre define the number of clusters(non-parametric means computation complexity depends in number of samples). It is an unsupervised machine learning technique. Source: miro.medium.com From the above figure, the algorithm finds the similarity between points and group them into clusters (green, blue and red in this case). Let us see what are the steps required and how the algorithm arrived at 3 clusters as above. Determine K value:  K value is basically how many centroids is needed for our data to form the best clusters. Here we can take any value for beginning.  Initialize K points (randomly) as cluster centers in the plane( K = 3 in this case) Find the distance between the points nearer to the centroids:  Here we can calculate the distance either using Euclidean and Manhattan Distance (Click here to know more about these distance). Based on the shortest distance from the centroids, clusters are formed. Sele
Read more