Decision tree with adaboost

Helllo! I'm currently learning the AdaBoost algorithm to use it with Decision Tree. I want to implement everything myself (that's the way I learn - implement everything from scratch and later use redy-to-go libraries like SciKitLearn), so I don't use any external tools.

The problem is, that I have read few books (including Machine learning algorithmic perspective and a lot of tutorials available online. Almost everywhere people use the same example and say "you need to use weighted examples in order to put more attention to incorrectly classified cases). Ok, cool. But I cannot find ANY concrete example HOW to calculate e.g. information gain using those weights.

Can somebody provide me with a simple, toy example how to calculate:

Shannon entropy Gini index Information gain/Information gain ratio (any or all of the above)

with the weighted examples?

Here is some very very simple example invented by me: suppose we have the following examples:

╔═════╦══════╦══════╦══════╦═══════╗
║ idx ║  A1  ║  A2  ║  A3  ║ Class ║
╠═════╬══════╬══════╬══════╬═══════╣
║   0 ║ "A1" ║ "B1" ║ "C1" ║ "qqq" ║
║   1 ║ "A1" ║ "B2" ║ "C1" ║ "www" ║
║   2 ║ "A2" ║ "B1" ║ "C2" ║ "qqq" ║
║   3 ║ "A2" ║ "B2" ║ "C2" ║ "qqq" ║
║   4 ║ "A1" ║ "B2" ║ "C2" ║ "www" ║
╚═════╩══════╩══════╩══════╩═══════╝
╔═════╦════════╗
║ idx ║ weight ║
╠═════╬════════╣
║   0 ║   0.75 ║
║   1 ║      2 ║
║   2 ║      2 ║
║   3 ║      3 ║
║   4 ║    0.5 ║
╚═════╩════════╝

Suppose we can make only binary split on concrete attribute and concrete value (e.g. A2 == "B2"). How should I calculate values mentioned above? Knowing this is important for e.g. choosing the best split or checking the significance of each split.

My first impression and idea was to multiply each example by it's weight, but it's not practical in case of fractional weights. Any other ideas?

If my "toy" example is not enough, you can find a famous weather-based example with all necessary calculations without weights in the following lecture slides: (lecuture slides in pdf)

I was thinking about the following solution - because the Shannon Entropy takes into account the PROBABILITY of given example occurring, we can use weights to count them. So (using my toy eample):

qqq: 0.75 + 2 +3 = 5.75
www: 2 + 0.5 = 2.5

So

P("qqq") = 0.69
P("www") = 0.3

Original probabilities, without weights, were trivial:

P("www") = 2/5
P("qqq") = 3/5

But I don't know if it can be applied like this :)

Thank you in advance and best regards!

• Could you not just resample the data, weighted by the adaboost coefficients, and then build your decision trees in the normal fashion using whatever metric you like to choose the splits? – image_doctor Jan 16 '15 at 18:30
• Hmmm..... you mean normalizing all weights to 0-1 range, and then resampling data with such probabilities? It won't guarantee that all of the examples with the bigger weights will show up, and that (in my opinion) is the point of boosting. But I'm not sure. – Animattronic Jan 16 '15 at 20:39
• It is a recognised way of applying boosting, and will approximate re-weighting. How closely will depend on your sample size and class distributions. It's advantage is that its quite trivial to implement and you don't need to change your boosting scheme. So you may explore if it is effective for little opportunity cost. – image_doctor Jan 17 '15 at 13:02
• Thanks. I have implemented this solution and it really works. Great! – Animattronic Jan 18 '15 at 7:32
• @Animattronic I am learning in the same way as yours; can you share your implemented solution, so I can work on it to understand the concept properly Thank you – Ankit Dixit Sep 12 '17 at 11:53