Is (nearly) all data separable? Suppose I have some data set with two classes. I could draw a decision boundary around each data point belonging to one of these classes, and hence, separate the data, like so:



Where the red lines are the decision boundaries around the data points belonging to the star class.

Obviously this model overfits really badly, but nevertheless, have I not shown that this data set is separable?

I ask because in an exercise book, a question asks "Is the above data set separable? If it is, is it linearly separable or non-linearly separable?"

I would say "Yes it is separable, but non-linearly separable."

No answers are provided, so I'm not sure, but I think my logic seems reasonable.

The only exception I see is when two data points belong to different classes, but have identical features. For instance, if one of the stars in the figure above was perfectly overlapping one of the circles. I suppose this is quite rare in practise. Hence, I ask, is nearly all data separable?
TL;DR

Yes, with overfitting all data becomes (non-linearly) separable (as long as the points don't precisely overlap).

Explanation

The problem with your argument is that you are using circles on a 2D plane, which is very difficult to learn. However, I think your argument can be made stronger with a decision-tree.

(0.2, 3.1)? --&gt; yes -&gt; star
            \-&gt; no  -&gt; (1.2, 4.5)? --&gt; yes -&gt; circle
                                   \-&gt; no  -&gt; (x1, x2)? --&gt; yes ...
                                                        \-&gt; no  ...


Decision trees are well accepted models, but note that they are non-linear models. With that, it is easy to argue that all data becomes separable.

However, the issue lies with overfitting. Because models like that become unstable with data points that were unseen before. So, just because the training data is separable, it doesn't mean that the models generated from it become any useful.