Boosting

Boosting is perhaps one of the most powerful ideas in Machine Learning. The idea is to combine several weak classifiers and turn it into a strong classifier. A weak classifier is a classifier that has Boosting has proven to be a very powerful approach and is used for various real world applications. The basic idea behind boosting is to concentrate on the examples that were incorrectly classified and use a majority voting from the various classifiers. One of the most popularly used boosting algorithms is known as AdaBoost.

The basic algorithm of Ada Boost is as follows: Suppose we have T weak classifiers such that the error on each of them is slightly less than 1/2 i.e., εt = 1/2 - γt
Input: Training points (x1, y1), (x2, y2) ...... (xn, yn) where xi ∈ X and yi ∈ {-1,1}
Let wt(i) be the weight associated with the ith training point ∀i ∈ 1..N in the t-th iteration
Let αt be the weight associated with the t-th classifier ∀t ∈ 1..T
Let the output of the t-th classifier for the ith point be Gt(xi)
  1. Initialize the weight w1(i) on all training points to be 1/N
  2. for t=1 ... T
  3. Train the t-th classifier using the distribution wt (Note that we need to modify the base classifier so that it can handle weighted versions of the training set. For example, ∑ wi*loss(xi,yi))
  4. Compute the error on the t-th classifier as εt = Pr[Gt(x) ≠ y]
  5. Update the weight of the classifier as αt = 1/2 ln( 1 - εt/ εt)
  6. ∀ i ∈ 1..N update the weight on the training samples using the multiplicative rule as - wt+1(i) = wt(i)exp(-αtyiGt(xi))/ Zt where Zt is the normalization factor
  7. end for
  8. The final output of the algorithm is G(xi) = sign [ ∑ t=1^T αtGt(xi)]

Let us try to understand this. Initially, we set the weight of all the training points to be equal which is the input to the 1st classifier. In the subsequent iterations however the weight on the training point that has been misclassified is increased and the weight on the point that has been classified correctly is decreased (From step 6, the value of the exponential is very large when yi*Gt(xi) is negative and the point is misclassified as it becomes an exponential of a positive term. On the contrary it is very small when yi*Gt(xi) is positive and the point is classified correctly and the weight of the point is reduced as it becomes exponential of a negative term as αt is positive.). Now, we see that the quantity αt represents the weight of the classifier used to compute the final output and is larger when the error εt of the classifier is small.(From step 5, if εt is low αt is high. Remember that εt should be < 1/2 otherwise αt will be negative.) Note that instead of using an exponential in the update as used in Adaboost other updates can be tried like in logit-boost.
Let us write some code in matlab that does boosted decision stumps. A decision stump is just a one-level decision tree. 
function [] = boosted_stump()


end

The figure showing the impact on test error as we increase the number of decision stumps is as follows:
In order to show why boosting works, we need to show that the training set error is bounded. Let us examine the total training error. In order to do that we examine the final output of the algorithm and see how much it is off from the given class labels. Thus, we have,
1/N ∑ i=1^N I(g(xi ≠ yi)) ≤ 1/N ∑i=1^N exp(-yiG(xi)) = ∏ t=1^T Zt
In order for the training error to be bounded the Zts should be less than 1. Actually, it can be shown that Zt = 2*sqrt(εt (1 - εt)) = sqrt(1 - γt^2)
Alternative view of Boosting:
Useful Links
Rob Schapire's notes on boosting

Comments

Post a Comment

Popular posts from this blog

MinHash, Bloom Filters and LSH

Lets talk about some large scale algorithms widely used in the document world. MinHash: Minhash is a really cute algorithm to determine how does a document compare to another. One simple way to compute document similarity is to compute the jaccard similarity between them. The jaccard similarity between the documents is computed as follows: def jaccard_similarity(set1: set, set2: set): if len(set1) == 0 or len(set2) == 0: return 0.0 common = len(set1.intersection(set2)) if common == 0: return 0.0 union = len(set1.union(set2)) return common / union One problem with Jaccard similarity is that it can take a lot of time to compute especially for large scale documents. The idea behind minhashing is to first operate on the space of document shingles. Shingles are basically any combination of k consecutive words of the document. For example, for the sentence "hi i am jaya" the possible 3 shingles are "hi i am" and "i am jaya...
Read more

Perceptron Algorithm

Image
The perceptron algorithm is a linear classifier using a linear function (w'x + b) to classify the points into two classes. The loss function for the perceptron algorithm just counts the points misclassified and then incrementally adjusts the weight vector and thus the decision boundary to appropriately classify the two classes. Perhaps this is the simplest algorithm one can think of to update the weight vector and is shown as follows: w(k+1) = w(k) + yt*xt if yt ≠ f(xt; w) i.e. we cycle through the training points and adjust the weight vector only if the points are misclassified. Note that our class labels are -1 and 1 and hence if the points are misclassified then y_t* f(xt; w) will be negative. In order to understand why the seemingly simple update rule works and leads to a convergence, lets closely examine it. One of the underlying assumption in the perceptron model is that the points are linearly separated hence there exists an w* such that y_t * f(xt; w*) ≥ γ for all...
Read more

Logistic Regression

The logistic regression method even though called regression has a unique ability to give posterior probability values for a data point to belong to a particular class and hence serve as a discriminative function useful for classification. The idea is simple, to use the logistic sigmoid function on the linear function of feature vector. p(y = 1| x) = σ(w'x +b) The likelihood function can be written as p(t|w) = Π y_i^t_i*(1 - y_i)^(1 - t_i) ln p(t|w) = Σ t_i*ln(y_i) + (1 - t_i)*ln(1 - y_i) The error function is computed by taking the negative of the log likelihood function and is computed as follows: E(w) = -ln p(t|w) Now, ∇E(w) is computed as follows: y = 1 / (1 + exp(-w'x) Taking derivative of both sides, ∇y/∇w = exp(-w'x)(x)/(1 + exp(-w'x))^2 ∇y/∇w = xy(1-y) Substituting the value in ∇E(w), we get ∇ E(w) = Σ (y_i - t_i)*x_i The derivative of the error function is similar to the least squares problem, although w...
Read more