Adaboost (Adaptive Boosting) Classifier

Boosting algorithms try to aggregate a couple of poor classifiers by order to make a powerful one. They assign weights to every labeled sample. When one of the poor classifier fails to correctly classify a sample, the weight of that sample is boosted. Then it tries another poor classifier.
Let’s take Adaboost and Pruning algorithms for example:

1. For the training set {(xi,yi)}ni=1, initialize their weights {wi}ni=1 as 1/n. And let f←0.
2. For j=1,…,b:
   
   1. Based on current sample weights {wi}ni=1, pick up the classifier with the smallest weighted error rate R:
      φj=argminφR(φ),R(φ)=∑j=1nwi2(1−φ(xi)yi)
   2. Calculate the weight of classifier φj:
      θj=12log1−R(φj)R(φj)
   3. Update the aggregated classifier f:
      f←f+θjφj
   4. Update the weights of samples {wi}ni=1:
      wi←exp(−f(xi)yi)∑nk=1exp(−f(xk)yk),∀i=1,2,…,n

n=50; x=randn(n,2); 
y=2*(x(:,1)>x(:,2))-1;
b=5000; a=50; Y=zeros(a,a);
yy=zeros(size(y)); w=ones(n,1)/n;
X0=linspace(-3,3,a);
[X(:,:,1), X(:,:,2)]=meshgrid(X0);

for j=1:b
    wy=w.*y; d=ceil(2*rand); [xs,xi]=sort(x(:,d)); 
    el=cumsum(wy(xi)); eu=cumsum(wy(xi(end:-1:1)));
    e=eu(end-1:-1:1)-el(1:end-1);
    [em,ei]=max(abs(e)); c=mean(xs(ei:ei+1));s=sign(e(ei));
    yh=sign(s*(x(:,d)-c)); R=w'*(1-yh.*y)/2;
    t=log((1-R)/R)/2; yy=yy+yh*t; w=exp(-yy.*y); w=w/sum(w);
    Y=Y+sign(s*(X(:,:,d)-c))*t;
end

figure(1); clf; hold on; axis([-3,3,-3,3]);
colormap([1 0.7 1; 0.7 1 1]);
contourf(X0,X0,sign(Y));
plot(x(y==1,1),x(y==1,2),'bo');
plot(x(y==-1,1),x(y==-1,2),'rx');