intuition behind Cover's theorem?

Question

I was going over https://en.wikipedia.org/wiki/Cover%27s_theorem And I am a bit lost with the intuition.

I do understand that if it's not linearly separable, then projecting it into a higher-dimensional space shall solve it (it can be nicely explain with a real piece of paper).

The "projecting it into a higher-dimensional space" makes me uncomfortable since its basically introducing a new column into the dataset with unrelated values...

I feel it's cheating, the data was in a lower-dimensional space for a reason... You may now be able to separate data but its not the original data, some arbitrary new "column" has been added.

Isn't it better trying to find a non-linear separation, instead of projecting into a higher dimension?

Answer 1

Finding a non-linear separation curve is equivalent to projecting the dataset into a higher dimensional space with a transformation closely associated with this curve. In essence, that is trying to find a non-linear separation. Sometimes, we don't even map the data onto a higher dimensional space (like in RBF kernel) but we use its direct consequences, e.g. dot products.

For example, assume the separation curve is $x_2=x_1^2$. Adding a new polynomial feature to the dataset, makes it 3D, e.g. $x=[x_1,x_2,x_1^2]$, and we could use a hyperplane in 3D space to separate the data, using $w=[0,1,-1]$ and $L(x)=w^Tx$, which corresponds to the original curve in 2D space. It's not cheating, it's a disguise.