2
$\begingroup$

I'm trying to create a step-by-step visual of how Adaboost works. I'm training a series of decision tree stumps (tree with depth of 1) and for each iteration, I want to plot that particular stump, showing that the points that were misclassified are now weighted more heavily, and the next classifier should focus on those points. I do this by looping:

for i in range(N):
    clf = DecisionTreeClassifier(max_depth=1).fit(X,y, sample_weight=d)
    pred = clf.predict(X)
    # plot output of pred
    # calculate a new d using the Adaboost algorithm

My problem is that after a few iterations, it appears that the Decision tree stump doesn't get re-weighted and continues to predict all observations belonging to one class. Here is what each plot looks like:

enter image description here

Great - got some, missed others. If I continue in this fashion, then after 4 or 5 iterations, I get this:

enter image description here

This particular classifier has classified all the points as one class, and all the rest of the iterations do the same thing.

Can someone explain to me why this is the case with stumps? It doesn't happen when I use trees of greater depth.

EDIT

Here are my X's and y's (a new, smaller dataset than the images):

X's: [[-0.43838916 -1.71793854]
 [-1.51794608 -0.34487949]
 [-0.77530244  0.74435691]
 [ 0.48372805  0.76491468]
 [ 0.84696082  1.00027914]
 [-1.61250896  0.87429049]
 [ 0.92385058 -2.59586644]
 [ 0.12134204  1.03762471]]
y's:  [0 0 1 1 1 1 0 0]

Here is the output of my predictions and the re-weighted samples:

Iteration:  0
Weights: [ 0.125  0.125  0.125  0.125  0.125  0.125  0.125  0.125]
Predictions: [0 0 1 1 1 1 0 1]
+++++++++++++++++++++++++++
Iteration:  1
Weights: [ 0.18142703  0.18142703  0.06857297  0.06857297  0.06857297  0.06857297
  0.18142703  0.18142703]
Predictions: [0 0 1 1 1 1 0 1]
+++++++++++++++++++++++++++
Iteration:  2
Weights: [ 0.21223494  0.21223494  0.03776506  0.03776506  0.03776506  0.03776506
  0.21223494  0.21223494]
Predictions: [0 0 0 0 0 0 0 0]
+++++++++++++++++++++++++++
Iteration:  3
Weights: [ 0.21223494  0.21223494  0.03776506  0.03776506  0.03776506  0.03776506
  0.21223494  0.21223494]
Predictions: [0 0 0 0 0 0 0 0]
+++++++++++++++++++++++++++

After only 3 iterations on this dataset it predicts all class 0.

$\endgroup$
  • $\begingroup$ Do you get negative weights with Ada-boost? $\endgroup$ – Simone Oct 31 '15 at 2:05
  • $\begingroup$ I don't. They always sum to 1.0 (after I normalize). They just converge to some number and don't change $\endgroup$ – ilanman Oct 31 '15 at 3:01
  • $\begingroup$ Can you please provide the last datataset you show and the weight vector d? Just print X y and d. You can even print a reduced version as long as you get the same error $\endgroup$ – Simone Oct 31 '15 at 3:08
  • $\begingroup$ From a quick look your problem starts to appear when your weights get close to 0: eg 0.037 try to multiply your weights by a constant. I will investigate further tomorrow $\endgroup$ – Simone Oct 31 '15 at 13:34
  • $\begingroup$ Hmmm...I don't know because the weights are normalized, so multiplying them won't change anything (they must sum to 1). $\endgroup$ – ilanman Oct 31 '15 at 17:50
1
$\begingroup$

Ok I figured it out - my labels were [0,1]. But the way I had implemented the algorithm it required the labels to be [-1,+1].

epsilon = d.dot(pred != new_labels) # calculate error
alpha = (np.log(1 - epsilon) - np.log(epsilon)) / 2
d = d * np.exp(- alpha * new_labels * pred) # Update the weights
d = d / d.sum() # Normalize

When I make that change, it works out.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.