Datasets that "simple" models fail but more complex models work

Question

Notes:

1. The term "simple" in this context is defined at the end of the question;
2. I believe this question is somehow not about dataset request even if its title is named this way...

Main body:

Datasets I have seen usually fall within one of the following three categories:

1. "simple" models work (i.e., prediction consistently better than random guess, even by a tiny margin such as 1%), machine learning/deep learning models work better
2. "simple" models work, machine learning/deep learning models are more or less the same
3. "simple" models don't work (i.e., prediction not better than random guess), machine learning/deep learning models don't work either.

This rule does not only apply to tabular data but also apply to some simple image classification tasks as well (but yes, you may argue that underlyingly images are tabular data as well since we flatten the high-dimensional data to 1-D array anyway). I tried cats and dogs classification--logistic regression can do better than random guess although it is much worse than CNN (so it falls to category I). Since I work mostly with tabular data, I did not try some even more complicated image classification tasks.

Let's say we discuss only supervised classification using tabular datasets, that is, the datasets with a few (or a LOT if you wish...) columns as X and one categorical column as y. Under this constraint, do you know any publicly available or synthetically generated datasets with which a "simple" model does not work at all but a more complex model can do better (even just slightly) than random guess?

In the context of this question:

1. "simple" means linear models (e.g., OLS, Ridge, Lasso, Logistic, etc) plus decision tree and k-NN. These models are considered "simple" mostly because they are computationally inexpensive;
2. "linear" means linear with respect to X and no feature engineering, such as $x_2 = x_1^2$, is allowed. So that one can not add non-linearity to the model by manually creating new features from old olds--I believe this makes my question easier; otherwise feature engineering allows OLS to go much further;
3. I confine the question to classification tasks only because the meaning of "random guess" is not very clear for a regression problem (we guess by mean? median? mode? frequency? how about continuity and differentiability?) Please let me know if I am wrong;
4. Overfitting control techniques such as cross validation are allowed just in case the synthetic dataset tries to trick a simple model into severe overfitting, which is not the intent of this question;
5. SVM, Gradient Boosting, etc are not considered "simple", but suppose you have a dataset or you can generate a synthetic dataset which fails these models but cannot fail a neural network, I will be even more interested to know what such dataset looks like.

Datasets tried:

1. vanilla hand-written digit recognition: Category I
2. obfuscated hand-written digit recognition: Category I
3. obfuscated hand-written digit recognition with binary label: Category I

EDIT 1: The original term "linear" is changed to "simple", which reflects what I want to ask more accurately;

EDIT 2: k-NN is added to the list of "simple" models.

Answer 1

Dataset requests are off-topic, but there is an interesting statistical take. I will simulate some data in R.

set.seed(2021)
N <- 10000
x <- runif(N, -1, 1) 
y <- 2 + x^2 + rnorm(N, 0, 0.1) 
L <- lm(y ~ x)
L2 <- lm(y ~ x^2)

If you just run linear regression on “x”, your performance will be awful. However, if you run a complex algorithm like a neural network, perhaps with more data, you can get a decent fit to the parabolic shape. If, however, you know to expect the parabolic relationship, the regression on “x^2” has excellent performance.

Some of the appeal of machine learning is that we can delegate this “figure out the features” to algorithms, rather than doing it by hand.

The universal approximation theorem in neural networks says that, for “decent” functions and with some technical considerations, single-layer neural networks can approximate anything. If you visualize the architecture of such a neural network, you will see that the final output is a linear combination of the hidden layer (plus an activation function). That is, a neural network does feature extraction and then applies a linear regression (or generalized linear model).

If you’re able to figure out the features in that hidden layer the way that you could have figured out that my simulation included a quadratic term, your linear regression (or other GLM, such as logistic) will do just as well as the neural network.

Some of the trouble with finding a dataset where a (generalized) linear model does not work at all is that there is likely to be some linear component.

Answer 2

You are making so many ad hoc assumptions and it is hard to meet them all.

• You want to focus only on "supervised classification using tabular datasets", that's the kind of datasets where many "simple" algorithms work very well. This kind of problems commonly are solved with algorithms like logistic regression or decision trees. If you look at the 2021 Kaggle Survey, they are the most popular ones.
• If you included natural language data or image classification, in many cases deep learning algorithms would outperform other algorithms. Deep learning got popular because it proven to work good for such examples.
• You could design datasets that would guarantee a particular algorithm to fail. For example, linear regression assumes linearity in parameters, so you need to break this assumption (or data with interaction term needs an algorithm that can fir such patterns). But this would be hard when you pick an arbitrary list of algorithms.
• Your distinction between "simple" and "complicated" algorithms is very arbitrary. Linear regression is a parametric model, that makes very strong assumptions about the data. $k$-NN is a non-parametric model that makes almost no assumptions about the data. $k$-NN can be able to fit arbitrarily complicated patterns given that you have enough data and a computer with enough memory for it to work. If you consider decision tree a “simple” algorithm, why not include random forest in this set? If you consider logistic regression, why not neural network as logistic regression is the simplest possible neural network?
• Polynomial regression is a universal function approximator same as decision trees. Those algorithms can solve very complicated data problems.

So basically, you are trying to cherry-pick a dataset under a rather arbitrary set of constraints. The constraints are not clear-cut and well defined, so there is no obvious answer. You can always go through Kaggle competitions to find such dataset that meets the constraints.

Answer 3

Let's say we discuss only supervised classification using tabular datasets, that is, the datasets with a few columns as X and one categorical column as y. Under this constraint, do you know any publicly available or synthetically generated datasets with which a "simple" model does not work at all but a more complex model can do better (even just slightly) than random guess?

I believe that any such example would have to be so contrived that you are very unlikely to see it in real life.

If by "better" you mean in terms of classification error, you can actually get close to a proof of this fact by using the Cover-Hart inequality.

(The Cover-Hart inequality says that in a two-class classification problem, the error of a 1-nearest neighbour classifier is asymptotically not worse than twice the Bayes rate. Here the "Bayes rate" is the lowest possible error for any classifier, and "asymptotically" means as the number of rows of your data set gets larger and larger.)

I know that your list of simple classifiers doesn't include 1-nearest neighbour, but in practice it seems that the performance of a decision tree is likely to be quite close to 1-NN, because both algorithms partition the feature space into regions around known data points in which the predicted value for y is constant. (Certainly, I think quite some work would be required in order to get an example in which a decision tree doesn't work at all, but 1-NN has some predictive power.)

So, the only hope for finding a data set like this in the wild would be to have a situation in which you had a very large number of columns, which might be something like image classification, or even better maybe something like an algorithm which inputs a chess position and outputs the best move.

Actually, isn't this chess thing an example? It has about 64 features and you have to predict a categorical y. It's known that it can be done with a neural network, but certainly I don't think that any simple algorithm could work. Wouldn't other games like backgammon also provide examples? Now I have confused myself.