A data set that is linearly separable is a precondition for algorithms like the perceptron to converge. It's well-known that we can project low-dimensional data to a higher dimension using kernel methods in order to make it linearly separable:

enter image description here

But is it always true that there is some transformation to convert every non-linearly separable data set into a linearly separable one? If not, what would be an example of such a data set where this is impossible?


For a given, finite data set it should always be possible—just let each data point have its own dimension! So, maybe a more interesting question would be for a stochastic model, generating a data set, such that for $n$ realizations, linear separability would require a dimension growing linearly with $n$?

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.