Given a dataset with no noisy examples, is the training error for the ID3 algorithm always 0?

Question

Given a dataset with no noisy examples (i.e., it is never the case that for 2 examples, the attribute values match but the class value does not), is the training error for the ID3 algorithm is always equal to 0?

Answer 1

Yes, if you can assume that your data is separable on the features given then ID3 will find a decision tree for it (Note: this will not necessarily be an optimal tree, or even a good tree). To understand why let's look at a proof.

Assume we have one feature left and some number of examples in a leaf that does not have separated data points then, either:

1. This feature perfectly splits the data into their desired categories. In this case ID3 will split over this feature and be done.

2. This feature does not split the data into their desired categories. In this case, we have at least 2 examples with the same feature value, but they do not share the same class. This means either these two examples have the same feature value for all features (a contradiction to our assumptions) or we have created a leaf with non-separable data points (which we prove is impossible later on).

Now for the inductive step.

Assume that ID3 used some number of features to somewhat separate our examples already. Thus, we have some number of features not used and some number of examples not separated on any current leaf, and one of the following is true:

1. All our leafs contain data points of only one class. In which case, ID3 is done and returns.

2. All leafs contain data points that are separable by the remaining features. Then ID3 splits over the local optimum and continues.

3. At least one leaf contains data points that are not separable by the remaining features of each own's branch. Then there exists two examples p and q such that p and q share all the same remaining feature values, but do not share the same class. Thus, one of the following is true:

   1. There is a feature that we already used that differs between p and q. This is a contradiction as we said ID3 already separated over this feature, and thus p and q must be on different branches.

   2. p and q have the same feature value for all features previously used. But we already said p and q share all the same remaining feature values. Therefore, they share all feature values which is a contradiction to our assumptions.

Therefore, at no point in the creation of the decision tree is ID3 allowed to create a leaf that has data points that are of different classes, but can't be separated on remaining features. And thus, ID3 must create a solution that perfectly separates the data and has 0 training error.

Something to note however, is that allowing ID3 to grow the decision tree in this way will likely cause us to overfit the training set. To combat this we set a maximum depth that we allow ID3 to grow to.