Month: January 2021

Entropy is the measure of randomness in data. Randomness signifies the heterogeneity of labels. Decision trees split the data in manner that leads to decrease in entropy. Thus Decision Trees aim to divide the data with heterogenous labels into subsets/sub-regions of data with homogenous labels. Thus with each division level of homogeneity increases and entropy decreases. In fact entropy is the cost function that decision trees employ as basis of splitting the data, if the the split leads to decrease in entropy then it’s carried out else not.

For a dataset with 4 labels- say a, b, c, d – with probability of occurrence of each label being p, q, r, s respectively, then the entropy of the data would be given by the following equation:

For a dataset with n classes, the formula would be:

Where p is the probability of occurrence of each class.

Decision trees are notoriously famous for overfitting. Pruning is a regularization method which penalizes the length of tree, i.e. increases the value of cost function.

Pruning is of two types:

1. Post Pruning(Backward Pruning): Full tree is generated and then the non-significant branches are pruned/removed. Cross validation is performed at every step to check whether addition of the new branch leads to increase in accuracy. If not the branch is converted to leaf node.
2. Pre Pruning(Forward Pruning): This approach stops the non-significant branches from generating. It terminates the generation of new branch based on the given condition.

What is greed and why is it there a negative connotation attached to it?

Wikipedia defines greed as: “Greed (or avarice) is an uncontrolled longing for increase in the acquisition or use: of material gain (be it food, money, land, or animate/inanimate possessions); or social value, such as status, or power. Greed has been identified as undesirable throughout known human history because it creates behavior-conflict between personal and social goals.”

But other terms – like ambition, savings, self preservation, achievement etc. – which are also associated with increase in personal worth, increase in status etc. are considered virtues. So longing for personal gain is in itself not bad, so it must be other traits that make greed a vice.

Following are the factors which make greed undesirable:

1. Short Sightedness: Prioritizing instant gratification over long term gains.
2. Negative Externalities:  Greed not only hurt the your long term interests but also adversely affect others.

 

How Decision Trees work?

Decision Trees start select a root node based on a given condition and split the data into non overlapping subsets. Then the same process is repeated on the newly formed branches and the process continues till we reach desired result i.e. answer to our business question. The condition for splitting is the decided by the value of cost function. The condition corresponding to which the value of cost function, at that stage, is minimum is chosen. What I mean by at that stage is that overall value of cost function is not taken into account but the value of cost function at that level i.e. instant gratification. This approach may result in a tree for which overall value cost function may be higher than a tree in which splitting was done on the basis of overall value of cost function. Therefore this approach creates a tree whose accuracy is less that that of a tree where overall cost function was employed i.e. negative externalities. Therefore this approach is termed as greedy approach

 

Why is this approach chosen if it results in a suboptimal tree?

If the overall cost function was considered at every step, the process would have been highly computationally intensive. Thus by using greedy approach decision trees save both computation time and hardware costs.