Consider classification problems, where features do not give any information about the class label.
I do not know what kind of behavior to expect when running a classification algorithm in this setting (let's assume ID3 decision trees for simplicity).
The decision tree constructed should be some kind of "empty" model, because it's even less than a decision stump (i.e. there exists no split that results in purer leaf nodes).
In practice however, the model is likely to fit the noise, and find some kind of pattern that does not exist. The algorithm could still manage to come up with decision trees on training data for an output that is in actual fact independent of given features.
If test set is large enough: The class distribution of instances that are classified, end up in leaf nodes that have the same class distribution as the entire dataset (like random guessing).
Is this assumption correct? How can you interpret the complexity of the classifier "trained" relative to the prediction accuracy on the test set?