Classification when Learning is not Feasible

Question

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?

Answer 1

A decision tree will always try to find splits and fit the data, whether it is "noise" or not. The nodes will end up being more pure than the initial full distribution. However, you'll likely get very close to a score that represents the distribution of the class labels.

The only way to get a single node is if all the data are the same. You can test this out yourself, using different distributions of X and Y: https://share.cocalc.com/share/a20be7c6-920f-4a02-a210-5f78edc58fd4/2018-12-01-191018.ipynb?viewer=share

Here's an excerpt from that for random features, with a section of the tree showing the pure nodes:

import numpy as np
from sklearn import tree
from sklearn.model_selection import train_test_split
import random, graphviz

def test_tree(X, Y=np.random.randint(0,n_classes,(n_samples,1))):
    X_train, X_test, y_train, y_test = train_test_split(X, Y, random_state=seed)
    clf = tree.DecisionTreeClassifier()
    clf.fit(X_train, y_train)
    print("Score on test data: ", clf.score(X_test, y_test))
    dot_data = tree.export_graphviz(clf, out_file=None, 
                      feature_names=range(X.shape[1]),  
                      class_names=[chr(i) for i in range(ord('a'),ord('a')+n_classes)],  
                      filled=True, rounded=True,  
                     special_characters=True)  
    return graphviz.Source(dot_data) 

seed = 42
random.seed(seed)
np.random.seed(seed)
n_features = 10
n_samples = 500
x_max = 100
x_min = 0
n_classes = 3
# Test a random distribution of samples and features
test_tree(np.random.randint(x_min,x_max,(n_samples,n_features)))

---

('Score on test data: ', 0.312)

And when all the data are the same:

# Test where all samples are the same value
test_tree(np.ones(X.shape))

---

('Score on test data: ', 0.34399999999999997)

Try increasing the number of features or number of samples or both, or altering the class distribution, and you'll see you can get fairly consistent score results representing the distribution of the classes.

Answer 2

Usually, the "empty" decision tree you are referring to is a single node (e.g: in WEKA). It contains all the data (no splits). Other ml algorithms have some kind of "empty" model as well.

On real-life data, this will not happen, and model complexity in this setting will be "more than 0".

Class distributions will vary more with increasing model complexity.

Answer 3

This really depends how you define "noise".

Assume you have training data and there exists a relationship between your target and predictors over some partition of the data. Then your tree will find a way in which to split and make predictions it believes to be better than the mean. You then apply your model to a test set and discover your tree made predictions even worse than applying the mean.

Was the signal in the training data "noise"? Certainly not if you had no hold out data or didn't know the underlying data generating function. Certainly if you did. It all depends on what you consider "noise".

Answer 4

This is my first time answering a question in this site.

I think this setting violates the requisite universal in almost all machine learning algorithms, that is the examples $(\mathbf{x}_i,y_i)$ have to be independently drawn from same underlying distribution $\mathcal{D}: \mathcal{X}\times \mathcal{Y}$. In this sense, it is not likely that $\mathbf{x}_i$'s do not provide any information about $y_i$'s.

However, in practice, this might occur because of inappropriate measurement of your data (either $\mathbf{x}_i$'s or $y_i$'s), but this has nothing to do with machine learning algorithm itself but related to your measurement and some data preprocessing techniques might be relatable to your question.