Why a decision tree can't learn this simple rule?

Question

I wonder which ML algorithm is able to learn the appearently simple rule:

If [category] == 1 Then [A]

Below a demo script with an input variable [A] that contains noise, but if [category] == 1 then [A] matches exactly the target variable. Even after 5000 samples it doesn't get the rule right.

Which ML algorithm would you recommend that is able to learn that rule in a regression problem?

from math import floor, ceil
import numpy as np
import pandas as pd
from sklearn.tree import DecisionTreeRegressor

seq_length = 6
rows = 5000
max_value = 100
test_data_factor = 0.2

input = pd.DataFrame(np.random.uniform(0, max_value, size=(rows)), columns=["target"])
input["category"] = (list(range(1, seq_length + 1)) * ceil(rows / seq_length))[:rows]

def f_a(row):
    if row["category"] == 1:
        return row["target"]
    else:
        return row["target"] * np.random.uniform(0.8, 1.2)

input["A"] = input.apply(f_a, axis=1)

cnt_input_data = len(input.index)
rows_test_data = floor(cnt_input_data * test_data_factor)
rows_train_data = cnt_input_data - rows_test_data

train_data = input.head(rows_train_data)
test_data = input.tail(rows_test_data)

model = DecisionTreeRegressor()
model.fit(train_data.drop("target", axis=1), train_data["target"])
test_data["pred"] = model.predict(test_data.drop("target", axis=1))

print(test_data[test_data["category"] == 1])

Answer 1

The reason that the Decision Tree does poorly here is the algorithm isn't equipped to deal with the situation you're throwing at it. You need to understand how a CART model gives its predicted output value for a continuous response.

You fit a CART model to the response target, predicted by inputs category and A. You want the decision tree to learn the rule if category == 1, predict target = A. But all the classical CART algorithm can do is partition the space based on the input values, and then output a final predicted value based on the responses only (target) that fall into the given partition; it doesn't incorporate predictor information like you want it to in the final prediction. So it can only do things like if category == 1, predict target = (mean target of all observations with category == 1). Since the observations that fall into category 1 are just uniform random variates, you won't do very well predicting their value by grouping them up and just taking the mean, right?

Sounds like a "model-tree" based approach might be more appropriate (disclaimer: I'm not an expert in these). In the terminal node of the tree, instead of simply predicting the mean of all values falling into that node (like CART), model-trees fit a linear model to all observations in the terminal node, using all predictors that gave rise to the splits that define that terminal node (that's a mouthful, I know, not sure how else to say it).

I'll give an example in sloppy R code (sorry, too nooby in Python) wherein I:

1. setup dummy data
2. fit a CART model to show how bad it is
3. fit a Cubist model to show that it fits well on the category == 1 data and poorly on the category != 1 data

Step 1: Setup data

set.seed(111)

library(rpart) # CART model
library(Cubist) # model-trees model

seq_length = 6
rows = 30000
max_value = 100
test_data_factor = 0.2

df <- data.frame(category = as.character(rep(1:seq_length, length.out = rows)),
                 target = runif(rows, 0, max_value))

df$A <- df$target
for(i in 1:rows) if(df$category[i] != 1) df$A[i] <- df$A[i] * runif(1, 0.8, 1.2)

test_ind <- 1:floor(test_data_factor * nrow(df))

training <- df[-test_ind, ]

test <- df[test_ind, ]
test_1 <- test[test$category == 1, ] # Test observations w/ cat 1
test_not1 <- test[test$category != 1, ] # Test observations w/ other categories

Step 2: Fit a CART model and show how crappy it is

treemod <- rpart(data = training, target ~ .)

treepred_1 <- predict(treemod, newdata = test_1) # CART predictions in category 1
treepred_not1 <- predict(treemod, newdata = test_not1) # CART predictions in other categories
print(paste0("Mean Absolute Error of CART Model in Category 1: ", round(mean(abs(treepred_1 - test_1$target)), 3)))
print(paste0("Mean Absolute Error of CART Model other Categories: ", round(mean(abs(treepred_not1 - test_not1$target)), 3)))

[1] "Mean Absolute Error of CART Model in Category 1: 4.061"
[1] "Mean Absolute Error of CART Model other Categories: 6.178

Step 3: Fit a Cubist model and show improvement in Category 1

cubistmod <- cubist(x = training[ , -2], y = training$target)

cubistpred_1 <- predict(cubistmod, newdata = test_1)
cubistpred_not1 <- predict(cubistmod, newdata = test_not1)

print(paste0("Mean Absolute Error of Cubist Model in Category 1: ", round(mean(abs(cubistpred_1 - test_1$target)), 3)))
print(paste0("Mean Absolute Error of Cubist Model other Categories: ", round(mean(abs(cubistpred_not1 - test_not1$target)), 3)))

[1] "Mean Absolute Error of Cubist Model in Category 1: 0.01"
[1] "Mean Absolute Error of Cubist Model other Categories: 4.434"

So the test error in category 1 has gone from about 4.1 to 0.01 by switching from CART to Cubist. The error is non-zero so it's not learning like a human might that if the category is 1, then just return A exactly. But perhaps the analyst might notice the minute error and consider that this is likely just numerical precision issues. Indeed, if you check summary(cubistmod), which lists the model splits and resulting models, you'll see among the rules:

if
    category = 1
    then
    outcome = 0 + 1 A

I'm not sure what other kinds of algorithms could help you out, but just some random thoughts: you could maybe check out association rule learning or literature in the data mining community ("data mining" being kind of a buzzword but this idea of finding hidden relationships among variables in the dataset seems to be a common motif in the lit of the self-professed miners)

Answer 2

This is not how decision trees work. Roughly speaking, decision tree splits data into bins (branches), conditionally on the features, and per each bin it predicts mean of the target variable. So for decision tree to predict something like identity function $y = f(y)$, you would need decision tree with the number of branches equal to the size of the data, i.e. one that literally memorized the data.